5 ms·

A linked list is a fundamental data structure. Being expected to reason about fundamental data structures is not unreasonable. Unless you specifically know tha

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.

helpless 12y ago
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 :) ).
- seanflyon 12y ago
  If the interviewer was satisfied, are you sure the linked list question was the issue?
- wolfgke 12y ago
  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 12y ago
    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 12y ago
      I'm unconvinced knowing how to manipulate data structures is useless knowledge.
      - brudgers 12y ago
        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.
        smeyer 12y ago
        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 12y ago
        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.
- conistonwater 12y ago
  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 12y ago
  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.
tpae 12y ago
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 12y ago

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 :) ).

seanflyon 12y ago
If the interviewer was satisfied, are you sure the linked list question was the issue?
wolfgke 12y ago
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 12y ago
  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 12y ago
    I'm unconvinced knowing how to manipulate data structures is useless knowledge.
    - brudgers 12y ago
      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.
      - smeyer 12y ago
        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 12y ago
        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.
conistonwater 12y ago
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 12y ago
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.

tpae 12y ago

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.