9 ms·

Typical programming interview questions.

147 points by gaiusparx 16y ago

wh-uws 16y ago
This is a great resource but lists like these without the accompanying answers are always frustrating to me. I would like a way to be able to check that I am right.
- Symbol 16y ago
  It bears repeating: good interview(er)s will try to determine how you think, not your end result. I do a decent amount of interviews (maybe 2-3 a month), and we by and large are looking for people who can think through a problem, defend a solution, ask good questions, not give up, and appear to be cool to work with. That's it. Some of these questions are great, fundamental CS stuff that I would expect any engineer to have in their back pocket, but some are trivia. Trivia is great, but if you dont't know it I wouldn't hold it against you. I guess my point is to relax. If you thought about some of these things and answered them, great. You're better prepared for next time. Memorizing answer sheets doesn't help in the long run
  - rimantas 16y ago
    > good interview(er)s will try to determine how you think, I can say up front: I don't usually do my thinking at the interviews.
    - sh4na 16y ago
      Oh, if only I could upvote a million times...
  - sown 16y ago
    But doesn't all this imply that I have to get the answer at least right?
    - RiderOfGiraffes 16y ago
      No. good wrong answers are just as valuable in seeing your thought processes in action. This, of course, assumes a good interviewer. If you're dealing with HR-type people then you're screwed anyway unless you play buzzword-bingo.
orijing 16y ago
From the link: What is the next line in the following sequence: 1 11 21 Answer: it's 1211 and the next is 111221 Why would 31 and 41 be illogical answers? I understand where 1211 comes from, but 31 and 41 are totally logical IMO. It's a linear function that goes up by 10.
- patio11 16y ago
  All problems of the form "Provide the next number of this sequence" are attempts to demonstrate that you think, or are capable of thinking, in a fashion similar to the way the decisionmaker thinks. 31 is a totally reasonable answer to that question, mathematically. So is pi. So is "zebra". (The question was "Provide the traditional lexicographic sorting in English of the elements zebra, one, twenty one, and eleven, except o comes before e.") The reason that 31 is not a good answer in terms of securing a job is because your decisionmaker prides himself on being intelligent and he does not see arithmetic sequences as being sufficiently impressive. The reason pi is not a good answer is, despite there being uncountably many mathematical phenomena for which {1, 11, 21, pi} are correct answers, it is insufficiently elegant/tricky for what he has in mind.
  - lkozma 16y ago
    I agree about 31 but not necessarily about zebra or pi. A reasonably meaningful metric is compressibility of the sequence, or how short code could produce it. Although that just opens a different can of worms, it could be argued that 31,41 is better solution than the one given in answer in OP which is better than pi or zebra.
    - patio11 16y ago
      That is begging the question -- it moves the "I am totally winging this because it makes me feel superior" from the "prefer 'elegant' answers" to "prefer 'elegant' languages for writing compressed descriptions of problems". A rigorous program expressing the sequences to which "pi" and "zebra" are the next answers takes only 0 bits and 1 bits respectively to compress in Patio11, a pedantic language created purely for the purpose of this post. It is far more rigorous than either English or C-style pseudocode, has a well-defined grammar, and could have an interpreter written in any common programming language that would fit on the side of a business card. I stick with the original contention: any problem of this nature is about either identifying birds of a feather or lording one's intellectual superiority over the candidate.
huhtenberg 16y ago
There is a lesser known variation of "find a cycle in a linked list". Given a function int f(int arg); that returns a value computed solely from arg, find the length of the repeating sequence in f(x), f(f(x)), f(f(f(x))), ... The primary use is determining the period of a state-less PRNG such as a linear congruential one.
- psykotic 16y ago
  > There is a lesser known variation of "find a cycle in a linked list" There's also a lesser known alternative to Floyd's tortoise-and-hare algorithm called Brent's algorithm. It's a little faster in practice, but more importantly it represents an algorithm design technique that everyone should know.
  - RiderOfGiraffes 16y ago
    See http://news.ycombinator.com/item?id=1068715 http://news.ycombinator.com/item?id=1068715 for a lot of discussion on this.
akavlie 16y ago
What sort of programming positions? I've done a fair amount of web development in PHP & Python (as well as introductory C++ & Java). I had to look up "linked list" on Google just to get some understanding of what that is.
- deleted 16y ago
  [deleted]
- naner 16y ago
  A linked list is a pretty elementary data structure. That being said, these questions seem like they're for a job writing client software on Windows some time before .NET existed.
  - Stormbringer 16y ago
    No, even in VB you wouldn't do that. Of course, way back in the dark ages when I wrote VB for client Windows apps I was all "lets keep this nice and simple, nice and simple.... arrrrrrghhh, why doesn't this POS language do what I want?! HULK SMASH", and then I'd break out the Win32 APIs and hit it with the big guns. I feel a little sorry for the 'normal' VB programmers, because they'd be following my code and then BLAM it'd disappear into hyperspace, and re-emerge and something magical† would have happened. †Read as: a sufficiently advanced technology
    - Vivtek 16y ago
      Ha! Fond, fond memories of VB for Word 6.0.
  - xiongchiamiov 16y ago
    It's worth noting that Python has just one linear structure - lists* (Ruby avoids lists and just has arrays). Now, they're actually much fancier under the hood, which is why you can get away with not having a bunch of choices, but it's the approach of "Oh hey, I want to store a bunch of stuff in a sequence of some sort - why should it matter how that's implemented?". Now, I happen to agree with you that it's important to know how a basic linked list works. Beyond that, though, is far less important to some people than others. * Okay, I lied. Halfway through writing this I remembered tuples (duh!), and I'm sure someone is going to point out several other things I've missed.
