Home > Reflections | ⏮️ ⏭️

2024-06-05

🪞 Practice Reflections

Yesterday, I observed a problem with my programming problem solving strategy.
This prompted the question: 🤔 How can I generate higher quality algorithms without relying on testing?

🧠⛈️ Brain Storming

1. Become familiar with more solutions

1. Maybe this is a signal that the current bottleneck in my coding interview performance isn’t coding.
2. At least while practicing, when planning a solution to a problem, if I can’t identify an algorithmic approach I’m confident in, it may be more fruitful to stop and do some research than to continue down a likely dead end path.

2. Develop a systematic approach to generating ideas

When stuck in the planning phase, maybe I start asking myself a series of questions that may highlight an approach I’m familiar with, but that is currently not front of mind. Examples:

1. What would a brute force approach look like? Typically, this involves generating every possible solution, testing each one, and returning a successful candidate.
2. Is there a natural recursive solution? What is the base case? What do the sub problems look like?
3. Is there a simpler version of this problem that I know how to solve? Sometimes a solution to a simpler problem can be modified to solve a more complicated problem.
4. Is there a preprocessing step that would make this easier to solve? For example, sometimes sorting the input enables a tractable solution.
5. Can I break the problem down into sub problems whos solutions can be combined to form a solution to the problem at hand?
6. Is there a data structure that would make this problem easier to solve? Arrays, lists, stacks, queues, trees, graphs, tries, maps…

3. Practice writing algorithmic solutions in a shorthand pseudo code

1. I’m kind of just winging it in the planning phase when it comes to writing out an algorithmic approach.
2. It’s easy to have a fuzzy idea in mind, but writing that idea out explicitly forces a degree of clarity. It also frees up cognitive resources to focus on the sticking points.
3. Having a systematic and familiar approach to writing down a solution can save a lot of time and help structure our thoughts in a way that aids analysis and elaboration.
4. Of course, to be useful, this short-hand pseudo code would need to be much faster to write than a real programming language.
5. What kinds of primitives would empower such an algorithmic pseudo code to be expressive, flexible, and precise enough to formulate a solution to any programming problem?
6. Does this already exist? Can I copy someone else’s approach rather than invent my own?
7. Perhaps I can practice writing in such a language backward: by translating real solutions into this higher level pseudo code. This certainly seems like a good way to test the language for practicality. How much shorter is the pseudo code than the real solution? How much faster is it to write? What details can be omitted completely while maintaining a useful representation of the algorithm?

4. Practice planning solutions to programming problems without actually implementing or testing them.

1. If I’m already pretty good at translating plans to code, I could save a lot of time and quickly develop a sense for how many and what kinds of problems I’m not prepared to solve.
2. This could inform a study plan: ah, of a dozen LeetCode problems I wrote out plans for today, I couldn’t confidently identify solutions to those involving e.g. binary search or tree traversal, etc

🏋️ Practice

1002. Find Common Characters

Problem Statement

Given a string array words, return an array of all characters that show up in all strings within the words (including duplicates). You may return the answer in any order.

🪞 Reflections

This took about 3x as long (46m) as my target time for an interview (15m)

Why did planning take 21 minutes?

1. It took a bit of time to come up with a strategy to accurately count duplicate characters across words
2. The initial plan didn’t come out smoothly on the first try
3. After analyzing the runtime complexity of the initial plan, I decided to optimize to eliminate a W^2 term, which seems significant given the problem constraints

Initial implementation took ~8m

Not bad.

Why did testing take ~14m?

I split the problem into 3 helper functions and tested each helper function independently, then I tested the top level function.
I feel like this worked out well.
I don’t think any particular function took very long to test.
Testing was pretty easy; there wasn’t much state to track and I didn’t need many test cases to gain confidence.
While testing the top level function, I was confident that each helper was correct.

Testing effectiveness

• I don’t think I actually caught any bugs during testing
• Yet there were 2 syntax errors and 1 simple return type error I found while attempting submission
• I’m not particularly worried about any of these errors.
  • They weren’t logic errors
  • I don’t think an interviewer would care

The uncaught errors

1. syntax error in frequencyMap return type (⇒ instead of :)

• I probably annotated the return type after initially writing the function. This mixup isn’t a big deal.

2. syntax error in frequencyMap for of (no const in c of word)

• I don’t actually use the for-of syntax very often, but wanted to reduce a bit of complexity by not dealing with indices
• A .forEach method call would have worked just as well and probably would have avoided the syntax error

