12 ms·

Interview Programming Problems Done Right

92 points by cletus 15y ago

gjm11 15y ago
Extra bonus points if they reduce quadratic to linear time with something like def pascal_row(n): row = [1] for i in range(1,n+1): row.append(row[-1]*(n+1-i)/i) print row (and more if they can talk intelligently about additions versus multiplications and divisions, the cost of [].append(), when if ever linear-versus-quadratic actually matters, bignum arithmetic, etc., etc., etc.).
- WildUtah 15y ago
  Yeah, I finished the article still wondering when he was going to get to one of the good solutions. A programmer with good math should be able to write a nice linear time solution right away. And that's one more reason why it's a terrible question. If you're looking for good programmers and not math whizzes then the solutions in the article tell you more. But they're all badly suboptimal if you know what you're doing. If you don't know what you're doing, the best answer is that you'd Google for it on Wikipedia.
tkahn6 15y ago
> Bonus points if the candidate correctly states this as "memorization" (rather than the more generic "caching"). Probably an autocorrect mishap there.
- baddox 15y ago
  An unfortunately placed one at that.
jchonphoenix 15y ago
I'm being nitpicky, but the iterative and "dynamic programming" solution are both dynamic programming if you follow the strict definition. Both are exploiting optimal substructure and the recursive nature of the problem. The best solution, labeled as "dynamic programming" in this article is actually just the most well optimized dp solution.
- jakubw 15y ago
  While we're at it, the last one could work purely in-place.
jjcm 15y ago
Typically we'll start with an even simpler problem before dropping them into something like this. Over time, we've found that a good 1/3rd of candidates can be eliminated with just fizzbuzz (print the numbers 1-100, for numbers divisible by 3, print fizz. For numbers divisible by 5, print buzz. For both, print fizzbuzz). Even if they do stellar on a phone interview, a large number of candidates still cant get past this simple problem. It's also easy enough that you can give it to people at job fairs on the spot. Any programmer that you'd want to hire can finish this in less than 5 minutes, which is an easy time investment to make.
- fbuilesv 15y ago
  One of the advantages that proponents of reviewing the candidate's code before the interview have is that you don't have to spend any time doing FizzBuzz kind of problems, which are just time wasters. If you're interviewing people who can't print the numbers 1-100 then something in your process is just wrong. Why did they get that far?
  - charlesju 15y ago
    Asking FizzBuzz is a lot easier than reviewing code, which may or may not be theirs.
    - cpt1138 15y ago
      Who said it was supposed to be easy?
    - sontek 15y ago
      If they have a github/bitbucket, this will show more than answering silly questions.
      - jjcm 15y ago
        Until you have someone who just gives you the link to someone else's github account. You'd be amazed at what people do.
seekely 15y ago
This is not, nor are similar whiteboard questions, a good interviewing problem. Not because the problem is particularly difficult or uninteresting, but because no matter how much the interviewer wants these questions to just be 'signals' of your ability, the candidate's performance at the whiteboard will likely be the determining factor for landing a job. The whiteboard gets too much weight, because it's too hard for an engineer (or likely anybody) to ignore somebody having a bad moment and flailing on something that seems so trivial to the interviewer. And this is why Google's interviewing process and reliance on these problems is terrible. You are put in five 1 hour sessions where you are asked Pascal Triangle esque whiteboard problems. Get a bit intimated? Stressed because of the interview? Miss your morning coffee? Start to panic a little bit? And suddenly you stumble on 1 or 2 of the problems and make an embarrassing impression. At this point, it does not matter how strong your portfolio is, how many recommendations from fellow Googlers you have received, past performances, or your samples of past code (all of which are much stronger signals than a whiteboard problem). You will not be getting the job.
- jameshart 15y ago
  I hear this complaint a lot, but I kind of don't get it. I just don't know any way to make job interviews fair for people who are having a bad day. Can we just stipulate that any interview technique will fail to recognise the potential of some candidates? False negatives of that sort are kind of inevitable. And from the point of view of a hiring company? a few false negatives aren't the end of the world. A false positive is way more costly.
  - seekely 15y ago
    Because a candidate with a mediocre background yet a strong showing on the whiteboard will get the job. The problem isn't not hiring somebody having a bad day. The problem is the over reliance on the whiteboard signal, despite a candidate's history of contradictory evidence (either positive or negative). If you are going to use typical whiteboard problems as a signal, it is really really hard to not heavily weigh the results, especially when sour.
dools 15y ago
If you ask me to do anything on a whiteboard I assure you it will take me a very long time and probably not work when transferred to an executable environment. At least let me type it in VIM and have an interpreter handy so I can test as I go. If I'm not expected to code on a whiteboard, having me write code on a whiteboard during an interview is retarded. I think that it would be appropriate to have me, say, model a database by drawing an ERD on a whiteboard as part of an interview question. If I went for a job interview and was asked to hand write code or write on a whiteboard I'd probably leave.
- tikhonj 15y ago
  I think some companies like Pivotal labs actually have you pair-program with your interviewer. I haven't applied there so all my knowledge is second-hand. Would you like that sort of interview?
  - dools 15y ago
    Sure I'm more than happy to code with someone assessing me.
- kls 15y ago
  I actually had an interview where I not only had to code the solution on the whiteboard but the developers then gave me parameters that they wanted passed in and I had to execute the function in my mind and give the correct output of the function.
  - roel_v 15y ago
    That's what efficient developers do. Relying on the compiler/interpreter for seeing if an algorithm works is a crutch. Mentally stepping through an algorithm, including keeping track of the state of e.g. state variables or stacks, is a litmus test to see if you really understand the code you just wrote. (preemptive nitpicker rebuke: getting the exact numeric output if that output depends on calculating e.g. the root of 34252 in your head is not what I mean by this)
- 15y ago
avallark 15y ago
You can learn a lot about a programmer, the way he thinks etc by asking very simple questions .. my favorites being "reversing a string" and frequency of characters in a given sentence etc.
- sontek 15y ago
  But thats just another popular interview question that all developers have memorized. So in python every developer you ask will just say s[::-1], they aren't even going to think about it. I prefer hiring based on Github or having them design a small project.
dxbydt 15y ago
Let me point out a slightly different whiteboarding approach I've used. I give you the problem. I give you the solution too! I will even explain the solution patiently, line by line, until you are absolutely convinced. Then I simply grow the problem - just one tiny step. I ask for the solution for this new problem. And guess what ? Most people still flunk! Here's the problem I use( we are a quant outfit ): --- Say I have $100 in 1 dollar bills. How to make the most money if I have to split it between google and apple ? ---- solution -- val apple = (0.015,0.1) // 1.5% return/month, 10% risk val google = (0.008,0.05) // 0.8% return/month, 5% risk val rho = 0.4 // google apple correlation is 40% // returns are weighted means val myreturns = (0.0 to 1.0 by 0.01).map(x=>(x * a._1 + (1-x) * b._1 )) // risks are standard deviations val myrisks = (0.0 to 1.0 by 0.01).map(x=>sqrt( x * x * a._2 * a._2 + (1-x) * (1-x) * b._2 * b._2 + 2 * x * a._2 * (1-x) * b._2 * rho)) // sharpe = my return over my risk val sharpes = (0 to 100).map(x=>myreturns(x)/myrisks(x)) // goal is to make most money ie. max sharpe println( "Most money has sharpe:" + sharpes.max ) ------ Now let me grow this problem, by just 1 more stock. I have $100 in 1 dollar bills. I give you 3 stocks: google, apple and amazon. How to make the most money ? This stumps so many people I have lost count! The ones who do well have usually taken a semester of undergraduate combinatorics, so they see instantly what needs to be done.
- forrestthewoods 15y ago
  That's a terrible programming question. You might as well just ask "Hey, did you take combinatorics in school? Ok, cool."
  - gcp 15y ago
    If that's important for his company, why not? It's like the people that apply for a programming job and complain they get O(n) questions. Also, it doesn't just test if they took it. It also tests whether they understood it and can apply it. (You would expect the schools to do that, but...) Of course, if this question requires combinatorial knowledge, and its irrelevant or not critical for the job, then that's just bad.
