I am doing interviews few times a year, and it's probably not enough[1]. Opportunities aside, I learn a valuable lesson every time.
Interview pressure uncovers weaknesses. Mine are overcomplication, impatience and panic:
- I somehow expect the problem to be hard. So, I dismiss valuable cues and intuitions if they look too obvious.
- If I feel a hunch, I dive in without full understanding. I keep stepping on this rake... and solving a wrong problem!
- I the problem sounds intimidating, I panic and freeze, not knowing where to start.
Brute Force
To compensate for these weaknesses, I now start with a simplest solution that comes to mind. I work on a naïve solution first, clarifying my understanding, and then brainstorm ideas to improve it.
Structuring your work this way reduces the cognitive load when you start working on an improved solution.
This is an intuitive and well-recommended technique. However, I feel that candidates are afraid to look inexperienced and skip this step. As an interviewer, you may want to offer your candidate to start easy.
The Game Plan
It helps to mentally structure the interview into phases. The opening is important as it sets the tone, and brute-force can help you get through. Early phases are head-up: collaborate, learn and explore. Late phases are head-down: focus and deliver.
The game plan also helps manage your time and deliver a solution before the interview is over.
The Opening
The entire phase should feel like a fluid conversation with some prototyping. The goal here is to understand and get a feel of the problem. Do not try to ask every question upfront - build it as you go. You will have more questions, and some questions will resolve themselves.
Discuss and implement a brute-force solution. Write some good code, show your skills by following design principles. Make sure your solution is correct, check for edge-cases. Determine runtime and memory complexity. Have a chat, relax.
The Middlegame
As you talk about the complexity, discuss any trade-off and think what the best conceivable runtime is. This narrows down approaches you can try. For example, if you are aiming for O(n log n), you could try the sorting or some other D&C technique. If the problem is about continuous subarrays, the sliding window may help solve it in O(n).
It is important to have a good test case to run your ideas against. Your interviewer could provide just a basic one to explain the problem. This is often done purposely, so go find a good test case - it's essential to spark your intuition!
Now it's time to ask - again - about constraints. Will the input fit in memory? What are possible values of a parameter - can we map it in a vector, or we must use a hash set?
If you got stuck, ask for a hint. This is better than continue digging yourself in. If you pick up the hint and do a good job with your code, it will be a successful interview! Some interviewers would consider it a stronger signal than when you come up with a solution by yourself (maybe you knew the answer?)
I am not suggesting asking when you know the answer; the point here is that you should not be afraid to ask for a hint.
The Endgame
Finalize the approach with your interviewer and carefully implement it. This should be easy as you have everything figured out - just focus on the code and tune out distractions!
Verify your code using the test cases from before. It's important to double-check you work even if you feel confident.
Brainstorm new ideas that came to you during the focus time. Have a chat, smile :)
Codding Practice
The most important advice - keep solving problems! You need to practice various techniques and approaches; this is like a set of tools you can try to crack your next problem!
LeetCode is my favorite destinations for algorithmic problems. It has one thousand problems and counting, with test cases to validate the correctness, as well as computational and memory complexity. There is also a large community discussing different approaches, tips and tricks.
1 The next best thing is online contents (or mock interviews, if you have a programmer friend), which I am trying to take every week. You need to solve 3-4 problems - easy, medium, and hard - within 90 minutes, and write code that passes all test cases and memory/runtime limits.