AndrewMoffat 16y ago
Well, I feel pretty stupid now.
- smcl 16y ago
  Yep, me too. I'm pretty nervous at interviews already, so I reckon I'd melt down if I was presented with some of the questions without having vaguely prepared. But I suppose that's why the page is there, not so we can feel stupid but so we can re-engage that "solve arbitrary problem X" mentality.
- Stormbringer 16y ago
  Problem is, when would you ever do any of that in the real world? Has anybody ever needed to reverse a string in place since the 80s? (Demo scene excluded of course, they swallowed a different colour pill from the rest of us) I'm aware for instance of the XOR trick to swap to variables in place. I think I used it once in the last ~20 years, and really only then because I was being pleased with my excessive cleverness. These days I wouldn't bother, because it would just make the code fractionally harder to read, it makes for a speed-bump for the mind, whereas spelling it out with a temporary variable lets your brain keep cruising at interstate speeds.
panic 16y ago
You may be asked about using Unicode strings. What the interviewer is usually looking for is: - each character will be two bytes (so, for example, char lookup table you may have allocated needs to be expanded from 256 to 256 x 256 = 65536 elements) - that you would need to use wide char types (wchar_t instead of char) - that you would need to use wide string functions (like wprintf instead of printf) Unicode support involves more than just the minimum number of bits used per character. Say you're writing a method to truncate a string to a certain length. What if your text contains a code point outside the basic multilingual plane, and each character can't be represented in just 16 bits? If you truncate in the middle of a character, the result will be an invalid string. What about combining characters? If you truncate in the middle of a combining character sequence, you'll end up with half-formed output (e.g., letters missing a diacritic). If you work with text, you should know this stuff!
- WildUtah 16y ago
  The OP is a page from 2002 (or possibly 1902; didn't people remember Y2K back then?), so I expect the recent new code points beyond U+65535 were still outside the imagination of potential interviewers.
  - panic 16y ago
    The higher planes were added in 2001 with Unicode 3.1: http://unicode.org/reports/tr27/tr27-4.html http://unicode.org/reports/tr27/tr27-4.html
    - Stormbringer 16y ago
      These things normally take time to trickle down to us lesser mortals. I suggest a high level circle of protection and an astral binding. :D
      - voidpointer 16y ago
        This little thread illustrates nicely that the smart thing to do is not to implement list or string functions yourself but to use a library that has been tried and tested. Spend your brain cycles on the important stuff. I find it much more interesting to ask people when and why they would choose a linked or an array/buffer based list...
darkxanthos 16y ago
"You are given an array with integers between 1 and 1,000,000. One integer is in the array twice. How can you determine which one?" Sum(Array) - 1000000(1000000 + 1)/2 = X For the other part it's just 1000000(1000000 + 1)/2 - Sum(Array) = Y EDIT: n*(n+1)/2 is the formula for the sum of the numbers from 1 to n
- raptrex 16y ago
  For finding the duplicate integer, I'm kind of lost. Say you have an array: 1,1,2,3,4. According the the equation: 11 - 5(6)/2 = -4?
  - darkxanthos 16y ago
    11 - 4*(4+1)/2 = 11 - 10 = 1 n is not an index... it's the last number. I wasn't explicit, sorry. :)
  - Stormbringer 16y ago
    it is based on the formula (n^2 + n)/2 picture it like finding the area of a trinagle that is half of a square (long side goes from diagonally opposite corners) formula for area of a square is n^2, so we need half that. What about +n part of it? It is because we are dealing in discrete chunks, not smoothly continuous. --- Alternately, imagine a series of children's blocks 1 2 3 now we have a 'triangle' with left side 3 high and bottom 3 wide. IF we make an identical triangle and rotate it round so that they fit together to make a rectangle, it looks like this 1 + 3 2 + 2 3 + 1 This makes a rectangle 3 x 4, and we should be able to figure out that this gives us an area of 12. So the original triangle ( 1,2,3 ) gives us half that and thus the sum from 1 to 3 is 6. So the pattern for summing the numbers 1 through N is to take a square of length N, add 1 to one of its sides, so it has sides of length N and N+1, and then find the area (which is always N^2 + N) and then halve that.
- JeanPierre 16y ago
  This function would be good if you know that all other integers are in the array once. However, this isn't elaborated within the question. A perfectly legal array with the restrictions we've been given is this: [1, 3, 3, 9, 42] All numbers in the array are integers between 1 and 1,000,000, and one integer is in the array twice. As for the solution, allocate 1,000,000 bits and do a "bucket sort". If the next number in the array is n, check if the nth bit is 1. If it is, you've found the integer appearing twice. If the nth bit is 0, change it to 1 and continue.
