Facebook Engineering Puzzles
facebook.com
facebook.com
I think one of the reasons I don't do well on these is because my brain doesn't seem to work well for hypotheticals. I need real world use cases or else it's exceedingly difficult for me to work out a solution for a problem that is too abstract.
Maybe I'm unique amongst other programmers with my level of experience. It's possible that other programmers love doing puzzles like this, but I tend to get discouraged if I'm looking at a company, and they use tests and puzzles to gauge my capabilities.
Especially (and I wouldn't accuse Facebook of this, but it happens much too often), if those tests and puzzles are substitutes for looking at the massive amounts of code I've written.
(I ask this from the perspective of a young, inexperienced developer.. so excuse the thoughtlessness!)
I don't mean to imply that you are unable to think, of course - the puzzles are surely an imperfect heuristic - but that's my understanding of their aim.
(selected few and summarized...)
Hoppity Hop!
Input: filename as arg from command prompt, file contains a number
Output: Some variation on the word "Hoppity" repeated
Simon Says
the gist: Connect to some server, call some api's in a certain order.
Battleship - write a client that connects to some server that plays battleship...
Find Sophie - read some data,build some data structures/run algorithm,output result
Input: filename and specifications of the file format
Output: result
If the questions were more like "How would you move Mt. Fuji", then that's certainly hypothetical.
Why not give me a real world use case, with a code base to work off of? Put up a codebase on github, provide a set of user stories and requirements to satisfy (ie, "add a real time search using this data set and code base which works cross-browser and degrades in IE"), and ask me to add it, thus basically mirroring a normal development process.
As someone who has had to interview programmers before, that would tell me infinitely more than their ability to re-iterate the word "Hoppity" on the command line.
Puzzle-based interview questions are meant to be a rough cut to weed out the people who are clearly unqualified for the position. They're not meant as a substitute for more in-depth discussion of skills, work experience, etc. If the filter is too time-consuming, it's going to weed out some of the best people who are confident they'll get offers from other companies. And a large company like Facebook doesn't necessarily want to test specific skills because they may not have yet decided which position you'd be hired for, and in any event you're likely to work on multiple projects during your time with the company. For entry-level positions (which is presumably what these questions are designed for), it's better to hire the smartest guy you can find and train him on specific technologies than to hire a guy who already has a specific skillset and then discover he's a one-trick pony.
Because they want you to be good enough to do it without that.
(I'm saying this as an about to be new grad who is studying these subjects to not have that much help and have to do it on a whiteboard in an interview
and also working on these puzzles and similar ones from a lot of other companies)
Dealing with things in the abstract, stripping it of context, interface, interaction, and real world requirement, seems to be an incomplete way to understand the capabilities of the person you're potentially hiring.
Unless, of course, you're hiring for the position of Junior Abstract Puzzle Solver. In which case, by all means, Godspeed.
If you consider the fact that:
- It is unlikely I am well-versed in the problem domain of your code,
- I am unlikely to be aware of external design constraints or coding pressures,
- I am probably going to randomly select the worst section of code to review,
- I have no context for how the code evolved
the chances that I walk away with a negative impression are high enough that it should give you pause. If I do manage to walk away with a positive impression of your code, it will be offset by the perception that you believe your time is more valuable than mine (why else would you send me a massive amount of code and ask me to review it to determine your suitability for a position) - and you still haven't answered the other big question I need answered which is whether you are a good "fit" for the team from a personality/cultural perspective.
If you really want to impress me, go ahead and send me a list of your projects and contributions and then slice a relevant sample of code from it. Describe what the problem was and how you solved it so I can understand the context. Try to make it relevant to the position, but failing that describe how you could utilize that experience in the relevant domain. Keep it small enough that I can review it in under an hour or two.
Is it a lot more work for you? Absolutely, but if you do this I guarantee you I will look at your code and will likely call you for an interview because you are demonstrating a high level of competence and professionalism while still respecting my time and needs.
It's presumptuous that I would be asking you to do a full code review (my Appleseed project is tens of thousands of lines of code, for instance), and that I wouldn't recognize the impracticality of such a request.
I would find it problematic, then, if you responded with tests and puzzles, without any interest or questions about my code. Or if the test and puzzles couldn't be skipped once I mentioned my experience level and accomplishments. This is often what interviewers have done, and I find it to be a good indicator of a workplace I'm not interested in working in.
The best workplaces let their developers take some time to comb through the best parts and the worst parts, and have a conversation about what I've done, my goals, how I did things, etc.
And for the record, I don't like "puzzles" either - even if I know the "trick" to the puzzle, sometimes my brain doesn't work right and I can't think of it after a long day of interviews. I would much prefer to be evaluated on how I work in a real environment, seeing my real code and my approach to real problems as opposed to impossible problems whose solution hinges on an obscure bit of semantic parsing in order to arrive at the solution. But as an interviewer, I don't have unlimited time to evaluate candidates so if you want me to do something, it helps to make it as easy as possible for me to do it.
In the end, I don't disagree with you, but I can understand interviewers that don't make the effort if you don't also make an effort.
I think it's fair to assume that after my years in the industry, that I would not simply hand you a link with no context, nor that I would be applying for a job which didn't relate to the work I had done, and I don't feel these arguments apply to the situation I presented.
But as far as I'm concerned, my preference would be to hire based on established code and real world tasks, not abstract puzzles. Not only are puzzles like these faddish, I've met too many programmers who excelled at puzzles, but were severely lacking in more mundane (but all too necessary) departments, so in terms of what kind of things I would use to weed people out, I'd do a set of real world tasks like the one I mentioned above, well before I'd ever give a list of clever puzzles to solve.
Assuming the applicant didn't contribute to open source, which would always be a huge plus in my book.
However, that leaves a whole lot of candidates out of the picture. Faced with limited recruiting resources, puzzles are about the next best thing to serve as a recruiting filter. Plus some people send them in without being told to, which is usually a plus, as it implicates coding in their spare time is something they enjoy doing.
But it is important for Facebook - so that's what they test.
In another, say, 5 years, expect to hear about Facebook giving out massive retention bonuses to top engineers who are defecting en masse to a hot new startup... :-D
1) The people who submit them are most likely interested in your company, took the time to solve the problem, and have a mind that works well. That already saves a lot of time screening people you wouldn't want for those top positions.
2) It attracts other smart people because you wouldn't refer puzzles to stupid people -- notice how we posted it on Hacker News. On a similar note, if you google for Node.js like I did, you'll find a sponsored result from Meebo offering you to apply to their "secret jobs!" -- because not just anyone searches for Node.js, but rather people who are interested in the new technology, which they are probably using or looking into.
3) Psychology -- people feel like they want something they worked towards. They committed time to facebook, so they will take it more seriously, and when someone from facebook talks to them, and asks them about their background AFTER solving the puzzle, they will feel a sense of accomplishment and engage back.
4) Notice how many of these puzzles have specified the exact outputs. They can screen the initial applicants with an automated test suite to see how well they did. Cheapest first round candidate evaluation ever :)
5) The puzzles are hopefully related to the kinds of architectural and social challenges they actually have to solve at facebook, so this prepares the candidate for that kind of thinking. If the candidate doesn't like thinking in this way, perhaps it's better to find out as early as possible, and before even SPEAKING to the candidate is pretty early!
If anything I would definitely set this kind of thing up for the top (architectural, etc.) development positions at facebook. They were recently named the best place to work at in 2010, so they can afford to do this.
"A 7 digit number consists of 7 distinct digits (from 0..9 ofcourse); The product of the first 3 digits = product of central 3 digits = product of last 3 digits; Find the middle digit."
"Middle Number: 2" "Set: 1892463" "Common Products: 72"
The next question I did not understand; I just figured I was not smart enough because I have no college and I am just a hacker that makes shit not a "software eng.". I sent it to a friend of mine that teaches Econ. at a top college and he said he had no idea what they were even asking. (see question below)
Given a list of N line segments on the X axis: (x1[i], x2[i]) where i = 1 to N; And then a list of M queries. Each query inputs one x-coordinate and you need to output the number of line segments that overlap this point. Assume M & N are very large. (So O(M*N) is really bad.)
I asked for clarification and got none so I guess they figured i was just too stupid to respond to which is cool but it made me wonder if when people talk about programmers that cant program do they mean people that cant answer these types of questions? I spent 5 or 10 min or it and gave up. But even though I didn't answer this I can code like a MF and if this question had been a programming challenge I think I could have done it.
My point is that companes should really think before sending out stuff like that to potential developers because they might pass up on some really good talent. I am not saying that I am very talented but I do know how to code and build cool products. I made digest.io and it uses clojure, ML, MapReduce to learn about your diet and help manage digestive conditions and it has paying customers that are happy. I made that and it works well so im not a rookie but I still have no idea what that 2nd question is asking.
BTW: Even though i hate these puzzles the FB puzzles are simple and I have always been able to complete them quickly.
You have a collection of N intervals. And a collection of M points (which they call queries). For a given interval and point, that point can be in the interval or not. For each point you are supposed to find out how many intervals it is inside of. And you're supposed to make the code fairly efficient.
From the way you've written it, the intervals look like open intervals. So x1[i] is not in the i'th interval. That is a minor but significant detail, and I expect their test data to check it.
The naive solution is to write a function that takes an interval and a point, and says whether that point is in that interval. Then you just loop over all points and intervals. This works, but the number of times you run that comparison is N * M. Which, if N and M are large, is going to be painfully slow. In fact there is a notation to discuss how slow, and that notation would say O(N * M). They don't want any variant on this solution.
The solution they are probably looking for is O((N + M) * log(N)). One solution is to try to first find and put into sorted form all of the intervals where the answer is going to be constant across the interval, and then do a binary search for each point to find what interval it falls into (and therefore what the answer is for that point).
My guess as to their thinking is that anyone who can't figure out something like this won't have any clue when they cause scalability problems. This matters for larger sites.
If you don't understand any of what I just said, that's a hole in your background. To fix it go off and learn about little-o, big-O, and some basic algorithms. A short list of algorithms to learn could include quicksort, merge sort, hashing, binary search and how a BTree works. That combination will solve most problems pretty easily.
--Thanks
Probably a stupid way to do it but it worked.
I think the issue was that I did not know points == queries
Taking too long is a real problem with a few of the puzzles (eg breathalyzer). If you read the comment threads there are some astoundingly fast solutions out there. My C breathalyzer solution was pretty quick but I was running it on an Ubuntu VM running inside Windows 7 and that did impact performance (particularly I/O). I've been meaning to run it on a real Ubuntu setup but haven't gotten around to it.
Anyway it all became moot as I ended up getting a job at Google but I did find it an interesting exercise.
Are they saying that the archive shouldn't have any directories in it period or that it should all be in one directory?
here's a kind of medium example from Fog Creek: given a list of elements in lexicographical order (i.e. ['a', 'b', 'c', 'd']), find the nth permutation
I'll add that they'll give you a certain amount of guidance if you require it, but beyond a certain point they're just helping you to make it less awkward.
Submissions should be sent via email to the address: {0xFACEB00C>>2 in decimal}@fb.com
The email address is also listed on the fan page.
It's automated grading, so it's nitpicky about the submission format, etc.
I do wish their grading script could give a little more indication of what failed, as I'm not sure it will even tell you the difference between a build error and a test failure. If it does, great. I struggled with that a year ago when I first worked on them.