Igor Afonov

Posted on Jul 29, 2019

Interview Preparation Notes

#career #computerscience #beginners

Interview Preparation Notes

These are the edited notes that I used during preparing for CS-101-style whiteboard interview (a.k.a Google/FB/Leetcode style interview).

Whiteboard style interviews have a mixed attitude - some people like them; some people hate them. My strategy is pretty straightforward - you can whine about the world being an unfair place, or you can push yourself and learn how to invert that binary tree instead 😉

The benefit for me and the biggest drawback for many people - these interviews seem to 'invalidate' previous experience with particular technologies and test basics. Experience of setting up k8s on OpenBSD doesn't matter much, however understanding of how various tech works under the hood matters a lot. The generic process opens the ability to switch technology stack entirely and try something new without being anchored by a particular experience.

An unexpected thing that I noticed while going through coding interview preparation - I feel that it has made me a better programmer. I started to think faster and code cleaner from the first pass. System design pushed me into learning a bunch of things that I used in practice but never bothered to learn how they work under the hood. The behavioral part involved quite a bit of self-reflection and thinking about past experiences and what I want from my future career (and life).

I broke my notes into a few parts:

A bit about about psychology
Behavioral
Coding
System design
Questions for interviewers
Offer Negotiation

Psychology

I feel that anchoring on getting a job in a particular company and position is flawed. Interviewing is a lottery (for both parties to be fair). Internalizing your goal helps a lot. My goal was to teach myself algorithms, improve my coding skills, and learn the internals of databases and large scale architectures.

There was no goal to get that job at FAANG. Always optimize for learning, and results come as a byproduct.

Behavioural

Behavioral or leadership interview is the most important part of the whole process. Coding and System Design are mostly pass/fail stages, and behavioral interview matter most when the time comes for leveling or offer.

My take away:

Be yourself
Be kind
Do not lie and make up stories (even unconsciously)
Spend time on self-reflection and thinking about the past
Think about the future and what you want from your career

I didn't found STAR and other 'smart' frameworks helpful. Maybe they work if you don't have much experience - if you have stories to tell - you're good to go.

Coding

I prepared for a classic whiteboard style interview. I trained myself to write code on the piece of paper or whiteboard without being able to run or debug the code. I invested time into training myself to write clean and readable code from the first pass.

Communication is a crucial part. You should be able to explain what you're going to do before writing code and surprisingly sometimes it's the hardest part. When I'm doing 'normal' programming, I experiment a lot and sometimes start writing code with the idea that I'll refactor or rewrite it on the go or later. It doesn't work if you have 45 minutes, whiteboard and pair of eyes staring at you.

You have to push yourself into thinking first, explaining your thoughts, and only then starting to write the code.

The thing that helped me with all of these parts is formalizing algorithm for solving algorithmic problems. I think this is a bit personal thing and I suggest trying various approaches yourself before settling in. But after you settle - always push yourself to follow it.

My Algorithm for Solving an Algorithmic problem

All these steps are essential, and even if I feel that I can skip one - I always push myself and avoid doing that.

There were a handful of situations when I skipped step only to realize a few steps later into solving the problem that I was wrong and need to go back and start from the skipped step.

Repeat the question in your own words and confirm that you understood it correctly
Build 2-3 regular flow examples - write them
Outline corner cases and ask the interviewer what's expected (and feel free to make it up yourself but mention to the interviewer)
Outline approach and think loudly about its time and space complexity
- If you can't come up with approach try to solve the problem by hand
Confirm with the interviewer (or yourself) that approach is a good starting point. Repeat previous steps if not.
Very slowly write code
Debug manually by using your examples. If you can execute the code - use your examples as unit tests
Optimize (In 80% of situations stick Hash/Set to simplify the algorithm and trade time for space 😉)
Repeat

If all goes right - you're good, if you can't figure out the solution - push yourself. Carefully listen for direct and indirect hints. Do not give up.

Mock inteviews

Mock interviews help with anxiety management, timing, and communication. I used interviewing.io and got a few practice interviews there. You can use friends or hire somebody to do it.

You can also try to interview in companies that you're less interested in. I don't feel bad about it. The company interviews you, and in return, it's getting a chance to hire you.

The Book

I've read Cracking the Coding Interview, but I didn't like it. It's bad. It's too simple, high-level, it's writing is weird and creates a false feeling of this thing being easy. It's not.

