Home > Reflections | ⏮️ ⏭️

2024-06-19

🧠 Education

📜 Don’t Get Down Leveled or How to Tell a Good Story (From a Principal at Amazon)

✍️ Writing Behavioral Stories

1. Yesterday, I started brain dumping a timeline of recent work experiences that may make for good behavioral stories.
2. I’m trying to focus on experiences that involve
   1. multiple, cross functional teams, and
   2. conflict resolution
3. Today, I drafted a story from one of these experiences, applying the man in a hole story structure.
4. My story rambled a bit on first draft, but while summarizing, I think I came up with some good bullet points.
5. Honestly, it’s not my favorite kind of prep work, but I think if I keep devoting time to story crafting, I’ll wind up with some good fodder for interviews.

🏋️ Coding Practice

2235. Add Two Integers

Given two integers num1 and num2, return the sum of the two integers.

🪞 Reflections

1. Perhaps they need a new category that’s easier than Easy. Maybe they should call this Trivial.
2. I could see asking about adding numbers when built in types can’t hold the result, but the constraints were -100 → 100, so there really doesn’t seem to be anything to this.

⌨️ My Solution

/* Um... really?  
- Is there any catch? Are the integers too big for built ins or something?  
  
Plan: return a + b  
Runtime complexity: O(1)  
Extra space complexity: O(1)  
[0:52] Done planning  
[1:03] Done with initial implementation  
[1:24] Done with a test  
[1:41] Successful submission  
*/  
function sum(num1: number, num2: number): number { // -3 4  
  return num1 + num2 // -1  
};  

1051. Height Checker

A school is trying to take an annual photo of all the students. The students are asked to stand in a single file line in non-decreasing order by height. Let this ordering be represented by the integer array expected where expected[i] is the expected height of the ith student in line.
You are given an integer array heights representing the current order that the students are standing in. Each heights[i] is the height of the ith student in line (0-indexed).
Return the number of indices where heights[i] != expected[i].

🪞 Reflections

1. Another easy problem with an easy solution.
2. Looking at the recommended solution, they note that sorting is required, but they suggest that the point is to implement the sorting algorithm.
   1. I haven’t implemented a sorting algorithm from scratch for some time, so I’ll probably come back and try that out here.

⌨️ My Solution

/* return the number of indices where elements aren't in sorted order  
1. if swap 2 unequal values in the array, we get 2 elements out of place. Does that count as 2 differences or only 1?  
  
Plan  
1. An easy strategy would be to copy and sort the array, then compare index by index.  
  1. This would take O(N * log(N)) time due to the sorting  
2. I'm tempted to scan the list left to right and count each time when an element is not greater than or equal to its left neighbor, but I'm not 100% sure this will actually give us what we want. Let me try it on a couple of examples first.  
  1. No, this doesn't work  
  2. Counter example: 1,1,4,2,1,3  
  3. Result of this algorithm: 2 (2 < 4, 1 < 2)  
  4. Expected result: 3 (indices 2, 4, & 5 are out of place)  
  5. I wonder if it's always N + 1... maybe another example will help  
  6. Nope.. this doesn't work either  
  7. Counter example: 5,1,2,3,4  
  8: Modified algorithm result: 2 (1 < 5; + 1 = 2)  
  9: Expected result: 5 (every element is out of place)  
3. Maybe there's a linear time algorithm, but it doesn't seem obvious and I'm almost 9 minutes in.  
4. I'll just go for the O(N * log(N)) algorithm for now  
[9:21] Done planning  
[11:09] Done with initial implementation  
[12:40] Done with test  
No bugs found during manual testing  
[12:56] Successful submission; perfect on first try  
*/  
function heightChecker(heights: number[]): number { // 5, 1, 2  
  const expected = heights.slice().sort((a, b) => a - b) // 1, 2, 5  
  const diff = expected  
    // 1 != 5 => 1  
    // 2 != 1 => 2  
    // 5 != 2 => 3  
    .reduce((d, n, i) => d + (n !== heights[i] ? 1 : 0), 0)  
  return diff // 3  
};  

346. Moving Average from Data Stream

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.
Implement the MovingAverage class:

• MovingAverage(int size) Initializes the object with the size of the window size.
• double next(int val) Returns the moving average of the last size values of the stream.

🪞 Reflections

