5 ms·

Yeah, but If I had to reverse a linked list without recursion to be hired, I'll be damned if I'm going to allow someone else to be hired without doing that.

• gonzo41 10y ago
  put it in a stack then take it back out, first in last out.
  • dkopi 10y ago
    Follow up is usually: now do that with O(1) memory.
    • jstelly 10y ago
      This doesn't seem like a very valuable interview question anymore because it's well known and you can probably google the simple answer, but if not this is the basic idea (walk the list once pointing each next at the previous node and return the new head when you reach the end): List *Reverse( List *pList ) { List *pPrevious = nullptr; List *pCurrent = pList; while ( pCurrent ) { List *pNext = pCurrent->GetNext(); pCurrent->SetNext( pPrevious ); pPrevious = pCurrent; pCurrent = pNext; } return pPrevious; }
      • khedoros 10y ago
        I've never seen an interview question that I couldn't Google an answer for, after the fact. That doesn't seem like a necessary criterion to decide if it's a valuable question or not. However, it's a problem if the question's so common that even unqualified candidates would be able to answer it. We ask these questions for a few reasons. You hope that the candidate hasn't seen it before, because you want to see their problem-solving process. You also want to see which questions they ask, which assumptions they make, etc. How well do they explain their thought process? Do they understand the algorithm, or did they rote-learn it? Will they need to jump through algorithmic hoops writing a CRUD app? Probably not...but they'll need to solve problems creatively. It might be better to walk through an actual investigation+bugfix in a piece of software, but that takes more time to do (interviewer+candidate) and more effort (interviewer) to set up, so it's not surprising that most interviewers would take the easier way out.
    • huherto 10y ago
      I used these examples for interviews back in the 90s. I liked the follow ups. I don't use it any more because linked lists with pointers doesn't seem relevant now that computer languages have some sort of native dynamic list implementation.
  • jcadam 10y ago
    GAAAAAAHHHH!! I mean, Of course I knew that already :)
• mesozoic 10y ago
  It's hard to know you can simulate a function stack with a for loop I guess...
• Joof 10y ago
  If there isn't tail recursion should I implement it with trampolining in the compiler first?