Cracking the Tech Career: Insider Advice on Landing a Job at Google, Microsoft, Apple, or any Top Tech Company
By coding on a whiteboard, you're encouraged to have a conversation with your interviewer. This helps the interviewer understand how you're thinking.
Coding on a whiteboard encourages you to focus on the meat of the algorithm and code, rather than getting caught up in the details.
For example, on a computer, a candidate is likely to spend time getting the exact syntax for a sort method correct. This isn't the type of stuff interviewers care about.
Because you're not worried about making all the little pieces work correctly, you can actually write more complex code. Need a helper function to find the smallest value in an array? No problem. Just pretend you have one.
Coding on a whiteboard tests how well you reason about how code works.
Do you just verify that your code works by running it? Or do you actually think conceptually about how it works?
Whiteboard coding encourages you to write good, clean code from the beginning, because it's so much slower. When you have a computer, you can be a bit sloppier and clean it up later.
What's Expected—And What's Not
Do what you can to demonstrate that you care about clean, beautiful code.
Wrap your code in a method declaration; loose code looks sloppy and can be confusing. You generally do not need to write the class definition, unless it's particularly relevant to the problem at hand.
Modularize your code. This shows an eye for maintainability.
If you notice parts of your code that you can refactor or clean up afterward, just go ahead and make the changes. You want to demonstrate that you are the kind of person who cares about the beauty of code.
Google tends to emphasize questions on scalability more than other companies (for instance, “Design a web crawler”). Questions on bit manipulation are also quite common.
Amazon loves object-oriented design questions. If you're going to interview at Amazon, make sure you study these problems. And, since Amazon is a web-based company, you'll also want to prepare for scalability questions.
Yahoo has historically emphasized more terminology and knowledge-based questions, but has begun to transition more to typical algorithm and problem-solving questions.
Implement the common data structures and algorithms from scratch, first by hand and then via a computer.
Let interview questions be your guide for what you need to know.
Try to solve the problem on your own—really try to solve it. If you read a question and get stuck solving it, that's okay and normal. Questions are designed to be tough. Don't give up, though. Keep working through the problem.
Write the code for the algorithm on paper.
Test your code! By hand, that is. No cheating with a computer!
Type your code into a computer exactly as is. Rerun both the test cases you tried and some new ones.
Start a list of all the mistakes you made, and analyze what types of mistakes you make the most often. Are there specific mistakes?
When you get a hard question, don't panic.
Just start talking aloud about how you would solve it.
Understand the question.
In fact, some interviewers (especially at Microsoft) will specifically test to see if you ask good questions.
A question like “Design an algorithm to sort a list” might turn into “Sort a sequence of values between 1 and 10 that are stored in a linked list.” This is a very different problem.
it's important to make sure that you really remember all those details that the interviewer mentioned.
If you think you might have forgotten some details, you can always ask your interviewer to repeat the problem.
Draw an example.
Design a brute force algorithm.
What are the space and time complexities?
What happens if there is a lot of data?
Does your design cause other issues? (That is, if you're creating a modified version of a binary search tree, did your design impact the time for insert/find/delete?)
If there are other issues, did you make the right trade-offs?
If the interviewer gave you specific data (e.g., mentioned that the data is ages, or in sorted order), have you leveraged that information? There's probably a reason that you're given it.
OPTIMIZE THE BRUTE FORCE
look for the bottlenecks, unnecessary work, and duplicated work (BUD) areas:
Bottlenecks.
Is there one part of the code that's taking a long time? For example, if your algorithm has first step that's O(N log N) and a second step that's O(N), there's little sense in optimizing the second step. The first step will always be a bottleneck. A bottleneck could also be a particularly slow part of the code that is called repeatedly. That might be a good place on which to focus your optimizations.
Unnecessary work.
Duplicated work.
Is there anything you're doing over and over again? For example, if you're continuously searching for the same elements, this could constitute duplicated work and you could optimize it with a hash table.
UNDERSTAND THE CODE
Interviewees spend too little time on this step and, unfortunately, it typically results in their writing sloppy and incorrect code.
Run through your algorithm meticulously before coding.
For example, imagine you're trying to merge two sorted arrays into a new sorted array. Many candidates start coding when they understand the basic gist: two pointers, move them through the array, copy the elements in order.
This probably isn't sufficient. You should instead understand it deeply. You need to understand what the variables are, when they update, and why. You should have logic like this formulated before you start coding:
Initialize two pointers, p and q, which point to the beginning of A and B, respectively.
Initialize k to an index at the start of the result array, R.
Compare the values at p and q.
If A[p] is smaller, insert A[p] into R[k]. Increment p and k.
If B[q] is smaller, insert B[q] into R[k]. Increment q and k.
Go to step 3.
You don't have to write this out by hand, but you do need to understand it at this level. Trying to skip a step and code before you're totally comfortable will only slow you down.
STEP 6: IMPLEMENT THE CODE
You don't need to rush through your code; in fact, this will most likely hurt you. Just go at a nice, slow, methodical pace
Use data structures generously. Where relevant, use a good data structure or define your own.
Modularize your code first.
If there are discrete steps in your algorithm, move these into separate functions. In fact, this can actually help you get out of doing tedious work. Imagine, as part of a broader algorithm, you need to convert a letter from A to Z to a number from 0 to 26. This is a tedious thing to write. Just modularize it off to another function and you probably won't need to worry about ever writing it.
Don't crowd your code.
If you feel yourself getting confused while coding, stop and go back to your example. You don't need to code straight through. It's far better that you take a break than write nonsensical code.
STEP 7: TEST
Review your code conceptually.
What is the meaning of each line? Does it do what you think it should?
Review error hot spots.
Is there anything in your code that looks funny (e.g., “int n = length − 2”)? Do your boundary conditions look right? What about your base cases (if the code is recursive)?
Test against a small example.
Pinpoint potential issues.
What sorts of test cases would test against specific potential issues? For example, you might sense that there could be a bug with one array that's much shorter than the other; test for this situation specifically.
Test error cases.
Finally, test the true error conditions. What happens on a null string or negative values?
Point out the mistake, and carefully analyze why the bug is occurring.
Is it really just when you pass in 0, or does it happen in other cases, too?
Bugs are not a big deal (bug-free code is very unusual). The important thing is that you think through how to fix issues you see rather than making a quick and dirty fix. A fix that works for that test case might not work for all test cases, so make sure it's the right one.
Algorithm Questions: Four Ways to Create an Algorithm
APPROACH 1: PATTERN MATCHING
Pattern matching means to relate a problem to similar ones, and figure out if you can modify the solution to solve the new problem.
This is one reason why practicing lots of problems is important: the more problems you do, the better you get.
APPROACH 2: SIMPLIFY AND GENERALIZE
In Simplify and Generalize, we change constraints (data type, size, etc.) to simplify the problem, and then try to solve the simplified problem. Once you have an algorithm for the simplified problem, you can generalize the problem back to its original form.
APPROACH 3: BASE CASE AND BUILD
APPROACH 4: DATA STRUCTURE BRAINSTORM
This approach works because many algorithms are quite straightforward once we find the right data structure.
A heap is really good at basic ordering and keeping track of maxes and mins.
Problem Solving
make sure you know what problem you're solving is common to many types of interview questions.
Rather, interview questions are about the process you take. Do you check your assumptions? Do you think through all possible cases? How do you break down the problem? Are you sure you're even solving the right problem?
HOW TO APPROACH ESTIMATION QUESTIONS
Ask clarifying details.
Find a structure. Break down the problem in separate chunks you can solve, almost like an equation.
Compute each component. For each component of this equation, make reasonable assumptions in order to estimate the answer.
Sanity check. Once you've come up with an answer, sanity check your value to see if it basically makes sense.
By coding on a whiteboard, you're encouraged to have a conversation with your interviewer. This helps the interviewer understand how you're thinking.
Coding on a whiteboard encourages you to focus on the meat of the algorithm and code, rather than getting caught up in the details.
For example, on a computer, a candidate is likely to spend time getting the exact syntax for a sort method correct. This isn't the type of stuff interviewers care about.
Because you're not worried about making all the little pieces work correctly, you can actually write more complex code. Need a helper function to find the smallest value in an array? No problem. Just pretend you have one.
Coding on a whiteboard tests how well you reason about how code works.
Do you just verify that your code works by running it? Or do you actually think conceptually about how it works?
Whiteboard coding encourages you to write good, clean code from the beginning, because it's so much slower. When you have a computer, you can be a bit sloppier and clean it up later.
What's Expected—And What's Not
Do what you can to demonstrate that you care about clean, beautiful code.
Wrap your code in a method declaration; loose code looks sloppy and can be confusing. You generally do not need to write the class definition, unless it's particularly relevant to the problem at hand.
Modularize your code. This shows an eye for maintainability.
If you notice parts of your code that you can refactor or clean up afterward, just go ahead and make the changes. You want to demonstrate that you are the kind of person who cares about the beauty of code.
Google tends to emphasize questions on scalability more than other companies (for instance, “Design a web crawler”). Questions on bit manipulation are also quite common.
Amazon loves object-oriented design questions. If you're going to interview at Amazon, make sure you study these problems. And, since Amazon is a web-based company, you'll also want to prepare for scalability questions.
Yahoo has historically emphasized more terminology and knowledge-based questions, but has begun to transition more to typical algorithm and problem-solving questions.
Implement the common data structures and algorithms from scratch, first by hand and then via a computer.
Let interview questions be your guide for what you need to know.
Try to solve the problem on your own—really try to solve it. If you read a question and get stuck solving it, that's okay and normal. Questions are designed to be tough. Don't give up, though. Keep working through the problem.
Write the code for the algorithm on paper.
Test your code! By hand, that is. No cheating with a computer!
Type your code into a computer exactly as is. Rerun both the test cases you tried and some new ones.
Start a list of all the mistakes you made, and analyze what types of mistakes you make the most often. Are there specific mistakes?
When you get a hard question, don't panic.
Just start talking aloud about how you would solve it.
Understand the question.
In fact, some interviewers (especially at Microsoft) will specifically test to see if you ask good questions.
A question like “Design an algorithm to sort a list” might turn into “Sort a sequence of values between 1 and 10 that are stored in a linked list.” This is a very different problem.
it's important to make sure that you really remember all those details that the interviewer mentioned.
If you think you might have forgotten some details, you can always ask your interviewer to repeat the problem.
Draw an example.
Design a brute force algorithm.
What are the space and time complexities?
What happens if there is a lot of data?
Does your design cause other issues? (That is, if you're creating a modified version of a binary search tree, did your design impact the time for insert/find/delete?)
If there are other issues, did you make the right trade-offs?
If the interviewer gave you specific data (e.g., mentioned that the data is ages, or in sorted order), have you leveraged that information? There's probably a reason that you're given it.
OPTIMIZE THE BRUTE FORCE
look for the bottlenecks, unnecessary work, and duplicated work (BUD) areas:
Bottlenecks.
Is there one part of the code that's taking a long time? For example, if your algorithm has first step that's O(N log N) and a second step that's O(N), there's little sense in optimizing the second step. The first step will always be a bottleneck. A bottleneck could also be a particularly slow part of the code that is called repeatedly. That might be a good place on which to focus your optimizations.
Unnecessary work.
Duplicated work.
Is there anything you're doing over and over again? For example, if you're continuously searching for the same elements, this could constitute duplicated work and you could optimize it with a hash table.
UNDERSTAND THE CODE
Interviewees spend too little time on this step and, unfortunately, it typically results in their writing sloppy and incorrect code.
Run through your algorithm meticulously before coding.
For example, imagine you're trying to merge two sorted arrays into a new sorted array. Many candidates start coding when they understand the basic gist: two pointers, move them through the array, copy the elements in order.
This probably isn't sufficient. You should instead understand it deeply. You need to understand what the variables are, when they update, and why. You should have logic like this formulated before you start coding:
Initialize two pointers, p and q, which point to the beginning of A and B, respectively.
Initialize k to an index at the start of the result array, R.
Compare the values at p and q.
If A[p] is smaller, insert A[p] into R[k]. Increment p and k.
If B[q] is smaller, insert B[q] into R[k]. Increment q and k.
Go to step 3.
You don't have to write this out by hand, but you do need to understand it at this level. Trying to skip a step and code before you're totally comfortable will only slow you down.
STEP 6: IMPLEMENT THE CODE
You don't need to rush through your code; in fact, this will most likely hurt you. Just go at a nice, slow, methodical pace
Use data structures generously. Where relevant, use a good data structure or define your own.
Modularize your code first.
If there are discrete steps in your algorithm, move these into separate functions. In fact, this can actually help you get out of doing tedious work. Imagine, as part of a broader algorithm, you need to convert a letter from A to Z to a number from 0 to 26. This is a tedious thing to write. Just modularize it off to another function and you probably won't need to worry about ever writing it.
Don't crowd your code.
If you feel yourself getting confused while coding, stop and go back to your example. You don't need to code straight through. It's far better that you take a break than write nonsensical code.
STEP 7: TEST
Review your code conceptually.
What is the meaning of each line? Does it do what you think it should?
Review error hot spots.
Is there anything in your code that looks funny (e.g., “int n = length − 2”)? Do your boundary conditions look right? What about your base cases (if the code is recursive)?
Test against a small example.
Pinpoint potential issues.
What sorts of test cases would test against specific potential issues? For example, you might sense that there could be a bug with one array that's much shorter than the other; test for this situation specifically.
Test error cases.
Finally, test the true error conditions. What happens on a null string or negative values?
Point out the mistake, and carefully analyze why the bug is occurring.
Is it really just when you pass in 0, or does it happen in other cases, too?
Bugs are not a big deal (bug-free code is very unusual). The important thing is that you think through how to fix issues you see rather than making a quick and dirty fix. A fix that works for that test case might not work for all test cases, so make sure it's the right one.
Algorithm Questions: Four Ways to Create an Algorithm
APPROACH 1: PATTERN MATCHING
Pattern matching means to relate a problem to similar ones, and figure out if you can modify the solution to solve the new problem.
This is one reason why practicing lots of problems is important: the more problems you do, the better you get.
APPROACH 2: SIMPLIFY AND GENERALIZE
In Simplify and Generalize, we change constraints (data type, size, etc.) to simplify the problem, and then try to solve the simplified problem. Once you have an algorithm for the simplified problem, you can generalize the problem back to its original form.
APPROACH 3: BASE CASE AND BUILD
APPROACH 4: DATA STRUCTURE BRAINSTORM
This approach works because many algorithms are quite straightforward once we find the right data structure.
A heap is really good at basic ordering and keeping track of maxes and mins.
Problem Solving
make sure you know what problem you're solving is common to many types of interview questions.
Rather, interview questions are about the process you take. Do you check your assumptions? Do you think through all possible cases? How do you break down the problem? Are you sure you're even solving the right problem?
HOW TO APPROACH ESTIMATION QUESTIONS
Ask clarifying details.
Find a structure. Break down the problem in separate chunks you can solve, almost like an equation.
Compute each component. For each component of this equation, make reasonable assumptions in order to estimate the answer.
Sanity check. Once you've come up with an answer, sanity check your value to see if it basically makes sense.
