It was probably one of those retarded interview questions. "Show us how you would implement a linked list because that's what you will be doing for a living: implementing links lists!"

/rolleyes

The very nature of software is that you should only implement everything only once.

Clearly, this is not conducive to creating a repeatable test. Therefore any test must involve reproducing code that already exists.

If you are going to ask a candidate to reproduce code that already exists, it stands to reason that you would ask them to create something for which the definition is well understood in order to make the question fast to ask and require little explanation.

Therefore a linked list or hash table is a good example of a practical coding question. It's a good test to give you a negative result even if it's not a good test to get a positive result.

No. If you want a test to accurately predict the candidate's job performance, it needs to be a work sample test that represents and is similar to the types of problems the candidate will be solving at that job.

In other words, unless the job is literally about finding creative ways to implement linked lists, then it is near worthless as an interview question. (I say "near worthless" because there is some value in seeing how candidates respond when given questions that are obviously nonsensical or just outright dumb.)

Implementing a linked list is a good test if the job is programming in C. If you can't do it there's a good chance you aren't really a C programmer. It's a weird question if the job doesn't require programming in C.

I'd be surprised if he's talking about the guy failing an interview, given that he describes it as 'we hired a guy'.

What? Making a linked list in e.g. C is so easy it's not even a task. It may just be a property of some struct you're making.

struct foo { int x; struct foo *next; };

Why would you though given there are so many implementations that have nice features like sentinels, freelists and are optimized for cache locality, thread-safe and potentially even lock-free?

(a simple struct for your linked list isn't really the implementation for the linked list operations. obviously in C you would define your own next pointer. i seriously doubt this guy had trouble with that part of it.)

For example, one of the ways to implement order independent translucency involves a linked list of fragments in a render target. You cannot really use some external library in a HLSL/GLSL/Cg/whatever shader language you use. Even if you could - since all you need is the very basic list, any overhead from a library would be unacceptable.

Linked lists are ubiquitous in programming, hooking up a library every time you need a linked list is as same as using some library for loops. Sure, you can get some fancy loops with guards and Duff's device built-in, but in some fields of programming you will be laughed out of the job if you ever try to do this.

Because some large percentage of candidates can't handle pointers. If you can't come up with a viable "delete a node from the middle of a linked list" during an interview where you are supposed to program in c then you don't get the job. No, you probably won't need to implement a linked list, but you will need to dereference pointers, and the linked list is an adequate proxy for your ability to understand the most fundamental of systems programming tasks.

Pfft. I feel like I could teach pointers to someone who had a firm grasp of any iterative language in less than 15 minutes.

Heck, I'm pretty sure I could teach pointers to someone who has only worked in matlab occasionally by cut-and-pasting others code in less than 30.

And teaching someone something new during an interview and seeing if they can understand it and then turn around and use it is far more valuable for interviewing the types of people I want to hire than asking them random questions they could find the answer to on google in less than a minute.

    void delete_nodes(struct node n) {
     if (n.next)
      delete_nodes(n->next);
     free(n.next);
    }

like that?

I mostly use linked lists when I need to allocate a bunch of stuff and it doesn't have to be contiguous, so I can avoid the cost of the mremap happening in a realloc() call. Linked lists aren't exactly a commonly used data structure by C or C++ programmers, due to their large storage overhead (usually one heap object and two pointers per item) and awful cache locality (heap object headers and list pointers between successive items).

You seem to suggest that there's a wide variety of linked list implementations whose existence you agree with, so at least you agree that some programmers should be making linked list implementations.

the problem with linked list is the cost of cache misses from memory fragmentation killing any iteration. On a current x86 processor a linked list is death for performance. For light insert/deletions work vectors still outperform. However there's always the possibility that "linked list with a twist" may provide a unique solution to a specific problem.

I can't speak for the op, but I would think that writing linked lists is something that pretty much anyone working in performance constrained environments does. No one solution is perfect for all situations, so you end up writing one that is tweaked for your use case. It's not like they're hard to write, so why wouldnt you roll your own?

I don't think linked lists and hash tables show if you are a great programmer or not. But if you CANNOT program those, then I really have no use for you.