Programming interviews - strategy sheet

From NoskeWiki
Jump to navigation Jump to search


This page is a child of: Programming and Programming interviews

Below is a programming strategy cheat sheet I developed in 2012 that helped me land a job at Google because I wrote it on a piece of cardboard and used it to great success in 2 phone coding interviews + 5 onsite coding interviews. I ended up working for Google for 11 years, so I haven't personally use the sheet a tonne, but whenever I interviewed candidates at Google on the phone, and I thought they had potential, I sent them to my programming interviews wiki page so they could use this sheet in future interviews to maximize their chances of landing a great job. Many of them used and loved it. You'd be shocked how many candidates forget simple things like calling out Big O notation before or even after coding their solution. So here's my printable cheat sheet:

The "DAIT" Programming Challenge Strategy Cheat Sheet

    • draw example (i/o)
    • assumptions
      • data types / limits / range / edge cases
    • brainstorm:
      • strategies: ...... bitwise, recursive, flip, swap, pointers, two-pointer, dynamic
      • search: ......... binary (low/high), nested loop (look ahead), reverse (look behind)
      • data structs: ... hash, stack/queue, heap, tree, graph, suffix arr, bit vector, list
      • sorts: ........... insertion, merge, m quicksort, heap, bucket
    • time/space (O(n))
    • code / explain
  • TEST
    • examples
    • edge cases

How to Use It

I would suggest practicing a few real questions with this sheet. It looks unassuming enough, but it makes a huge difference. The way it works is you write out a copy on paper and bring it to the interview... and rather than try to rush ahead and solve the problem, you take a breath and strategically talk through each bullet point. Here's an example of what that look like:

  • Define Problem:
    • "So first up let me draw up a small new input/output example to check I understand the question".
    • "Before I start, I'd like to cover assumptions - can the numbers be negative, decimal or null. What are the size limits of the input (a terabytes long string?). What are my memory constraints (do I have to solve in-place instead of creating a new string/array)? Should I error check input, should I test for edge cases, etc".
  • Brainstorm:
    • "Okay, so I can imagine a solution already that iterates backward... that would take O(n log n) time and requires O(n) extra space, but let me look at this list of data structures to see if I can think up something faster".
  • Coding:
    • "Okay, so I've written some basic pseudo-code, I'd like to start writing code.".
  • Test:
    • "I think that solution works, but if there's time would you like me to write and run through some test cases and edge cases?".

If you say some of these things you are already miles ahead of most of the many people I've interviewed! Even if you don't fully solve the problem, at least you showed logical thinking, and whenever you get stumped you can look at the brainstorming section and think about what data structures and search/sorting strategies might help. The most common, obvious piece of advice is to keep talking through your thought process as this is how your interviewer learns about how you think on your feet. Maybe it feels silly at first, but whenever I've had a "silent candidate" I quickly get bored and it feels awkward. Practice thinking out loud as you go through practice interview questions. You can actually make the interviewer relax into comfort and excitement if you already described the solution and big O notation, and are now just turning it into code.

While this strategy cheatsheet is designed for programming interviews, it can also be really useful to use whenever you are lucky enough to have a fun/novel programming challenge emerge in your workplace or studies. In case you haven't realized this already, my sheet is based on the waterfall model of software development (analysis, design, implementation, testing, evaluation). Sadly, that is where it falls apart.

Where it Falls Apart: Agile Development

In 2023 I left Google and started looking for a new job, the first exciting company I interviewed with gave me my first-ever Agile-inspired Pair Programming and Test-First interviews. My mind was blown. In these interviews, the interviewer wrote the code and I gave directions on what to type as we chatted through the problem together. If it was just a pair programming interview my sheet may still have worked, but testing first is a strategy where you start with a simple (possibly "empty") test case in one file and you write *just enough code to make your next pass* then add another test, and read another requirement. Crazy! Instead of looking for a holistic solution you read one or two requirements at a time and build up. The genius is that it simulates the real world better, and usually ends up with better-tested and more robust code - albeit at the cost of coding speed. Pair programming is also fantastic to ensure you are not the only developer who can understand the code, and with an extra pair of eyes, you are more likely to learn new approaches, dream up creative solutions, avoid mistakes, and write better documentation. Since it was my first time, and because I was unpracticed with telling people "so copy lines 5-9 below row 13" or "could we add some comments for each test case I'm imagining and then fill them in one at a time", I felt like I could have been better. In particular, I didn't necessarily say all the right things and ask all the right questions to set myself up for success. So learn from my mistakes! If you encounter these styles of interviews, here's the type of questions I suggest you ask:

Suggestions for Iterative Test-First Interviews

In an interview where you can only see part of the problem at a time, or must code tests first, it's imperative you practice test-writing beforehand - it's a specific skill and you might want to set up an easy testing template (like these python test libraries) with one or two files beforehand.

At the start:

  • Before we start, is the main focus of this interview to show good testing and logic, solve the whole solution within the time limits or 50/50 of each?
  • Instead of writing out every possibly useful test case, which can be slow, is it appropriate for me to write code comments of all the tests I would ideally want and then populate only the most valuable of those as we go? (not necessarily every case)
  • Since testing is pretty boilerplate, do you mind if we copy and paste in a simple hello-world test example to start?

