43

Reading this site and SO I've seen many stories of interview questions and answers saying a candidate had to implement a linked list from scratch. Usually this is a "gimme" exercise for programming role candidates like writing FizzBuzz. The idea is that if the candidate can't do this, they can't program and should be rejected almost immediately.

However, I can't help but think this could be a poor practice for the following reasons:

  • Modern higher level languages like C# and Python natively use lists extensively; writing your own linked list object would be only required under unusual circumstances and even then probably ill-advised.
  • Lower level languages like C++ have standard libraries with iterators/list containers and objects.
  • In light of the first two points, coders can go years without even thinking about implementing a list (linked, doubly-linked, etc) themselves. Some may not even really see such things since college days.
  • Computing power also isn't the factor it was years ago, so efficiency via pointers isn't the issue it used to be (in general).
  • A simple web search of something like "linked list example" would bring up plenty of code examples that could just be memorized and spat back out, not really indicating the true competence of the applicant.

I should say that using a linked list to lead to open-ended questions/discussions of candidates' problem solving/critical thinking abilities is mostly likely a really good interview practice. Any way an interviewer can really see what an applicant is like and how they think is massively beneficial.

I think this binary approach of "no linked list code, no job" for programmers working on a desktop or web application is a bit outdated. It could also be quite harmful; a candidate who can't remember how to properly work with the head of a list could be an otherwise excellent coder and co-worker and be lost in the mix. Thoughts?

EDIT: There are many (good) comments suggesting that whether this is a good or bad question to ask depends on the context of the job. I strongly agree, so let me rephrase this question: Implementing a linked-list is a common interview question for a wide range of coding jobs, similar to questions like FizzBuzz or writing a recursive function for calculating factorials. Does this question have enough utility to be used commonly for evaluating programming candidates across the board? Or should considered a bad question to ask except for "Senior Developer, Embedded Linked Lists Team" positions?

9
  • 11
    What position is this for? What type of job is this? What domain is it in?
    – Thomas Owens
    Commented Jan 11, 2012 at 17:33
  • 1
    I see your edits, but still - what type of job is this? Is this an internship? An entry level job? An intermediate job? Are you looking to hire a programmer or an engineer or a scientist? What domain is this in? Would they ever be in a position such that they would need to roll their own algorithms or data structures for any reason?
    – Thomas Owens
    Commented Jan 11, 2012 at 18:17
  • 3
    'C# (...) natively use lists extensively' and 'efficiency via pointers isn't the issue it used to be': you do know that these native lists are not linked lists but rather lists based on arrays? Arrays tend to perform better because of caching. In fact, IIRC the .NET framework didn't even have linked lists until 2.0. I'm pretty sure the majority of the C# programs out there don't use linked lists. Commented Jan 11, 2012 at 22:52
  • 1
    @AlextenBrink Interestingly, I think that means that linked list knowledge is even less important for C#. Why implement a data structure yourself (with possible bugs) when I can use a better structure built right into the language? Commented Jan 12, 2012 at 1:19
  • The question I have in mind is 'why even consider using a data structure that is in just about all cases inferior to another data structure'? Linked list are slower for most operations than lists based on arrays; the only thing linked lists are good for is deletion in constant time, but there are very few situations in which that is needed. Note that I'm not talking about whether it'd be a good data structure for an interview question: the concepts involved might be a good test, I don't know. Commented Jan 12, 2012 at 1:33

13 Answers 13

52

If answering the question tells you what you want to know about a candidate, then it's a good interview question. If it doesn't tell you that, it's a bad question.

Easy questions like FizzBuzz do serve a specific purpose. If a candidate can't code FizzBuzz, they simply can't code and you can end the interview early. I'd rate implementing a linked list only slightly harder, but it can start a conversation about data structures in general that will reveal a lot.

Just remember that no single interview question will tell you everything you want to know. You really need to have a group of questions ready. You should ask questions in a sequence from easiest to hardest so you can find the limit of what the candidate knows. If you ask one question and they nail it, you still don't know what else they do or do not know.


Regarding your edit:

Does this question have enough utility to be used commonly for evaluating programming candidates across the board? Or should considered a bad question to ask except for "Senior Developer, Embedded Linked Lists Team" positions?

I think it is a good general purpose question that could be used for evaluating practically any programming candidate. It just needs to be part of a larger group of questions. It would be a good ice breaker for many types of position (even if the candidate can't implement a linked list from scratch, maybe they can explain how they've used one before and what the key functions are), or the beginning of a long sequence of more advanced questions for the "Senior Developer, Embedded Linked Lists Team" position.

4
  • 19
    Your first paragraph is half the story. The other half is: If being asked the question makes the candidate want to work for you, then it's a good interview question. If it makes the candidate not want to work for you, it's a bad question.
    – ruakh
    Commented Jan 12, 2012 at 0:41
  • 5
    You can't find the limit of what the candidate knows that way, because you have no way of asserting that what you consider "complicated" and "basic" apply in the same order to your candidate. LinkedList is probably a basic for a university taught programmer, but a self-taught programmer most likely never had to write one. After all he probably wrote "LinkedList<string> ..." whenever he needed one. Does it means that his knowledge is pegged under the "linkedList" level? He could be an expert in more complex subjects and be able to learn LLs in 5min in Google.
    – Sylver
    Commented Jan 12, 2012 at 9:10
  • 1
    @Sylverdrag That's why I said you need more than one question. Once you find the limit of their knowledge about linked lists, move to another topic. Commented Jan 12, 2012 at 11:28
  • @ruakh That definitely plays a part. If every single question I'm asked at an interview is about mundane aspects of CRUD apps (i.e., I don't think that I could learn anything new at that company), then it wouldn't excite me to work there. Commented Jan 12, 2012 at 15:46
34

I have missed out on jobs purely because my mind blanked on simple puzzles like this. I've also done brilliantly on such puzzles in other interviews -- I know how to implement a linked list in a non-pressure environment. I've never had a complaint about my abilities from someone I've worked with, so maybe I shouldn't think that I've missed out on jobs, I should think that they've missed out on me.

So yeah, I think it's a questionable practice at best, but I do understand it. I have also considered the possibility that it's not the fault of the question but the questioner, for making it a high-pressure situation.

Personally, I prefer to ask open-ended questions about a problem the candidate has already solved -- recently, if possible, and covering both coding and process problems. If they can bring code-samples, fantastic.

11
  • They need to ask something, be it puzzle or anything else. Any question can cause the person to blank.
    – Sign
    Commented Jan 11, 2012 at 19:21
  • 2
    @pdr - " If they can bring code-samples, fantastic." If they wrote the code samples they brought, priceless. Commented Jan 11, 2012 at 23:10
  • 4
    If someone's mind blanks on a linked list implementation and they can't work through it with a little prompting or get frustrated easily, I think it would be someone I wouldn't mind missing out on.
    – Bill K
    Commented Jan 11, 2012 at 23:49
  • 1
    @pdr - "And if you can't, how long do you think you'll have the job for?" - For as long as it takes to fire them under whatever HR regime you suffer through. Then there's the added cost of restarting your candidate search. Also the opportunity cost inherent in the fact that the very next person you would have interviewed might have become the technical linchpin of your entire department. But of course now they aren't available because you hired the wrong person and they found another job. Commented Jan 12, 2012 at 2:56
  • 1
    @robrambusch: He exhibited excellent problem-solving skills and talked about class structure well. But he didn't write code. On the subject of writing code in an interview, yes, that can be useful, but I maintain that I can learn more about you in an hour of talking to you about problems you've solved than giving you a single contrived problem that takes an hour to solve.
    – pdr
    Commented Jan 12, 2012 at 17:07
25

One has to define the programming job type. If you are in the business of developing compilers and algorithms, questions about such things should be expected. If you are in line-of-business type applications and you expect the candidate to do CRUD applications, then, may be the knowledge of the concept (without writing a program) is sufficient. Today, the knowledge of different technologies required to get the job done specially in the LOB type of applications supersedes the need for neat algorithms.

