You're defending your honesty, but your honesty isn't what's being attacked; it's your competence.
I've been asked in interviews before, how to reverse a single-linked list, and impressed interviewers with my answer to this seemingly trivial problem; but I also remember when I first met the problem, in a newsgroup posting nearly two decades ago, and I had temporarily convinced myself it couldn't be done in constant space. But then I saw the problem as pushing and popping of stacks: view the old list as a stack to be popped, and the new list as a stack to be pushed, and thence the list shall be reversed.
But doing it elegantly - in constant space - is besides the point. Reversing a linked list is a problem which can be solved, even clumsily, without much thought. But demonstrating problem-solving in an interview situation, that is the point.
Perhaps I've just worked with linked lists too much at this point, but I find it nigh impossible to understand how reversing one could be considered even minimally difficult. "Pop the head of the source list and prepend it to the target until the source list is empty." One sentence, no complex concepts involved at all.
If it's unfair to expect someone to answer a question like that in an interview, then I'm not certain what is fair. In a world where people with literally no programming skills whatsoever regularly apply for programming jobs, I need to apply some filter to weed out the incompetent. Sad experience has told me that educational credentials and claims of past work experience are insufficient.
It's very hard for you or I now, to appreciate what it was like before you learned to think of linked lists as stacks. The point is, there is definitely a leap of insight necessary if you've never thought of things in this way before. I was 12 or so when I made the leap, and I guess I'm slightly lucky that I remember the exact moment for this particular case.
I don't think I knew what a linked list was at age 12, but I don't think you even have to know what a stack is to do this. Just draw it on a whiteboard, and it becomes obvious that you just walk the list and flip arrows. Seeing that linked lists can represent interesting structures is I think an even more advanced concept, but one that is unnecessary for this particular question.
I really have a hard time believing that coming from a C/C++/embedded background you couldn't whip up something reasonably workable (linked list) in 15 minutes on a whiteboard. It's usually the people that have gone on to become "architecture astronauts" who can't do it, or the people who could never do it in the first place. I mean it's as much a test of passion as a test of competence. You can see that certain people are physically pained by writing code. They just don't enjoy it and want it to stop. Other people are engaged and clearly want to produce something. Even if their result isn't perfect. If they are verbalizing something relatable as they get stuck on the same stupid ha-duh mistakes you get stuck on when you do your own job day in an day out. For the people who I think are exceptional, this should be refreshing to them, almost nostalgic. No need to worry about browser compatibility of your linked list, no need to worry about its latency, its availability, making a mobile version of it, etc etc etc. It should just be "I haven't done anything this uncomplicated in a long time." Maybe you should just bust out notepad (no compiling!) and try it and time yourself. Without the pressure of someone staring you down, maybe you'll surprise yourself.
I don't know what to say guys. I'm not incompetent but if you want to assume that I am, then I cannot stop you from drawing those conclusions. Let me say this : it's not a matter of comprehension. It's a matter of performing flawlessly under pressure at the whiteboard.
This is getting to be a really silly off-topic discussion, but I have to admit, I would be totally curious to hear if you could identify what is difficult for you about this task:
A) Pressure of an interview situation makes it hard to think straight?
B) Absence of familiar IDE, environment, REPL/compile-run cycle makes it hard to work or think effectively?
C) Something else?
I just don't see how it could be difficult for someone who understands loops and pointers (as I assume you certainly do.) I would have filed "reversing a linked list" under the Fizzbuzz category of things-that-anyone-who-has-ever-actually-programmed-can-do.
I am not a stupid copy/paste programmer who doesn't know what the fuck she's doing. Trust me on that. As my blogpost said, I thoroughly understand the concepts. But if you read my blogpost comments, you'll notice that many people sympathize -- and I doubt that these people are incompetent. Some people will impress at whiteboard coding, others will not. That's it.
When I first started programming I was doing VBA on spreadsheets. I thought entirely in terms of simple commands, variables, events, if statements and the occasional loop. I could vaguely remember what an array was from highschool but never needed one (although, to be fair, I had a spreadsheet to work with).
I did not have a clue about objects, classes, pointers (Pass By Val vs Pass By Ref was like flipping a coin), never mind linked lists. But despite this, I managed to get a lot done. Of course since I've taken the time to educate myself I understand now, but my point is in some settings you can go quite far without ever engaging the fundamentals of computer science.
I know the OP said she does understand all that stuff but it's also possible she barely needs to use it.
Maybe it's the "computer scienciness" of the term. I'm a practical programmer with a tiny bit of industry experience, and have only just started attending university. And I'm intimidated by it all. Memory allocation! Pointers! My brain shuts down and I imagine anything I say will put McCarthy in the grave and cause Dijkstra to rise from it.
But the first time I read some blogger ragging on interviewees who didn't know how to reverse a linked list, I read the first sentence of the wikipedia article and realized it would be easy to do (albeit probably not elegantly): just loop over the list doing push/pop operations.
It's a pretty easy solution, and already runs in O(n) time, so I'm not sure why I doubt myself. It's probably that although I'm used to devising solutions for complex problems, I'm unused to problems that are formally defined.
I think that sounds like probably a big component. I do know what you mean -- something about the words "linked list" seems complicated, even though there's nothing much simpler than an actual linked list.
I wonder if people who would freeze at a question about reversing a linked list could answer that and similar questions if they were turned into "word problems" somehow; e.g. evilduck in another comment compared it to reversing the order of charms on a bracelet. Although I can't think of any examples that doesn't sound terribly contrived.
Of course it's doable. Like I said on my website, I need to get off my ass and start coding up linked lists, binary search trees and sorts "til I fucking throw up all over Manhattan". Yes, of course it's doable. I'm no dummy. I can stumble through it on the whiteboard as well -- I'm not deaf, dumb and clueless -- I don't just stand there at the whiteboard listlessly, with blank stares, if that's what you mean. If I practice enough, reciting from memory (and on the whiteboard), coding the stuff up perfectly will be trivial. But to me, that's gaming the interview.
Rather than memorizing stuff forever, you could develop your intuitions about data structure design trade-offs and what makes them behave the ways they do. After I learned OCaml, a lot of data structure design seemed obvious.
Also, read _Purely Functional Data Structures_ by Chris Okasaki. Unlike (say) CLRS (http://mitpress.mit.edu/algorithms/), it's even a pretty short book.
Exactly. The OP thinks that when I ask her to reverse a linked list, I expect her to whip out the perfect code from memory on the fly. I would be even more suspicious if you did that actually. I want you to structure the data. I want you to try out variants of reversing. It is ok if you can't give me the optimal solution in 5 minutes, as long as you demonstrate the capability to reason with data structures and pointers and tools at hand.
I'd actually recommend not reading Chris's book in isolation. There are a lot of things that are ugly to do in functional languages (w/ respect to data structures), but are easy with assignment (and of course vice-versa). I'd read Chris's book with Sedgewick (Sedgewick is a super applied algorithms text). This will help give a good balance.
I partially suggested it because it uses SML for the code. Even if one doesn't use OCaml / SML for actual programming, using the notation will probably help quite a bit with reasoning about data structures.
When encountering problems where I have to derive the answer without a crutch, I solve most by thinking how to solve them either through native language or spatial movement of object, then translating into code.
How would you reverse the order of charms on a bracelet? Any time a step isn't clear, break it down further.
> Any time a step isn't clear, break it down further.
And that really is the key to programming. Which makes pretty much anything solvable from scratch. Whether or not you'll come up with the most efficient solution (or at least one that runs reasonably fast) is another thing but at least you'll come up with something, or at a minimum a well defined little black box that you know you're going to have to fill based on the name you gave it.