Early stages:

  • After each test I write, should I write the minimum code to solve it - even if it's just returning a hardcoded answer - or should I be brainstorming, explaining, and coding my vision for a full solution at each step?
  • I didn't quite catch a full input and output example, can we come up with one that looks nice, or

Mid stages:

  • I just realized my test case input is hard to read, do you mind if I spend 5 minutes refactoring so that all our test cases are easier to read and understand?
  • So to satisfy this new requirement, will take quite a bit of refactoring, should I take some kind of snapshot of where the solution is now?

If stumped:

  • I'm a bit stuck in this part, do you mind if I pull out my programming strategy sheet and we work through it together to brainstorm a solution?
  • I'm actually a little nervous right now, but I'm still excited to solve the problem, can you suggest where I should move next with the testing and solutions?

At the end:

  • This interactive programming approach is new for me, if you have time I'd love feedback on areas I could improve on!

Suggestions for Pair Programming Interviews

In many interviews, the interviewer might *intervene* and offer suggestions, but in this scenario, the interviewer is the one typing the code and you are seeing how well you work with them! Here are some questions you might want to ask:

At the start:

  • Before we begin, I'm new to this type of interview, can you explain what a successful pair-programming interview looks like to you?
  • In an ideal interview, what fraction of talking do you think should each of us be doing?
    • To elaborate: I know pair programming is supposed to be interactive but this is also a code interview, so I'm just wondering, in an ideal interview should it be more like 90 percent talking and instruction on my side, or should it be more towards a 50/50.

During the interview:'

  • This is tricky to visualize in my head: is it okay if I use a pen and paper to show you on VC to help figure it out?

If stumped:

  • I'm a bit stuck in this part, do you mind if I pull out my programming strategy sheet and we work through it together to brainstorm a solution?
  • I'm actually a little nervous right now, but I'm still excited to solve the problem, can you suggest where I should move next with this problem?

At the end:

  • Since pair-programming is not the norm I'd appreciate any feedback on where I might have gone wrong or areas I should revisit.

There may actually be many different setups for pair programming, but thinking of the right questions to set you up for success beforehand is critical.

Suggestions For When You Get Stumped

The best interview questions are the ones that have you stumped. If it's a pattern you have already come accross and you figure it out immediately, then the interviewer doesn't learn that much about you, versus them seeing how you handle it when you don't immediately know a solution. So most importantly:

  • Don't panic.
  • Breath.
  • Break the problem down into easier parts.
  • Go back to the cheat sheet.

While you are doing that, obviously you want to keep talking. Here's some smart things you can say when you get stumped:

  1. Clarify the Problem: Before you dive into a solution, ensure you understand the problem.
    • "Let me make sure I understand the requirements correctly. Are you asking...?"
  2. Discuss Similar Problems: Talking about a related problem or concept can showcase your experience and potentially help you approach the solution from a different angle.
    • "This reminds me of [X problem] which had a similar challenge. I tackled it by..."
  3. Break it Down: Dissect the problem into smaller parts.
    • "I may not know the entire solution immediately, but I can start by addressing this specific part..."
  4. Honesty: It's okay to admit when you don't know something immediately.
    • "I haven't encountered this exact scenario before, but I'm eager to work through it."
    • "I feel like (X technique) isn't a strength of mine, but I will try to come up with some ideas."
    • "I honestly feel a little nervous right now, but I will push past that."
  5. Ask for Hints: If the interview format permits, it's alright to ask for a slight hint.
    • "I'm a bit stuck on this part. Would you mind giving me a hint to nudge me in the right direction?"
  6. Think Aloud: As mentioned before, you should always describe your thought process. This can provide insights into your problem-solving methodology.
    • "Here's what I'm thinking right now..."
  7. State Assumptions: If you're unsure about certain aspects, it's okay to make assumptions, but voice them.
    • "I'm going to assume [X] for now. If that's not the case, please correct me."
  8. Consider Edge Cases and Optimization: If you have a brute force solution but not an optimal one, share it and then discuss potential ways to optimize it.
    • "One way to approach this could be [brute force method], but I recognize that's not efficient. I'm thinking of ways to improve that..."
  9. Feedback: If you're unable to find a solution, ask for feedback afterward.
    • "I'm struggling with this problem at the moment, but I'd appreciate any feedback on where I might have gone wrong or areas I should revisit."
  10. Lifelong Learning: Highlight your willingness to learn.
    • "This has been a great learning experience. I'll certainly be researching more on this topic after our discussion."

See Also

Fun Afterthought: The only other interview I had taken was before Google was for Amazon (in 2012), which I didn't do as well, because I didn't have the sheet and was also a bit out of practice with certain data structures like Tries and Suffix Arrays. One of the best assessts of any engineer is taking time to reflect: "what have I learned", "where could I have improved", and "is there a template I could use to solve challenges like this in the future". For inspiration watch: "Beat Any Escape Room - 10 proven tricks and tips".