6
  • Exactly. Last year I wrote a general purpose genetic sort component which also used a bit of simulated annealing(to create class schedules) and used several "advanced" data structures to get it performing. I Didn't need to code single one. If the .Net framework didn't have what I needed I used C5 or Power Collections. Commented Jan 11, 2012 at 18:23
  • 4
    Agreed, I write LOB apps all day, I have in the past written linked list implementations...in college...in COBOL. I could do it again, but why? Lots of competent LOB developers have probably never written one, and will never need to.
    – CaffGeek
    Commented Jan 11, 2012 at 18:42
  • 1
    Agreed in general, but a linked list is nothing exotic, really. It's the basics, just one level past FizzBuzz. Commented Jan 12, 2012 at 7:22
  • 1
    @FrancescoDeVittori: Isn't that sometimes the issue though? Someone gives you a problem to solve. It seems simple enough, but you've never done it before, so your brain starts racing, trying to find the gotchas, the thing that is going to cost you the interview if you don't think of it. And it's not there, but that's distracting you from solving the actual problem.
    – pdr
    Commented Jan 12, 2012 at 8:41
  • @FrancescoDeVittori: Can you give a couple of examples of non-basic interview questions? I need this for self-improvement. Thanks.
    – Den
    Commented Jan 30, 2012 at 21:30
9

My answer is "It depends". I would ask this question if a candidate has listed C or C++ on his resume. Asking to implement a linked list is a good test for the understanding of pointers which is absolutely essential for a C or C++ programmer.

On the other hand, if a candidate does not claim to know C or C++, I would not ask him to implement a linked list, but I would consider asking questions about it. Explain at a high level how a linked list works. What is the complexity of adding an element to the head of the list? The tail of the list? Inserting an element in the middle of the list? When would you use a list as opposed to an array? These are fundamental data structure concepts that, IMHO, every programmer should know.

7

I wouldn't consider it a bad interview question. A lot of data structure understanding and programming starts with a really good understanding of Linked Lists. That said, there are some caveats:

1) It is a fizz-buzz type question. You are just validating something very basic: Does the person understand a linked-list. Ask it and move on.

2) There is the challenge with linked lists that the languages that are highly suited to showing your understanding of linked-list concepts (e.g., C) may not the same as the language they will be working with on the job. You can demonstrate basic understanding in any language with structures, of course, but asking a candidate to re-implement a linked list in Erlang without using [] isn't the same challenge and won't tell you the same thing about a candidate's understanding as asking them to do it in C. Asking them to do it in C if the job is around Java is also missing the point somewhat.

3) With that in mind and the general challenges of "whiteboard programming," when asking this sort of question I'd accept pseudocode or diagrams so long as they demonstrate understanding of the core principles. I don't ask that people write code on a whiteboard that is syntactically and logically perfect, especially if they can then turn around and identify any logical problems when asked to look at it again. YMMV.

6

When I was giving interviews, I was often asked for linked list implementations and some algorithms centered around linked-lists. I solved most of them, and some of them required me exercise my neurons a bit.

If I was ever taking an interview, I would go for some sort of a linked-list implementation, not to test how good a person is in coding, but to check how much attention a person pays to details. Anyone can write a linked list, but it is the boundary cases that even some good programmers fail at. Don't ask him: Write a code for linked list in C/C++. Ask him to write a generic linked list in C (not C++), etc.

Twist the problem, and put some other conditions on the linked list, and you'll have a good question to ask. Some people are bound to make mistakes then.

8
  • 2
    No such thing as a generic linked list in C.
    – DeadMG
    Commented Jan 11, 2012 at 17:53
  • 1
    Seriously? I thought void pointers are there for that only... :) The first link I found on google for "generic linked list in c" was: daniweb.com/software-development/c/threads/109260 and another one was technical-interview.com/… I thought everyone knew this!
    – c0da
    Commented Jan 11, 2012 at 17:56
  • I haven't tested these codes, but I have this type of linked list earlier, and it sure worked fine...
    – c0da
    Commented Jan 11, 2012 at 17:58
  • Even writing a generic linked list in C# has one or two "gotchas" (e.g. comparing elements of type T is non-obvious; ie. (T v1, T v2) => { return v1 == v2; } will fail to compile unless you have class constraints or use the default equality operator) Commented Jan 11, 2012 at 18:32
  • @c0da In my opinion, a list that uses void pointers are not generic, but just general for any time. They can hold any type of things in it, and even mix them all they want – and exactly that makes it non-generic for me. It’s like using the base type object in object oriented languages…
    – poke
    Commented Jan 12, 2012 at 9:53