oniTony 16y ago
At top-tier software companies, expect all of the (applicable) questions to be accompanied by the "and what is the runtime complexity of your solution" followup question. Depending on your abilities, the interviewer will try to lead you towards an optimal solution.
dlevine 16y ago
I HATE interview questions that ask the candidate to write some trivial piece of code. Particularly the ones that need to be written in C to give an optimal answer "if you just do pointer math, this would be trivial..." Not to say that some good candidates won't be excellent at C coding, but these problems often test for specific knowledge, when they should be screening for critical thinking skills. I've seen candidates who were "good" at this sort of problem (probably because it was on a CS homework in College), but didn't have much in the way of critical reasoning skills. I prefer asking questions that require them to devise some sort of algorithm to solve a problem (typically by walking through the situation methodically), and then implement that algorithm in the language of their choice. No real ahas or tricks, and I don't care if you write it in Python or Assembler...
djhworld 16y ago
I think a lot of these questions don't really reflect what someone will be doing in their real job. It's more of a "how much do you remember from your CS degree" test that has little relevance to your job duties of maintaining some monolithic Java based enterprise platform. I mean come on, Binary Trees? I know what a Binary tree is but I'd have to look up the definitions of all the traversal types because there's no way I'd be able to remember what Post/Pre/In Order traversals actually entail. And this question is an absolute abomination: - What is the next line in the following sequence: 1 11 21 Answer: it's 1211 and the next is 111221 That's a joke right? I'd personally answer 31 to this question.
- Stormbringer 16y ago
  It's to identify those that have 'architect potential'. If you pick the simple, easy to implement and blindingly obvious answer you don't make the cut, sorry. :D
  - Deestan 16y ago
    "I can complicate this. I know I can!"
    - Stormbringer 16y ago
      Easy, just add a layer of indirection. Then carpet bomb it back into the dark ages with patterns. :D
- deleted 16y ago
  [deleted]
- cheald 16y ago
  I hate being given questions with ambiguity and not enough context to answer them, and then getting it "wrong". It's fine if you want to test my thinking processes, but make the question about listing my assumptions and reasoning rather than expecting a single empirically-derived answer. The next item in the sequence could justifiably be 31, or 1111, or 121, or 0004, or 100. Given an ambiguous question, I'm going to take the less clever answer which is more readily supported by the most common assumptions (y = (x-1) * 10 + 1, as the problem appears to be presented as a numeric sequence and the entire world counts in base 10). In programming, any undocumented assumptions should be blindingly obvious. Anyone that works on a system with unobvious and undocumented assumptions is playing software Russian roulette. If the kind of person you want to hire is the kind of person who comes up with unobvious, esoteric solutions to problems, I'm not sure I want to be working on your software team anyhow.
jasonjei 16y ago
These questions remind me of the time when I took AP Computer Science AB, many years ago (10 years ago to be exact Freshman year). To be honest, many of these concepts are good to know, but I find a much more useful test is to test them on something that they probably haven't used before, especially a technology that you use in your project. For instance, our project uses a good deal of Jabber, so we test our applicants if they can write a program to act as a bot responding to the Jabber message "ping" with "pong." It tests their ability to develop rapidly and to justify their choice of a library and how fast they can pickup our technology. It's been a great filter as well as a useful test to see if they can assemble a solution on their own. Even non-working solutions work well for us because we can examine their thought process. Asking them to develop a sort solution isn't useful for us as much as seeing if they can develop code relevant to the components we use--because, let's face it; you aren't going to be writing your own string class from scratch, but it is good to know how one works. And in our case, they'll learn about XMPP/Jabber if successful--and it will test to see if they are willing to learn. Seeing which library they use is also interesting, because it tests their system design skills, and in some cases, will indicate if they can make good design decisions. But if we do have doubts about them being able to assemble a program, we will test them computer science questions, but in the meantime, we want to see if they can engineer a solution. But if you are looking for a low-level programmer to develop you a compiler from scratch, maybe these are the right questions to ask. But we don't expect our applicants to build a hammer; we want them to know how it works, but we don't expect them to build us one. I guess if we need a hammer maker, we will find one, but if we need an applications programmer, we will have them use the hammer. Just like your engineer knows how a spectrum analyzer works, but won't be expected to build one. Unless you are hiring them to do that.
- daleharvey 16y ago
  that test is quite funny considering maintaining an irc connection needs you to respond with a pong from pings, and xmpp doesnt
barmstrong 16y ago
I'm surprised that these are commonly asked and I'm guessing these aren't for a position building web apps. Most of these are distant memories from a CS degree and rarely used concepts in the word of y-combinator startups where Ruby and Python are common. I think people building web apps look more for developers who write maintainable code, design good user interfaces, write good tests, make cross browser solutions, etc. These would be nice to have but too low level for everyday use at most startups.
paulitex 16y ago
Github (and similar evidence of actual abilities) are already making questions like these extinct, thank god. Reading through a single project an applicant has written themselves is immensely more informative than these silly CS brain teasers: actual solutions to actual problems, style & documentation habits, testing practices, evidence of being able to code & ship, being a self starter, etc... Classic example of actions speak louder than words. Thankfully the technology is now in place so that resumes can be replaced with coding community profiles, and interviews can focus on filling in the blanks and assessing the compatibility of the applicant as a person.
- askedrelic 16y ago
  Are Github and open source projects turning programmers toward a portfolio based resume? I've had success in interviews initially linking to my github repo and letting the interviewer view for themselves what I can accomplish. It has been a good diving board when you start talking in person.
- tocomment 16y ago
  Yeah except Interviewers assume by default that you don't know how to program and you somehow cheated and got someone else to write your open source project.
- synnik 16y ago
  While I'd love to agree, reading someone's code does not tell you: 1) If they actually wrote all of it, or if it derivative of someone else's work. 2) Whether any particular function took them 10 minutes or 10 hours. 3) What options they considered when choosing how to architect a particular solution. 4) Why they made any particular choice in their solutions. 5) Whether or not they will fit on your team, take constructive criticism, etc. The questions posed in the article don't give you those answers either, but the applicant's speed at answering, their confidence, they demeanor as you ask further questions and discuss answers... all that communication does answer most of the above questions.
  - raganwald 16y ago
