Technical questions Flashcards
List the steps of solving a technical question.
- Listen
- Example
- Brute force
- Optimize
- Walk through
- Implement
- Test
Detail phase
(1) Listen
Pay very close attention to the problem description. Write the pertinent [1] information on the whiteboard.
You probably need it all for an optimal algorithm.
[1] Record any unique information. E.g. “given two sorted arrays” or “algorithm to be run repeatdely on a server”.
Detail phase
(2) Example
Draw an example on the whiteboard:
1. Specific: Use real numbers or strings (if applicable).
1. Big enough. [1]
1. Not a special case. [2]
1. Get the interviewer’s explicit confirmation.
1. Make the best example you can in the first go. [3]
If it later turns out your example isn’t quite right, fix it.
[1] It’s hard to find patterns if the example is too small, like a 3 node binary search tree.
[2] Be vey careful. It’s very easy to inadvertently draw a special case like a balanced tree. If there’s any way your example is a special case (even if you think it probably won’t be a big deal), you should fix it.
[3] Don’t move on with an obviously flawed example with the plan to fix it later as you understand the problem better.
Detail phase
(3) Brute force
Get a brute-force solution ASAP. Don’t worry about developing an efficient algorithm yet. State a naive algorithm and its runtime, then optimize from there.
Don’t code yet!
During the “Brute force” phase, should you write some code?
No.
During the “Brute force” phase, should you state the big O?
runtime / space complexity
Yes.
This will help in the following optimization step.
During the “Brute force” phase, should you test the code?
Not in detail [1]. But do quickly run through 1-2 approved examples.
[1] The algorithm will change during optimization.
Detail phase
(4) Optimize
Walk through your brute force solution:
1. Look for any unused info. [1]
1. Make a time vs. space tradeoff. [2]
1. Consider precomputation.
1. Consider best conceivable runtime (BCR).
1. Apply the 5 “Optimize and Solve” techniques.
[1] You usually need all the information in a problem.
[2] Hash tables are especially useful! Present the trade off. Let the interviewer pick a side.
Detail phase
(5) Walk through
Now that you have an optimal solution, walk through your approach in detail:
1. Get a feel for the structure.
2. Know what the variables are and when they change.
3. Have a clear idea of the implementation for each part. [1]
4. If pseudocode, keep it short and high level.
It’s faster to fix conceptual errors now than after implementation.
[1] If you don’t understand exactly what you’re about to write, you will struggle to code it. It will take you longer to finish the code, and you’re more likely to make major errors.
Detail phase
(6) Implement
Your goal is to write beautiful code:
1. Start in the top left corner.
2. Keep code lines straight and short.
3. Check the validity of all input and values returned by helpers. If time permits, explicitly, otherwise, add TODOs for validity checks and talk out how you would handle which kind of invalidity.
4. Implement from most to least abstract. [1]
5. Modularize your code from the beginning. [2]
6. Use expressive variable names.
7. If variable name too long, explain that you will use an abbreviation starting from the second usage, like “sc” for “startChild”.
6. Refactor to cleanup anything that isn’t beutiful - or at least add a TODO and explain what you would refactor.
7. If you get confused, walk through the example again.
You only have this little code to demonstrate that you’re a great DEV.
[1] Assume custom classes and less abstract functions already exist. Implement them later if time allows / interviewer asks for them.
[2] Separate class for each data structure. Separate function for each “one thing” in the sense of CC.
Detail phase
(7) Test
Test in this order:
1. Conceptual tests. Walk through your code like you would for a detailed code review.
2. Unusual or non-standard code, e.g. length - 2.
3. Hot spots, like arithmetics and null nodes.
4. Small test cases. [1]
5. Special cases.
And when you find bugs, fix them carefully.
[1] Don’t use the big 8-element array from the algorithm part. Use a 3-4 element array. It’s much faster than a big test case and just as effective.
In the “(7) Test” phase, how big should be the test cases?
Rather small. Don’t use the big 8-element array from the algorithm part. Use a 3-4 element array. It’s much faster than a big test case and just as effective.
But not too small, so that it doesn’t become a special case.
List the 5 “Optimize and Solve” techniques
- Look for BUD
- DIY (do it yourself)
- Simplify and generalize
- Base case and build
- Data structure brainstorm
Define the “optimize and solve” technique
(1) Look for BUD
- Bottlenecks [1]
- Unnecessary work
- Duplicated work
Check for those during the “Optimize” phase.
[1] The parts of the algorithm which contribute most to the big O complexity.
In BUD optimization, what are “bottlenecks”?
The parts of the algorithm which contribute most to the big O complexity. Common types:
1. Slow one-time work: Imagine an algorithm which does some work A once, and then some work B once. If A is O(n^2) while B is O(n), A is the bottleneck. There is no point in optimizing B as long as the runtime of A is bigger than the one of B.
2. Slow repeated work: Imagine some work A with O(n), done n times, resulting in a total runtime of O(n^2). Can A be reduced to O(log(n)) or O(1)? Maybe with some precomputation or caching?
