Algorithms & Data Structures Cheat Sheet

Part I: Algorithms & Data Structures

This topic may span semesters worth of study for undergraduate software engineering or computer science majors. Without prior exposure, I’d recommend watching the lecture videos for MIT 6.0001 and MIT.6.006. It’s not unreasonable to absorb the content of each class in only a few weeks. Algorithms research will always remain a topic of current interest in research, but we don’t need to dive into the darkest depths of the field to have a solid grip on what we’ll need to know to have successful careers as developers.

Deep knowledge of data structures and algorithms may be used rarely, if ever, in a career as a developer. In practice, using a proven solution is often preferable to authoring our own. But for the purposes of an interview, new programmers typically aren’t expected to know the nuances of specific languages, tools, or technologies, so these topics offer a good source of puzzles and brain teasers that candidates can prepare for. Beyond the interview, the concepts covered in this post form the foundation of a vocabulary shared by many developers.

We’ll explore some of the topics listed below (derived from typical CS curricula), but not all are required for all dev careers. Having prior background in the first half of this list will be of assistance for the remainder of this post:

• Set theory (including N0, N1, Z, Q, R, C, cardinality)
• Functions, functionals
• Combinatorics, counting probabilities, probability distributions
• Recursion (and how it relates to proof by logical induction)
• Logic, K-maps
• Graph theory
• Complexity (Theta, O, Omega)
• Linear algebra, ODEs
• Matrix / tensor calculus
• Optimization
• Design of experiments (full / fractional factorial, Latin hypercube)
• Select topics from information theory
• Stats and stochastic processes, Markov chains
• Orthogonal functions, encoding / decoding, PDEs

Review content follows.

Part II: Algorithms & Data Structures For Technical Interviews

While Part I covered a broad-brush of the vocabulary relevant to conversational fluency in these topics, the application of these ideas to the interview process and beyond has not yet been addressed.

Interview questions on these topics most frequently arise in the context of a programming language. As such, the implementation will depend heavily on our language of choice. In all cases, the builtin tools we use will have time and memory complexity aspects we should be aware of. Most interview questions will be posed in terms of a highly specific problem (e.g. invert a string, rotate a matrix in-place, etc.), so we’ll need to decide which abstract concepts apply. It’s worth grinding through practice problems in advance, but memorizing all the answers is both impractical and insufficient for the needs of the interviewer. Remember that these questions can be made arbitrarily easy or difficult on the fly — most interviewers are looking to examine our thought processes, so we need to keep an open dialogue and say what’s on our mind. Solving the problem is important, but working with the interviewer to analyze it from multiple angles is equally important. It’s inappropriate to flounder on an implementation of a specific algorithm or data structure of our choosing (once we name an intended solution), but it will always be appropriate to work closely with the interviewer to fully understand the problem.

There are a several interview-appropriate problems that are so famous they have a name. Occasionally you’ll hear of interviewers who present these famous problem statements without naming them. While I’d speculate this is uncommon (I haven’t personally experienced it at least), if it happens to us we should be mindful that it’s our job to call them out by name (and ideally know some properties of optimal solutions). Some of the more popular problems include:

• the Traveling Salesman Problem (TSP)
• the Towers of Hanoi
• the N-Queens Problem
• the M-Coloring Problem
• the Knapsack Problem
• the Fractional Knapsack Problem

The infamous problems listed above are far less common than some of the standard fare used to demonstrate comfort and fluency with a programming language itself. While only tangentially related to the above discussion on algorithms & data structures, it is always a good idea to practice language-agnostic interview questions like the ones listed here.

If you’re interested in truly putting the topics we’ve covered into action, an excellent categorized pool of more difficult algorithm & data structures questions are listed here.