Home > Reflections | ⏮️ ⏭️

2024-06-10

🏋 Practice 1

The Problem

56. Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

🪞 Reflections

1. This problem felt pretty easy.
2. I realized mid-problem that I’d need to track the maximum endpoint while iterating
3. The one logic error (< vs <=) was a careless error. I didn’t find it with the one test I selected, as it didn’t come up in that problem.

My Solution

/* Plan  
1. Sort intervals by start  
2. Scan sorted intervals left to right  
3. For each interval starting before the end of the current interval  
  a. track a max end interval  
4. On the first interval that starts after the end of the current interval, push the previous interval into the results  
- Time complexity: O(N * log(N)) (for sorting)  
[5:00] Done planning  
[10:08] Done with initial implementation  
[14:12] Done with test  
Bugs found in programmatic testing  
1. pushed 2 elements instead of an array into results  
2. intervals that touch at a point aren't merged  
[15:52] Successful submission  
*/  
function merge(intervals: number[][]): number[][] { // 1,3 2,4 5,6  
  intervals.sort(([a], [b]) => a - b)  
  const results = []  
  for (let i = 0; i < intervals.length;) {  
    const interval = intervals[i] // 5,6; 1,3  
    let maxEnd = interval[1] // 6; 3  
    while (++i < intervals.length && intervals[i][0] <= maxEnd) {  
      maxEnd = Math.max(maxEnd, intervals[i][1]) // 4  
    }  
    results.push([interval[0], maxEnd]) // 5,6; 1,4  
  }  
  return results // 1,4 5,6  
};  

🏋️ Practice 2

The Problem

617. Merge Two Binary Trees

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

🪞 Reflections

1. Even though this problem is labeled Easy, I panicked a bit when first approaching it, as I haven’t spent a lot of time working on trees.
2. Initially, I was trying to solve the problem iteratively. When I realized there was a natural recursive solution, I regained a lot of confidence, as that solution very simple.
3. I keep missing opportunities to use recursion during the planning phase. Occasionally, I realize this during the implementation, which can save me from floundering with a complicated iterative solution. I should practice recognizing when a recursive solution will be natural during the planning phase to save time and avoid changing plans mid-problem.
4. Changing plans mid problem resulted in using incorrect variable names. This is another common consequence of making a change mid-solution.
5. Also, during a mock interview yesterday, I noticed the existence of a recursive solution in the middle of floundering with an iterative solution. While I pointed this out, my interviewer asked me to continue with the iterative solution anyway. 2 possible conclusions from this scenario: 1. If I identify the recursive solution earlier, I may not be blocked from changing course to use it mid-implementation; 2. Some interviewers may hold a bias against recursion, so I may need to practice iterative solutions for times when I’m explicitly asked not to use recursion.
6. I’m still not keeping my planning phase near 2 minutes. In this case, I think that’s because I wasn’t confident with my approach, so felt the need to plan more carefully. While that may be the right thing to do in this scenario, it’s also worth considering how to avoid this scenario.
7. < 18 minutes total isn’t bad, and I’m happy with my solution.
8. Practicing writing the iterative version felt valuable. I like my more or less mechanical approach of thinking about stack frames to convert a recursive function into an iterative one.
9. That said, in the iterative version, I didn’t catch several bugs during manual testing. This isn’t great. Conclusions: try to identify when I can use recursion during planning. Use recursion when possible. Continue practicing iterative solutions for the scenario where recursion is explicitly barred.

My Solution

/* Merge 2 trees by adding nodes at the same position (assume missing nodes are zero)  
- Choose one tree to be the result  
- Traverse both trees simultaneously  
- When the cursor of one tree is missing relative to the other, set the node from the other tree and don't traverse it further  
- When both nodes exist, add the auxiliary tree node value to the result tree node value  
Time complexity: O(n) in the size of the smaller binary tree  
[4:40] done planning  
[14:24] done with initial implementation  
[17:00] done with test  
Bugs found after testing  
1. name cr not found (renamed variables)  
[17:44] successful submission  
*/  
/**  
 * Definition for a binary tree node.  
 * class TreeNode {  
 *     val: number  
 *     left: TreeNode | null  
 *     right: TreeNode | null  
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {  
 *         this.val = (val===undefined ? 0 : val)  
 *         this.left = (left===undefined ? null : left)  
 *         this.right = (right===undefined ? null : right)  
 *     }  
 * }  
 */  
  
