[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".

[brudgers]

Questions warrant answers commensurate with the effort invested in their construction. "How do you reverse a linked list?" is, on it's face, a waste if time. Beyond being a solved problem:

~ Single or doubly linked?

~ How is the data structure implemented (e.g. is there a header structure and to what does it point)?

~ What does "reverse" mean? mutate in place? create a new list? and if I am to mutate it in place, why?

~ Reversing a linked list is O(n). One implementation us pretty much as good as another. It doesn't really differentiate on insight into the problem.

~ Winding up in a situation where reversing a list is critical smells like bad design...a stack/queue would have been a better choice upstream than a queue/stack.

But though all that may make for interesting conversation, "with a library call" is the only professional answer to "How would you write a function to reverse a list?"

[zimpenfish]

> Most people will need to reason about fundamental data structures.

I've had to use linked lists precisely twice in the last 10 years and both times were because I'd been forced down to C for API reasons. Even then I just used the BSD macros and didn't give it a second thought. When on earth would I ever need to reason about them?

[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.

[brudgers]

It seems to me that data-structures are the wrong level of abstraction for software engineering positions that aren't using C or an equivalent portable assembly language.

In most situations what matters is datatypes, not data structures. That is, queues and stacks, are the important abstractions...and reversing a linked list in non-trivial cases means that:

~ Either a queue was used instead of a stack

~ or vice versa

~ or perhaps a dequeue should have been used.

Does it matter if an ordered bag is layed out in memory sequentially or with links until profiling justifies refactoring? And when you're in Java, refactoring largely going to be a matter of swapping out one set of library calls for another congruent set...and hopefully, all this happens behind an interface.

Using off the shelf components when it makes engineering sense is a hallmark of professionalism. Reinventing linked list functions is, in most situations, a indicator that a person needs close supervision.

[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?