Home > Reflections | ⏮️ ⏭️

2024-06-21 | 👿🐈 Terror 🌃 | 📏🌲 Trees ⌨️

👿 Night Terrors

😴 I got 8.5 hours of sleep last night.
💩 Yet I woke up feeling like crap.
🐈 Our orange tabby is vocal. And demanding.
💥 And this little terrorist has been waking us up in the middle of the night, refusing to go away or shut up until someone feeds him again.
➕ On one hand, I’m glad our little cancer survivor is eating and putting on weight.
➖ On the other hand, sleep is critical, and this behavior has been consistent in recent days and weeks.
🤔 What to do?
🔮 My wife will know.

❌ Rejection

✉️ I heard back from my recruiter today.
🤫 As is standard, they won’t provide specific feedback, though I can opt for a phone call with my recruiter.
🚫 While I’m surprised that I’m not continuing past the technical screen, this was definitely a stretch position.
⬇️ I don’t think I’ll be applying to positions at this level again this time around.
🏋️ But the experience was useful, and I’m still happy with my steady progress and routines in interview preparation.
⏭️ It’s time to refocus and queue up some more interviews.

🏋️ Coding Practice

Revisiting 543. Diameter of Binary Tree

I solved this yesterday, but wasn’t satisfied with the solution.

🪞 Reflections

1. I didn’t time or manually test any of these, I just wanted to come up with a cleaner solution, not relying on global, mutable state.
2. I’m happy enough with today’s second solution.

⌨️ My Solutions

/* Refactor depth to its own function  
- This can be much less efficient because we may recompute depth multiple times.  
- To be precise, we might compute depth for O(N) nodes to determine diameter  
so this may be O(N^2) runtime complexity  
*/  
function depth(root: TreeNode | null): number {  
  if (!root) return 0  
  if (!root.left && !root.right) return 0  
  const leftDepth = root.left ? depth(root.left) + 1 : 0  
  const rightDepth = root.right ? depth(root.right) + 1 : 0  
  return Math.max(leftDepth, rightDepth)  
}  
  
function diameterOfBinaryTree2(root: TreeNode | null): number {  
  if (!root) return 0  
  if (!root.left && !root.right) return 0  
  const leftDepth = root.left ? depth(root.left) + 1 : 0  
  const rightDepth = root.right ? depth(root.right) + 1 : 0  
  const diameter = leftDepth + rightDepth  
  let maxDiameter = diameter  
  const queue = [root.left, root.right]  
  while (queue.length) {  
    const node = queue.pop()  
    const d = depth(node)  
    if (d * 2 > maxDiameter) {  
      const dL = depth(node.left)  
      const dR = depth(node.right)  
      const thisDiameter = dL + dR + 2  
      if (thisDiameter > maxDiameter) maxDiameter = thisDiameter  
      if (node.left) queue.push(node.left)  
      if (node.right) queue.push(node.right)  
    }  
  }  
  return maxDiameter  
};  
  
/*  
To calculate diameter, we need to know  
- depth of left and right sub-trees  
- diameter of left and right sub-trees  
So let's write a function that returns both depth and diameter.  
Then we can call this function once and return only the diameter.  
*/  
function diameterOfBinaryTree(root: TreeNode | null): number {  
  function depthAndDiameter(root: TreeNode | null): [number, number] {  
    if (!root) return [0, 0]  
    if (!root.left && !root.right) return [0, 0]  
    const [leftDepth, leftDiameter] = root.left ? depthAndDiameter(root.left) : [0, 0]  
    const [rightDepth, rightDiameter] = root.right ? depthAndDiameter(root.right) : [0, 0]  
    const depth = Math.max(leftDepth, rightDepth) + 1  
    const diameter = (root.left ? leftDepth + 1 : 0) + (root.right ? rightDepth + 1 : 0)  
    const maxDiameter = Math.max(leftDiameter, rightDiameter, diameter)  
    return [depth, maxDiameter]  
  }  
  const [, diameter] = depthAndDiameter(root)  
  return diameter  
};