1. Timing was fine
2. Approach was good
3. Errors I’m not worried about
   1. forgetting to prefix with this. - I used it in 3/4 places. This was an obvious slip. Perhaps a more careful final reading should have caught it. That said, I don’t expect to be implementing classes in interviews very often.
   2. Using Array.unshift instead of Array.shift.
      1. During an interview, I’d just mention which method I intended to use.
      2. I can never remember which I want between shift and unshift.
      3. I should probably come up with some kind of mnemonic.
      4. shift removes the first element from the array and shifts every other element 1 back. unshift inserts an element at the beginning and shifts every other element 1 forward.
      5. This is difficult to remember because elements are shifting in both cases, and shift doesn’t imply a direction.
      6. The end-of-array counterparts to these methods are push and pop, which I never confuse.
      7. I know that push inserts and element at the end and pop removes one.
      8. This is the abstract API of a stack and the methods do what they say they do.
      9. Why were the terms shift and unshift used?
      10. They’re obviously inverse operations, but which one inserts and which one removes?
      11. shift is to pop as unshift is to push.
      12. 🤔 How to remember this relationship…
          1. ✅ push and unshift both contain a u.
          2. ✅ pop and shift are the shorter words in their respective pairs.
          3. ❌ You have to push before you can pop. You have to unshift before you can shift (this language seems counter-intuitive in this respect).
      13. 😆 Ah, the internet is great sometimes. Here’s a good one from stack overflow: “Easy to remember if you mentally drop the “f” in shift / unshift: shift removes elements and unshift adds them :)” – Vicky Chijwani
4. The error I shouldn’t make during an interview: The moving average I computed used the window size as the denominator instead of using the length of the array. This computed the wrong value when we hadn’t yet seen size elements. My test didn’t catch this because the example assumed we’d already seen so many values. Running another manual test would not have taken much time, and would have caught this bug.
5. Even though I got the problem wrong, timing was fine. Even if I’d taken the time to run another test, which probably would have caught my bug, this would have been an acceptable amount of time for this problem.

⌨️ My Solution

/* implement a class to return a fixed size moving average on demand  
Questions  
1. What should we do when we haven't yet seen `size` elements? Just return the average of what we've seen so far? Or assume some fixed value for out of bounds values? Something else?  
Based on examples, just return the average of what we've seen so far.  
  
2. How are we reading the stream of values?  
They're passed into the next function, which accepts a value from the stream and returns the moving average at that point in time.  
  
Plan  
1. We'll need to store the previous N values, so the class should maintain an array of appropriate size  
2. Keep it simple - just calculate the average on demand  
  
[9:05] Done with initial implementation  
[11:16] Done with test  
Bugs found after manual testing:  
1. referenced values without `this.` prefix  
2. returned wrong average for initial values  
3. used unshift instead of shift  
  
[14:00] Successful submission  
*/  
class MovingAverage {  
  size: number  
  values: number[]  
  
  constructor(size: number) {  
    this.size = size  
    this.values = []  
  }  
  
  next(val: number): number { // size=2 values=[1, 2] val=3  
    this.values.push(val) // [1, 2, 3]  
    if (this.values.length > this.size) {  
      this.values.shift() // [2, 3]  
    }  
    return this.values.reduce((a, b) => a + b, 0) / this.values.length // 5 / 3 = 1.666  
  }  
}  
  
/**  
 * Your MovingAverage object will be instantiated and called as such:  
 * var obj = new MovingAverage(size)  
 * var param_1 = obj.next(val)  
 */  

704. Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.

🪞 Reflections

1. I’m glad I finally got around to implementing this basic algorithm, as it should roll off my mind quickly if I need it as part of a larger solution during an interview, and there are a few tricky bits to be careful with.
2. ✅ I found a bug during testing: we have to adjust the index inward by 1 to ensure we don’t infinite loop (due to rounding). After doing this, I also realized I should change my loop condition from !== to <= to avoid my boundary indices missing each other and then looping forever. I’m not actually sure if that’s necessary here, but it’s a good safeguard.
3. It can be difficult to remember if it matters whether we use floor, ceiling, or rounding when the midpoint is a fraction. As long as we adjust the boundaries properly, it doesn’t matter. Here’s a good explanation on stack overflow.

⌨️ My Solution

/* use binary search to find (and return) the target value or -1 if it doesn't exist  
  
Plan:  
1. implement binary search  
Runtime Complexity: O(N * log(N))  
[1:07] Done planning  
[5:57] Done with initial implementation  
Found & fixed 1 bug during testing.  
[16:46] Done testing  
bugs found after testing:  
1. returned value instead of index (misread problem)  
[18:12] Successful submission  
*/  
function search(nums: number[], target: number): number { // [-3, 9, 26], 8; [-3, 9, 26], 8; [-3, 9, 26], 9; [-3, 9, 26], 26  
  let result = -1  
  for (let l = 0, r = nums.length - 1; l <= r;) { // 0,0; 0,2;; 0,1; 0,2;; 0,2;; 1,2; 0,2  
    const m = Math.round((l + r) / 2) // 0; 1;; 1; 1;; 1;; 2; 1  
    const value = nums[m] // -3; 9;; 9;; 9;; 9;; 26; 9  
    if (target === value) {  
      result = m // 9; 26  
      break  
    } else if (target < value) {  
      // BUGFIX: infinite loop - need to slide index in 1 extra  
      r = m - 1 // 0;; 1 1  
    } else if (target > value) {  
      l = m + 1 // 1; 1  
    }  
  }  
  return result // -1; 9; 26  
};