- gcp 15y ago
  I don't really know anything about this, and I'm finding the code written hard to understand (what language is this?). If I would have to guess, you need to add var amazon = (foo, bar), adjust myreturns and myrisks to calculate over 3 arguments (or generalize them). Then modify the maps to map over 2 variables instead of one (like nested loops). The allocation is the x,y in sharpes() that gave sharpes.max, though I have no idea how to get that out of this language. Edit: Ok, so you need to define another rho, and the problem is that a) not all mappings over x,y (0->1) are valid allocations a) the stocks are discrete. So that's where the combinatorics come in, as you need to consider all possible combinations of allocating 100 dollars over 3 stocks, and then map over that instead. I'd have absolutely no idea how to express that in this language. Also, what are the stock prices? Google, Amazon and Apple all trade at >100USD/share. You can't buy fractional shares, can you? PS. One thing I like in this approach is that you're requested to understand code that's already written. This is what happens in real life, too.
mattieuga 15y ago
I'm not sure how this is any better than any other annoying cs question asked by 90% of companies nowadays. My best interviewing experience was with a fairly large startup for an iOS programming position. Instead of a phone screening interview, they sent me a small iOS app description and asked me to code it and send it in. The in-person interviews was me and the interviewer, at a computer, coding sample iOS applications and looking through code. This is directly related to the job and through asking questions about the code and how to accomplish different things, the employer knows all they need to about the candidate's abilities. I've been asked to write the Fibonacci algorithm so many times that I can literally code every version of it with my eyes closed. Does that mean I'm a good programmer? I'm pretty sure anyone can memorize a dozen lines of text.
sontek 15y ago
The biggest issue with these puzzle questions is they are easy to memorize and encourage solving in the shortest amount of lines of code. I don't know why people rely on them at all because most candidates they hire probably have just went on pythonchallenge or interviewstreet and learned all the solutions to popular problems and then went to the interview or even learned the solutions by going to enough interviews. I want someone who can think on their own (not memorization) and can write good code (read: not shortest lines possible).
jhack 15y ago
I personally don't care how simple a question is or how well it's explained. If I walk into an interview with a portfolio full of samples and completed projects, and a resume full of references and qualifications, it's insulting and leaves me with a bad impression of the employer.
- orangecat 15y ago
  When Robert Metcalfe calls his ISP with a connectivity problem, they're still going to tell him to power cycle the modem first.
- gcp 15y ago
  At one point in one of my first hiring experiences I was asked at the last minute to come sit in on interview of a candidate, and handle the technical part of it. This was for low-level driver development work. I hadn't seen his resume before, so I got a pretty bad shock when this candidate said at one point "I'm the maintainer of subsystem X in the Linux kernel". With a a laptop on hand, "cd ~/git/linux-2.6; grep -R candidate_name" revealed easily enough to verify he wasn't joking. I bailed out of that interview, as I considered it grossly inappropriate to interview someone who was obviously much my senior in the relevant subject matter. The more senior interviewers informed me afterwards that was a mistake. If the candidate is who he claims he is, it will be immediately obvious during the questions, you apologize profusely and all are happy. If that doesn't happen, you might have saved the company from a major screw-up. And that does happen. TL;DR easier to apologize to a candidate than to to fire someone
derekprior 15y ago
Done right? Sorry, you bored me to death as soon as you started blabbering about Pascal's Triangle. I'm sure I learned about that at some point, but I've forgotten it. You asking me that questions would result in: 1) Me feeling stupid because I don't remember what Pascals Triangle is. 2) Me stumbling through some code while I try to understand the explanation you give me.
swanson 15y ago
My main issue with this type of question is that people will take this (or other popular questions) as the catch-all type of problem to ask in any interview for any candidate. If you are hiring a generalist or you are in a company that writes code in everything under the sun (Experience in Java, Ruby, Python, iOS, and Javascript preferred!), these questions are probably appropriate. But when you are hiring a web developer to work on your Rails app - the interview question should not revolve around optimizing space complexity or a recursive algorithm that exploits symmetry. The question should be more targeted to what the day in and out work will be - write some RSpec tests, fill in some controller methods, create a simple model. Use that as the filter. I don't think anyone applying to a Rails gig is going to balk at doing that kind of interview and I think it will be a better predictor than if they can find the largest substring palidrome in O(n).
- roel_v 15y ago
  You'd rather test for trivial mechanical skills rather than fundamental understanding?
  - swanson 15y ago
    As a filter? Yes. I'm not saying hire anyone that can do a fill-in-the-blank Rails controller action - but how they handle that mechanical task should help you figure out what direction to proceed in (a deeper dive into the fundamentals, a "Thanks, we'll be in touch"). I'd rather test trival mechanical skills rather than puzzles .
tmountain 15y ago
Hrm, I don't like this. I consider myself a pretty competent programmer, and I like doing programming puzzles for fun. I've spent a decent amount of time on 4clojure, project euler, and similar sites, and I can generally come up with solutions I'm happy with (elegant enough for my own liking). That said, from the stress free environment of my couch, some of these puzzles take me quite a while. I'm fairly confident that if asked to hash out a solution to this on a whiteboard in an interview situation, the stress of being put on the spot would impede my ability to perform up to par, and I'd probably come across as inept. Ironically, I'm one of the principal interviewers at the medium-sized company I work at. Many of the interviews I conduct delve into fairly technical discussions of previous projects the candidate has worked on, and I can generally walk away with a fairly firm gut feeling of how competent someone is. Candidates that give a solid initial impression are always asked to submit additional code samples (sometimes several rounds thereof), and occasionally asked back for one additional followup interview if we need any additional details. Through this gradual feeling out process, I feel like we've acquired some very excellent hires that we may have otherwise looked over if we based our process strictly on brain teaser type screenings.
- gcp 15y ago
  I'm fairly confident that if asked to hash out a solution to this on a whiteboard in an interview situation, the stress of being put on the spot would impede my ability to perform up to par, and I'd probably come across as inept. There's a mistaken assumption here that because you're a competent programmer you're expected to solve these exercises with ease [1]. If you're interviewing with that expectation, you'll have a huge false negative rate and only hire people with nerves of stainless steel. Even experienced programmers can make very silly mistakes when coding under pressure in front of an audience. What you're expecting to see is that the person can reason, knows the basic syntax of the language he claims to be familiar with, and doesn't make any mistakes that show a total misunderstanding or unfamiliarity of how it works. (Put differently, have they read a book/website of examples of the language, or have they actually coded in it?) If you point the experienced programmer that's very nervous a few of his mistakes, you're expecting him to show sheer terror and panic as he realizes what he's done [2]. If the candidate is showing you a blank stare instead, you might have a problem. If you're only verbally interviewing and asking for code samples, you can get fooled easily. Some candidates think that if they can bullshit their way through the interview, they'll stay hired. And sometimes, they're even right, because most people don't like to fire. At some point, we were having serious problems filling positions and started de-emphasizing doing bad/mediocre on the coding part of the interview, and focus more on the experience and verbal interview, on the assumption radiated in many posts here that serious coders might not necessarily be able to show their ability in a coding interview. All of those hires turned out to bad. You'll have a hard time convincing me now that coding interviews aren't effective. [1] The example here is FizzBuzz. Why is it so trivial that many people can't believe it works? Because even good coders will fuck up more complicated questions in interviews. [2] Just as an observation and nothing more: experienced coders tend to also not being able to bear the sight of those mistakes and insist on being allowed to correct them even if told it really doesn't matter.
