[davelnewton]

A linked list is a fundamental data structure. Being expected to reason about fundamental data structures is not unreasonable.

Unless you specifically know that taking 20m to reverse a linked list was the reason for not being hired (I'm skeptical), you're just guessing.

While I don't generally ask questions like this, I'd also be wary of someone that can't reverse a linked list in 20 minutes, although it depends on what type of position you're actually applying for.

I also didn't go to a competitive school; I don't know what arbitrary criteria you'd use to decide if I've "done anything special".

I expect coders to be able to code, or at least reason about code, more or less on demand. I'm pretty forgiving about poor whiteboard coding performance since I also suck at it. But even a terrible whiteboard performance can be accompanied by the thought process behind it, and from that, you can discern whether or not the coder knows anything and just sucks at being put on the spot, or if they truly don't know.

[tpae]

It's not about the knowledge, it's more about being on the spot.

More experience and credentials you have, the higher expectation is desired, which leads to higher pressure to solve that problem in the best case possible.

I've been coding since 14 years old, got a degree in Computer Science, haven't been back to school in 5 years, and most of my work just comes to me as second nature. If I have just small doubts of my abilities, I just cannot perform. Which happens during interviews.

[helpless]

I can reverse a linked list even in my dreams. But I was not able to finish the coding under the pressure and time constraint. I explain all the pointer manipulation etc and interviewer was satisfied (unless he was lying :) ).

[conistonwater]

These two sentences:

> "I can reverse a linked list even in my dreams."

> "I was not able to finish the coding"

are to my mind incompatible. Are you absolutely sure the issue is not that you haven't practiced enough? Bear in mind that it is a fairly trivial data structure.

[davelnewton]

I'm having a hard time reconciling the first two sentences.

If it's intuitive then where was the pressure from? And if you had 20 minutes there wasn't much of a time constraint.

The last sentence is counter to your original post, which was that because of this part of the interview you didn't get the job (which is possible, but I'm still skeptical).

I'd spend some time practicing "mini presentations" where you take a problem like this, and pretending like you're in that situation. Code on a whiteboard (or some paper on the wall). Think out loud so the interviewer knows where you're at. Practice how to write code for someone else to read, and so you have an idea of what patterns or anti-patterns you exhibit.

[wolfgke]

No need for pointer manipulation. When I had to implement reversing a linked list (for which already an implementation is there) I'd first ask whether it's single or double linked. In the former case (Pseudocode)

    LinkedList toInvert;
    LinkedList out;

Either iterate through toInvert and call out.push_front(...) on each element or (if the operation may be destructive) do

    while (!toInvert.empty)
      out.push_front(toInvert.pop_front())

All this should not take more than 5-6 lines - should be doable in 20 minutes. Also: these two lines surely could also be written under pressure.

If the linked list is double linked, I'd ask whether the reversing has to be called often in the code. If yes, you could add a direction flag to the linked list, which tells in which direction the iterator will iterate. This makes the iterator implementation a little bit more complicated, but makes the reversing O(1).

[brudgers]

This is a solved problem.

   Collections.reverse(myLinkedList);

Absent a demonstrated performance issue, there's no reason to even consider writing and tuning a new version. There's a debugged performant library. The first engineering tool is to apply is Google, not a whiteboard.

[davelnewton]

I'm unconvinced knowing how to manipulate data structures is useless knowledge.

[brudgers]

It's not useless knowledge, but it's less useful than sound judgement regarding which problems require the preparation of a new design and which can be solved with off the shelf components.

Twenty-five years ago It might have been faster to write such a routine than to find it in a library. I found `Collections.reverse()` in under five minutes on StackOverflow and I suck.

[davelnewton]

I think you've missed my point.

Your "sound judgement" argument is orthogonal to my "being able to reason about fundamental data structures". I doubt most people will need to manually re-write list operations. Most people will need to reason about fundamental data structures.

Ultimately I guess I just find it impossible to believe that basic coding skills are no longer relevant to a large number of commenters here, and that using a "but I can find it on teh Googs" is a reasonable response to "please write a few lines of trivial code that operate on a trivial, but fundamental, data structure".

[smeyer]

But they want to find out about both kinds of knowledge, your sound judgement on problems and your ability to prepare designs by reasoning about data structures and such. If they only asked questions where the correct answer in production is to come up with a new design, they'd have to ask pretty difficult interview questions. Instead, they ask questions that are simpler and common enough to be implemented by libraries to test your design skills, and your ability to determine when to use off the shelf components should be tested somewhere else. It's quite common to ask more general questions about problem solving and evaluation to get at those sorts of things.

[seanflyon]

The real problem is: Show me you understand this basic data-structure well enough to perform a simple task.

"Collections.reverse(myLinkedList);" is the correct answer to "How would you reverse a linked list if it came up in your job?", but is not a relevant answer to the interview question.

[mcintyre1994]

When I was asked this they specified doing it in-place - I figured that was the only reason it'd be interesting.

[seanflyon]

If the interviewer was satisfied, are you sure the linked list question was the issue?