Home > Reflections | ⏮️ ⏭️
2024-06-09
☕ Motivation
🏋 Practice
Today I want to try a new planning strategy.
The plan is to
- Paraphrase the question
- Consider any clarifying questions
- 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
- Write down the expected run-time complexity
- 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
numsand an integerk, return the number of non-empty subarrays that have a sum divisible byk.
A subarray is a contiguous part of an array.
🪞 Reflections
- 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.
- 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.
- But - getting a working (though not fast enough) solution in under 19 minutes is still pretty good.
- 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
- Overall, the session went pretty well.
- I did get bogged down managing state during code implementation, which is an area to continue to focus on improving.
- 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.
- 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.
- 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.