cfhjtykty 16y ago
Click on our website: http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com The website wholesale various fashion shoes, such as Nike, Jordan, prada, also includes the jeans, shirt, bags, hats and decoration. All these products are our free transport, prices are competitive, we can also accept paypal j, after the payment within short time, can ship. Air jordan(1-24)shoes $30 Handbags(Coach l v f e n d i d&g) $35 Tshirts (Polo ,ed hardy,lacoste) $15 Jean(True Religion,ed hardy,coogi) $30 Sunglasses(Oakey,coach,gucci,A r m a i n i) $15 New era cap $12 Bikini (Ed hardy,polo) $20 accept paypal and free shipping http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com
Stormbringer 16y ago
"You have 2 supposedly unbreakable light bulbs and a 100-floor building. Using fewest possible drops, determine how much of an impact this type of light bulb can withstand. (i.e. it can withstand a drop from 17th floor, but breaks from the 18th). Note that the ever-popular binary search will give you a worst case of 50 drops. You should be able to do it with under 20." Maybe there's something I don't understand, because my reaction to that question was "lolwut?" In that scenario, with a binary search you drop from the 50th, 25th, 13th, 19th, 16th, 17th and 18th floors. By my back of the postage stamp calculations you need to do (log N) + 1 drops... My question: how did they get a number of 50 for binary search??? Is it because you're limited to 2 failures? And by 'binary search' they mean something like start at floor 2 and drop, if it is still intact go to floor 4 and then drop it, if it breaks you don't know about floor 3, so you have to use the remaining one to check that. That's not binary search, that's linear. To do it in 20 or less drops you could drop it from the 20th floor, and if it smashes, go to floor 1 and start going up in increments of 1. Otherwise go to floor 39 and drop it (etc). But that makes me think it is not the best for that starting number, we can do better. Just pull out the good old (n^2 + n)/2 formula again and the first one in that progression that ticks over the 100 threshold is 14. So we drop it at floor 14 first, if it breaks then start from floor 1 and go up. Otherwise go up 13 floors and repeat... Our major floor increments are 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99. I'm not sure if there is a better solution, if you have one, feel free to chip in. :D
- protothomas 16y ago
  Even if the lightbulbs are breakable I think you would need a maximum of (2√n)-1 drops - i.e. go up in increments of √n then when it breaks work forward from the previous drop.
  - Stormbringer 16y ago
    That must be where they get the 20 figure from. My way has a shorter worst case even than that though, 14 vs 19
- NickPollard 16y ago
  Yes, it's because it's limited to two failures. If you drop the first bulb at floor 50 and it breaks, you have only one bulb left, so you MUST not break it until you have limited the possible range to 1, so you have to just incrementally test 1, 2, 3, 4, etc. If you went straight to floor 25 and it broke, all you know is 0 < x < 25, and you have no bulbs left.
Vlasta 16y ago
If I were given questions like these, I would politely refuse to answer them explaining they have nothing to do with the important things a typical software developer does. Having a solid portfolio of past successful projects to demonstrate your abilities (including participation in a open source development) is way safer than being able to solve artificial problems.
- synnik 16y ago
  And we would politely end the interview and not call you back. Questions like these are not made to decide who to hire -- They are made to establish a base level of competence. The ability to answer these questions does not prove anything. However, the INABILITY to answer these questions says quite a lot. So you gotta ask.
smikhanov 16y ago
The bottom line here is that though today's interviewers' repertoire is a little bit different, it only takes a small practice to excel in the questions they ask. Author seem to make the same point. Usual comments from "ninjas" in this thread are very amusing though.
raganwald 16y ago
> The interviews were pretty evenly split between very large, large, and startup-sized tech companies. Really? One person is looking for a job in a big company or a startup?? One of the most common programmer interview questions is What type of job are you looking for? I suspect that "Oh, I don't know, maybe cubicle dweller in BigCo, but then again a startup might be fun" is not the best answer, and describing each company as being your ideal destination is dishonest. Then again, another possibility is that he looked for a startup job, and when he couldn't find the right spot he tried some medium sized companies, and so on. That might make sense in an interview: "I was really interested in exploring a startup, but when I actually looked into it I realized it was far more romantic in theory than it was practical. I like the idea of writing great software, but it turns out that the companies I met with aren't very committed to some of the best practices that interest me." So I won't jump to conclusions about the OP, but certainly I am interested in hearing what chain of events led to what appears to be a wide spread of environments.
- fjh 16y ago
  I honestly don't think that everyone cares about the size of the company they're working for. I'm currently applying for internships for this summer and I am far more interested in what kind of work I could be doing than how big the company is. I don't think that's uncommon.
  - raganwald 16y ago
    I know that many people don't care about the size of the company they're working for, but turn it around: Do you think that employers care about whether an applicant cares? To make this perfectly clear, let me propose this interview question: What is more important to you: The company and culture or the work that you'll be doing? I think that people being people, they will prefer applicants who honestly are more interested in the company and culture than the work. This is absolutely true of BigCo, and applies to startups as well. What if the company needs to pivot and you are no longer working on whatever excited you about coming to work on day zero? Will you start looking for somewhere else?
wulf 16y ago
These sequence questions drive me up the wall. It's so unbelievably stupid that out of the near infinite functions that can produce a given list you should come up with the one the interviewer thought was the "obviously correct" one. The sequence in the example: 1, 11, 21, x ... with the information given then the X=31 is just as valid as anything that the interviewer came up with.
- obitoo 16y ago
  yes of course thats a valid reply; the next question they'll ask you is "Can you think of another one?" and try to steer you towards it.
tszming 16y ago
I also recommend the book "Programming Interviews Exposed", it contains the absolute minimum every software developer must know about...
Hominem 16y ago
All this is still useful. I have to fix code all the time where the original developer paid no attention to complexity and a algorithm that was fast with the 10 items they tested with is dog slow once it makes it to production and there are 10,000 items.

