Programming Interviews

This article is meant for people looking for software positions in the robotics industry. It introduces the data structure, algorithms, and other related topics you need to know in order to prepare for your technical interview. It also provides a detailed instruction on how to crack your coding sessions.

Google tips

This is a list of Google’s tips to use when preparing for a job interview for a coding position.

Algorithm Complexity

• Please review complex algorithms, including “Big O” notation.

Sorting

• Know how to sort. Don’t do bubble-sort.
• You should know the details of at least one n*log(n) sorting algorithm, preferably two (say, quicksort and merge sort). Merge sort can be highly useful in situations where quicksort is impractical, so take a look at it.

Hash Tables

• Be prepared to explain how they work, and be able to implement one using only arrays in your favorite language, in about the space of one interview.

Trees and Graphs

• Study up on trees: tree construction, traversal, and manipulation algorithms. You should be familiar with binary trees, n-ary trees, and trie-trees at the very least. You should be familiar with at least one flavor of balanced binary tree, whether it’s a red/black tree, a splay tree or an AVL tree, and you should know how it’s implemented.
• More generally, there are three basic ways to represent a graph in memory (objects and pointers, matrix, and adjacency list), and you should familiarize yourself with each representation and its pros and cons.
• Tree traversal algorithms: BFS and DFS, and know the difference between inorder, postorder and preorder traversal (for trees). You should know their computational complexity, their tradeoffs, and how to implement them in real code.
• If you get a chance, study up on fancier algorithms, such as Dijkstra and A* (for graphs).

Other data structures:

• You should study up on as many other data structures and algorithms as possible. You should especially know about the most famous classes of NP-complete problems, such as traveling salesman and the knapsack problem, and be able to recognize them when an interviewer asks you them in disguise.

Operating Systems, Systems Programming and Concurrency:

• Know about processes, threads, and concurrency issues. Know about locks, mutexes, semaphores, and monitors (and how they work). Know about deadlock and livelock and how to avoid them.
• Know what resources a processes needs, a thread needs, how context switching works, and how it’s initiated by the operating system and underlying hardware.
• Know a little about scheduling. The world is rapidly moving towards multi-core, so know the fundamentals of “modern” concurrency constructs.

Coding

• You should know at least one programming language really well, preferably C/C++, Java, Python, Go, or Javascript. (Or C# since it’s similar to Java.)
• You will be expected to write code in your interviews and you will be expected to know a fair amount of detail about your favorite programming language.

Recursion and Induction

• You should be able to solve a problem recursively, and know how to use and repurpose common recursive algorithms to solve new problems.
• Conversely, you should be able to take a given algorithm and prove inductively that it will do what you claim it will do.

Data Structure Analysis and Discrete Math

• Some interviewers ask basic discrete math questions. This is more prevalent at Google than at other companies because we are surrounded by counting problems, probability problems, and other Discrete Math 101 situations.
• Spend some time before the interview on the essentials of combinatorics and probability. - You should be familiar with n-choose-k problems and their ilk – the more the better.

System Design

• You should be able to take a big problem, decompose it into its basic subproblems, and talk about the pros and cons of different approaches to solving those subproblems as they relate to the original goal.

Recommended Reading

• Google solves a lot of big problems; here are some explanations of how they solved a few to get your wheels turning.
  • Online Resources:
    • Research at Google: Distributed Systems and Parallel Computing
    • Google File System
    • Google Bigtable
    • Google MapReduce
• Algorithm Recommended Resources:
  • Online Resources:
    • Topcoder - Data Science Tutorials
    • The Stony Brook Algorithm Repository
  • Book Recommendations:
    • Review of Basic Algorithms: Introduction to the Design and Analysis of Algorithms by Anany Levitin
    • Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani
    • Algorithms For Interviews by Adnan Aziz and Amit Prakash,
    • Algorithms Course Materials by Jeff Erickson
    • Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
• Coding Book Recommendation:
  • Programming Interviews Exposed; Secrets to landing your next job by John Monagan and Noah Suojanen

Leetcode Tips

Leetcode must be a familiar platform to you if you are trying to find any software roles. However, there are just too many Leetcode questions and say, given only a month before your first interview, it is difficult to know where to start, even though you might get yourself conceptually familiar with all of the topics above. Therefore, in limtied time, the key to coding practice is inductive learning. Rather than spending a lot of time from the first question to question 200, you should do Leetcode questions topic by topic. The steps can be as follows:

• If you do not have a Leetcode premium subscription, find a reference which maintains a full list of categorized Leetcode questions. A good reference can be found here. Otherwise, with the premium subscription, you can sort the questions of interest by using the “tag” feature.
• Choose a language: if you are mainly looking for roles in machine learning, or deep learning, stick with Python. Otherwise, for software positions in the robotics industry, C++ will be more popular.
• List out topics you want to practice with priority assigned. For software positions in the robotics industry, the most important data stucture would be Graph, Hash Map, Stack, Queue, and Tree, and the most important algorithm you should have a grip of is DFS, BFS, Topological Sort, and some classic Dynamic Programming approaches (listed below). You should be familiar with the runtime complexity of BFS/DFS implemented in either iteration or recursion, as well as the pros and cons of implementation of recursion or iteration. Plus, the idea of DFS is not only applied to graphs, but problems that involve strings are also solved by DFS (e.g. Permutation and Combination).
• Dynamic Programming (DP) is not very popular when compared to the other algorithms in technical interviews for robotics software engineers. Questions asked during interview when DP is the optimal solution are usually tailored for DP. For example, Jump Game (and its other variants too, e.g. Jump Game II) and Climbing Stairs are some classic (as well as popular) problems using 1-dimensional DP. Unique Paths and Dungeon Game are some classic problems using 2-dimensional DP that are encountered very frequently during interviews.
• For each topic in the list: sort the questios by the tag first, then sort by its frequency. Complete top 10~50 frequent questions and move on to the next topic in your list. (Note: premium subscription is required to see a question’s frequency, but you can easily “bypass” this by asking for a screenshot from any of your friends who has premium subscription)
• Create an excel sheet that records every question that you have completed, along with its related topic, runtime & space complexity, and, if possible, its difference compared to its other variants (e.g. Jump Game I to VII, Combination Sum I to IV). This is the cheat sheet you will cram for on the night before the interview.
• Do mock interviews with peers. This will be very helpful if you are the type of person whose mindset will be influenced by the stress, or tension during an interview. Also mock interviews will improve your communication abilities during coding, because an interviewer usually expects you to explain your approach while you are writing up your solution.

Additional resources

• Daily plan for programming interview practice: https://github.com/jwasham/coding-interview-university#the-daily-plan