3. returned a string instead of string[]

• I simply forgot (or didn’t initially pay attention to) the fact that they wanted an array of character strings instead of a single string
• not really worried about this

Are my rationalizations justified? Useful?

While i’m not particularly worried about these minor classes of errors, it’s possible I’m rationalizing poor performance due to a self-serving bias and a desire to perform well.
To control for bias, perhaps it’s still worth considering how to improve.

1. For the careless return type syntax error

• Perhaps a habit of one final scan of a function implementation (focusing specifically on syntax) before moving on could help catch these.
• That said, in a real interview, speed is likely to be the major challenge. I’d rather include a few minor syntax errors in my final solution and increase my odds of finishing on time than risk missing the timeline but have perfect syntax.
  • Compromise: save the syntax scan as an optional last step, time permitting.

2. Prefer familiar syntax (e.g. xs.forEach(x => ...)) over less familiar syntax (e.g. for (const x of xs) ...)
3. Consider another optional, time-permitting step at the end: re-read the problem statement and double check that I’m returning the right thing.

Further Considerations

I don’t think my analysis above indicates a path to reducing time from 46 → ~15 minutes.
Some thoughts on compromises and further improvement:

1. When writing a solution involving helper functions, define the helper functions last. Perhaps just write the function signature and initially assume that it’ll work. It’s probably better to finish a high level solution and not have time to implement (and test) all of the helper functions rather than run out of time during helper function implementation before having the full high-level implementation in place.
2. Since my testing is happening at the end, it’s always possible to stop testing early. Perhaps it’s good enough to see that I have a systematic approach to testing that could catch bugs if I had enough time to apply it. In this case, it’s probably worth writing out a few example cases to test before running all of the tests.
3. Still, my manual testing process tends to be slow. It’s worth considering how I might be able to speed it up.
4. I can hear people talking in a nearby room. This distraction likely slowed me down a bit. Definitely prepare to have a quiet environment during a real interview.
5. Again, what about this 21 minute planning phase? That already blows the entire budget and then some.

• In a real interview, I’ll need to be sure to think aloud and discuss all of my decisions with my interviewer before following through on them. For example, it may have been good enough to note that my first plan had a sub-optimal runtime, rather than actually re-planning my solution. I’m not 100% sure if I should be monitoring the clock while practicing and deciding to cut things short, or if it’s better to focus on accuracy initially and assume that accurate practice will improve time. Perhaps I should keep an eye on the clock so as to make practice more realistic. In this case, a quick glance at the clock after my first implementation would likely have resulted in a decision to skip the optimization. Or at least, if I have a good idea of how much time each phase should take…
• Identify a budget. Monitor the clock aiming to stay within the budget. For example: 5 minutes to plan, 5 minutes to implement, 5 minutes to test. Having these milestones in mind in advance may support better decision making during an interview. Counterpoint: it’s important not to let the stress of time pressure encourage bad decisions. So maybe it’s worth considering in advance what kinds of short cuts are worth taking, and where I absolutely should not cut corners to save time. Examples:
  • Good short cuts to save time:
    • Note the likely existence of an optimization up front, but don’t re-plan or re-implement a working solution unless the interviewer insists.
    • Assume the existence of helper functions when initially implementing a high level solution. Write the helper functions if there’s extra time at the end and the interviewer wants to see them.
  • Situations when short cuts should not be used to save time:
    • I’m not confident that my planned solution will work. My intuition seems to be pretty good. If I’m not confident in my plan, the solution likely won’t work. Stick it out in the planning phase even if this means we don’t ultimately have time to implement and test. If we identify a solution we’re confident in with only a few minutes remaining, pull out all of the time saving tricks at our disposal to attempt to get some form of implementation in place. Don’t implement helper functions. Don’t fret about exact syntax or perfect use of built-in functions. Ideally, we also at least have a tiny bit of time to demonstrate some form manual testing. Even just mentioning a test case and talking through the simplest test case can demonstrate that the skill exists, even if we don’t have time to fully show it off.

My Solution