pslam 15y ago
This is an awful interview question. It falls into the same trap that a lot of questions fall into: this is not something that would likely turn up in every-day work. Why are you asking a candidate questions about work they will never do? It's also too Computer Science. They're not interviewing for a CS course. They're interviewing to write, debug, maintain and ship code. What you should be exploring is code style, correctness, error catching, and the thought process that goes into it. Expand the question in that manner. Code golf is a very poor signal for a good engineer. Edit: For example, ask "Will this work for all input values of n?". Negative values might have issues, and as 'n' increases it either takes too long to complete or runs out of memory. It's surprising how many candidates don't understand that - and the way this question is asked would not discover it.
astrofinch 15y ago
"Any solution trumps no solution but the quality of the solution will give you a useful signal (IMHO)." I hate how it sends a negative signal in a programming interview to do the obvious recursive solution first instead of leaping directly to the dynamic programming one. I'm already nervous enough for Christ's sake!
- cpeterso 15y ago
  As an interviewer, I would not mind seeing a "naive" recursive solution first, though I would want the interview candidate to either mention this before implementing the recursive solution or later when they "discover" the inefficiencies. Showing your work (and describing your thought process) can provide more insight to an interviewer than just popping out an optimal solution without explanation!
Stormbringer 15y ago
You're all wrong. Firstly, for the crowd arguing about whether this is a good/bad/ugly question, your initial premise is wrong, because you pre-suppose that there are any good programming questions to ask in an interview. Since waffling about this sort of crap is entirely orthogonal to actual coding skill, there are no good questions, they are all bad. It's like trying to find the fastest marathon runner before the race by interviewing everyone and deciding who will win based on who gives the 'best' answer. Secondly, for the crowd debating the algorithms and offering better programming methods, or smug in your assurance of quadratic/linear/O(n) time or whatever, you're all wrong because your initial premise is wrong. You assume this is a programming problem, but programming is the wrong tool for the job. A much better general purpose tool for 'solving' this problem (but not even necessarily the 'best' tool) would be a spreadsheet for instance. Using a spreadsheet you could have finished (including testing - e.g. eyeballing the result for correctness) before the 'optimisers' have even finished typing in their code. In terms of effectiveness, you silly coders might as well be using pea-shooters in an ICBM competition.
agentultra 15y ago
This is still a terrible problem. It's simple exactly because it is familiar to the interviewer. It's easy for them to believe that anyone with half a brain should be able to answer it because they've practiced it a hundred times and have forgotten exactly what it is like to not know the answer. I think coding problems are terrible for almost any interview because the candidate is going to be struggling to find the right answer that will please you. They're looking to avoid causing you to press the big red button that gives them the electric shock and sends them home feeling like they're the most stupid person on Earth for not solving the easiest algorithm problem known to human kind. I get it though: as people who have to interview potential hires it gets tedious wading through the muck. Personally I don't understand how you can interview someone for a senior position without reviewing their prior work. I also find it rather insulting to assume that we should just separate them from the wheat just like all the other chaff. It's just disrespectful IMO. I'd done a lot of interviews about a year ago. All but one of them used a programming test of some sort. From fizzbuzz to fibonacci to splitting words, finding palindromes and implementing FIFO queues. I did it all. Some of them I got right. Some I didn't. Even the ones I had practiced and came to know really well... sometimes even then I would blow it. It was a really disheartening experience and I almost gave up programming forever when I started to believe that rigmarole about how any programmer worth their salt should be able to solve these problems without thinking about it. Which got me to thinking. I can solve these problems easily. I've got my algorithms books, I practice code kata, and I can generally golf some problems off the top of my head and they'll often compile. Why can't I do this in front of other people? The psychology of the situation is what gets in the way. If you give a candidate a problem they're going to immediately begin to think about what you want them to say. You say it's not trivia, but that's the exact mental process that will happen in most people. Given such a problem I'm certain a good number of candidates I interview would be able to solve them on their own. They might even be able to white board them once we start working together and they get to know me. But while we're in the interview room I'm the gatekeeper with the big red button and they've doing everything they can to keep me from pressing it. That doesn't work for me because I know that's not what I want from them. When I hire someone I look for initiative, experience, and intuition. I look for people who have taken what they've been given and made something more for themselves. If at their last job they weren't happy with something I'll ask what they did to change it. I also like to test their experience. I ask design-type questions, ask them what they like about their tools, what they don't like, patterns they've seen, how they practice... things like that. And finally with intuition I like to throw up some source code of some problem I'm working on or interesting ones I've come across (and solved) in the past and discuss it with them. I give them an over view of the code, my expectations of it, and then ask them to read it. We walk through it and I get to see how well they can spot bugs, code smell, what they focus on when they see code. IMO, these are the sort of things that I think demonstrate a person's knowledge of programming. And from my experience I think it's a better way to find good candidates.
mikehoward 15y ago
Problems on a whiteboard don't test programming skills simply because the whiteboard isn't executable. You don't get the feedback that REPL gives you, so you can't build up your solution - and understanding of the problem - iteratively. Seems to me that holding a code retreat and pairing with interviewee's would be more realistic. It would eliminate at least some of the pointless stress of interviewing and would get closer to a real programming environment. It's not like nobody has enough computers so you have to use whiteboards.
- gcp 15y ago
  Problems on a whiteboard don't test programming skills simply because the whiteboard isn't executable. You don't get the feedback that REPL gives you, so you can't build up your solution - and understanding of the problem - iteratively. Strange argument. What are people who write in compiled languages supposed to do? Particularly if their code is part of a product with a long build cycle? It's not like nobody has enough computers so you have to use whiteboards. On this I agree. We switched from whiteboards to giving the candidate a laptop, their editor of choice, and access to a compiler and the manpages and this was a major improvement.
  - mikehoward 15y ago
    look up doc - edit - compile - test - repeat is pretty close to interpreted language repl cycles. But then I started on punch cards, so maybe my perspective is different. [one to three compile & test cycles/day makes anything interactive look good] Appreciate the comment though. Gives me food for thought.
