Home > Reflections | ⏮️ ⏭️

2024-06-17

🏋️ Practice / Warm Up

1662. Check If Two String Arrays are Equivalent

Given two string arrays word1 and word2, return true if the two arrays represent the same string, and false otherwise.
A string is represented by an array if the array elements concatenated in order forms the string.

Reflections

1. The first implementation pass went really well, finishing everything in under 8 minutes
2. Trying the harder implementation
   1. My first implementation didn’t work
   2. But I caught the bug during my own manual testing
   3. My first attempt to fix it wasn’t fruitful
   4. But eventually, I abandoned that path and my second attempt to fix worked
   5. 36 minutes isn’t great, but this was the harder implementation and I did eventually get a working solution, so I think it’s good enough

My Solutions

/* decide if the two sring arrays concatenate to the same string  
Questions:  
1. Do I need to worry about diacritic marks (or whatever they're called)? When a single utf8 character can be represented by multiple bytes, thus might split or join differently?  
2. Typically, empty strings concatenate as an identity - is it safe to assume that ["abc", ""] is equivalent to ["abc"]?  
  
Approaches:  
1. concatenate the strings and test them for equality. O(N) runtime; O(N) extra space. Very simple to implement  
2. iterate through each element of each string in each array, skipping empty strings and comparing character by character. O(N) runtime, O(1) extra space. More complicated, but slightly more efficient.  
  
I'll go with approach 1  
[4:48] done planning  
[6:10] done with initial implementation  
No bugs found  
[7:21] done testing  
[7:39] first submission successful  
*/  
function arrayStringsAreEqual1(word1: string[], word2: string[]): boolean { // ["", "a", "bc"] ["abc"]  
  const sentence1 = word1.reduce((a, b) => a + b, "") // "abc"  
  const sentence2 = word2.reduce((a, b) => a + b, "") // "abc"  
  return sentence1 === sentence2 // true  
};  
  
/* Now let's try with constant space  
Bugs found during testing:  
1. incrementing word pointers in their own loop iterations  
[35:01] done fixing & testing  
[35:43] success on first submission  
*/  
function arrayStringsAreEqual(word1: string[], word2: string[]): boolean { // ["", "a", "bc"] ["abc"]  
  let w1OutOfBounds = false  
  let w2OutOfBounds = false  
  for (let i = 0, j = 0, wi = 0, wj = 0; i < word1.length || j < word2.length;) {  
    let w1  
    if (i >= word1.length) {  
      w1OutOfBounds = true // true; true  
    } else {  
      w1 = word1[i] // "bc"; "bc"; "bc"; "a"; "a"; ""  
      if (wi >= w1.length) {  
        i++ // 3; 2; 1  
        wi = 0 // 0; 0; 0  
        continue  
      }  
    }  
    let w2  
    if (j >= word2.length) {  
      w2OutOfBounds = true // true  
    } else {  
      w2 = word2[j] // "abc"; "abc"; "abc"; "abc"  
      if (wj >= w2.length) {  
        j++ // 1  
        wj = 0 // 0  
        continue  
      }  
    }  
      
    if (w1OutOfBounds !== w2OutOfBounds) return false  
    if (w1OutOfBounds) return true // return true  
      
    if (w1[wi] !== w2[wj]) return false  
    wi++ // 2; 1; 1  
    wj++ // 3; 2; 1  
  }  
  return true  
};  

Day-of Interview Preparation

1. I got to bed early last night and slept well.
2. I had breakfast, practiced a bit in the morning, ran, had a short nap, and a cold shower… I did everything I wanted to do in prep.
3. I felt good coming into the interview.

The Interview

There weren’t any surprises in the format of the interview.
15 minutes of behavioral questions, about 40 minutes of coding and about 5 minutes of my questions for my interviewer.

Behavioral Questions

1. Tell me about a time when you had a cross-functional conflict between teams.
2. Tell me about a time when you collaborated cross-functionally to solve a business problem.

For both of these questions, he asked me to be more specific multiple times.
I think my answers qualified, but I don’t think my interviewer was particularly impressed with them.
Maybe I should put more time into writing more detailed stories to field a broader spectrum of behavioral questions.

Coding Question