147 points by gaiusparx 16y ago

This is a great resource but lists like these without the accompanying answers are always frustrating to me. I would like a way to be able to check that I am right.

Symbol 16y ago
It bears repeating: good interview(er)s will try to determine how you think, not your end result. I do a decent amount of interviews (maybe 2-3 a month), and we by and large are looking for people who can think through a problem, defend a solution, ask good questions, not give up, and appear to be cool to work with. That's it. Some of these questions are great, fundamental CS stuff that I would expect any engineer to have in their back pocket, but some are trivia. Trivia is great, but if you dont't know it I wouldn't hold it against you. I guess my point is to relax. If you thought about some of these things and answered them, great. You're better prepared for next time. Memorizing answer sheets doesn't help in the long run
- rimantas 16y ago
  > good interview(er)s will try to determine how you think, I can say up front: I don't usually do my thinking at the interviews.
  - sh4na 16y ago
    Oh, if only I could upvote a million times...
- sown 16y ago
  But doesn't all this imply that I have to get the answer at least right?
  - RiderOfGiraffes 16y ago
    No. good wrong answers are just as valuable in seeing your thought processes in action. This, of course, assumes a good interviewer. If you're dealing with HR-type people then you're screwed anyway unless you play buzzword-bingo.

orijing 16y ago

From the link: What is the next line in the following sequence: 1 11 21 Answer: it's 1211 and the next is 111221 Why would 31 and 41 be illogical answers? I understand where 1211 comes from, but 31 and 41 are totally logical IMO. It's a linear function that goes up by 10.

patio11 16y ago
All problems of the form "Provide the next number of this sequence" are attempts to demonstrate that you think, or are capable of thinking, in a fashion similar to the way the decisionmaker thinks. 31 is a totally reasonable answer to that question, mathematically. So is pi. So is "zebra". (The question was "Provide the traditional lexicographic sorting in English of the elements zebra, one, twenty one, and eleven, except o comes before e.") The reason that 31 is not a good answer in terms of securing a job is because your decisionmaker prides himself on being intelligent and he does not see arithmetic sequences as being sufficiently impressive. The reason pi is not a good answer is, despite there being uncountably many mathematical phenomena for which {1, 11, 21, pi} are correct answers, it is insufficiently elegant/tricky for what he has in mind.
- lkozma 16y ago
  I agree about 31 but not necessarily about zebra or pi. A reasonably meaningful metric is compressibility of the sequence, or how short code could produce it. Although that just opens a different can of worms, it could be argued that 31,41 is better solution than the one given in answer in OP which is better than pi or zebra.
  - patio11 16y ago
    That is begging the question -- it moves the "I am totally winging this because it makes me feel superior" from the "prefer 'elegant' answers" to "prefer 'elegant' languages for writing compressed descriptions of problems". A rigorous program expressing the sequences to which "pi" and "zebra" are the next answers takes only 0 bits and 1 bits respectively to compress in Patio11, a pedantic language created purely for the purpose of this post. It is far more rigorous than either English or C-style pseudocode, has a well-defined grammar, and could have an interpreter written in any common programming language that would fit on the side of a business card. I stick with the original contention: any problem of this nature is about either identifying birds of a feather or lording one's intellectual superiority over the candidate.

huhtenberg 16y ago

There is a lesser known variation of "find a cycle in a linked list". Given a function int f(int arg); that returns a value computed solely from arg, find the length of the repeating sequence in f(x), f(f(x)), f(f(f(x))), ... The primary use is determining the period of a state-less PRNG such as a linear congruential one.

psykotic 16y ago
> There is a lesser known variation of "find a cycle in a linked list" There's also a lesser known alternative to Floyd's tortoise-and-hare algorithm called Brent's algorithm. It's a little faster in practice, but more importantly it represents an algorithm design technique that everyone should know.
- RiderOfGiraffes 16y ago
  See http://news.ycombinator.com/item?id=1068715 http://news.ycombinator.com/item?id=1068715 for a lot of discussion on this.

akavlie 16y ago

What sort of programming positions? I've done a fair amount of web development in PHP & Python (as well as introductory C++ & Java). I had to look up "linked list" on Google just to get some understanding of what that is.

deleted 16y ago
[deleted]
naner 16y ago
A linked list is a pretty elementary data structure. That being said, these questions seem like they're for a job writing client software on Windows some time before .NET existed.
- Stormbringer 16y ago
  No, even in VB you wouldn't do that. Of course, way back in the dark ages when I wrote VB for client Windows apps I was all "lets keep this nice and simple, nice and simple.... arrrrrrghhh, why doesn't this POS language do what I want?! HULK SMASH", and then I'd break out the Win32 APIs and hit it with the big guns. I feel a little sorry for the 'normal' VB programmers, because they'd be following my code and then BLAM it'd disappear into hyperspace, and re-emerge and something magical† would have happened. †Read as: a sufficiently advanced technology
  - Vivtek 16y ago
    Ha! Fond, fond memories of VB for Word 6.0.
- xiongchiamiov 16y ago
  It's worth noting that Python has just one linear structure - lists* (Ruby avoids lists and just has arrays). Now, they're actually much fancier under the hood, which is why you can get away with not having a bunch of choices, but it's the approach of "Oh hey, I want to store a bunch of stuff in a sequence of some sort - why should it matter how that's implemented?". Now, I happen to agree with you that it's important to know how a basic linked list works. Beyond that, though, is far less important to some people than others. * Okay, I lied. Halfway through writing this I remembered tuples (duh!), and I'm sure someone is going to point out several other things I've missed.