/* find all characters common to all words including duplicates  
Thoughts:  
1. Including duplicates makes this a bit more challenging. Otherwise we could just use a set.  
2. But we can adapt by using a map to count the number of occurrences that are common to all words  
3. If characters are common to all words, we can use the first word as our reference for every other word  
4. Tricky: ensuring that we accurately detect the presence of duplicates in other words (i.e. a simple character in string check isn't sufficient)  
5. So maybe our basic operation isn't checking the existence of a character, but counting it instead  
  
Question:  
1. is this case sensitive?  
The examples don't show any capitals  
But the constraints mention the input is only lowercase, so it's irrelevant  
  
Plan:  
1. Create a map M of character counts in the first word W1  
2. For each character C in the map M:  
     Update the count to the minimum count across all input words  
3. Initialize the result string  
4. For each non-zero character count (N):  
     Repeat the character N times and append this to the result  
5. return the result  
  
runtime complexity:  
- we touch each word once (O(N))  
  - for each word, we count each character from our initial word (O(W))  
- result: O(N*W^2)  
  - where N is the number of words  
  - and W is the size of the average word  
- We might be able to reduce the W^2 by taking a single pass across the word  
- But I'm not really sure about that...   
- what if we created a map for each word, then merged the maps with the minimums?  
  - O(W) to create each map * O(N) to process each word + O(N * W) to merge the maps = O(W*N) + O(N*W) = O(2*N*W) = O(N*W)  
- I like this better  
  
revised plan:  
1. Create a character count map for each word  
2. Merge the maps, taking the minimum value for each element  
3. Create the result string by repeating each character the appropriate number of times according to our merged map  
[21:31] completed plan  
[29:45] completed initial implementation  
[43:10] finished testing  
Uncaught bug: syntax error in frequencyMap return type (=> instead of :)  
Uncaught bug: syntax error in frequencyMap for of (no const in c of word)  
Uncaught bug: returned a string instead of string[]  
[46:01] successful submission  
*/  
  
const frequencyMap = (word: string): Map<string, number> => {  
  // 1. word=''  
  // 2. word='aba'  
  const map = new Map()  
  for (const c of word) {  
    // 2.1 c=a  
    // 2.2 c=b  
    // 2.3 c=a  
    map.set(c, (map.get(c) || 0) + 1)  
    // 2.1 map={a:1}  
    // 2.2 map={a:1,b:1}  
    // 2.3 map={a:2,b:1}  
  }  
  return map  
  // 1. return {}  
  // 2. return {a:2,b:1}  
}  
  
const mergeMinimum = (m1: Map<string, number>, m2: Map<string, number>): Map<string, number> => {  
  // 1. m1={} m2={}  
  // 2. m1={a:1,b:2,c:3} m2={b:2,c:1,d:5}  
  const result = new Map()  
  Array.from(m1.entries()).forEach(([c, n]) => {  
    // 2.1 c=a n=1  
    // 2.2 c=b n=2  
    // 2.3 c=c n=3  
    const otherCount = m2.get(c) || 0  
    // 2.1 otherCount=0  
    // 2.2 otherCount=2  
    // 2.3 otherCount=1  
    const min = Math.min(n, otherCount)  
    // 2.1 min=0  
    // 2.2 min=2  
    // 2.3 min=1  
    if (min) {  
      result.set(c, min)  
      // 2.2 result={b:2}  
      // 2.3 result={b:2,c:1}  
    }  
  })  
  return result  
  // 1. return {}  
  // 2. return {b:2,c:1}  
}  
  
const mapToString = (m: Map<string, number>): string =>  
  // 1. m={}  
  // 2. m={a:2,b:1}  
  Array.from(m.entries())  
    .reduce((r, [c, n]) =>  
      // 2.1 r='' c=a n=2  
      // 2.2 r='aa' c=b n=1  
      r + c.repeat(n),  
      // 2.1 => 'aa'  
      // 2.2 => 'aab'  
      ''  
  )  
  // 1. => ''  
  // 2. => 'aab'  
  
function commonChars(words: string[]): string[] {  
  // 1. words=['']  
  // 2. words=['abac','aac', 'aa']  
  const maps = words.map(frequencyMap)  
  // 1. maps=[{}]  
  // 2. maps=[{a:2,b:1,c:1},{a:2,c:1},{a:2}]  
  const merged = maps.reduce(mergeMinimum)  
  // 1. merged={}  
  // 2. merged={a:2}  
  const result = mapToString(merged)  
  // 1. result=''  
  // 2. result='aa'  
  return result.split('')  
};  

🏋️ More Practice

59. Spiral Matrix II

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.

🪞 Reflections