1. Whew - that was intense.
2. This felt like a weird looking tree problem, but perhaps that means that I just haven’t spent enough time practicing tree problems.
3. Note: this problem is very similar to LeetCode’s 199. Binary Tree Right Side View, but I was asked for both sides.
4. In my planning phase, I identified an approach of turning the tree into levels, then processing those levels.
5. During the coding phase
   1. ✅ I started with a top down implementation
   2. ✅ I did not immediately implement the one helper function I posited
   3. ✅ I asked my interviewer if he wanted to see the implementation of the helper function first or a test of the top level function (he said to finish implementing the code)
   4. ✅ I identified recursion as probably a good approach before starting, since I was working with a recursive data structure (a tree)
   5. 😬 My first attempt at implementing this levelsFromTree function recursively did not go well. I spent some time with it, but it didn’t feel right. I tried fixing it, but still didn’t make progress.
   6. ✅ Eventually, I thought: rather than be stuck down this path that doesn’t look promising, can I think of a different way to do this?
   7. ✅ I somehow came up with a different recursive approach that seemed more likely to produce a correct result
   8. ✅ I implemented this second approach without too much trouble, then asked if he’d like to see a test.
   9. 😬 He asked if I thought I was done coding.
   10. ✅ Which I took as a cue to review my code for obvious missing pieces
   11. ✅ The recursive helper function looked correct, but when reviewing the high level implementation, I realized that it was now incorrect due to pivoting the implementation of the helper function.
   12. ✅ I fixed up the top level function until it looked correct given the new helper
   13. ✅ I told my interviewer that I thought it was now complete, given a correct implementation of my recursive helper function.
   14. ✅ He asked me to test the code, so I chose the more challenging looking example input he’d provided initially.
   15. ✅ I used my well-practiced manual testing strategy, annotating important variable state in-line where variables are declared.
   16. ⌛ It took a while to test my recursive helper function, but I worked through it one step at a time, and the results looked good.
   17. ✅ I didn’t find any bugs in the recursive helper function, but I did find and fix a small bug in the top level implementation while finishing my test case.
   18. 😬 After finishing my test case, I felt pretty good about the implementation, and I felt like a lot of time had passed.
       1. 😬 Perhaps I should have tried another test case with the time we had left.
       2. 😬 Perhaps I should made some remarks about the code quality at this point.
       3. 🤷 But instead, I felt like I was probably about out of time, so said I thought I was done and asked how he felt about it.
6. 🆗 He said okay and moved on to invite me to ask him questions.
7. ❔ I asked him 2 questions, the latter of which he said was a good question.
   1. I felt like I was making these questions up on the fly, and really should have written out example questions to ask before my interview.
   2. On the other hand, I could also feel the residual stress hormones pulsing through my body, and I think I did a pretty decent job of holding it together to ask decent questions.
   3. My first question related his personal experience (which I’d noted during his intro) to recent developments at the company (which I’d learned about by studying the week prior). He answered my question, but didn’t seem too engaged by it.
   4. My second question attempted to reveal some details about leadership and autonomy within company culture. My first phrasing of the question elicited a “can you be more specific?” After refining my question, he remarked that it was a good question and answered it reasonably.
8. After my second question, time was about up, so I thanked him for his time and we ended the interview.
9. How do I feel about this?
   1. I need to do a better job preparing for behavioral questions and (less importantly) for questions that I’ll ask my interviewers.
   2. I feel like I probably struggled more than I should have with this coding problem.
      1. I really hope he didn’t intend for us to do 2 questions, because we only attempted 1. I’m pretty sure there wasn’t a second problem planned…
      2. But assuming it was only intended to be a single question interview, I feel good enough about having come up with a complete solution that seemed like it would work.
   3. Overall, I think I probably did well enough to move on to the next round. That said, I expect them to dig into some weaknesses displayed in this first interview. I have homework to do.

A rough reconstruction of my implementation

/*  
What do we see when looking at a tree bottom to top from the left perspective, then top to bottom from the right perspective?  
Example  
input tree:  
  1  
 /  \  
2    3  
<br/>
  5  
  
output: [5, 2, 1, 3, 5]  
  
1. turn the tree into levels of nodes  
* from each level, the leftmost element is the first and the rightmost element is the last element in the array  
2. from levels array, extract leftmost element for each level, then rightmost element from each level except top where we only use the root node once  
  
runtime complexity: O(N)  
extra space complexity: O(N)  
*/  
  
const levels = []  
  
function levelsFromTree(rootNode, currentLevel = 0) { // { value: 3 }; { value: 5 }; { value: 2, right: { value: 5 } }; { value: 1, left: { value: 2, right: { value: 5 } }, right: { value: 3 } }  
  if (!rootNode) return  
  levels[currentLevel] = (levels[currentLevel] || []).concat(rootNode.value) // [[1], [2, 3], [5]]  
  if (rootNode.left) levelsFromTree(rootNode.left, currentLevel + 1) //  
  if (rootNode.right) levelsFromTree(rootNode.right, currentLevel + 1) //  
}  
  
function wrapperFromTree(rootNode) { // { value: 1, left: { value: 2, right: { value: 5 } }, right: { value: 3 } }  
  levelsFromTree(rootNode)  
  const result = [] // [[1], [2, 3], [5]]  
  for (let i = levels.length - 1; i >= 0; i--) {  
    const level = levels[i] // [1]; [2, 3]; [5]  
    result.push(level[0]) // [5, 2, 1]  
  }  
  for (let i = 1; i < levels.length; i++) {  
    const level = levels[i] // [5]; [2, 3]  
    result.push(level[levels.length - 1]) // [5, 2, 1, 3, 5]  
  }  
  return result // [5, 2, 1, 3, 5]  
}