Cracking the Coding Interview by Gayle Laakmann McDowell

• Getting the easy questions doesn't make it any easier to get the offer. Receiving an offer is not about solving questions flawlessly (very few candidates do!). Rather, it is about answering questions better than other candidates.
• Academic books prepare you for fancy research, and they will probably make you a better software engineer, but they're not sufficient for interviews.
• From the company's perspective, it's actually acceptable that some good candidates are rejected. The company is out to build a great set of employees. They can accept that they miss out on some good people.
• If you're able to work through several hard problems, you're probably pretty good at developing optimal algorithms. You're smart. Smart people tend to do good things, and that's valuable at a company. It's not the only thing that matters, of course, but it is a really good thing.
• Whiteboards tend to encourage candidates to speak more an explain their thought process. When a candidate is given a computer, their communication drops substantially.
• Interviewers asses you relative to other candidates on that same question by the same interviewer. It's a relative comparison.
• If you have waited more than a week, you should follow up with your recruiter. If your recruiter does not respond, this does not mean that you are rejected (at least not at any major tech company, and almost any other company). Let me repeat that again: not responding indicates nothing about your status. The intention is that all recruiters should tell candidates once a final decision is made. Delays can and do happen.
• If your recruiter isn't very responsive, it's because she's busy, not because you're being silently rejected.
• The number one ting that SDETs get rejected for is coding skills. Although coding standards are typically lower for an SDET than for a traditional developer, SDEs are still expected to be very strong in coding and algorithms.
• Strong communication skills can also be very important for testers, since your job requires you to work with so many different people.
• Never let your coding skills atrophy.
• PMs need to be able to communicate with people at all levels in the company, across many positions and ranges of technical skills. Your interviewer will want to see that you possess this flexibility in your communication.
• Happy employees are productive employees, so a company wants to make sure that you'll enjoy the job and be excited about your work.
• Strong coding skills are almost always required for dev lead positions and often for management positions as well. If you'll be coding on the job, make sure to be very strong with coding and algorithms--just like a dev would be.
• Anyone in a management-like role needs to be able to both lead and work with people.
• Prioritization means asking the right questions to understand what is critical and what you can reasonably expect to accomplish.
• Perhaps the most important thing that a manager can do is be a person who "gets things done". This means striking the right balance between preparing for a project and actually implementing it. You need to understand how to structure a project and how to motivate people so you can accomplish the team's goals.
• Startups tend to want engineers who are not only smart and who can code, but also people who would work well in an entrepreneurial environment. Your resume should ideally show initiative.
• Being able to "hit the ground running" is also very important; they [startups] want people who already know the language of the company.
• These [knowledge transfer positions] are temporary positions with the expectation that the employee leaves at the termination of the contract, although sometimes the employee ends up being retained.
• The big companies tend to take a risk-averse approach to hiring. If someone is on the fence, they often lean towards a no-hire.
• If your interview question expects obscure knowledge, ask yourself: is this truly an important skill? Is it so important that I would like to either reduce the number of candidates I hire or reduce the amount to which I focus on problem-solving or other skills?
• Every new skill or attribute you evaluate shrinks the number of offers extended, unless you counter-balance this by relaxing the requirements for a different skill.
• You want candidates to feel good about the experience, about you, and about their performance. You want them to feel comfortable. A candidate who is nervous will perform poorly, and it doesn't mean that they aren't good. Moreover, a good candidate who has a negative reaction to you or to the company is less likely to accept an offer--and they might dissuade their friends from interviewing/accepting as well.
• No matter how poorly a candidate is doing, there is always something they got right. Find a way to infuse some positivity into the interview.
• At a very, very high level, there are four modes of questions:
• Sanity Check: These are often easy problem-solving or design questions. They assess a minimum degree of competence in problem-solving. They won't distinguish between "okay" versus "great", so don't evaluate them as such.
• Quality Check: These are the more challenging questions, often in problem-solving or design. They are designed to be rigorous and really make a candidate think. Use these when algorithmic/problem-solving skills are of high importance.
• Specialist Questions: These questions test knowledge of specific topics, such as Java or machine learning. They should be used for skills a good engineer couldn't quickly learn on the Job. These questions need to be appropriate for true specialists.
• Proxy Knowledge: This is knowledge that is not quite at the specialist level, but that you would expect a candidate at their level to know.
• When companies get into trouble is when they mix and match these:
• They ask specialist questions to people who aren't specialists.
• They hire for specialist roles when they don't need specialists.
• They need specialists but are only assessing pretty basic skills.
• They are asking sanity check (easy) questions, but think they're asking quality check questions.
• Without a great resume, there's no interview. And without great experience, there's no great resume. Therefore, the first step in landing an interview is getting great experience. The further in advance you can think about this the better.
• Few things are as impressive to an interviewer as a candidate who built something "just for fun".
• All of these boil down to the two big things that companies want to see: that you're smart and that you can code. If you can prove that, you can land your interview.
• Resume screeners look for the same things that interviewers do. They want to know that you're smart and that you can code.
•  In the US, it is strongly advised to keep a resume to one page if you have less than ten years of experience. More experienced candidates can often justify 1.5-2 pages otherwise.
• Your resume does not--and should not--include a full history of every role you've ever had. Include only the relevant positions--the ones that make you a more impressive candidate.
• For each role, try to discuss your accomplishments with the following approach: "Accomplished X by implementing Y which led to Z".
• Developing the projects section on your resume is often the best way to present yourself as more experienced.
• Be conservative about what software you list, and understand what's appropriate for the company.
• Listing everything you've ever worked with is dangerous. Many interviewers consider anything on your resume to be "fair game" as far as the interview.
• One alternative is to list most of the languages you've used, but add your experience level.
• Behavioral questions are asked to get to know your personality, to understand your resume more deeply, and just to ease you into an interview.
• When asked about your weaknesses, give a real weakness! A good answer conveys a real, legitimate weakness but emphasizes how you worked to overcome it.
• Most interviewers will give you a chance to ask them questions. The quality of your questions will be a factor, whether subconsciously or consciously, in their decisions. Walk into the interview with some questions in mind.
• Arrogance is a red flag, but you still want to make yourself sound impressive. So how do you make yourself sound good without being arrogant? By being specific! Specificity means giving just the facts and letting the interviewer derive an interpretation.
• Big O time is the language and metric we use to describe the efficiency of algorithms. Not understanding it thoroughly can really hurt you in developing an algorithm.
• Time is not the only ting that matters in an algorithm. We might also care about the amount of memory--or space--required by an algorithm.
• An ArrayList, or a dynamically resizing array, allows you to have the benefits of an array while offering flexibility in size. You won't run out of space in the ArrayList since its capacity will grow as you insert elements. An ArrayList is implemented with an array. When the array hits capacity, the ArrayList class will create a new array with double the capacity and copy all the elements over to the new array.
• You're usually only expected to know the basics. Here's a list of the absolute, must have knowledge:
• Data Structures
• Linked Lists
• Trees, Tries, & Graphs
• Stacks & Queues
• Heaps
• Vectors/ArrayLists
• Hash Tables
• Algorithms
• Breadth-First Search
• Depth-First Search
• Binary Search
• Merge Sort
• Quick Sort
• Concepts
• Bit Manipulation
• Memory (Stack vs Heap)
• Recursion
• Dynamic Programming
• Big O Time & Space
• In particular, hash tables are an extremely important topic. Make sure you are very comfortable with this data structure.
• Get a brute-force solution as soon as possible. Don't worry about developing an efficient algorithm yet. State a naive algorithm and its run-time, then optimize from there. Don't code yet though!
• Walk through your brute force with BUD optimization (Bottlenecks, Unnecessary Work, Duplicated word) or try some of these ideas:
• Look for any unused info.
• Solve it manually on an example, then reverse engineer your thought process.
• Solve it "incorrectly" and then think about why the algorithm fails.
• Make a time vs. space trade off. Hash tables are especially useful!
• Interviews are supposed to be difficult. If you don't get every--or any--answer immediately, that's okay! That's the normal experience, and it's not bad.
• Despite being possibly slow, a brute force algorithm is valuable to discuss. It's a starting point for optimizations, and it helps you wrap your head around the problem.
• This is perhaps the most useful approach I've found for optimizing problems. "BUD" is a silly acronym for:
• Bottlenecks
• Unnecessary Work
• Duplicated Work
• These [BUD] are three of the most common things that an algorithm can "waste" time doing.
• A bottleneck is a part of your algorithm that slows down the overall run-time. There are two common ways this occurs:
• You have one-time work that slows down your algorithm.
• You have a chunk of work that's done repeatedly, like searching.
• Optimizing a bottleneck can make a big difference in your overall run-time.
• This approach [data structure brainstorm] is certainly hacky, but it often works. We can simply run through a list of data structures and try to apply each one. This approach is useful because solving a problem may be trivial once it occurs to us to use, say, a tree.
• Broadly speaking, good code has the following properties:
• Correct: The code should operate correctly on all expected and unexpected inputs.
• Efficient: The code should operate as efficiently as possible in terms of both time and space.
• Simple: If you can do something in 10 lines instead of 100, you should. Code should be as quick as possible for a developer to write.
• Readable: A different developer should be able to read you r code and understand what it does and how it does it. Readable code has comments where necessary, but it implements things in an easily understandable way.
• Maintainable: Code should be reasonable adaptable to changes during the life cycle of a product and should be easy to maintain by other developers, as well as the initial developer.
• Writing modular code means separating isolated chunks of code out into their own methods. This helps keep the code more maintainable, readable, and testable.
• One sign of a careful coder is that she doesn't make assumptions about the input. Instead, she validates that the input is what it should be, either through ASSERT statements or if-statements.
• When you decline an offer, provide a reason that is non-offensive and inarguable.
• Perhaps the biggest mistake that candidates make in evaluating an offer is looking too much at their salary. Candidates often look so much at this number that they wind up accepting the offer that is worse financially. Salary is just one part of your financial compensation.
• Negotiation isn't fun for most of us. But still, the financial benefits of negotiation are usually worth it.
• Do yourself a favor. Negotiate. Here are some tips to get you started:
• Just do it.
• Have a viable alternative.
• Have a specific "Ask".
• Overshoot.
• Think beyond salary.
• Use your best medium.
• It's more important that you attempt to negotiate than that you do it via a specific medium.
• When you're enjoying your job, it's very easy to get wrapped up in it and not realize that your career is not advancing. This is why you should outline your career path before starting a new job.
• By outlining your path in advance and checking in on it regularly, you can avoid falling into this complacency trap.
• It's up to you to pursue the challenges that are right for your career.
• You need to be your best advocated, so that you can achieve goals according to your timeline.
• Set a goal of interviewing at least once a year, even if you aren't actively looking for a new job. This will keep your interview skills fresh, and also keep you in tune with what sorts of opportunities (and salaries) are out there.
• If you get an offer, you don't have to take it. It will still build a connection with that company in case you want to join at a later date.
• A hash table is a data structure that maps keys to values for highly efficient lookup. In this simple implementation, we use an array of linked lists and a hash code function.
• When you need an array-like data structure that offers dynamic resizing, you would usually use an ArrayList. A typical implementation is that when the array is full, the array doubles in size.
• A linked list is a data structure that represents a sequence of nodes. In a singly linked list, each node points to the next node in the linked list. A doubly liked list gives each node pointers to both the next node and the previous node.
• The benefit of a linked list is that you can add and remove items from the beginning of the list in constant time.
• The stack data structure is precisely what it sounds like: a stack of data. In certain types of problems, it can be favorable to store data in a tack rather than in an array.
• A stack uses LIFO (last-in first-out) ordering. That is, as in a stack of dinner plates, the most recent item added to the stack is the first item to be removed.
• Note that a stack can also be implemented using a linked list, if items were added and removed from the same side.
• One case where stacks are often useful is in certain recursive algorithms. Sometimes you need to push temporary data onto a stack as you recurse, but then remove them as you backtrack. A stack offers an intuitive way to do this.
• A stack can also be used to implement a recursive algorithm iteratively.
• A queue implements a FIFO (first-in first-out) ordering. As in a line or queue at a ticket stand, items are removed from the data structure in the same order that they are added.
• One place where queues are often use is in breadth-first search or in implementing a cache.
• A nice way to understand a tree is with a recursive explanation. A tree is a data structure composed of nodes. Each tree has a root node. The root node has zero or more child nodes. Each child node has zero or more child nodes, and so on.
• A binary tree is a tree in which each node has up to two children. Not all trees are binary trees.
• When given a tree question, many candidates assume the interviewer means a binary search tree. Be sure to ask. A binary search tree imposes the condition that, for each node, its left descendants are less than or equal to the current node, which is less than the right descendants.
• Two common types of balanced trees are red-black trees and AVL trees.
• A complete binary tree is a binary tree in which every level of the tree is fully filled, except for perhaps the last level. A full binary tree is a binary tree in which every node has either zero or two children. That is, no nodes have only one child. A perfect binary tree is one that is both full and complete. All leaf nodes will be at the same level, and this level has the maximum number of nodes.
• A min-heap is a complete binary tree (that is, totally filled other than the rightmost elements on the last level) where each node is smaller than its children. The root, therefore, is the minimum element in the tree.
• A trie (sometimes called a prefix tree) is a funny data structure. A trie is a variant of an n-ary tree in which characters are stored at each node. Each path down the tree may represent a word.
• Very commonly, a trie is used to store the entire (English) language for quick prefix look-ups. While a hash table can quickly lookup whether a string is a valid word, it cannot tell us if a string is a prefix of any valid words. A trie can do this very quickly.
• Many problems involving lists of valid words leverage a trie as an optimization.
• A tree is actually a type of graph, but not all graphs are trees. Simply put, a tree is a connected graph without cycles. A graph is simply a collection of nodes with edges between (some of) them.
• Graphs can be either directed or undirected. While directed edges are like a one-way street, undirected edges are like a two-way street.
• The two most common ways to search a graph are depth-first search and breadth-first search.
• Bidirectional search is used to find the shortest path between a source and destination node. It operates by essentially running two simultaneous breadth-first searches, one from each node. When their searches collide, we have found a path.
• You should be comfortable doing bit manipulation by hand, as well as with code. Be careful; it's easy to make little mistakes.
• Computers typically store integers in two's complement representation. A positive number is represented as itself while a negative number is represented as the two's complement of its absolute value (with a 1 in its sign bit to indicate that a negative value). The two's complement of an N-bit number (where N is the number of bits used for the number, excluding the sign bit) is the complement of the number with respect to 2^N.
• As you probably know, every positive integer can be decomposed into a product of primes.
• The Sieve of Eratosthenes is a highly efficient way to generate a list of primes. It works be recognizing that all non-prime numbers are divisible by a prime number.
• Object-oriented design (OOD) questions are often intentionally vague in order to test whether you'll make assumptions or if you'll ask clarifying questions.
• When being asked an object-oriented design question, you should inquire who is going to use it and how they are going to us it. Depending on the question, you may even want to go thr0ught the "six Ws": who, what, where, when, how, why.
• Be careful you don't fall into a trap of constantly trying to find the "right" design pattern for a particular problem. You should create the design that works for that problem.
• The Singleton pattern ensures that a class has only one instance and ensures access to the instance through the application. It can be useful in cases where you have a "global" object with exactly one instance.
• The Factory Method offers an interface for creating an instance of a class, with its subclasses deciding which class to instantiate.
• While there are a large number of recursive problems, many follow similar patterns. A good hint that a problem is recursive is that it can be built off of sub-problems.
• Recursive solutions, by definition, are built off of solutions to sub-problems.
• There are many ways you might divide a problem into sub-problems. Three of the most common approaches to develop an algorithm are bottom-up, top-down, and half-and-half.
• Recursive algorithms can be very space inefficient. Each recursive call adds a new layer to the stack, which means that if your algorithm recurses to a depth of n, it uses at least O(n) memory.
• It's often better to implement a recursive algorithm iteratively. All recursive algorithms can be implemented iteratively, although sometimes the code is more complex.
• Dynamic programming is mostly just a matter of taking a recursive algorithm and finding the overlapping sub-problems (that is, the repeated calls). You then cache those results for future recursive calls.
• A key goal of system design questions is to evaluate your ability to communicate.
• An incorrect assumption can dramatically change the problem.
• You can't design a system if you don't know what you're designing. Scoping the problem is important because you want to ensure that you're building what the interviewer wants and because this might be something that interviewer is specifically evaluating.
• A system can be scaled one of two ways:
• Vertical scaling means increasing the resources of a specific node.
• Horizontal scaling means increasing the number of nodes.
• Vertical scaling is generally easier than horizontal scaling, but it's limited. You can only add so much memory or disk space.
• Typically, some frontend parts of a scalable website will be thrown behind a load balancer. This allows a system to distribute the load evenly so that one server doesn't crash and take down the whole system. To do so, of course, you have to build out a network of cloned servers that all have essentially the same code and access to the same data.
• Denormalization means adding redundant information into a database to speed up reads.
• Sharding means splitting the data across multiple machines while ensuring you have a way of figuring out which data is one which machine.
• An in-memory cache can deliver very raid results. It is a simple key-value pairing and typically sits between your application layer and your data store.
• Slow operations should ideally be done asynchronously. Otherwise, a use might get stuck waiting and waiting for a process to complete.
• Some of the most important metrics around networking include:
• Bandwidth: This is the maximum amount of data that can be transferred in a unit of time.
• Throughput: Whereas bandwidth is the maximum data that can be transferred in a unit of time, throughput is the actual amount of data that is transferred.
• Latency: This is how long it takes data to go from one end to the other.
• MapReduce is often associated with Google, but it's used much more broadly than that. A MapReduce program is typically used to process large amounts of data.
• As it's name suggests, a MapReduce program requires you to write a Map step and a Reduce step. Map takes in some data and emits a pair. Reduce takes a key and a set of associated values and "reduces" them in some way, emitting a new key and value. The results of this might be fed back into the Reduce program for more reducing.
• MapReduce allows us to do a lot of processing in parallel, which makes processing huge amounts of data more scalable.
• Essentially any part of a system can fail. You'll need to plan for many or all of these failures.
• Availability is a function of the percentage of time the system is operational. Reliability is a function of the probability that the system is operational for a certain unit of time.
• Whether an application will do a lot of reads or a lot of writes impacts the design. If it's write-heavy, you could consider queuing up the writes (but think about potential failure here!). If it's read-heavy, you might want to cache.
• Security threats can, of course, be devastating for a system. Think about the types of issues a system might face and design around those.
• Understanding the common sorting and searching algorithms is incredibly valuable, as many sorting and searching problems are tweaks of the well known-algorithms. A good approach is therefore to run through the different sorting algorithms and see if one applies particularly well.
• Radix sort is a sorting algorithm for integers (and some other data types) that takes advantage of the fact that integers have a finite number of bits. In radix sort, we iterate through each digit of the number, grouping numbers by each digit.
• When we think of searching algorithms, we generally think of binary search. Indeed, this is a very useful algorithm to study.
• Testing is an important task for a software engineer, and for this reason, testing questions may come up during your interview.
• Note that software testing has two core aspects to it:
• manual vs automated testing
• black box testing vs white box testing
• In an ideal world, we might love to automate everything, but that's rarely feasible. Some things are simply much better with manual testing because some features are too qualitative for a computer to effectively examine.
• Whereas a computer can generally recognize only issues that it's been told to look for, human observation may reveal new issues that haven't been specifically examine. Both humans and computers form an essential part of the testing process.
• In block box testing, we're just given the software as-is and need to test it. With white box testing, we have additional programmatic access to test individual functions.
• In general, you should think about the following types of test cases:
• The normal case
• The extremes
• Nulls and "illegal" input
• Strange input
• The constructor of a class is automatically called upon an object's creation. If no constructor is defined, the compiler automatically generates one called the Default Constructor. Alternatively, we can define our own constructor.
• The destructor cleans up upon object deletion and is automatically called when an object is destroyed. It cannot take an argument as we don't explicitly call a destructor.
• Operator overloading enables us to apply operators like + to objects that would otherwise not support these operations.
• A pointer holds the address of a variable and can be used to perform any operation that could be directly done on the variable, such as accessing and modifying it.
• Two pointers can equal each other, such that changing one's value also changes the other's value (since they, in fact, point to the same address).
•  Templates are a way of reusing code to apply the same class to different data types.
• Overloading is a term used to describe when two methods have the same name but differ in the type or number of arguments.
• Overriding occurs when a method shares the same name and function signature as anther method in its super class.
• Java's collection framework is incredibly useful. Here are some of the most useful items:
• ArrayList: An ArrayList is a dynamically resizing array, which grows as you insert elements.
• Vector: A vector is very similar to an ArrayList, except that it is synchronized.
• LinkedList: LinkedList is, of course, Java's built-in LinkedList class.
• HashMap: The HashMap collection is widely used, both in interviews and in the real world.
• Normalized databases are designed to minimize redundancy, while denormalized databases are designed to optimize read time.
• We can denormalize the database by storing redundant data. Denormalization is commonly used to create highly scalable systems.
• Threads within a given process share the same memory space, which is both a positive and a negative. It enables threads to share data, which can be valuable. However, it also creates the opportunity for issues when two threads modify a resource at the same time.
• A lock (or monitor) is used to synchronize access to a shared resource by associating the resource with the lock.
• A common use case for locks is when a resource is accessed from multiple places, but should by only accessed by one thread at a time.
• A deadlock is a situation where a thread is waiting for an object lock that another thread holds, and this second thread is waiting for an object lock that the first thread holds. Since each thread is waiting for the other thread to relinquish the lock, they both remain waiting forever. The threads are said to be deadlocked.
• In order for a deadlock to occur, you must have all four of the following conditions met:
• Mutual Exclusion: Only one process can access a resource at a given time.
• Hold and Wait: Processes already holding a resource can request additional resources, without relinquishing their current resources.
• No Preemption: One process cannot forcibly remove another process' resource.
• Circular Wait: Two or more processes form a circular chain where each process is waiting on another resource in the chain.
• The sum of a sequence of powers of two is roughly equal to the next value in the sequence.
• Logs of different bases are only off by a constant factor. For this reason, we largely ignore the base of a log within a Big O expression. It doesn't matter since we drop constants anyway.
• Dijkstra's algorithm is a way to find the shortest path between two points in a weighted directed graph (which might have cycles). All edges must have positive values.
• MapReduce is used widely in system design to process large amounts of data. As its name suggests, a MapReduce program requires you to write a Map step and a Reduce step. The rest is handled by the system.
• The system slits up the data across different machines.
• Each machine starts running the user-provided Map program.
• The Map program takes some data and emits a pair.
• The system-provided Shuffle process reorganizes the data so that all pairs associated with a given key go to the same machine, to be processed by Reduce.
• The user-provided Reduce program takes a key and a set of associated values and "reduces" them in some way, emitting a new key and value. The results of this might be fed back into the Reduce program for more reducing.