AndrewMoffat 16y ago

Well, I feel pretty stupid now.

smcl 16y ago
Yep, me too. I'm pretty nervous at interviews already, so I reckon I'd melt down if I was presented with some of the questions without having vaguely prepared. But I suppose that's why the page is there, not so we can feel stupid but so we can re-engage that "solve arbitrary problem X" mentality.
Stormbringer 16y ago
Problem is, when would you ever do any of that in the real world? Has anybody ever needed to reverse a string in place since the 80s? (Demo scene excluded of course, they swallowed a different colour pill from the rest of us) I'm aware for instance of the XOR trick to swap to variables in place. I think I used it once in the last ~20 years, and really only then because I was being pleased with my excessive cleverness. These days I wouldn't bother, because it would just make the code fractionally harder to read, it makes for a speed-bump for the mind, whereas spelling it out with a temporary variable lets your brain keep cruising at interstate speeds.

panic 16y ago

You may be asked about using Unicode strings. What the interviewer is usually looking for is: - each character will be two bytes (so, for example, char lookup table you may have allocated needs to be expanded from 256 to 256 x 256 = 65536 elements) - that you would need to use wide char types (wchar_t instead of char) - that you would need to use wide string functions (like wprintf instead of printf) Unicode support involves more than just the minimum number of bits used per character. Say you're writing a method to truncate a string to a certain length. What if your text contains a code point outside the basic multilingual plane, and each character can't be represented in just 16 bits? If you truncate in the middle of a character, the result will be an invalid string. What about combining characters? If you truncate in the middle of a combining character sequence, you'll end up with half-formed output (e.g., letters missing a diacritic). If you work with text, you should know this stuff!

WildUtah 16y ago
The OP is a page from 2002 (or possibly 1902; didn't people remember Y2K back then?), so I expect the recent new code points beyond U+65535 were still outside the imagination of potential interviewers.
- panic 16y ago
  The higher planes were added in 2001 with Unicode 3.1: http://unicode.org/reports/tr27/tr27-4.html http://unicode.org/reports/tr27/tr27-4.html
  - Stormbringer 16y ago
    These things normally take time to trickle down to us lesser mortals. I suggest a high level circle of protection and an astral binding. :D
    - voidpointer 16y ago
      This little thread illustrates nicely that the smart thing to do is not to implement list or string functions yourself but to use a library that has been tried and tested. Spend your brain cycles on the important stuff. I find it much more interesting to ask people when and why they would choose a linked or an array/buffer based list...

darkxanthos 16y ago

"You are given an array with integers between 1 and 1,000,000. One integer is in the array twice. How can you determine which one?" Sum(Array) - 1000000(1000000 + 1)/2 = X For the other part it's just 1000000(1000000 + 1)/2 - Sum(Array) = Y EDIT: n*(n+1)/2 is the formula for the sum of the numbers from 1 to n

raptrex 16y ago
For finding the duplicate integer, I'm kind of lost. Say you have an array: 1,1,2,3,4. According the the equation: 11 - 5(6)/2 = -4?
- darkxanthos 16y ago
  11 - 4*(4+1)/2 = 11 - 10 = 1 n is not an index... it's the last number. I wasn't explicit, sorry. :)
- Stormbringer 16y ago
  it is based on the formula (n^2 + n)/2 picture it like finding the area of a trinagle that is half of a square (long side goes from diagonally opposite corners) formula for area of a square is n^2, so we need half that. What about +n part of it? It is because we are dealing in discrete chunks, not smoothly continuous. --- Alternately, imagine a series of children's blocks 1 2 3 now we have a 'triangle' with left side 3 high and bottom 3 wide. IF we make an identical triangle and rotate it round so that they fit together to make a rectangle, it looks like this 1 + 3 2 + 2 3 + 1 This makes a rectangle 3 x 4, and we should be able to figure out that this gives us an area of 12. So the original triangle ( 1,2,3 ) gives us half that and thus the sum from 1 to 3 is 6. So the pattern for summing the numbers 1 through N is to take a square of length N, add 1 to one of its sides, so it has sides of length N and N+1, and then find the area (which is always N^2 + N) and then halve that.
JeanPierre 16y ago
This function would be good if you know that all other integers are in the array once. However, this isn't elaborated within the question. A perfectly legal array with the restrictions we've been given is this: [1, 3, 3, 9, 42] All numbers in the array are integers between 1 and 1,000,000, and one integer is in the array twice. As for the solution, allocate 1,000,000 bits and do a "bucket sort". If the next number in the array is n, check if the nth bit is 1. If it is, you've found the integer appearing twice. If the nth bit is 0, change it to 1 and continue.

oniTony 16y ago

At top-tier software companies, expect all of the (applicable) questions to be accompanied by the "and what is the runtime complexity of your solution" followup question. Depending on your abilities, the interviewer will try to lead you towards an optimal solution.

dlevine 16y ago

I HATE interview questions that ask the candidate to write some trivial piece of code. Particularly the ones that need to be written in C to give an optimal answer "if you just do pointer math, this would be trivial..." Not to say that some good candidates won't be excellent at C coding, but these problems often test for specific knowledge, when they should be screening for critical thinking skills. I've seen candidates who were "good" at this sort of problem (probably because it was on a CS homework in College), but didn't have much in the way of critical reasoning skills. I prefer asking questions that require them to devise some sort of algorithm to solve a problem (typically by walking through the situation methodically), and then implement that algorithm in the language of their choice. No real ahas or tricks, and I don't care if you write it in Python or Assembler...

djhworld 16y ago