nessus42 15y ago
I'm with the camp that thinks that having to code on a whiteboard for an interview is just INANE. Worse than that, I find it to be borderline abusive. The whole concept just makes me quite mad. I graduated from MIT, and in my first programming class there (SICP), which I took first semester freshman year, I scored in the top 10 students out of 200 in the class. I've written software to control a space telescope and adapted brain imaging software to visualize astronomical data. I wrote a tutorial on how to do coordinate frame transformations, after first deriving the math myself (which isn't rocket science, but I hadn't done any linear algebra in 20 years at the time, so it took some thought). Clearly I know how to code! But put me at a whiteboard and ask me to code Hello World, and I'm likely to start sweating profusely and then get very dizzy, and then just ask to leave. I managed to make it through a first round of interviews at Google, but I had to take tranquilizers before the interview to make sure that the aforementioned scenario would not happen, but I don't think that people should have to be subjected to this. And I certainly wouldn't subject myself to this for almost any other company. I'd just say, "Screw you--I can find a job elsewhere." (I didn't end up doing the second round of Google interviews because I was offered a job elsewhere, and Google said that it would take a least an additional month to make a hiring decision.) Where I work now, the interviewing process is much more civilized. We send the specs for a small program along with some unit tests, and give the applicant however long they'd like to complete it. It should take a page or two of code and a couple of hours to complete at most. One might worry that people would cheat, but that hasn't been my experience. Most applicants never submit a solution at all. I suspect this is because they couldn't get their solution to pass the unit tests. (What we ask them to do, is not difficult. Anyone who passed a college course in software engineering with a grade better than a C should have absolutely no problem completing the assignment.) So, then some fraction of applicants actually complete the assignment. These submissions show that the vast majority of so-called software engineers -- or at least those who are looking for jobs -- can't code their way out of a paper bag. I.e., most of the submissions are grossly inefficient and hugely over-engineered or under-engineered. Finally, a few of the submissions are passable (rarely do we get a truly excellent solution, which is kind of sad), so we have them come in, and as part of the interview, we'll have them go over their code a bit and explain why they made certain design decisions, etc. If you ask me, this process gives us a much better idea of how someone would perform in the real world of being a software engineer and any amount of coding on a whiteboard ever could.
alok-g 15y ago
A good test to see if interview questions are you are posing to a potential candidate are good ones is to allow the candidate to pose a similar number of interview questions to you. If they can also pose problems that by your own standards you should be able to answer, but aren't, then you are not doing it right (unless you yourself are not a fit for the position under consideration which may very well be because you are in a different position). For some reason, some interviewers start with a belief that they are smarter than the candidate. While any reasonable person would feel that they do not fall in this category, think about how would you actually know if you do (this is not to say that you do fall in this category). The job of a good interviewer is as much to not reject a good candidate as it is to not accept a bad candidate; in both cases thinking of the position under consideration. If you start with this mindset, and by default subject yourself to as much doubt as you are subject the candidate to when her answer does not match your thinking, you are doing great.
JoachimSchipper 15y ago
Mathematician's solution: the entries in Pascal's triangle are combinations (n-over-k), which can be calculated directly: n-over-k = n!/((n - k)!k!). (If you want to be even faster, use Stirling's approximation to the factorial.)
- qntm 15y ago
  Yes, neatly circumventing all of the clever algorithmic complexity optimisation that the interviewer is apparently looking for, and making this an even worse interview question.
jaimzob 15y ago
The problem with tech interviews is that we tend to debug candidates rather than interview them, which leads to this confrontational, almost antagonistic pop-quiz process. An interview should be a conversation - sure you're trying to ascertain whether the candidate is smart and, most importantly, whether you could stand working with them but it should still be a two-way, human interaction. If you genuinely think that their tech skills aren't good enough then I've found the best test is to give some simple exercise for them to do in their own time, which you can then talk through in the interview. In this way you can set a realistic exercise (as opposed to 'generate me Pascal's triangle') and dedicate more time in the interview to the interesting stuff - 'why did you do this this way?', 'what the complexity of this approach?', 'can we improve that?' etc. How the candidate answers those question are a much better signal of intelligence then how adept he is with a whiteboard.
rickmb 15y ago
No, this isn't "right". It may be right for a specific job with specific skill requirements. I've been programming for over 25 years, and I've never had to solve any problem even remotely like it. I've also worked with dozens of programmers who could easily solve a problem like that, yet couldn't deliver a working application if their live depended on it. Different programming jobs require different skill sets. There is no universal test.
- lukes 15y ago
  I agree. I think the attribute most important to my job is being able to turn a complex specification into an app with clean architecture, with no two way coupling between components, generally useful parts abstracted away into reusable code, usage of existing open source modules instead of rolling my own where appropriate and so on. I don't think this test would reveal much of that about me. That said, for the first time in my career I was given a test to do and that seemed to be specifically designed to see how well I could architect code and yet I still screwed it up. That might show that I'm a bad programmer, or it might show that it's dangerous to use a short test to generalise about someone's ability. I like to take jobs on a contract basis, that way there's less risk for the clients as they can cut me whenever if it doesn't work. As a result of that the interview process is usually pretty quick and informal and I can show on a day to day basis that I am good at what I do.
sambeau 15y ago
Why don't people pay candidates for a day's work and see how they do? It would be cheaper and a far better indicator of actual potential.
- gcp 15y ago
  The administrative overhead of doing this would be immense, if it is even legal (at least in my country).
bambax 15y ago
> The second optimization one could make is that since f(r, i) == f(r, i-1) + f(r, i) then to calculate f(r, i) you only need to calculate up to the i'th element of each row. You actually only need to calculate up to the i'th element of the row you want. The Wikipedia page about Pascal's triangle [1] teaches us that it's possible to calculate a row directly (without any knowledge of other rows). Therefore we can do this: #!/usr/bin/python for row in xrange(200): curr = [1] vc = 1 for c in xrange(1, row/2+1): vc = int(vc * (row+1-c)/float(c)) curr.append(vc) curr.extend(curr[::-1]) print curr (And of course since each line is symmetrical we only need to compute half of it). This version is only a little faster than the last one provided by the author, but for some reason it's much more consistent, time-wise. For 200 rows it stays between 250-330ms between runs, whereas the author's last version is between 300-550ms. And with a little modification, this version will let us compute any row much more efficiently than starting at the first row every time. [1]: http://en.wikipedia.org/wiki/Pascals_triangle http://en.wikipedia.org/wiki/Pascals_triangle PS: There may be a more efficient way to calculate vc (Cell Value) than using int() and float(), but I don't really know Python so that's the best I can do ;-)
cruise02 15y ago
I think a lot of people here are missing the point that this is only one interview question, not the entire interview. You still need to ask icebreaker questions about the candidates experience to get them comfortable before breaking out a whiteboard question, and you should still follow up a "stock" question like this with a more specific question taken from your domain (if they make it that far). I'd also add that you need to have several of these "stock" whiteboard questions on hand. If the interviewee seems to get the solution too easily, they may have heard the question before. Everyone knows FizzBuzz by now, and I gave three answers to "compute the nth Fibonacci number" at my last interview. These questions are no good anymore if you're trying to see how a candidate thinks on their feet.
jrockway 15y ago
I think this problem is a great interview question. It's easy to describe, and it's easy to get started solving it by writing the first few lines on the whiteboard. From there, the pattern should be obvious, and once you've recognized the pattern, you only need to write a few lines of code. The disadvantage is that someone might remember Pascal's triangle from high school math, and will try to "remember" the answer instead of actually solving the problem incrementally. This is worthless because the question is about problem solving ability rather than your memory of exam questions like "Expand (x+3)^27" or "Factor x^3 + 3x^2y + 3xy^2 + y^3". (I do remember writing Pascal's triangle on these sorts of exams, incidentally!) Anyway, reading the other comments in the thread, it seems I am alone in liking this sort of question. I think these types of questions are good indicators of programmer quality. Anyone can read a Ruby on Rails tutorial and make an application that stores some records in a database. It doesn't take understanding to do that, it takes practice. That's all very good, as long as you're sure that your work will only be repeating what you've practiced rather than developing new skills. I think that programming work is very rarely like that. Yes, your job involves Ruby on Rails, but it's largely about solving some sort of complicated problem and then hooking the answer into your UI. Your experience with Rails will speed up the UI work, but if you aren't willing to understand and solve problems, you'll never have anything to put in the UI. (The people that can only do the UI part are "code monkeys" and don't get paid very well.) If you think that you'll never need to understand problem X, it's simply because you are unwilling to understand problem X. Once you understand graphs and algorithms and data structures, you'll see how you can apply your understanding to write better software. You might not think they're very important, but that's because, right now, you have no idea of how those techniques might be important. Learn them and then come back and say "everything in CS class is garbage". You won't, because it's not. Your job will be easier and you won't be navigating the waters blind. So I guess my point is: algorithm questions are good. There are a lot of programmers who can't solve problems (but can monkey code), and if you want the best programmers, you want the ones who can both solve problems AND write code.

92 points by cletus 15y ago

gjm11 15y ago

Extra bonus points if they reduce quadratic to linear time with something like def pascal_row(n): row = [1] for i in range(1,n+1): row.append(row[-1]*(n+1-i)/i) print row (and more if they can talk intelligently about additions versus multiplications and divisions, the cost of [].append(), when if ever linear-versus-quadratic actually matters, bignum arithmetic, etc., etc., etc.).

WildUtah 15y ago
Yeah, I finished the article still wondering when he was going to get to one of the good solutions. A programmer with good math should be able to write a nice linear time solution right away. And that's one more reason why it's a terrible question. If you're looking for good programmers and not math whizzes then the solutions in the article tell you more. But they're all badly suboptimal if you know what you're doing. If you don't know what you're doing, the best answer is that you'd Google for it on Wikipedia.

tkahn6 15y ago

> Bonus points if the candidate correctly states this as "memorization" (rather than the more generic "caching"). Probably an autocorrect mishap there.

baddox 15y ago
An unfortunately placed one at that.

jchonphoenix 15y ago

I'm being nitpicky, but the iterative and "dynamic programming" solution are both dynamic programming if you follow the strict definition. Both are exploiting optimal substructure and the recursive nature of the problem. The best solution, labeled as "dynamic programming" in this article is actually just the most well optimized dp solution.

jakubw 15y ago
While we're at it, the last one could work purely in-place.

jjcm 15y ago

Typically we'll start with an even simpler problem before dropping them into something like this. Over time, we've found that a good 1/3rd of candidates can be eliminated with just fizzbuzz (print the numbers 1-100, for numbers divisible by 3, print fizz. For numbers divisible by 5, print buzz. For both, print fizzbuzz). Even if they do stellar on a phone interview, a large number of candidates still cant get past this simple problem. It's also easy enough that you can give it to people at job fairs on the spot. Any programmer that you'd want to hire can finish this in less than 5 minutes, which is an easy time investment to make.

fbuilesv 15y ago
One of the advantages that proponents of reviewing the candidate's code before the interview have is that you don't have to spend any time doing FizzBuzz kind of problems, which are just time wasters. If you're interviewing people who can't print the numbers 1-100 then something in your process is just wrong. Why did they get that far?
- charlesju 15y ago
  Asking FizzBuzz is a lot easier than reviewing code, which may or may not be theirs.
  - cpt1138 15y ago
    Who said it was supposed to be easy?
  - sontek 15y ago
    If they have a github/bitbucket, this will show more than answering silly questions.
    - jjcm 15y ago
      Until you have someone who just gives you the link to someone else's github account. You'd be amazed at what people do.

seekely 15y ago

This is not, nor are similar whiteboard questions, a good interviewing problem. Not because the problem is particularly difficult or uninteresting, but because no matter how much the interviewer wants these questions to just be 'signals' of your ability, the candidate's performance at the whiteboard will likely be the determining factor for landing a job. The whiteboard gets too much weight, because it's too hard for an engineer (or likely anybody) to ignore somebody having a bad moment and flailing on something that seems so trivial to the interviewer. And this is why Google's interviewing process and reliance on these problems is terrible. You are put in five 1 hour sessions where you are asked Pascal Triangle esque whiteboard problems. Get a bit intimated? Stressed because of the interview? Miss your morning coffee? Start to panic a little bit? And suddenly you stumble on 1 or 2 of the problems and make an embarrassing impression. At this point, it does not matter how strong your portfolio is, how many recommendations from fellow Googlers you have received, past performances, or your samples of past code (all of which are much stronger signals than a whiteboard problem). You will not be getting the job.

jameshart 15y ago
I hear this complaint a lot, but I kind of don't get it. I just don't know any way to make job interviews fair for people who are having a bad day. Can we just stipulate that any interview technique will fail to recognise the potential of some candidates? False negatives of that sort are kind of inevitable. And from the point of view of a hiring company? a few false negatives aren't the end of the world. A false positive is way more costly.
- seekely 15y ago
  Because a candidate with a mediocre background yet a strong showing on the whiteboard will get the job. The problem isn't not hiring somebody having a bad day. The problem is the over reliance on the whiteboard signal, despite a candidate's history of contradictory evidence (either positive or negative). If you are going to use typical whiteboard problems as a signal, it is really really hard to not heavily weigh the results, especially when sour.

dools 15y ago

If you ask me to do anything on a whiteboard I assure you it will take me a very long time and probably not work when transferred to an executable environment. At least let me type it in VIM and have an interpreter handy so I can test as I go. If I'm not expected to code on a whiteboard, having me write code on a whiteboard during an interview is retarded. I think that it would be appropriate to have me, say, model a database by drawing an ERD on a whiteboard as part of an interview question. If I went for a job interview and was asked to hand write code or write on a whiteboard I'd probably leave.

tikhonj 15y ago
I think some companies like Pivotal labs actually have you pair-program with your interviewer. I haven't applied there so all my knowledge is second-hand. Would you like that sort of interview?
- dools 15y ago
  Sure I'm more than happy to code with someone assessing me.
kls 15y ago
I actually had an interview where I not only had to code the solution on the whiteboard but the developers then gave me parameters that they wanted passed in and I had to execute the function in my mind and give the correct output of the function.
- roel_v 15y ago
  That's what efficient developers do. Relying on the compiler/interpreter for seeing if an algorithm works is a crutch. Mentally stepping through an algorithm, including keeping track of the state of e.g. state variables or stacks, is a litmus test to see if you really understand the code you just wrote. (preemptive nitpicker rebuke: getting the exact numeric output if that output depends on calculating e.g. the root of 34252 in your head is not what I mean by this)
15y ago

avallark 15y ago

You can learn a lot about a programmer, the way he thinks etc by asking very simple questions .. my favorites being "reversing a string" and frequency of characters in a given sentence etc.

sontek 15y ago
But thats just another popular interview question that all developers have memorized. So in python every developer you ask will just say s[::-1], they aren't even going to think about it. I prefer hiring based on Github or having them design a small project.

dxbydt 15y ago

Let me point out a slightly different whiteboarding approach I've used. I give you the problem. I give you the solution too! I will even explain the solution patiently, line by line, until you are absolutely convinced. Then I simply grow the problem - just one tiny step. I ask for the solution for this new problem. And guess what ? Most people still flunk! Here's the problem I use( we are a quant outfit ): --- Say I have $100 in 1 dollar bills. How to make the most money if I have to split it between google and apple ? ---- solution -- val apple = (0.015,0.1) // 1.5% return/month, 10% risk val google = (0.008,0.05) // 0.8% return/month, 5% risk val rho = 0.4 // google apple correlation is 40% // returns are weighted means val myreturns = (0.0 to 1.0 by 0.01).map(x=>(x * a._1 + (1-x) * b._1 )) // risks are standard deviations val myrisks = (0.0 to 1.0 by 0.01).map(x=>sqrt( x * x * a._2 * a._2 + (1-x) * (1-x) * b._2 * b._2 + 2 * x * a._2 * (1-x) * b._2 * rho)) // sharpe = my return over my risk val sharpes = (0 to 100).map(x=>myreturns(x)/myrisks(x)) // goal is to make most money ie. max sharpe println( "Most money has sharpe:" + sharpes.max ) ------ Now let me grow this problem, by just 1 more stock. I have $100 in 1 dollar bills. I give you 3 stocks: google, apple and amazon. How to make the most money ? This stumps so many people I have lost count! The ones who do well have usually taken a semester of undergraduate combinatorics, so they see instantly what needs to be done.

forrestthewoods 15y ago
That's a terrible programming question. You might as well just ask "Hey, did you take combinatorics in school? Ok, cool."
- gcp 15y ago
  If that's important for his company, why not? It's like the people that apply for a programming job and complain they get O(n) questions. Also, it doesn't just test if they took it. It also tests whether they understood it and can apply it. (You would expect the schools to do that, but...) Of course, if this question requires combinatorial knowledge, and its irrelevant or not critical for the job, then that's just bad.
gcp 15y ago
I don't really know anything about this, and I'm finding the code written hard to understand (what language is this?). If I would have to guess, you need to add var amazon = (foo, bar), adjust myreturns and myrisks to calculate over 3 arguments (or generalize them). Then modify the maps to map over 2 variables instead of one (like nested loops). The allocation is the x,y in sharpes() that gave sharpes.max, though I have no idea how to get that out of this language. Edit: Ok, so you need to define another rho, and the problem is that a) not all mappings over x,y (0->1) are valid allocations a) the stocks are discrete. So that's where the combinatorics come in, as you need to consider all possible combinations of allocating 100 dollars over 3 stocks, and then map over that instead. I'd have absolutely no idea how to express that in this language. Also, what are the stock prices? Google, Amazon and Apple all trade at >100USD/share. You can't buy fractional shares, can you? PS. One thing I like in this approach is that you're requested to understand code that's already written. This is what happens in real life, too.

mattieuga 15y ago

I'm not sure how this is any better than any other annoying cs question asked by 90% of companies nowadays. My best interviewing experience was with a fairly large startup for an iOS programming position. Instead of a phone screening interview, they sent me a small iOS app description and asked me to code it and send it in. The in-person interviews was me and the interviewer, at a computer, coding sample iOS applications and looking through code. This is directly related to the job and through asking questions about the code and how to accomplish different things, the employer knows all they need to about the candidate's abilities. I've been asked to write the Fibonacci algorithm so many times that I can literally code every version of it with my eyes closed. Does that mean I'm a good programmer? I'm pretty sure anyone can memorize a dozen lines of text.

sontek 15y ago

The biggest issue with these puzzle questions is they are easy to memorize and encourage solving in the shortest amount of lines of code. I don't know why people rely on them at all because most candidates they hire probably have just went on pythonchallenge or interviewstreet and learned all the solutions to popular problems and then went to the interview or even learned the solutions by going to enough interviews. I want someone who can think on their own (not memorization) and can write good code (read: not shortest lines possible).

jhack 15y ago

I personally don't care how simple a question is or how well it's explained. If I walk into an interview with a portfolio full of samples and completed projects, and a resume full of references and qualifications, it's insulting and leaves me with a bad impression of the employer.

orangecat 15y ago
When Robert Metcalfe calls his ISP with a connectivity problem, they're still going to tell him to power cycle the modem first.
gcp 15y ago
At one point in one of my first hiring experiences I was asked at the last minute to come sit in on interview of a candidate, and handle the technical part of it. This was for low-level driver development work. I hadn't seen his resume before, so I got a pretty bad shock when this candidate said at one point "I'm the maintainer of subsystem X in the Linux kernel". With a a laptop on hand, "cd ~/git/linux-2.6; grep -R candidate_name" revealed easily enough to verify he wasn't joking. I bailed out of that interview, as I considered it grossly inappropriate to interview someone who was obviously much my senior in the relevant subject matter. The more senior interviewers informed me afterwards that was a mistake. If the candidate is who he claims he is, it will be immediately obvious during the questions, you apologize profusely and all are happy. If that doesn't happen, you might have saved the company from a major screw-up. And that does happen. TL;DR easier to apologize to a candidate than to to fire someone

derekprior 15y ago

Done right? Sorry, you bored me to death as soon as you started blabbering about Pascal's Triangle. I'm sure I learned about that at some point, but I've forgotten it. You asking me that questions would result in: 1) Me feeling stupid because I don't remember what Pascals Triangle is. 2) Me stumbling through some code while I try to understand the explanation you give me.