5

In my about 10 years so far programming professionally (and around another ten years as a hobby), I don't think I have ever needed to implement a linked list. If someone asked me to do it during an interview, I might counter by asking if that's something I will be doing regularly on the job.

For sure, there almost certainly are jobs out there where you will need to write more-or-less-cleanroom implementations of commonly known algorithms - like implement a linked list from scratch. But for most programming jobs, what specific value does it have for the company that a candidate can do it during an interview? Is it really so important in such a setting that the candidate provides a perfect implementation which handles edge cases correctly, reports failures according to common practice in the language or framework, and so on? Or can you overlook that and instead focus on how they actually approach a problem that they perhaps haven't been faced with in 10-20 years?

When I interviewed for my current job, I had very little experience with the technology stack in use at the company. Now, a few years later, I regularly have colleagues come to me and ask questions not just about the products, the implementation of them, and the standards implemented by them, but also about much more general programming problems (just yesterday I was asked what the implications were of a circular dependency in a default constraint in SQL Server in the context of a particular table and its usage in our case - reasoning through it, it turned out that there were no implications in that particular case). I didn't need a brand new linked list implementation for that, either.

Ask questions that are relevant for the work that the candidate is likely to be assigned, and try to get an idea of how they feel about picking up new knowledge. How would they go about figuring out the meaning of some obscure syntax they have never seen? (If you are a C shop, for example, then you might try a question involving trigraphs.) For a programming position, do they regularly read or contribute to forums such as Stack Overflow? If they were asked to perform some task in a programming language or framework they have little or no experience with (say, if you are primarily a Java shop, what about Clojure or .NET?), then how would they approach the problem? Maybe take a real bug out of your bug tracker (might even be one that's long since resolved) and ask them how they in general terms would approach solving it, and be ready to explain the relevant parts of the product in question.

If the candidate can handle business-case-relevant types of problems and has a good attitude toward learning new things, that's probably a much better indicator of fit for that particular position than being able to provide canned responses to well-known questions, whether those questions are about FizzBuzz, linked lists, or something else. Throw in how well the candidate fits with the team and I would think that you are on fairly safe ground.

4

Of course most people would never need to implement a linked list, but to implement them from scratch one will probably need to handle pointers correctly. They idea is then that having formed a consistent mental model for pointers correlates with the language proficiency, understanding what happens on some (abstract) machine level and the ability to abstract in general.

I am not saying that this would necessarily be the best measure, but only that there is some correlation.

4

You start out saying that they're 'gimme' questions, but then you point out that people will understandably not be able to do them. I'm confused.

Here's how I think about it:

  • There's rarely a need to write one, as you say, so people will have easily forgotten.
  • They're not incredibly difficult to write.
  • The concepts used to write them can be considered fundamental.
  • They're used incredibly often (even if you're unaware of it).

I think that makes them good questions to ask. If you're worried about them pre-studying for the interview, then throw in a list. Have them write it circular and ask what the asymptotic running time of their implementation is. Or have them write another common and/or quick data structure... A binary search tree? A queue (FIFO)? A stack (FILO)? A naive (O(n)) priority queue? Lots of people I know think that a BST is O(log n) just because it's a tree.

If you're looking for someone who will be working at the metal, and needs a very solid foundation in data structures... these may even be far too trivial for the candidates you're looking to hire.

This assumes, of course, that you want a dev who has the basics/fundamentals of data structures and their position would benefit from those fundamentals. If you want someone who can throw together an asp page in seconds, interview for that. The point is not to pick an interview question because everyone else does, but to pick one that measures the skills you're looking for. Personally, I think data structures questions are good, linked list or no.