function mergeTrees(root1: TreeNode | null, root2: TreeNode | null): TreeNode | null { // [0, 1, 2] [7, 8]  
  if (!root1) return root2  
  if (!root2) return root1  
  
  const result = root1 || root2 // [0, 1, 2]  
  result.val = (root1?.val || 0) + (root2?.val || 0) // 7  
  result.left = mergeTrees(root1.left, root2.left) // 9  
  result.right = mergeTrees(root1.right, root2.right) // 2  
  
  return result // [7, 9, 2]  
};  

An iterative solution (+ a slight optimization)

/* Attempting an iterative implementation  
- Having the recursive version to reference helps plan an iterative version  
- I'm working with pairs of nodes at every step, so I should probably push pairs of nodes onto a stack  
- Because there are 2 recursive calls, I'll have to push work onto a stack because I can't follow both recursive calls simultaneously  
  
Plan:  
1. Initialize a stack  
2. Initialize the result as the non-null tree (if available)  
3. Push both tree nodes and the result node, as a triple onto the stack  
4. loop over the stack pulling out the triples of nodes, setting state on the result, and pushing left & right triples back onto the stack when they're not both null  
[4:09] Done planning  
[9:03] Done with initial implementation  
[13:00] Done with 1 test  
Bugs found after testing:  
1. cannot find name c1 & c2 (in early escape added mid-solution)  
2. null pointer error checking for left of null node  
3. wrong answer (was doubling values when one node was null)  
4. null pointer error inserting children into stack  
[27:47] successful submission  
*/  
type Frame = [TreeNode | null, TreeNode | null, TreeNode | null]  
function mergeTrees2(root1: TreeNode | null, root2: TreeNode | null): TreeNode | null { // 1,2,3 5,9  
  if (!root1 && !root2) return null  
  const result = new TreeNode()  
  const stack: Frame[] = [[result, root1, root2]] // [[1,1,5]]  
  
  while (stack.length) {  
    const [cr, c1, c2] = stack.pop() // [3, null, null]; [2,2,9]; [1,1,5]  
    cr.val = (c1?.val || 0) + (c2?.val || 0) // 3; 11; 6  
    if (c1?.left || c2?.left) {  
      cr.left = new TreeNode()  
      stack.push([cr.left, c1?.left, c2?.left]) // [2,2,9]  
    }  
    if (c1?.right || c2?.right) {  
      cr.right = new TreeNode()  
      stack.push([cr.right, c1?.right, c2?.right]) // [3,null,null]  
    }  
  }  
  return result // [6,11,3]  
};  
  
// optimization: don't merge nodes below where one tree is null, just take the non-null sub-tree  
function mergeTrees(root1: TreeNode | null, root2: TreeNode | null): TreeNode | null {  
  if (!root1) return root2  
  if (!root2) return root1  
  const result = new TreeNode()  
  const stack: Frame[] = [[result, root1, root2]]  
  
  while (stack.length) {  
    const [cr, c1, c2] = stack.pop()  
    cr.val = (c1?.val || 0) + (c2?.val || 0)  
    cr.left = c1?.left || c2?.left  
    if (c1?.left && c2?.left) {  
      cr.left = new TreeNode()  
      stack.push([cr.left, c1.left, c2.left])  
    }  
    cr.right = c1?.right || c2?.right  
    if (c1?.right && c2?.right) {  
      cr.right = new TreeNode()  
      stack.push([cr.right, c1.right, c2.right])  
    }  
  }  
  return result  
};