I clearly remember my technical screening with facebook back in 2008. We did live code (similar to etherpad) and he asked me to write out a explode() function, and to write a Person object that held an array of friends, and to write a simple algorithm to find friends within 2 degrees.
It was a straightforward technical screening but the reason I remember it was because of the verbal emptiness from the interviewer. As I coded for him live on the spot I swear to god he was doing his own work or doing something else. Often I would ask him questions, comment, or walk him through my code and he showed absolutely no interest and often got lost saying things like "hey wait a second, what did you say?" as I heard him typing away at his keyboard, lol.
I usually don't write the type of code to find users within two degrees, so I thought it'd be a fun exercise in my fun-time language, Python.
And did you mean users instead of friends? If a user is already a friend with someone, that means they can only be one degree away.
Here's what I came up with. Is this about right?
# Set up a mock DB holding users and relationships.
# 1 is 1 degree from 2, 5 and 6
# 1 is 2 degrees from 3, 4, 6
# 1 is 3 degrees from 7 and 8
# 1 is 4 degrees from 7 and 8
people_store = [''] #0 -- put blank in 0 so we can have a one-based list.
people_store.append([2,5,6]) #1
people_store.append([1,3]) #2
people_store.append([2,4,6]) #3
people_store.append([3,6,7,8]) #4
people_store.append([1]) #5
people_store.append([1,3,4]) #6
people_store.append([4,8]) #7
people_store.append([4,7,9]) #8
people_store.append([8]) #9
def find_users_within_x_degrees(user_id, degrees):
"""Given a user ID, find other users within two degrees."""
# Users that are within the degree range.
# Start by adding current user's friends (1 degree).
users_within_range = set(people_store[user_id])
# Keep track of user IDs that have been checked.
checked_ids = set()
# Start at 2, because we have already handled 1 degree above.
for degree in range(2, degrees+1):
# Get other users IDs and get their friends. Only do so for users we haven't checked.
for other_user_id in users_within_range.difference(checked_ids):
checked_ids.add(other_user_id)
# Add other user's friends.
users_within_range.update(people_store[other_user_id])
# Because friendships are reciprocal, if the number of degrees is > 1, the requested user_id will be in the set, and should be removed.
if degrees > 1:
users_within_range.remove(user_id)
return users_within_range
Personally, as an interviewer I would be looking for a graph traversal a la breadth first search within an arbitrary graph structure (adjacency list, et al). This seems like it could work though.
I will definitely look into your suggestion, because if it's the optimal solution, I want it to be the first one I think of. Even though these types of problems don't come up for me that often, I'm sure there are times where a textbook CS solution would have been the best solution.
It depends on exactly what you're trying to optimize and what the requirements are. While it's not necessarily the best solution for a Facebook style problem (where you actually want to aggregate the results, where other concerns would be pagination of said results, permissions, etc.), an interesting algorithm to look at when you want to traverse a graph up to a certain depth looking for some specific "target" is iterative deepening. In basic terms, it is a depth-first search up to depth N inside a loop that increments N on each iteration.
I'd guess he or she was taking notes. I don't know how it works with Facebook, but sometimes the interviewer has to write up the results for the hiring committee, and just saying "hire" or "don't hire" isn't enough - you have to justify your answer.
Every interview I've had for a job I really wanted (with Google, Amazon, etc) goes roughly like this. The ending where "I think I did pretty well but they decided not to continue" is pretty consistent - I did get a lot of onsites, though, so I got a step further than this guy.
This obsession with puzzles is frustrating.
For all I know on some of the puzzle-type questions I got a slightly wrong or sub-optimal answer... but I never have any idea if that's what sunk me, or if the interviewer didn't like me personally, or if my whiteboard handwriting was too bad to read, etc.
Very frustrating experience, these type of things. Though working on the puzzles is always fun (and sometimes, I kick myself afterward for missing something that seems obvious in retrospect)
Interviews like this make me feel pretty crappy. I've been a successful software engineer for 10 years, and I'm in a senior role at the company I currently work in, but these are not the kinds of problems that I find myself solving on a daily basis. I don't have a CS degree -- I'm mostly self-taught, which means that if I'm presented with a problem I do the research to figure out how to solve it and seek feedback from the smart people I work with to make sure that the solution I come up with is the best one possible.
If you're applying for a job at a puzzle-solving factory, fine. But if you want people who really know how to solve problems, this kind of question usually doesn't get you those kinds of people.
I was pretty much in the same boat as you, having seven years of experience but no hard CS qualifications. I was recently contacted by a Facebook engineer who'd seen my blog and who encouraged me to apply.
The team I interviewed for was less technical than a core engineering team but the process was much more straightforward and actually easier than I expected. I'm from outside the US and had heard about month long hiring processes and day long interviews but in reality it was three short phone interviews and a single in-person interview which they paid for. I got the feeling they were looking for a personality fit rather than just engineering skills.
Same - I had nine rounds with Facebook in 2008, for a position in their London offices to be an SRE.
The questions asked by the Palo Alto team in rounds 1-5 were some of the toughest real-world questions I've had for an infrastructure programming role.
The London team (in on on-site for rounds 6-9) were more concerned about whether I had a degree, that I used Linux at home rather than a Mac, and whether I could code PHP (which hadn't been mentioned before).
FYI, the answer to the EDIT:first tech interview is a rather clever dynamic programming solution. The thing to be careful of is that you can actually get two different dyn prog solutions: one which is O(n^2) and one which is O(nlog n). Also, the use of "ascending" seems inaccurate. Based on his example it looks closer to "monotonically non-decreasing."
FWIW, it seems like a good problem to me. Dynamic programming is essential to finding good algorithmic solutions to many fundamental CS problems so I would expect everyone to be able to use it.
Edit: Thanks to kenjackson for correcting my numbering. The second problem doesn't look like it requires dyn prog to me.
The questions are very academic-like. I can answer the questions, but I learned the answers in university, not on-the-job. If I'd not done a CS degree, I would not be able to answer those questions.
I think that on the one hand, this is because Facebook wants to put on the big-boy pants like the other grown-up companies. Gogle does this, so Facebook must. And Google does it because Microsoft does it. And Microsoft does it because Billy G is a freak of (un)nature.
At least they're not asking why man hole covers are round, or if you had a bathtub the size of New York how many Grand Pianos would fit in it (correct answer: "I'm not aware that the Grand Piano is an internationally recognised standard unit of measure")
On the other hand, interviewing is not a solved problem in IT. It can't be, otherwise half (or more) of the people would never have gotten in, and productivity would soar.
On the gripping hand, for all that I want to denigrate Facebook, these questions do actually make sense - do you want people on your server writing an O(n) algorithm when an O(log n) one will do? When N is ridiculously large, like 500 million or something like that? And if the only place to learn these things is in an academic environment, then so be it. I admire the generic self-taught programmer as much as anybody else, but if they really love what they do, it would behoove them to borrow someone's old computer science textbooks and skim through them.
These questions definitely do make sense. If you look at Google's white papers and research, you'll see that their creative implementations allow them to use commodity hardware to build a huge server farm. This allows them to scale quickly and cheaply. Any microsecond of downtime for Google/Facebook would be catastrophic yet it is unwise to dump all the cash buying expensive servers.
These questions seem to be levelled directly at students; I would be curious if they asked the same questions to someone with more experience. These seemingly have very little to do with the day-to-day development of the site.
I would much prefer to see a sample of data they work with anonymized and being asked to come up with a creative solution to a specific problem.
I interviewed for a senior level developer position, and was asked questions along these same lines. I also had questions around system design and network programming.
I had many interviews, for small and large companies (10 years experience, Java), never had such questions, I don't think I would answer them correctly unfortunately.
It looks like they are for graduates/junior positions when there are not so many other things to talk about.
It was a straightforward technical screening but the reason I remember it was because of the verbal emptiness from the interviewer. As I coded for him live on the spot I swear to god he was doing his own work or doing something else. Often I would ask him questions, comment, or walk him through my code and he showed absolutely no interest and often got lost saying things like "hey wait a second, what did you say?" as I heard him typing away at his keyboard, lol.