I think a lot of these questions don't really reflect what someone will be doing in their real job. It's more of a "how much do you remember from your CS degree" test that has little relevance to your job duties of maintaining some monolithic Java based enterprise platform. I mean come on, Binary Trees? I know what a Binary tree is but I'd have to look up the definitions of all the traversal types because there's no way I'd be able to remember what Post/Pre/In Order traversals actually entail. And this question is an absolute abomination: - What is the next line in the following sequence: 1 11 21 Answer: it's 1211 and the next is 111221 That's a joke right? I'd personally answer 31 to this question.

Stormbringer 16y ago
It's to identify those that have 'architect potential'. If you pick the simple, easy to implement and blindingly obvious answer you don't make the cut, sorry. :D
- Deestan 16y ago
  "I can complicate this. I know I can!"
  - Stormbringer 16y ago
    Easy, just add a layer of indirection. Then carpet bomb it back into the dark ages with patterns. :D
deleted 16y ago
[deleted]
cheald 16y ago
I hate being given questions with ambiguity and not enough context to answer them, and then getting it "wrong". It's fine if you want to test my thinking processes, but make the question about listing my assumptions and reasoning rather than expecting a single empirically-derived answer. The next item in the sequence could justifiably be 31, or 1111, or 121, or 0004, or 100. Given an ambiguous question, I'm going to take the less clever answer which is more readily supported by the most common assumptions (y = (x-1) * 10 + 1, as the problem appears to be presented as a numeric sequence and the entire world counts in base 10). In programming, any undocumented assumptions should be blindingly obvious. Anyone that works on a system with unobvious and undocumented assumptions is playing software Russian roulette. If the kind of person you want to hire is the kind of person who comes up with unobvious, esoteric solutions to problems, I'm not sure I want to be working on your software team anyhow.

jasonjei 16y ago

These questions remind me of the time when I took AP Computer Science AB, many years ago (10 years ago to be exact Freshman year). To be honest, many of these concepts are good to know, but I find a much more useful test is to test them on something that they probably haven't used before, especially a technology that you use in your project. For instance, our project uses a good deal of Jabber, so we test our applicants if they can write a program to act as a bot responding to the Jabber message "ping" with "pong." It tests their ability to develop rapidly and to justify their choice of a library and how fast they can pickup our technology. It's been a great filter as well as a useful test to see if they can assemble a solution on their own. Even non-working solutions work well for us because we can examine their thought process. Asking them to develop a sort solution isn't useful for us as much as seeing if they can develop code relevant to the components we use--because, let's face it; you aren't going to be writing your own string class from scratch, but it is good to know how one works. And in our case, they'll learn about XMPP/Jabber if successful--and it will test to see if they are willing to learn. Seeing which library they use is also interesting, because it tests their system design skills, and in some cases, will indicate if they can make good design decisions. But if we do have doubts about them being able to assemble a program, we will test them computer science questions, but in the meantime, we want to see if they can engineer a solution. But if you are looking for a low-level programmer to develop you a compiler from scratch, maybe these are the right questions to ask. But we don't expect our applicants to build a hammer; we want them to know how it works, but we don't expect them to build us one. I guess if we need a hammer maker, we will find one, but if we need an applications programmer, we will have them use the hammer. Just like your engineer knows how a spectrum analyzer works, but won't be expected to build one. Unless you are hiring them to do that.

daleharvey 16y ago
that test is quite funny considering maintaining an irc connection needs you to respond with a pong from pings, and xmpp doesnt

barmstrong 16y ago

I'm surprised that these are commonly asked and I'm guessing these aren't for a position building web apps. Most of these are distant memories from a CS degree and rarely used concepts in the word of y-combinator startups where Ruby and Python are common. I think people building web apps look more for developers who write maintainable code, design good user interfaces, write good tests, make cross browser solutions, etc. These would be nice to have but too low level for everyday use at most startups.

paulitex 16y ago

Github (and similar evidence of actual abilities) are already making questions like these extinct, thank god. Reading through a single project an applicant has written themselves is immensely more informative than these silly CS brain teasers: actual solutions to actual problems, style & documentation habits, testing practices, evidence of being able to code & ship, being a self starter, etc... Classic example of actions speak louder than words. Thankfully the technology is now in place so that resumes can be replaced with coding community profiles, and interviews can focus on filling in the blanks and assessing the compatibility of the applicant as a person.

askedrelic 16y ago
Are Github and open source projects turning programmers toward a portfolio based resume? I've had success in interviews initially linking to my github repo and letting the interviewer view for themselves what I can accomplish. It has been a good diving board when you start talking in person.
tocomment 16y ago
Yeah except Interviewers assume by default that you don't know how to program and you somehow cheated and got someone else to write your open source project.
synnik 16y ago
While I'd love to agree, reading someone's code does not tell you: 1) If they actually wrote all of it, or if it derivative of someone else's work. 2) Whether any particular function took them 10 minutes or 10 hours. 3) What options they considered when choosing how to architect a particular solution. 4) Why they made any particular choice in their solutions. 5) Whether or not they will fit on your team, take constructive criticism, etc. The questions posed in the article don't give you those answers either, but the applicant's speed at answering, their confidence, they demeanor as you ask further questions and discuss answers... all that communication does answer most of the above questions.
- raganwald 16y ago

cfhjtykty 16y ago