swanson 15y ago

My main issue with this type of question is that people will take this (or other popular questions) as the catch-all type of problem to ask in any interview for any candidate. If you are hiring a generalist or you are in a company that writes code in everything under the sun (Experience in Java, Ruby, Python, iOS, and Javascript preferred!), these questions are probably appropriate. But when you are hiring a web developer to work on your Rails app - the interview question should not revolve around optimizing space complexity or a recursive algorithm that exploits symmetry. The question should be more targeted to what the day in and out work will be - write some RSpec tests, fill in some controller methods, create a simple model. Use that as the filter. I don't think anyone applying to a Rails gig is going to balk at doing that kind of interview and I think it will be a better predictor than if they can find the largest substring palidrome in O(n).

roel_v 15y ago
You'd rather test for trivial mechanical skills rather than fundamental understanding?
- swanson 15y ago
  As a filter? Yes. I'm not saying hire anyone that can do a fill-in-the-blank Rails controller action - but how they handle that mechanical task should help you figure out what direction to proceed in (a deeper dive into the fundamentals, a "Thanks, we'll be in touch"). I'd rather test trival mechanical skills rather than puzzles .

tmountain 15y ago

Hrm, I don't like this. I consider myself a pretty competent programmer, and I like doing programming puzzles for fun. I've spent a decent amount of time on 4clojure, project euler, and similar sites, and I can generally come up with solutions I'm happy with (elegant enough for my own liking). That said, from the stress free environment of my couch, some of these puzzles take me quite a while. I'm fairly confident that if asked to hash out a solution to this on a whiteboard in an interview situation, the stress of being put on the spot would impede my ability to perform up to par, and I'd probably come across as inept. Ironically, I'm one of the principal interviewers at the medium-sized company I work at. Many of the interviews I conduct delve into fairly technical discussions of previous projects the candidate has worked on, and I can generally walk away with a fairly firm gut feeling of how competent someone is. Candidates that give a solid initial impression are always asked to submit additional code samples (sometimes several rounds thereof), and occasionally asked back for one additional followup interview if we need any additional details. Through this gradual feeling out process, I feel like we've acquired some very excellent hires that we may have otherwise looked over if we based our process strictly on brain teaser type screenings.