2
  • It's not confusing in practice. FizzBuzz is an even easier question and yet applicants routinely can't even begin to answer it. Same goes with linked lists. It's a mystery of the programming world. Commented Jan 11, 2012 at 19:10
  • @joshin4colours: No, I'm confused about the question. At first the OP says that LL questions are gimme's, but then goes on to list points as to why a qualified dev would fail the question. Commented Jan 11, 2012 at 20:25
3

Does this question have enough utility to be used commonly for evaluating programming candidates across the board?

No, absolutely not. Depending on how it's phrased, what it will tell you will range from "this candidate knows how to design a linked list" to "this candidate can program a linked list in language X". If you ask for pseudocode, it will tend more toward the first. If you ask for an implementation in a particular language, you will get more into their understanding of the language (especially with C and C++, where you can deal with pointers and references and structs).

I'd even go so far as to say that it's not possible to evaluate all candidates using the same questions. You need to tailor your interview questions to assess the skills that you are looking for in the position.

If the person is going to be in a position to write code, I'd think about including an algorithm and/or data structure question, as long as it was relevant to the position. I'd try to pick something that might have been discussed or used before. I'd also focus on things other than just the implementation of said algorithms and data structures, such as the running time and memory consumption (things like big-O notation). These concepts are relevant to not only creating the data structure, but also choosing which implementation is best suited (such as an ArrayList versus a LinkedList for example).

3

I dont think for a regular programming job should be a question that eliminates a candidate. But its a good one to see if you are dealing with a really senior programmer or someone who just has been monkey coding forms for a lot of years. And even so, it shouldnt be a fundamental criteria for choosing a programmer. Maybe is a great programmer with bad memory and hasnt read the words "linked list" on years (or doesnt remember the name) but still can do good apps.

So, as some said, if is going to be a job that need to work with linked list and a lot of fancy algorithms, etc.. then ok. Is if for the usual input data on a form, validate and show is kinda useless and unfair.

2

I think that this is a bad example of an interview question, but for a different reason. A linked list is such a simple concept that to know what it is is to know how to implement it. If the person doesn't know what a linked list is, then you have to explain how it works, and in doing so you give away the answer without discovering anything about whether or not they know how to solve problems. So the question is reducible to "do you already know what a linked list is and how it works?", which tells you nothing useful about their suitability as a programmer.

2
  • 2
    Popular questions also are subject to gaming by people who are good at memorizing. Commented Jan 11, 2012 at 18:42
  • 1
    If you have to explain how a linked list works to a candidate, than you should probably not hire him to do programming...
    – Dima
    Commented Jan 11, 2012 at 19:11
2

Writing a linked-list implementation is a good interview question, because it will reveal a lot about the candidate's way of coding:

  • Does he know what an API is? Can he use other people's code? Can he write code so other people can use it?

  • Does he know what a Linked List is? Does he know Collections, Data Structures, Algorithms?

If he doesn't even know what methods a Linked List should offer, you know he probably never used one, or knows when to use one.

  • How does he handle the problem? Does he start with an analysis first, a small specification, some tests beforehand? Or does he just start hacking away happily?

  • Does he handle edge cases? What about removing the last node from the Linked List? What if someone tries to add a reference to the linkedlist itself to the linkedlist, and then deletes the whole thing?

  • Does he handle exceptions? Each programming language has their own conventions for handling exceptions: in Java, you'll expect a LinkedList to throw a NoSuchElementException when you do a getFirst() on an empty list. Other languages might return undefined, -1 or a constant.

1
  • In an interview coding exercise, unless it's specifically asked for, I would skip all sorts of edge case handling, error handling, etc., beyond what is necessary for a proof of concept. BUT I would also make it clear that it's a choice I'm making. The constraints during a one-hour or even a few-hours interview are very different from the situation when you are actually working on something that will see real use.
    – user
    Commented Jan 12, 2012 at 8:49

Not the answer you're looking for? Browse other questions tagged or ask your own question.