Following is a guest post from ff Venture Capital winter intern Max Segan, a Colgate senior majoring in computer science, who is starting at Facebook this summer as a software engineer. From our perspective, Facebook is both our friend (training hundreds of talented future entrepreneurs) and enemy (competing with our portfolio companies for top talent like Max.) Max obtained approval from Facebook for the post below.
As I’ve just finished the interviewing/hiring process at Facebook, I thought it would be helpful to share some of the insights I gained, particularly for our many portfolio companies who are searching for talent. As the popularity of the recent Wall Street Journal article How to Ace a Google Interview shows, there is a great deal of interest regarding what should and shouldn’t go into recruiting.
Here are my top 6 pieces of advice if you’re looking to hire:
1) Fast turnaround between interviews. In a very competitive market for quality engineers they’re almost certainly interviewing elsewhere, too; it’s important to lose as few as possible due to poor response time or anything else easily preventable. Keep candidates engaged.
2) In person interviews are a must. If you’re hiring for a full time position it can be very risky to hire after only using email/phone/Skype. You can’t be certain of their ability or their fit, and the cost of a failed hire is incredibly high — even more so when contrasted with the benefit of a good one.
3) Always ask for an implementation. A lot of people can be very good problem solvers, but an employee who can’t code will be a bottleneck on projects — this is particularly true for smaller companies. For phone interviews I recommend websites such as Collabedit to let you watch candidates code in real time.
4) Provide interesting problems. If a candidate is good enough that you want to hire them, they could likely get another job as well; entice them by explaining some of the difficult and interesting questions that they’ll face on the job.
5) Network the candidate’s contacts. It’s hard to find good engineering talent right now, and if you’ve found somebody who knows what they’re doing they probably know others.
6) Use algorithms questions. Most places do this in addition to grilling their tech recruits on technical knowledge, but even non-technical candidates can tackle these problems if presented in an accessible manner. These types of questions illuminate how bright, quick, and creative a candidate is. The following are examples of such problems, and only the last requires any programming knowledge. The answers to all questions are at the bottom of the post.
Example Question #1
You have an array of N unique numbers distributed uniformly at random. You are searching for the largest one by starting at the beginning and iterating through, storing the current largest number at all times. You store the first number and then as you iterate you replace it with the current number when it is larger than the current one stored. How many stores should you expect to make, on average, in terms of N?
Example Question #2
You have two identical eggs and a building that is 100 stories tall that you’re dropping these eggs from. If an egg breaks it becomes unusable, but if it doesn’t break you can use it again and it is unaffected. There is no random chance in the drops, and there is some floor, F, such that eggs dropped from floor F don’t break while eggs dropped from F+1 will break. F might be floor 0, i.e. the eggs always break, or up to floor 100, i.e. they never break. You want to minimize the number of drops you have to make while determining this F. What is the best systematic way can you go about finding F regardless of what F is? In other words, find the smallest number K such that regardless of what F is no more than K drops are required to find it, and you’ll never break both eggs without finding it.
Example Question #3
There are 100 prisoners in a line. They each have either a red or a black hat on. They are able to see the hats of every prisoner ahead of them, but are not able to see their own hats or the hats of any prisoners behind them.
The executioner will start at the back of the line and asks each prisoner, in turn, to guess his or her own hat color. All prisoners in line can hear the guesses (but no information other than simply “Red” or “Black”). If they get it right they are allowed to live, and if they get it wrong they are killed immediately.
The prisoners have not yet been lined up or given their hats and are trying to decide on a strategy for guessing. They want to guarantee the survival of as many prisoners as possible, what is the best strategy you can come up with?
Example Question #4
You have an array of N integers, all between 1 and N-1. Using O(1) extra memory, O(N) time, and without modifying the array identify a repeated integer. Note that there may be multiple such integers.
__________________________________________
Answers to the Questions
Many questions have multiple answers that are all just about as good as one another. I’ll first say how efficiently the problem can be solved, then give one such way of how to solve it that well.
Answer to Question #1
The first number must be stored. The second number will be stored only if it’s larger than the first, so half the time. The third is stored only if it’s larger than the first two, and so on. So we see inductively that this becomes the harmonic series, i.e. 1+1/2+1/3+…+1/N, which is O(ln(N)).
Answer to Question #2
Find the smallest number, x, such that 1+2+…+x >= 100. Then start by dropping it from x, move up by x-1 and drop an egg, if it doesn’t break move up by x-2 and drop an egg, etc until an egg breaks. Then use the second egg to do a linear walk up from the last place it didn’t break up. This can take at most x+1 drops. For the 100-floor building this means 15 drops in the worst case.
This takes about sqrt(2n) drops for the mathematically interested. I leave the proof of this to readers.
Answer to Question #3
Have the prisoner in the back count how many black hats they see. If there is an even number they guess black, odd red. This prisoner may or may not die depending on luck.
The next prisoner can also check if there are an even or odd number of black hats in front of them. If the result differs from the guess of the prisoner behind them, they then know that their hat was black. Based on this guess the rest of the prisoners can update their knowledge and in this way continue to know if there is an even number of black hats from themselves to the front of the line when it’s their turn to guess, and can always use that to figure if their hat is black or not.
For the computer science minded people odd/even is the same as doing bit-wise XOR of the hats (say black is one, and red zero). It is an invertible function and after the first guess, all prisoners will know the XOR of all prisoners who still have to guess including their own, and can use this to get their own value.
Answer to Question #4
First view the array as a set linked list nodes, where each index is a node with an edge to the node at the index given by its value. Viewed this way if we begin at index 0 and find a loop, the start of that loop will be a repeated value. Starting from anywhere we must eventually reach a loop following the edges, as the node at index 0 cannot be in a loop as nothing can point to it, and all values are valid edges we can traverse the linked list indefinitely. The head of the loop can be found a number of ways, though the most elegant in my opinion is Floyd’s cycle-finding algorithm. For more information on Floyd’s algorithm see Wikipedia; it takes O(1) extra memory and O(N) time. The index of the head of the loop must then be the value of one node in the loop and one node not in the loop, so it is repeated at least twice.