gcp 15y ago
I'm fairly confident that if asked to hash out a solution to this on a whiteboard in an interview situation, the stress of being put on the spot would impede my ability to perform up to par, and I'd probably come across as inept. There's a mistaken assumption here that because you're a competent programmer you're expected to solve these exercises with ease [1]. If you're interviewing with that expectation, you'll have a huge false negative rate and only hire people with nerves of stainless steel. Even experienced programmers can make very silly mistakes when coding under pressure in front of an audience. What you're expecting to see is that the person can reason, knows the basic syntax of the language he claims to be familiar with, and doesn't make any mistakes that show a total misunderstanding or unfamiliarity of how it works. (Put differently, have they read a book/website of examples of the language, or have they actually coded in it?) If you point the experienced programmer that's very nervous a few of his mistakes, you're expecting him to show sheer terror and panic as he realizes what he's done [2]. If the candidate is showing you a blank stare instead, you might have a problem. If you're only verbally interviewing and asking for code samples, you can get fooled easily. Some candidates think that if they can bullshit their way through the interview, they'll stay hired. And sometimes, they're even right, because most people don't like to fire. At some point, we were having serious problems filling positions and started de-emphasizing doing bad/mediocre on the coding part of the interview, and focus more on the experience and verbal interview, on the assumption radiated in many posts here that serious coders might not necessarily be able to show their ability in a coding interview. All of those hires turned out to bad. You'll have a hard time convincing me now that coding interviews aren't effective. [1] The example here is FizzBuzz. Why is it so trivial that many people can't believe it works? Because even good coders will fuck up more complicated questions in interviews. [2] Just as an observation and nothing more: experienced coders tend to also not being able to bear the sight of those mistakes and insist on being allowed to correct them even if told it really doesn't matter.