1. Ugh. This was painful. Death by a thousand little bugs. Or, I guess, 10 little bugs.
2. That said, while the overall time to completion was unacceptable (~84m), my plan did ultimately work.
3. Yes, there were a lot of errors I had to work through to get a working implementation, but they were:
   1. a syntax error nobody will care about
   2. a syntax error due to the (apparently old) version of TypeScript LeetCode is using
   3. a syntax error nobody will care about… basically a typo
   4. a type error that required me to give TS more information… it would have worked at runtime
   5. a type error that I had to ignore to appease the TS
   6. a typo
   7. a typo
   8. maybe a bad poorly thought through short-cut or maybe just the result of a yet-to-be-fixed typo
   9. a typo
   10. a bad copy/paste (basically a typo)
4. Yes, it feels like a lot of errors, but none of them indicate a lack of understanding of the problem or a lack of programming ability… just a lack of compiler-level code perfection. I don’t think they’d be held against me in an interview.
5. I’m happy with the order I chose to work in.

• 17 minutes may be a long time to plan, but I was (rightfully) confident in my plan when I moved to implementation.
• I spent ~9 minutes implementing the top-level solution, putting off implementation of the helper functions.
• I spent the next 10 minutes thoroughly testing my high-level solution before moving on to implement and test the helper functions.
• In an interview, I likely would have been stopped mid-testing to move on to the next problem. At that point, I’d demonstrated a well-planned solution, awareness of the possibility of maybe-easier alternate approaches, a high-level implementation, and an ability to thoroughly, manually test my code. This is what they’re looking for.

6. I’m definitely happy with my decision to implement the steering approach rather than trying to come up with a calculation for the indices. While there may be a nice calculation, I don’t think I’d have come up with it in a reasonable amount of time (if at all).
7. I’m happy with my initial high-level solution. All the bugs were found in a helper function.
8. I’m pretty happy with my decomposition into helper functions.

My Solution

/* generate an n x n matrix filled with elements from 1 -> n^2 in spiral order (clockwise)  
Thoughts  
- Okay, this might be an interesting index computing challenge  
- 2 approaches come to mind  
1. fill the array in spiral order, computing the next index as we go  
  - e.g. start at the top left, fill to the right, when out of bound, turn right and head downward  
2. compute the appropriate indices in a regular 2D-array order  
  - e.g. first row: 1..n, 2nd row: ???  
- The first approach seems more tractable than the second...  
  it may take a while to come up with a general formula for which index goes in which slot  
- The second approach seems easier because we don't need to explicitly compute the indices  
  we can just steer as we go. That said, it does seem like a bit of a pain  
- I wonder if there's some kind of rotation scheme where we could just generate all the  
  needed numbers and rotate and combine as necessary...  
  
Any approach will take O(N^2) time, as that's the size of matrix we're generating  
  
Steering approach plan  
1. initialize a 2D-array full of n empty arrays  
2. We can be in one of 4 states: moving right, down, left, up  
3. We know we need to turn when we run out of bounds or when the next index is already filled  
4. Compute the next index based on the current index, the state of the next index, and our directional state  
5. We know we're done when we've set n^2 numbers  
  
example:  
N = 3  
indices = 0,0 0,1 0,2 1,2 2,2 2,1 2,0 1,0 1,1  
hmm: I wonder if we can turn after a know number of iterations instead of checking the boundaries  
in this case:  
0,0 0,1 0,2 1,2 2,2 2,1 2,0 1,0 1,1  
we did:  
n, n - 1, n - 1, n - 2, n - 2  
  
N = 2  
0,0, 0,1 1,1 0,1  
n, n - 1, n - 1  
  
formula for when to turn:  
N, (N - 1)x2, (n - 2)x2  
  
eh... I'm a bit unsure about this approach, I'll go with the first one, as I believe it'll work better  
  
- I'll need to ensure that I fill the arrays to the appropriate length, perhaps filling with -Infinity as a marker indicating it needs to be filled  
- I'll also need to be careful not to go out of bounds, using null protection ? and checking for typeof number should work  
  
  
[17:17] done planning  
[26:00] done with initial implementation (minus helper functions)  
[36:30] done with 2nd test of high level implementation  
[47:38] done with initial implementation of nextDirection  
[55:27] done with 1 test of nextDirection  
Uncaught errors on submission:  
1. bad enum syntax (spurious =)  
2. bad safe matrix element syntax (doesn't like ?. syntax for safe element access; switching to && chaining)  
3. extra closing paren  
4. type error TS doesn't trust my number[] is a [number, number]  
5. TS doesn't like my array filling trick: @ts-ignoring  
6. Right -> RIGHT  
7. maximum call stack size exceeded (used an `x` where I meant to use `next` in nextDirection element check)  
8. maximum call stack size exceeded (fine, remove recursive call and repeat earlier code to compute next index)  
9. result[x][y] = i + 1 (cannot set properties of undefined (setting '0')) - used old indices instead of new indices  
10. result[x][y] = i + 1 (cannot set properties of undefined (setting '2')) - console logging indicates negative index - ugh... earlier copy/pasted code wasn't updated to use the new direction variable  
[1:22:40] first successful (local) test  
[1:23:45] first submission is successful  
  
*/  
  
