Gaming CS Interviews

Tips for Kicking Ass at Whiteboard Interviews for Non-CS Peeps Let me start by saying that have started traditional, technical whiteboard interviews, myself included, because they tend to bare little relevance to an employee’s day-to-day development work. Most companies are better off focusing on testing as opposed to algorithmic, computer science questions, and that’s coming from someone who genuinely loves those types of questions. There are exceptions to this, of course, but I believe most engineering jobs today fall into this category. many companies in the tech industry moving away from practical skills and the ability to deliver With that being said, the largest and most esteemed tech companies such as , etc. all still employ very similar technical interview loops that or who prefer to focus on software engineering over the “science” aspect of computer science. Google, Facebook, Amazon, Microsoft tend to greatly favor candidates with standard computer science backgrounds over candidates who are either self-taught Regardless of your views on whether or not this process is fair or optimal, I have a lot of friends who fall into this latter category of being self-taught or software-engineering heavy and scoff at the thought of interviewing with one of these bigger players, even though I know from experience that they would fit in just fine once they made it past the interviews. Given that these are also some of the better, more passionate devs I’ve had the pleasure of working with, I wanted to share some no-bullshit advice I’ve accumulated over the years in the hopes of encouraging other engineers out there to consider advancing their careers by spending time at one or more of the bigger tech companies. I sincerely believe that most developers who are proficient at developing code in their language of choice are capable of passing a Google-style interview loop by adopting the right mindset and studying a few key topics and question archetypes ahead of time. So, with that goal in mind, let’s dive into that whiteboard… Here’s a picture of a generic whiteboard… because it’s on topic and not at all redundant… General Tips When given a programming problem, never start coding right away. Always talk through the problem, by first verifying that your assumptions and thought processes are on the right track. I highly recommend trying to get comfortable verbalizing your thought process at all times but especially when you’re not sure how to proceed. Oftentimes, the interviewer cares more about your thought process than the solution and/or will give you guidance according to your thoughts. Guidance is expected; a great interview should be more of a conversation than a one-sided question and one-sided answer. Generally start out with the most naive, straight-forward approach to a problem you can think of, even if you think it’s really inefficient. Verbalize your thought process in doing so, and either the interviewer will say that‘s great and you can start coding, or you’ll get confirmation that they want to dig deeper into a more optimal solution which generally leads to a conversation about where the most inefficient part of the algorithm is (like the innermost loop) and how you could potentially mitigate its runtime. Always use the programming language you’re most comfortable with; never use a “harder” language because you think it will make you look more legit. At the end of the interview, your assessment will be highly subjective, so keep that in mind and try to have some fun and cold read the interviewer to play off of his or her interests. Almost always asking them early on about what they do at company X will help you understand the type of person they are and also helps to put them in a good mood because people love to talk about themselves. For instance, I recently interviewed with a developer who works on a compiler team at company X which adjusted the way I approached certain parts of the conversation to be more low-level and joke at one point about something all compiler peeps can relate to. If they like you as a person, they’ll be more lenient in their assessment whether they’re aware of it or not; that’s just human nature. Credit: xkcd Interview Topics There are some very common archetypes in algorithmic interviews that tend to account for the vast majority of questions you’ll encounter. If you understand these core question types and can solve some example problems from each of them, you’ll have a much better eye for solving similar problems during a real interview and subsequently solving real problems on the job. Algorithmic Complexity This topic boils down to understanding Even though there are other, more rare measures of complexity (like little-o, theta…) and topics like NP completeness, , as they’re unlikely to appear in a typical technical interview. big-O notation . I would recommend skimming them For almost every problem you’re asked to solve in an interview, you’ll either be asked explicitly about the big-O runtime of a proposed solution or be implicitly expected to bring it up during your discussion. This part can definitely be gamed somewhat by just practicing a bit on a representative set of problems ahead of time. You’ll both get the hang of it and also generally be able to fairly easily say that problem X looks like problem Y so they’re likely to have similar runtimes. I love how they portray algorithms in movies, don’t you? (Credit: , 2014) The Winter Soldier Note that with big-O complexity, it’s most common to think about the problem in terms of , but it can also come into play in terms of storage. For example, a sorting algorithm may take runtime which is pretty common but be able to operate on an array in-place, only requiring storage. Sometimes this can be an important factor when considering between alternative approaches or an interviewer will add that you are memory-bound or something. runtime space O(n log(n)) O(n) I recommend reviewing and understanding the big-O runtime of the most common data structure operations, such as: add / remove / get / find from an array add / remove / find from a linked list add / remove / peek from a stack add / remove / peek from a queue add / remove / get from a hashmap add / remove / get from a balanced binary tree add / remove / get from a (though heaps are less common…) heap You should be intimately familiar with the runtime of each of these operations, since many algorithms will use these as building blocks. It is extremely worth it to not only , but to have a solid understanding of how they are derived. memorize these runtimes This topic can be difficult to grasp under different circumstances for even the most qualified candidates, so don’t worry if you’re able to come up with a solution but have trouble fleshing out its runtime. Also note that this is one of the easiest topics to “game” by practicing on examples ahead of time. Understanding Big-O complexity will affect your ability to answer interview questions on all of the following topics, which is why it is the single most important base topic to focus on before proceeding. One common subtopic I would recommend having a basic familiarity with is big-O, aka big-O, whereby you use some neat probability theory to say that the of an operation is, for instance, even though sometimes it may be for individual calls. The most common examples of amortized / expected big-O in practice are hashmap lookups being amortized and quicksort being amortized . In Javascript, for instance, all object lookups such as or are amortized hashmap lookups (aside from special cases where the compiler is able to optimize these operations under the hood). amortized expected expected value O(1) O(n) O(1) O(n log(n)) myObject.foo window.document O(1) Graphs and Trees Example graph composed of nodes and edges. Graphs are one area where there is a of potential complexity and bullshit to wade through, but at the end of the day, almost all graph-related interview questions are really pretty simple once you understand the basics. and you’re trying to understand something like Djikstras algorithm which is definitely beyond the scope of what most interviews will delve into. lot It can just be overwhelming sometimes when you’re not sure what “the basics” are Terminology A graph is a set of nodes and edges between some of those nodes. Nodes and edges often have payloads like a label or weight associated with them. The most common graph distinction is between undirected vs directed graphs. E.g., when you have an edge between two nodes, is it a directed, one-way street, or is an undirected, two-way street where you can go in both directions when going from node to node. A tree is a very common type of graph with some interesting constraints, so anything you learn about graphs in general also applies to trees like binary search trees and the DOM. Traversing a graph is the process of visiting nodes in a graph, usually starting from a root node and expanding out from there based on each node’s neighbors. recursively The two main algorithms to understand w.r.t. graphs that , visualized briefly below. 95% of graph questions boil down to, are breadth-first-search (BFS), and depth-first-search (DFS) BFS vs DFS visualization (credit: ). https://github.com/kdn251/interviews Advice When working with graphs, it can be especially useful to visualize them by drawing examples on a whiteboard, which is one of the only good uses I can think of for a whiteboard during a generic technical interview... There are lots of different types of graphs and specializations that you may come across during studying, but their distinctions are rarely important for interviews. The (DOM) is an important example of a common graph used by many frontend developers. Document Object Model You should be very comfortable coding BFS and DFS from scratch. Even if the question isn’t directly “code BFS”, lots of questions will indirectly involve you traversing a graph starting from a given node of interest and making sure you’re not visiting nodes multiple times which is exactly what BFS/DFS excel at. Notice how interchangeably I use BFS/DFS; they are very slight variations on each other and most of the time it doesn’t matter if you use BFS or DFS, but you should still understand the difference between the two and be able to draw example traversals on a whiteboard. BFS and DFS can both be implemented iteratively or recursively (any so-called “tail-recursive” function can be rewritten iteratively). The recursive mindset is much more powerful so I’d focus your efforts there first. Most of the time, it’s totally up to you in terms of how you define the graph you’ll be working with. For example, here is a very succinct way of representing a graph by defining a single : Node Node-centric example graph representation. A common distinction with graphs is whether the data structure you use is “node-centric” or “graph-centric”. The previous definition is node-centric because each node is smart and encapsulates information about its adjacent edges. Here’s an alternative graph-centric example, where we also use integers to represent nodes: Node Graph-centric example graph representation. Example question: Given a graph where nodes represent major US cities and edges represent flights between those cities, write a function that takes in two cities and returns a valid flight path between those two cities or null if no such flight path exists. The most direct solution to this problem uses DFS. A harder variant of this type of question would be to find the path if each edge (flight) had a number associated with it that represented distance, which is where Djikstra’s algorithm would come into play. shortest Graph visualization of flights between major US cities (credit: ). databricks Sorting Sorting numbers, strings, etc. is a very common sub-problem in solving many interview questions. It won’t be common for an interviewer to ask you to write mergesort or quicksort or any other type of sort, but it will be quite common to either have to sort some part of your input as a piece of the puzzle or have the solution very closely resemble a widely-known sorting algorithm. For this reason, it’s useful to and be able to code the most common ones. review Note: please don’t take this algorithm seriously. (Credit: ) Reddit Common Sorting Algorithms ; in particular, its recursive “divide & conquer” approach comes up often. Mergesort O(n log(n)) ; generally considered the most robust, general-purpose sorting algorithm. generally amortized Quicksort O(n log(n)) ; only works on numbers using bit hacks but is significantly more efficient. Radixsort O(n) Radix sort is too advanced to implement in any interview that’s not from Hell, so don’t worry about its internals, but it can come in handy knowing that it exists and being able to make use of it. Example question: Given an array of integers, write a function that will remove all duplicates. (be sure to add the obligatory followup, what is its runtime?) The “aha” moment here comes if you realize that by sorting the input, you can just walk along the array with all duplicates being next to each other, resulting in an efficient solution. Strings Review string primitive operations in your preferred language. Eg., for javascript, , , , , , , and very basic regex stuff using . slice substr substring toLowerCase toUpperCase charAt match Luckily, most interview questions focus on ascii. Notes Strings are just arrays of characters, so any algorithms you learn for arrays also applies to strings. A very common type of string problem involves finding all possible substrings of a given input string. Example question: Given a password string of length n as input and a mapping from all 26 lowercase characters to possible alternates (like “e” maps to [ “e”, “E”, “3” ]), implement a function that returns all possible password combinations you could generate of length n. For example, “haxor” could be “Haxor”, “hax0r”, “HAX0r”, etc. Recursion Writing recursive functions should flow like bread & butter and has a lot of overlap with all the other topics listed here. Credit: The Internets Example question: Implement a function that will return the nth number in the fibonacci sequence (1, 1, 2, 3, 5, 8, 13, …). A common follow-up is that the straight-forward solution is typically pretty inefficient, so how could you optimize the recursion? Example question: Given a binary tree, implement a “visitor” pattern function that takes in a node and visits all children. Implement prefix, infix, and postfix traversals. The difference in the traversal order is just moving the order you visit the “current” node around, either before the children, after the left child, or after the right child. Example question: Given a simplified DOM node defined as: _class Node { string className; Array children; }_ , write a function that takes in a _Node_ along with a target css class and returns a list of all subnodes which match that CSS class. Aside from the traversal, which you’ll likely do recursively, the logic to visit each node needs to take into account the fact that DOM nodes can have multiple classnames, so it’s not enough just to do a direct comparison between the target CSS class and a Node’s . className This is exactly what the built-in function does. getElementsByClassName Brainteasers (Abstract Shit) Brainteasers aren’t as common as they used to be, and these types of questions are more common for PMs (project / program managers), but they still come up occasionally in developer interviews as well. They typically involve asking you to solve some impossible or outlandishly difficult problem, epitomizing the mantra that your thought process is more important than the solution you come up with. One of the most famous examples comes from Google back in the day asking candidates “How would you move Mt. Fuji?” Advice Realize that the goal isn’t to come up with the best possible solution, but rather a reasonable, viable solution that is backed by reasoning. Ask clarifying questions; “Where are we moving Mt. Fuji to?”, “What resources do we have to accomplish the task?”, etc. One common subset of brainteasers is to ask “How many X exist?” such as “How many gas stations are there in the US?” The goal here is to be able to guesstimate some numbers that give an idea of the order of magnitude of the response, so if we estimate that there are 10 gas stations per town and 2000 towns per state and 50 states, … which should be more than enough to get the ball rolling. Less Common Topics These topics aren’t as common as the core algorithm and data structure topics above, but depending on the position you’re applying for, it’s still a good idea to understand the high-level categories and be able to recognize a certain type of question when you encounter it. Concurrency Databases More generic data structures Dynamic programming Architecture And sooooo many more… Where To Go From Here? The purpose of this post is to serve as a jumping off point to focus your interview prep on a few, core topics. Once you’re ready to dive into more detail, here are some great resources that’ll help you flesh out a better understanding of these core concepts with a focus on practical interview training. is one of the most starred repos on Github and for good reason. It aggregates articles, classes, videos, and other learning resources across a large number of topics relevant to CS interviews. My only word of warning is that it is pretty overwhelming and covers a lot more areas than are really necessary for standard technical interviews. Nonetheless, this is the first place I would recommend going to learn or review any of the topics I’ve outlined in this post. Coding Interview University is an amazing, well-organized resource which covers a lot of useful high-level techniques as well as specific examples. I would thoroughly recommend checking it out. Hired in Tech The is a great resource that, in addition to covering a lot of CS material itself, also gives more practical tips for what to expect and how to approach technical interview loops. Tech Interview Handbook Once you’re comfortable with the core CS concepts I’ve outlined here, I’d recommend spending most of your prep time practicing online coding problems. Just remember while practicing to consider how you’d verbalize your thought process in a real interview setting and remember to consider things like big-O in addition to solving the problems themselves. Here are some of my favorite resources for finding quality practice interview questions: — Lists a large number of interactive practice questions, many of which come with solutions and explanations. Interactive Coding Challenges — Great list of interview questions previously used by Google provided by Interview Cake. Google Interview Questions — Their section on coding exercises / challenges is a great meta-list of additional resources to find practice questions. Coding Interview University Finally, the best way to get more comfortable with interviewing is by actually interviewing. I know this sounds obvious, but one concrete piece of advice I can give is to apply anywhere and everywhere, even to companies you wouldn’t necessarily consider working for, with the tacit goal of gaining valuable experience in real-world interviews and the added benefit of possibly finding opportunities you didn’t know existed beforehand. For example, if you’re interested in working for Google / Facebook / Twitter / etc, but you wouldn’t be too keen on working for Oracle & IBM (strictly for example purposes…), I’d encourage you to still apply to them in order to gain practical experience and get more comfortable with interviewing. This is the absolute best way I know of to hone your skills in real-world settings that are going to be fairly comparable to interview loops at the more prestigious tech companies. I hope you’ve enjoyed this article! If you found it useful, please clap / like / share it accordingly 😃