pslam 15y ago

This is an awful interview question. It falls into the same trap that a lot of questions fall into: this is not something that would likely turn up in every-day work. Why are you asking a candidate questions about work they will never do? It's also too Computer Science. They're not interviewing for a CS course. They're interviewing to write, debug, maintain and ship code. What you should be exploring is code style, correctness, error catching, and the thought process that goes into it. Expand the question in that manner. Code golf is a very poor signal for a good engineer. Edit: For example, ask "Will this work for all input values of n?". Negative values might have issues, and as 'n' increases it either takes too long to complete or runs out of memory. It's surprising how many candidates don't understand that - and the way this question is asked would not discover it.

astrofinch 15y ago

"Any solution trumps no solution but the quality of the solution will give you a useful signal (IMHO)." I hate how it sends a negative signal in a programming interview to do the obvious recursive solution first instead of leaping directly to the dynamic programming one. I'm already nervous enough for Christ's sake!

cpeterso 15y ago
As an interviewer, I would not mind seeing a "naive" recursive solution first, though I would want the interview candidate to either mention this before implementing the recursive solution or later when they "discover" the inefficiencies. Showing your work (and describing your thought process) can provide more insight to an interviewer than just popping out an optimal solution without explanation!

Stormbringer 15y ago

You're all wrong. Firstly, for the crowd arguing about whether this is a good/bad/ugly question, your initial premise is wrong, because you pre-suppose that there are any good programming questions to ask in an interview. Since waffling about this sort of crap is entirely orthogonal to actual coding skill, there are no good questions, they are all bad. It's like trying to find the fastest marathon runner before the race by interviewing everyone and deciding who will win based on who gives the 'best' answer. Secondly, for the crowd debating the algorithms and offering better programming methods, or smug in your assurance of quadratic/linear/O(n) time or whatever, you're all wrong because your initial premise is wrong. You assume this is a programming problem, but programming is the wrong tool for the job. A much better general purpose tool for 'solving' this problem (but not even necessarily the 'best' tool) would be a spreadsheet for instance. Using a spreadsheet you could have finished (including testing - e.g. eyeballing the result for correctness) before the 'optimisers' have even finished typing in their code. In terms of effectiveness, you silly coders might as well be using pea-shooters in an ICBM competition.

agentultra 15y ago

This is still a terrible problem. It's simple exactly because it is familiar to the interviewer. It's easy for them to believe that anyone with half a brain should be able to answer it because they've practiced it a hundred times and have forgotten exactly what it is like to not know the answer. I think coding problems are terrible for almost any interview because the candidate is going to be struggling to find the right answer that will please you. They're looking to avoid causing you to press the big red button that gives them the electric shock and sends them home feeling like they're the most stupid person on Earth for not solving the easiest algorithm problem known to human kind. I get it though: as people who have to interview potential hires it gets tedious wading through the muck. Personally I don't understand how you can interview someone for a senior position without reviewing their prior work. I also find it rather insulting to assume that we should just separate them from the wheat just like all the other chaff. It's just disrespectful IMO. I'd done a lot of interviews about a year ago. All but one of them used a programming test of some sort. From fizzbuzz to fibonacci to splitting words, finding palindromes and implementing FIFO queues. I did it all. Some of them I got right. Some I didn't. Even the ones I had practiced and came to know really well... sometimes even then I would blow it. It was a really disheartening experience and I almost gave up programming forever when I started to believe that rigmarole about how any programmer worth their salt should be able to solve these problems without thinking about it. Which got me to thinking. I can solve these problems easily. I've got my algorithms books, I practice code kata, and I can generally golf some problems off the top of my head and they'll often compile. Why can't I do this in front of other people? The psychology of the situation is what gets in the way. If you give a candidate a problem they're going to immediately begin to think about what you want them to say. You say it's not trivia, but that's the exact mental process that will happen in most people. Given such a problem I'm certain a good number of candidates I interview would be able to solve them on their own. They might even be able to white board them once we start working together and they get to know me. But while we're in the interview room I'm the gatekeeper with the big red button and they've doing everything they can to keep me from pressing it. That doesn't work for me because I know that's not what I want from them. When I hire someone I look for initiative, experience, and intuition. I look for people who have taken what they've been given and made something more for themselves. If at their last job they weren't happy with something I'll ask what they did to change it. I also like to test their experience. I ask design-type questions, ask them what they like about their tools, what they don't like, patterns they've seen, how they practice... things like that. And finally with intuition I like to throw up some source code of some problem I'm working on or interesting ones I've come across (and solved) in the past and discuss it with them. I give them an over view of the code, my expectations of it, and then ask them to read it. We walk through it and I get to see how well they can spot bugs, code smell, what they focus on when they see code. IMO, these are the sort of things that I think demonstrate a person's knowledge of programming. And from my experience I think it's a better way to find good candidates.

mikehoward 15y ago

Problems on a whiteboard don't test programming skills simply because the whiteboard isn't executable. You don't get the feedback that REPL gives you, so you can't build up your solution - and understanding of the problem - iteratively. Seems to me that holding a code retreat and pairing with interviewee's would be more realistic. It would eliminate at least some of the pointless stress of interviewing and would get closer to a real programming environment. It's not like nobody has enough computers so you have to use whiteboards.

gcp 15y ago
Problems on a whiteboard don't test programming skills simply because the whiteboard isn't executable. You don't get the feedback that REPL gives you, so you can't build up your solution - and understanding of the problem - iteratively. Strange argument. What are people who write in compiled languages supposed to do? Particularly if their code is part of a product with a long build cycle? It's not like nobody has enough computers so you have to use whiteboards. On this I agree. We switched from whiteboards to giving the candidate a laptop, their editor of choice, and access to a compiler and the manpages and this was a major improvement.
- mikehoward 15y ago
  look up doc - edit - compile - test - repeat is pretty close to interpreted language repl cycles. But then I started on punch cards, so maybe my perspective is different. [one to three compile & test cycles/day makes anything interactive look good] Appreciate the comment though. Gives me food for thought.

nessus42 15y ago