Click on our website: http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com The website wholesale various fashion shoes, such as Nike, Jordan, prada, also includes the jeans, shirt, bags, hats and decoration. All these products are our free transport, prices are competitive, we can also accept paypal j, after the payment within short time, can ship. Air jordan(1-24)shoes $30 Handbags(Coach l v f e n d i d&g) $35 Tshirts (Polo ,ed hardy,lacoste) $15 Jean(True Religion,ed hardy,coogi) $30 Sunglasses(Oakey,coach,gucci,A r m a i n i) $15 New era cap $12 Bikini (Ed hardy,polo) $20 accept paypal and free shipping http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com http://www.etradinglife.com

Stormbringer 16y ago

"You have 2 supposedly unbreakable light bulbs and a 100-floor building. Using fewest possible drops, determine how much of an impact this type of light bulb can withstand. (i.e. it can withstand a drop from 17th floor, but breaks from the 18th). Note that the ever-popular binary search will give you a worst case of 50 drops. You should be able to do it with under 20." Maybe there's something I don't understand, because my reaction to that question was "lolwut?" In that scenario, with a binary search you drop from the 50th, 25th, 13th, 19th, 16th, 17th and 18th floors. By my back of the postage stamp calculations you need to do (log N) + 1 drops... My question: how did they get a number of 50 for binary search??? Is it because you're limited to 2 failures? And by 'binary search' they mean something like start at floor 2 and drop, if it is still intact go to floor 4 and then drop it, if it breaks you don't know about floor 3, so you have to use the remaining one to check that. That's not binary search, that's linear. To do it in 20 or less drops you could drop it from the 20th floor, and if it smashes, go to floor 1 and start going up in increments of 1. Otherwise go to floor 39 and drop it (etc). But that makes me think it is not the best for that starting number, we can do better. Just pull out the good old (n^2 + n)/2 formula again and the first one in that progression that ticks over the 100 threshold is 14. So we drop it at floor 14 first, if it breaks then start from floor 1 and go up. Otherwise go up 13 floors and repeat... Our major floor increments are 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99. I'm not sure if there is a better solution, if you have one, feel free to chip in. :D

protothomas 16y ago
Even if the lightbulbs are breakable I think you would need a maximum of (2√n)-1 drops - i.e. go up in increments of √n then when it breaks work forward from the previous drop.
- Stormbringer 16y ago
  That must be where they get the 20 figure from. My way has a shorter worst case even than that though, 14 vs 19
NickPollard 16y ago
Yes, it's because it's limited to two failures. If you drop the first bulb at floor 50 and it breaks, you have only one bulb left, so you MUST not break it until you have limited the possible range to 1, so you have to just incrementally test 1, 2, 3, 4, etc. If you went straight to floor 25 and it broke, all you know is 0 < x < 25, and you have no bulbs left.

Vlasta 16y ago

If I were given questions like these, I would politely refuse to answer them explaining they have nothing to do with the important things a typical software developer does. Having a solid portfolio of past successful projects to demonstrate your abilities (including participation in a open source development) is way safer than being able to solve artificial problems.

synnik 16y ago
And we would politely end the interview and not call you back. Questions like these are not made to decide who to hire -- They are made to establish a base level of competence. The ability to answer these questions does not prove anything. However, the INABILITY to answer these questions says quite a lot. So you gotta ask.

smikhanov 16y ago

The bottom line here is that though today's interviewers' repertoire is a little bit different, it only takes a small practice to excel in the questions they ask. Author seem to make the same point. Usual comments from "ninjas" in this thread are very amusing though.

raganwald 16y ago

> The interviews were pretty evenly split between very large, large, and startup-sized tech companies. Really? One person is looking for a job in a big company or a startup?? One of the most common programmer interview questions is What type of job are you looking for? I suspect that "Oh, I don't know, maybe cubicle dweller in BigCo, but then again a startup might be fun" is not the best answer, and describing each company as being your ideal destination is dishonest. Then again, another possibility is that he looked for a startup job, and when he couldn't find the right spot he tried some medium sized companies, and so on. That might make sense in an interview: "I was really interested in exploring a startup, but when I actually looked into it I realized it was far more romantic in theory than it was practical. I like the idea of writing great software, but it turns out that the companies I met with aren't very committed to some of the best practices that interest me." So I won't jump to conclusions about the OP, but certainly I am interested in hearing what chain of events led to what appears to be a wide spread of environments.

fjh 16y ago
I honestly don't think that everyone cares about the size of the company they're working for. I'm currently applying for internships for this summer and I am far more interested in what kind of work I could be doing than how big the company is. I don't think that's uncommon.
- raganwald 16y ago
  I know that many people don't care about the size of the company they're working for, but turn it around: Do you think that employers care about whether an applicant cares? To make this perfectly clear, let me propose this interview question: What is more important to you: The company and culture or the work that you'll be doing? I think that people being people, they will prefer applicants who honestly are more interested in the company and culture than the work. This is absolutely true of BigCo, and applies to startups as well. What if the company needs to pivot and you are no longer working on whatever excited you about coming to work on day zero? Will you start looking for somewhere else?

wulf 16y ago

These sequence questions drive me up the wall. It's so unbelievably stupid that out of the near infinite functions that can produce a given list you should come up with the one the interviewer thought was the "obviously correct" one. The sequence in the example: 1, 11, 21, x ... with the information given then the X=31 is just as valid as anything that the interviewer came up with.

obitoo 16y ago
yes of course thats a valid reply; the next question they'll ask you is "Can you think of another one?" and try to steer you towards it.

tszming 16y ago

I also recommend the book "Programming Interviews Exposed", it contains the absolute minimum every software developer must know about...

Hominem 16y ago

All this is still useful. I have to fix code all the time where the original developer paid no attention to complexity and a algorithm that was fast with the 10 items they tested with is dog slow once it makes it to production and there are 10,000 items.