Home > Reflections | ⏮️ ⏭️

2024-06-09

☕ Motivation

• How to hack your brain to crave doing hard things.

🏋 Practice

Today I want to try a new planning strategy.
The plan is to

1. Paraphrase the question
2. Consider any clarifying questions
3. Identify the primary algorithm or technique that will drive my solution

• This primary algorithm or technique should
  • be recognizable to another engineer (e.g. an interviewer)
  • support runtime complexity analysis

4. Write down the expected run-time complexity
5. Stop planning and move on to coding
   The goal is to dramatically speed up my planning process.
   If I’m aiming to solve a problem in 15 minutes, I should aim to be done planning in 2 minutes.

The Problem

974. Subarray Sums Divisible by K

Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.
A subarray is a contiguous part of an array.

🪞 Reflections

1. It’s frustrating to not find the optimal solution, but I think I did the right thing during planning. I observed that this was an O(N^2) algorithm, it probably wouldn’t be fast enough, but I couldn’t come up with a better solution in a reasonable amount of time. This is the best I can do in this scenario during an interview.
2. I forgot to check the clock after planning, so I’m not sure if I hit my 2 minute mark or not. I suspect probably not, as it took a bit of time to think of a solution.
3. But - getting a working (though not fast enough) solution in under 19 minutes is still pretty good.
4. I’m not sure if this is a good sign or a bad sign, but even after reading through the optimal solution a few times, I find it nearly incomprehensible. Either this is a new trick I need to learn or it’s obscure and hopefully not critical to understand.

My Solutions

/* return non-empty subarrays with sum divisible by k  
- subarray implies contiguity  
- zero is divisible by k  
- -k is divisible by k  
  
- 2 pointers might work, but I'd need to reset the forward pointer multiple times  
- maybe dynamic programming. If [i...j] is divisible by k and [j+1...l] is divisible by k, then [i...l] is divisible by k  
- 2 pointers seems more tractable in short time. let's try that  
- O(N^2)  
  
[16:00] done with implementation and 1 test  
bugs after local test:  
1. can't find names i & j (changed variable names)  
2. any[] is not assignable to type 'number'  
3. tried returning the array, not its length (originally misread problem)  
4. cannot assign to a constant (let vs const)  
[18:24] first submission after local tests pass  
time limit exceeded  
This solution probably works, but O(N^2) is too big  
I'll probably need a dynamic programming solution to get it in time  
*/  
function subarraysDivByK1(nums: number[], k: number): number { // [3,0,-2] k=3  
  let total = 0  
  const sum = (xs: number[]) => xs.reduce((a, b) => a + b, 0)  
  for (let l = 0, r = 0; l < nums.length;) {  
    // might be off by 1 with slice 2nd index  
    const subarray = nums.slice(l, r + 1) // -2; 0,-2; 0; 3,0,-2; 3,0; 3  
    if (sum(subarray) % k === 0) {  
      total++  
    }  
    if (r === (nums.length - 1)) {  
      l++ // 3; 2; 1  
      r = l // 3; 2; 1  
    } else {  
      r++ // 2; 2; 1  
    }  
  }  
  return total // [[0],[3,0],[3]]  
};  
  
/*  
[20:00] plan dynamic programming solution  
okay, what are the sub problems?  
each individual element is a sub-array that can be combined with its neighbors  
if we try a bottoms-up approach, we can  
- start by computing all length-1 subarrays  
- then move on to length-2 subarrays, using previously calculated sums  
- continue in this fashion until we're asking if the entire array is divisible by k  
- it feels like there's some recursion here, starting with the length-1 and moving up  
- we can implement dynamic programming by caching results for recursive calls  
- let's try it  
- runtime O(N + N/2 + N/3 + ... + 1) = O(N * (1 + 1/2 + 1/3 + ... + 1/N))  
- I don't honestly know exactly what this series converges to, but it grows slowly  
- what is it for N=8?  
- = ((8 * (1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8)))  
- = ((8 * (1 + 9/20 + 15/56)))  
- = ((8 * (1 + 27/60 + 15/56)))  
- = ((8 * (1 + 27/60 + < 15/60)))  
- = (8 * (1 + < 42/60)) < 8 * (1 7/10)  
log_2 8 = 3 => n * log(n) shouldb e 8 * 3, we have less than that here, so maybe this is roughly logarithmic or less  
~ O(N*log(N))  
* wow, that runtime analysis took way too long and probably isn't right  
[39:00] done with runtime analysis  
  
[1:00:40] whew... changed direction during implmentation, done with first pass  
[1:06:00] done with 1 test  
bugs found  
1. cache type (boolean -> number)  
2. typo in recursive call function name  
[1:07:32] submission  
timeout  
... yeah, this is still N^2  
it's actually O(N + (N - 1) + (N - 2) + ... + 1) which is ~O(N^2)  
My analysis above was wrong.  
[1:20:21] okay, I can't think of a faster solution right now. Time to quit.  
*/  
const cache: Map<string, number> = new Map()  
const key = (i: number, j: number): string => `${i}-${j}`  
function subarraysDivByK2(nums: number[], k: number, n: number = 0): number { // [3,0,-2] k=3  
  const sum = (i: number, j: number): number => {  
    if (i === j) {  
      return nums[i]  
    } else {  
      return nums[i] + cache.get(key(i + 1, j))  
    }  
  }  
  let total = 0  
  for (let i = 0; i < (nums.length - n); i++) {  
    const j = i + n  // 2; 2; 1; 2; 1; 0  
    const s = sum(i, j) // 1; -2; 3; -2; 0; 3  
    cache.set(key(i, j), s)  
    if (s % k === 0) total++ // 3; 2; 1  
  }  
    
  const biggerTotals = n == nums.length - 1 ? 0 : subarraysDivByK2(nums, k, n + 1)  
    
  return total + biggerTotals // 3  
};  

🏋️ Another Mock Interview!

A friend offered to give me a mock interview today.
This was a great session and I got some good feedback.
After our session, I wrote up a couple of solutions to the problem in a git repo.

🪞 Reflections

1. Overall, the session went pretty well.
2. I did get bogged down managing state during code implementation, which is an area to continue to focus on improving.
3. I think he had a great tip for me here. When struggling to get the details right, it can be helpful to write out an example input (in a comment) and manually work through the algorithm. After writing it out, it should be easier to reference in code. I’ll need to practice this.
4. Whoops, I implemented a small helper function before the main function. He mentioned that I should avoid that, and I’d already come to this conclusion previously.
5. Time management.

• Don’t implement helper functions unless the interviewer asks for them.
• He said I did a great job of communicating and narrating my thought process, but I can afford to be less verbose. It’s okay to mention that I need to think for a bit, silently mull over the problem for 15 seconds, then continue on with my conclusions.
• It’s best to not have to change approaches mid problem.