I'm with the camp that thinks that having to code on a whiteboard for an interview is just INANE. Worse than that, I find it to be borderline abusive. The whole concept just makes me quite mad. I graduated from MIT, and in my first programming class there (SICP), which I took first semester freshman year, I scored in the top 10 students out of 200 in the class. I've written software to control a space telescope and adapted brain imaging software to visualize astronomical data. I wrote a tutorial on how to do coordinate frame transformations, after first deriving the math myself (which isn't rocket science, but I hadn't done any linear algebra in 20 years at the time, so it took some thought). Clearly I know how to code! But put me at a whiteboard and ask me to code Hello World, and I'm likely to start sweating profusely and then get very dizzy, and then just ask to leave. I managed to make it through a first round of interviews at Google, but I had to take tranquilizers before the interview to make sure that the aforementioned scenario would not happen, but I don't think that people should have to be subjected to this. And I certainly wouldn't subject myself to this for almost any other company. I'd just say, "Screw you--I can find a job elsewhere." (I didn't end up doing the second round of Google interviews because I was offered a job elsewhere, and Google said that it would take a least an additional month to make a hiring decision.) Where I work now, the interviewing process is much more civilized. We send the specs for a small program along with some unit tests, and give the applicant however long they'd like to complete it. It should take a page or two of code and a couple of hours to complete at most. One might worry that people would cheat, but that hasn't been my experience. Most applicants never submit a solution at all. I suspect this is because they couldn't get their solution to pass the unit tests. (What we ask them to do, is not difficult. Anyone who passed a college course in software engineering with a grade better than a C should have absolutely no problem completing the assignment.) So, then some fraction of applicants actually complete the assignment. These submissions show that the vast majority of so-called software engineers -- or at least those who are looking for jobs -- can't code their way out of a paper bag. I.e., most of the submissions are grossly inefficient and hugely over-engineered or under-engineered. Finally, a few of the submissions are passable (rarely do we get a truly excellent solution, which is kind of sad), so we have them come in, and as part of the interview, we'll have them go over their code a bit and explain why they made certain design decisions, etc. If you ask me, this process gives us a much better idea of how someone would perform in the real world of being a software engineer and any amount of coding on a whiteboard ever could.

alok-g 15y ago

A good test to see if interview questions are you are posing to a potential candidate are good ones is to allow the candidate to pose a similar number of interview questions to you. If they can also pose problems that by your own standards you should be able to answer, but aren't, then you are not doing it right (unless you yourself are not a fit for the position under consideration which may very well be because you are in a different position). For some reason, some interviewers start with a belief that they are smarter than the candidate. While any reasonable person would feel that they do not fall in this category, think about how would you actually know if you do (this is not to say that you do fall in this category). The job of a good interviewer is as much to not reject a good candidate as it is to not accept a bad candidate; in both cases thinking of the position under consideration. If you start with this mindset, and by default subject yourself to as much doubt as you are subject the candidate to when her answer does not match your thinking, you are doing great.

JoachimSchipper 15y ago

Mathematician's solution: the entries in Pascal's triangle are combinations (n-over-k), which can be calculated directly: n-over-k = n!/((n - k)!k!). (If you want to be even faster, use Stirling's approximation to the factorial.)

qntm 15y ago
Yes, neatly circumventing all of the clever algorithmic complexity optimisation that the interviewer is apparently looking for, and making this an even worse interview question.

jaimzob 15y ago

The problem with tech interviews is that we tend to debug candidates rather than interview them, which leads to this confrontational, almost antagonistic pop-quiz process. An interview should be a conversation - sure you're trying to ascertain whether the candidate is smart and, most importantly, whether you could stand working with them but it should still be a two-way, human interaction. If you genuinely think that their tech skills aren't good enough then I've found the best test is to give some simple exercise for them to do in their own time, which you can then talk through in the interview. In this way you can set a realistic exercise (as opposed to 'generate me Pascal's triangle') and dedicate more time in the interview to the interesting stuff - 'why did you do this this way?', 'what the complexity of this approach?', 'can we improve that?' etc. How the candidate answers those question are a much better signal of intelligence then how adept he is with a whiteboard.

rickmb 15y ago

No, this isn't "right". It may be right for a specific job with specific skill requirements. I've been programming for over 25 years, and I've never had to solve any problem even remotely like it. I've also worked with dozens of programmers who could easily solve a problem like that, yet couldn't deliver a working application if their live depended on it. Different programming jobs require different skill sets. There is no universal test.

lukes 15y ago
I agree. I think the attribute most important to my job is being able to turn a complex specification into an app with clean architecture, with no two way coupling between components, generally useful parts abstracted away into reusable code, usage of existing open source modules instead of rolling my own where appropriate and so on. I don't think this test would reveal much of that about me. That said, for the first time in my career I was given a test to do and that seemed to be specifically designed to see how well I could architect code and yet I still screwed it up. That might show that I'm a bad programmer, or it might show that it's dangerous to use a short test to generalise about someone's ability. I like to take jobs on a contract basis, that way there's less risk for the clients as they can cut me whenever if it doesn't work. As a result of that the interview process is usually pretty quick and informal and I can show on a day to day basis that I am good at what I do.

sambeau 15y ago

Why don't people pay candidates for a day's work and see how they do? It would be cheaper and a far better indicator of actual potential.

gcp 15y ago
The administrative overhead of doing this would be immense, if it is even legal (at least in my country).

bambax 15y ago

> The second optimization one could make is that since f(r, i) == f(r, i-1) + f(r, i) then to calculate f(r, i) you only need to calculate up to the i'th element of each row. You actually only need to calculate up to the i'th element of the row you want. The Wikipedia page about Pascal's triangle [1] teaches us that it's possible to calculate a row directly (without any knowledge of other rows). Therefore we can do this: #!/usr/bin/python for row in xrange(200): curr = [1] vc = 1 for c in xrange(1, row/2+1): vc = int(vc * (row+1-c)/float(c)) curr.append(vc) curr.extend(curr[::-1]) print curr (And of course since each line is symmetrical we only need to compute half of it). This version is only a little faster than the last one provided by the author, but for some reason it's much more consistent, time-wise. For 200 rows it stays between 250-330ms between runs, whereas the author's last version is between 300-550ms. And with a little modification, this version will let us compute any row much more efficiently than starting at the first row every time. [1]: http://en.wikipedia.org/wiki/Pascals_triangle http://en.wikipedia.org/wiki/Pascals_triangle PS: There may be a more efficient way to calculate vc (Cell Value) than using int() and float(), but I don't really know Python so that's the best I can do ;-)

cruise02 15y ago

I think a lot of people here are missing the point that this is only one interview question, not the entire interview. You still need to ask icebreaker questions about the candidates experience to get them comfortable before breaking out a whiteboard question, and you should still follow up a "stock" question like this with a more specific question taken from your domain (if they make it that far). I'd also add that you need to have several of these "stock" whiteboard questions on hand. If the interviewee seems to get the solution too easily, they may have heard the question before. Everyone knows FizzBuzz by now, and I gave three answers to "compute the nth Fibonacci number" at my last interview. These questions are no good anymore if you're trying to see how a candidate thinks on their feet.

jrockway 15y ago

I think this problem is a great interview question. It's easy to describe, and it's easy to get started solving it by writing the first few lines on the whiteboard. From there, the pattern should be obvious, and once you've recognized the pattern, you only need to write a few lines of code. The disadvantage is that someone might remember Pascal's triangle from high school math, and will try to "remember" the answer instead of actually solving the problem incrementally. This is worthless because the question is about problem solving ability rather than your memory of exam questions like "Expand (x+3)^27" or "Factor x^3 + 3x^2y + 3xy^2 + y^3". (I do remember writing Pascal's triangle on these sorts of exams, incidentally!) Anyway, reading the other comments in the thread, it seems I am alone in liking this sort of question. I think these types of questions are good indicators of programmer quality. Anyone can read a Ruby on Rails tutorial and make an application that stores some records in a database. It doesn't take understanding to do that, it takes practice. That's all very good, as long as you're sure that your work will only be repeating what you've practiced rather than developing new skills. I think that programming work is very rarely like that. Yes, your job involves Ruby on Rails, but it's largely about solving some sort of complicated problem and then hooking the answer into your UI. Your experience with Rails will speed up the UI work, but if you aren't willing to understand and solve problems, you'll never have anything to put in the UI. (The people that can only do the UI part are "code monkeys" and don't get paid very well.) If you think that you'll never need to understand problem X, it's simply because you are unwilling to understand problem X. Once you understand graphs and algorithms and data structures, you'll see how you can apply your understanding to write better software. You might not think they're very important, but that's because, right now, you have no idea of how those techniques might be important. Learn them and then come back and say "everything in CS class is garbage". You won't, because it's not. Your job will be easier and you won't be navigating the waters blind. So I guess my point is: algorithm questions are good. There are a lot of programmers who can't solve problems (but can monkey code), and if you want the best programmers, you want the ones who can both solve problems AND write code.