enum Direction {  
  RIGHT = "RIGHT",  
  DOWN = "DOWN",  
  LEFT = "LEFT",  
  UP = "UP"  
}  
  
const nextDirection = (d: Direction, cursor: [number, number], matrix: number[][]): [[number, number],Direction] => {  
  // 1. d=RIGHT cursor=[0,1] matrix=[[1,2],[-Infinity,-Infinity]]  
  const [x, y] = cursor  
  // 1. x=0 y=1  
  const maybeNext: [number, number] = d === Direction.RIGHT  
  // 1. maybeNext=[0,2]  
    ? [x, y + 1]  
    : d === Direction.DOWN  
    ? [x + 1, y]  
    : d === Direction.LEFT  
    ? [x, y - 1]  
    : [x - 1, y] // d === Direction.UP  
  const [xN, yN] = maybeNext  
  // 1. xN=0 yN=2  
  const next: number | undefined = matrix[xN] && matrix[xN][yN]  
  // 1. next = undefined  
  if (typeof next === 'number' && next <= -Infinity) {  
    return [maybeNext, d]  
  } else {  
    let newDirection: Direction  
    switch (d) {  
      case Direction.RIGHT:  
        newDirection = Direction.DOWN  
        // 1. newDirection=DOWN  
        break  
      case Direction.DOWN:  
        newDirection = Direction.LEFT  
        break  
      case Direction.LEFT:  
        newDirection = Direction.UP  
        break  
      case Direction.UP:  
        newDirection = Direction.RIGHT  
        break  
      default:  
        throw new Error(`unexpected direction: ${d}`)  
    }  
    const nextCursor: [number, number] = newDirection === Direction.RIGHT  
      ? [x, y + 1]  
      : newDirection === Direction.DOWN  
      ? [x + 1, y]  
      : newDirection === Direction.LEFT  
      ? [x, y - 1]  
      : [x - 1, y] // newDirection === Direction.UP  
    return [nextCursor, newDirection]  
    // 1. return [[1,1],DOWN]  
  }  
}  
  
const initializeMatrix = (n: number): number[][] => {  
  // @ts-ignore  
  return Array.apply(null, { length: n }).map(() => Array.apply(null, { length: n }).map(() => -Infinity))  
}  
  
function generateMatrix(n: number): number[][] {  
  // 1. n=1  
  // 2. n=2  
  let cursor: [number, number] = [0, 0]  
  let d: Direction = Direction.RIGHT  
  const result = initializeMatrix(n)  
  // 1. result=[[-Inf]]  
  // 2. result=[[-Inf,-Inf],[-Inf,-Inf]]  
  for (let i = 0; i < n**2; i++) {  
    const [x, y] = cursor  
    // console.log({n,i,x,y,result})  
    // 1. x=0 y=0  
    // 2.1 x=0 y=0  
    // 2.2 x=0 y=1  
    // 2.3 x=1 y=1  
    // 2.4 x=1 y=0  
    result[x][y] = i + 1  
    // 1. result=[[1]]  
    // 2.1 result=[[1,-Inf],[-Inf,-Inf]]  
    // 2.2 result=[[1,2],[-Inf,-Inf]]  
    // 2.3 result=[[1,2],[-Inf,3]]  
    // 2.4 result=[[1,2],[4,3]]  
    if ((i + 1) < n**2) {  
      [cursor, d] = nextDirection(d, cursor, result)  
      // console.log({cursor,d})  
      // 2.1 cursor=0,1 d=RIGHT  
      // 2.2 cursor=1,1 d=DOWN  
      // 2.3 cursor=1,0 d=LEFT  
    }  
  }  
  return result  
  // return [[1]]  
  // return [[1,2],[4,3]]  
};