10

I recently found out that Facebook had a programming challenge that if completed correctly you automatically get a phone interview.

There is a sample challenge that asks you to write an algorithm that can solve a Tower of Hanoi type problem. Given a number of pegs and discs, an initial and final configuration; Your algorithm must determine the fewest steps possible to get to the final configuration and output the steps.

This sample challenge gives you a 45 minute time limit but allows you to still test your code to see if it passes once your time limit expires.

I did not know of any cute math solution that could solve it, and I didn't want to look for one since I think that would be cheating. So I tried to solve the challenge the best I could on my own.

I was able to make an algorithm that worked and passed. However, it took me over 4 hours to make, much longer than the 45 minute requirement. Since it took me so much longer than the allotted time, I have not attempted the actual challenge.

This got me wondering though, in reality does it really matter that it took me that long? I mean is this a sign that I will not be able to get a job at a place like this (not just Facebook, but Google, Fog Creek, etc.) and need to lower my aspirations, or does the fact that I actually passed on my first attempt even though it took too long be taken as good?

JD Isaacks
  • 8,924
  • 12
  • 47
  • 54
  • 12
    It mattered here - is that real enough for you? –  Dec 10 '11 at 09:16
  • 2
    Why do you believe that not working for a big .com name implies that you lower your aspirations? – mouviciel Dec 10 '11 at 09:34
  • @mouviciel I didn't exactly mean lower my aspirations of working with a big .com name but more like working for a company where programming is the primary role vs working at a company that does something else like retail where nobody understands what you do. – JD Isaacks Dec 10 '11 at 14:54
  • Do you think that this single problem is representative of how you'll fare with all problems? Be wary of extrapolating too far! – Cascabel Dec 11 '11 at 04:33
  • 5
    LOL at Fog Creek software being included with Facebook and Google. – georgiecasey Apr 26 '12 at 23:38
  • IMHO it's more important to be right than to be quick. Often I don't feel like I really believe in an algorithm/program/language design until the 3rd or 4th version. At the same time, I'm often told that I work *fast*, but I don't look at it that way. As I look around, people just tend to make things way too complicated. – Mike Dunlavey Aug 10 '12 at 15:21
  • It seem sstrange to me that this test doesn't seem to look at how efficient the algorithm is. Producing an inefficient solution in 45 minutes would be worse for a company that producing an efficient solution in four hours. If your algorithm was 0.01 seconds faster per run than another it would only take 1.2Million runs before yours starts saving overall time. (NB for this problem I think (2^n-1) is the formula you need, though I've been known to be wrong) – Jaydee Aug 10 '12 at 15:46
  • Sorry, that formula is for the standard towers of Hanoi. The FB problem is apparently more complex – Jaydee Aug 10 '12 at 15:53
  • @Jaydee: I think of performance in terms of percentages, as opposed to a teeny bit multiplied over jillions of runs. I've managed to ruffle feathers [*with this viewpoint*](http://scicomp.stackexchange.com/a/2719/1262), but often programs contain larger speedup opportunities than you might think, but you do have to be smart about how you look for them. – Mike Dunlavey Aug 10 '12 at 15:57
  • 1
    related: [Is constantly looking for code examples a sign of a bad developer?](http://programmers.stackexchange.com/q/152020/31260), [Is it a really required skill to program without API documentation?](http://programmers.stackexchange.com/q/129806/31260) It's a matter of **fluency** – gnat Aug 11 '12 at 06:33
  • @MikeDunlavey There are certainly a lot of different ways to look at efficiency (I tend to look at efficiency as "does this make the user more efficient"). I was simply looking at the question posed by the testers and it seems to prioritise speed of completion over the effectiveness of the final solution. – Jaydee Aug 13 '12 at 08:15

7 Answers7

42

In practice it does matter how long it takes you. One that can solve the problem in 45 minutes is - all else equal - five times more productive than one that takes 4 hours, and hence more attractive to an employer.

That said, you do not say why you took four hours to solve this problem.

  • Were you at your best (well-fed, not tired, fully concentrated)?
  • Was the problem well specified, or did you need to do additional research on your own?
  • Did you have to learn new things to do this?
  • Were the tools familiar or not?
  • etc.

Any and all of these things might influence the time it takes you, and it is actually more important to be able to solve a problem when under pressure, without being told everything, and with the tools at hand, since that WILL happen during your career and it is usually at a point where it is very important to somebody whether you succeed or not.

  • Thanks for your answer. To answer why it took me long, one part is because I had a bit of trouble comprehending what it was I actually needed to do, once I understood that part, I still had to think for a bit to come up with a plan. For example, if a disc is blocking the disc I want to move, and I need to move it first, where should I move it to. The actually programming part was the shortest, but it all added to the time. – JD Isaacks Dec 10 '11 at 15:07
  • @JohnIsaacks So the problem was that you were unfamiliar with Towers of Hanoi. Most programmers I know have been introduced to it when being taught about recursion (each disk movement is essentially "move the disk above me to a vacant peg" which maps nicely to recursion). Have you received formal education and if so at what level? –  Dec 10 '11 at 15:16
  • @ThorbjørnRavnAndersen, I did not learn any programming in school. I am self taught, I learned on the job, by books, experimenting, etc. I was not familiar with the game (except for remembering a similar game being played in planet of the apes), I had to Google to even know it was called "Towers of Hanoi." I do understand recursion (at least I think I do) and I used it here. But simply solving the puzzle would have been much more easier for me, the harder part was "What pattern will yield the least amount of moves possible every time." – JD Isaacks Dec 10 '11 at 15:49
  • @JohnIsaacks programming is much like piano playing - you can get good on your own, but to get really good you need to be taught how to do things right by an experienced teacher. Could you elaborate on how you could solve the puzzle but find the "is it optimal" part hard? –  Dec 11 '11 at 17:48
  • I could make a recursive function that moves a piece into place, moves any blocking piece out of the way, then starts over with the next piece. Starting with the largest piece and working down to the last smallest piece. The "is it optimal" part comes from when you move a blocking piece. Depending on where you move it, it can create additional unnecessary steps. For example moving a 1 onto a 3 will then be blocking the 3 and need to be moved out of the way again when its time to move the 3. but depending on the current configuration this may not be avoidable. – JD Isaacks Dec 11 '11 at 19:59
  • Are you saying that I should go to school, or just get take a job where I will have a mentor? – JD Isaacks Dec 11 '11 at 20:00
  • Sounds like you solved it "from the top" instead of "I need to move disk X from pin 1 to 3" (which implies you have to move disk X-1 to pin 2 so disk X _can_ be removed from pin 1 and put on pin 3, which in turn require disk X-2 to be moved so disk X-1 is free, etc.). Anyway, what you should do to improve depends on your long term goals. At this point explicitly asking your current or future employer to help you get mentoring is probably the simplest thing to do. –  Dec 12 '11 at 06:51
  • Thanks for all your info. Also just to clarify, it looks like the classic Hanoi game always has 3 pegs and the discs are always in the same starting position and need to be moved to the same ending position. This particular challenge varies number of rods and starting & ending positions. – JD Isaacks Dec 12 '11 at 17:17
  • You may want to edit your question elaborating on why this was not "classic Hanoi". People may underestimate the effort needed when having more than three pegs. –  Dec 15 '11 at 22:42
  • "programming is much like piano playing - you can get good on your own, but to get really good you need to be taught how to do things right by an experienced teacher." I disagree, if that where true then how would the first person who learned piano have ever been really good? Or anyone after him? – khollenbeck Nov 19 '14 at 22:29
13

It does matter, to a company that is looking for general developers with good cash flow, because faster means more work can get done. However, in many other cases (I would argue in most cases, actually), it doesn't matter as much as your ability to solve problems, and your ability to solve them well.

I can think of five different types of problem solvers:

Those who...

  1. ...can solve problems quickly, with a clean and efficient solution.
  2. ...can solve problems quickly, but with a dirty and inefficient solution.
  3. ...can solve problems slowly, but end up with a clean and efficient solution.
  4. ...can solve problems slowly, but end up with a dirty and inefficient solution.
  5. ...cannot solve problems, either quickly, or slowly.

A Facebook-style test explicitly weeds out #3, #4, and #5 candidates because it has a time constraint, so we know that this test is for employers who have determined that they should only hire #1 or possibly #2 candidates (depending on further screening).

Some examples:

  • An employer like Facebook might only be looking for #1 programmers only, since they can afford huge salaries for super-star programmers.
  • An employer that has a high-volume of one-off sales (like some web design shops) might only want a #2 developer, who are cheaper than the equally effective #1 developers.
  • An employer that has a specialized problem domain (such as writing loan origination software), might accept a #3 developer over a #1 developer, since a dual-degree genius developer might be super-expensive, or they might be hard to find.
  • An employer that doesn't care or has limited budget for various reasons might be OK with a #4 developer.
  • #5 developers get hired by firms that don't know what they're looking for and fail to screen those applicants out.
Kevin McCormick
  • 4,064
  • 1
  • 18
  • 28
5

Tower of Hanoi? That was one of the first programming assignments I had on my freshman course at university (right after Fibonacci - yes, I had classes with one of those functional programming freaks :). And I'm not even on computer science, I'm on computer engineering.

And still, most so-called 'programmers' can't write this kind of algorithm correctly, because most programmers are awful. (search for fizzbuzz for added fun)

Anyway, once you are past a certain threshold, I think your programming skills doesn't matter as much as your ability to finish projects, your resiliency against difficulties, etc. And it seems you are past it for sure.

Facebook wants to hire the top devs, sure, but I don't know how much of them they hope to get with those kinds of games. I think they just don't want to lose time with awfully bad programmers.

A tip I always hear is that if you want to get hired by a cool tech company, try to get involved with open source projects. Also, try to get a internship.

elias
  • 109
  • 1
  • 1
3

When there is a lot of supply (many would-be programmers) and a little demand (few programming jobs) employers can be as demanding as they wish to be. As a matter of fact, they have to be demanding, or else they would be spending inordinate amounts of time interviewing people instead of getting any work done. So, they are giving candidates extremely hard tests so as to get a short list as quickly as possible, and so as to ensure that they will be interviewing people who are not just good, not even very good, but actually charismatic.

So, the fact that you did not complete the test within the allotted time frame does not mean you are a bad programmer; you just do not happen to fit the definition of what facebook considers charismatic. In my opinion, that's okay.

Mike Nakis
  • 32,003
  • 7
  • 76
  • 111
0

Time maters but don't get the idea that you're stupid if it takes you longer. A lot of people have things "memorized". They practice applying techniques like recursion so much that it becomes 2cd nature. It's not that their smarter, they just have practiced to the point of 2cd nature and you can too!

Consider the following math problem: 2+2=?

If you immediately knew the answer was 4 it's not because you're smart, but because it's 2cd nature. A child learning to add may be forced to go through the most basic operations of counting to get the answer. But that child may have the potential to surpass the adult.

Lord Tydus
  • 1,429
  • 1
  • 10
  • 12
-1

People don't really care how much time you spend doing something; just meet your deadlines and all's well.

user541686
  • 8,074
  • 8
  • 38
  • 49
  • 7
    So when the deadline is "45 mins from now" and you finish four hours later, people do care. –  Dec 10 '11 at 11:24
  • 1
    What Mehrdad means is that you can work overtime to meet the deadlines :D – quant_dev Dec 10 '11 at 17:59
  • 1
    If you have to work overtime to do things other devs wouldn't need overtime for -- you've got no stops left to pull out when the poop really hits the fan... – occulus Jun 20 '12 at 09:28
-1

It's quite tense, It would require me to read about what is tower of Hanoi -15min, start the IDE, create a blank solution -5min, so that's only 25 minutes to solve the problem. Simply writing code with all the plumbing like safe classes with good interface design would require some time as well -10min, so it's 15 minutes left for the actual idea. Depending on what is the tower on Hanoi, it might be enough, bit it might be not. And sometimes, I just need to let the problem solve itself while I'm working on other problems, because I don't see the solution right there on the spot. So it gets solved for free in a parallel thread, but it doesn't happen in an instant.

Anyway, it's one of the largest companies, so they can do whatever they want. But time limit is one of the worst factors in interviews IMHO, I always feel pressed, rushed, can't do everything clean, and can't concentrate on all details which are very important when actually working. :) Sure you can solve solutions fast, like, set access to admin so that everything works + 'SELECT * FROM pass WHERE usr == ' + user_input, but for any secure and well written task I would be proud with, I would need some time and 45 minutes is really quite intense.

Coder
  • 6,958
  • 5
  • 37
  • 49
  • 1
    I think they want people who simply remember what is the Tower of Hanoi problem (it's a classic). – quant_dev Dec 10 '11 at 18:01
  • Starting your IDE and creating a blank project takes five minutes? If you don't already know Towers Of Hanoi, at least do them in the opposite order so the IDE is loading (from a VM over the internet apparently) while you're researching! – Bryan Boettcher May 21 '12 at 19:29
  • In a test like this, they're not necessarily looking for "good interface design" and "plumbing" -- I'd expect that they want to see your understanding of the problem and ability to form an algorithm to solve it. If language wasn't a constraint, using something like Java and Eclipse is the last thing I'd be doing. I'd be using Python and a minimal text editor/compact IDE. (Not saying that you would be using Java yourself; just sayin'...) – occulus Jun 20 '12 at 09:31