I recommend getting good CS 101 or classic algorithms textbook, read it, and spend some time coding basic stuff.

The book that worked for me is Jeff Erickson - Algorithms. It's excellent - it's concise, it uses pseudocode for explaining the coding parts, and it's easy to read (it's for students at the end of the day).

Skienna's The Algorithm Design Manual is excellent too, but it's a bit harder to read, and you'll probably need to pick certain relevant parts yourself. It can work great if you have plenty of time.

The Basics - My Favourites

These are my favorite fundamental problems. They are building blocks for harder problems, so it makes sense to make sure that you can consciously, with full understanding, code them as fast as you can write on a board or type on a laptop.

My usual routine was solving 2-3 of those as a warm-up before doing something more sophisticated.

A lot of these problems are used during screens/actual interviews.

Array: Binary search, Search Insert Position, 2Sum, 3Sum, Non-decreasing Array, First Bad Version, Maximum Subarray, Subarray Sum Equals K, Rotate Array, Search in Rotated Array, Remove Duplicates from Sorted Array
Matrix: Rotate Image
String: Palindrome, Anagram, K-Palindrome, Sliding Window, Balanced Parenthesis
Graph*: DFS, BFS, Dijkstra
Tree: DFS, BFS, LCA, Level Order Traversal, Binary Tree Maximum Path Sum, Sum From Root to Leaf, Convert Tree To Linked List, Serialize/Deserialize Tree
Linked List: Reverse, Find Middle Element, Remove Element
Heap: Build one yourself and understand how it works, Kth Largest Element in Array
Combinatorics: Permutations, Subsets
Dynamic Programming**: Coin change, Generate Parentheses, Increasing subsequence, Buy and Sell Stock
Misc: Binary addition, Meeting rooms

* The hardest part with graph problems is seeing that it's a graph problem. If you see that it's a graph problem, you're 90% done

** Dynamic programming problems make the worst interview questions. They are useless. You're either know the trick or don't. There is little chance somebody can come up with an optimal solution under interview pressure. However, basic understanding helps a lot.

Misc

Buy an actual whiteboard and ultra-fine marker to have 4k resolution.
Look into it as a sport - do practice often. Rest when you need. You can call it competitive interviewing.

System design

The best advice is to find a way to get experience designing systems in real life.

I cheated here - I worked as DevOps for a significant part of my career and have a pretty good understanding of how to build web applications infra. Still, I needed time to systematize knowledge and build my approach. Again communication is the most critical part. If you can't explain your approach - it doesn't matter whether it's right or wrong.

I recommend avoiding mentioning particular technologies if you didn't use them in practice and use generic tools instead. So if you need distributed queue and you never used one - name component "distributed queue" don't dig yourself into details.

My Approach

Understand the goal of the system. Repeat it in your own words
Ask good questions. Define MVP. Think about features and requirements
Establish the scope of the system
Figure out what parts are interesting to interviewer
Make up numbers and drive requirements yourself
Start at the very very high level
Dig deeper and refine
Repeat
Keep going until time is up

My Favorites

These are my favorite problems. I learned a lot while practicing them and doing research.

Atomic counter
Rate Limiter
Distributed Queue
Video upload/serving infrastructure
Full-text search
Real-time messaging (with or without persistence)
Distributed log collector
Your favorite social network
Your favorite search engine

Practice on paper or whiteboard.

Reading and links

The holy grail - Designing Data-Intensive Applications, the book is outstanding. I recommend reading it even you are not preparing for an interview or you're not going to work with data. This is one of the best technical books from recent times.

Surprisingly I found really useful reading through Redis documentation. It's easy to read it, it has a lot of examples and reads more like a book on general storage systems than documentation for DB.

Questions for interviewers

I think these questions part during the interview is useless for both parties. The best time to ask questions is between the offer is made, and the offer is accepted. If you've been made an offer, you can always ask for 30-45 minutes with one of the interviewers and do a "reverse interview" - have a meeting fully devoted to asking questions about the company. Prepare for this meeting and listen very carefully, pay attention to small details - at the end you're at the sales pitch.

As for customary 5 minutes (in the best case) prepare 1 set of generic, but smart, questions and ask them to fill the time.

Offer Negotiation

Have a good alternative (a.k.a BATNA - Best alternative to a negotiated agreement). The best and a bit counter-intuitive alternative is to do great and be happy at your current job.