I never said linked lists were hard. I said that it's not necessary to know how to reverse a linked list from memory -- from scratch. I can look it up and get to it right away.
You know, at one point I thought that as well. I felt, that as someone who programs almost solely in 1) C# 2) Erlang -- "thanks I've got a stdlib for that".
And then I actually thought about what it takes to reverse a linked list for a second.
And immediately realized I will never, ever hire someone who can't regurgitate or reason how to reverse a linked list "from scratch" within a few minutes.
I'd go one further - if I thought somebody was giving me a rote answer for how to reverse a linked list, I would push them to see if they actually understand why it works. Or switch to something a bit more exotic, like a skiplist or radix trie, and see if they have any intuition about data structures.
I just went through this exact same process reading your comment. "Well, DSA was a couple years ago... I don't know if I could answer that right off the bat." "Come to think of it, how would I answer that?" "Oh, it's completely obvious."
Not that I expect to be in a position to make hiring decisions, but if someone can't answer that intuitively with a few moments' thought I know they're probably a couple of years' experience from being able to keep up with me.
1) That's irrelevant. I'm speaking to the importance of the ability to reason a linked list which is not really related to 'practical examples of linked lists in a web development context'. To quote silentbicycle above: "It's a linked list, people." We're not talking about 'the latest developments in red-black tree algorithms'.
However...
2) Probably every list of objects you throw around in whatever abstraction providing framework you're using.
Would you hire somebody who can't compute 2+4? For the same reason you wouldn't hire somebody who can't reverse a linked list, even if the actual reversing of the linked list doesn't come up in the job.
Why a linked list? Wouldn't something resembling a hash table or even a tree be a lot better.
I think with web development a lot of the situations where you would want a linked list are abstracted away. Personally I would be testing people on how they take some kind of design outline and map out how they would approach it. Something like dealing with bringing together multiple API's to would be high on the list, this is becoming a much bigger part of web development.
But on a whiteboard? That they then take a photograph of? Please! Let me pull out my computer and I'll TDD it for you right there. I coded doubly-linked lists in assembly language at age 15 without ever reading about them, but I can't spew it out onto a whiteboard.
Fair enough. But as someone who's conducted hundreds of developer interviews, I can say it's absolutely a huge red flag for me. Total failure would be a straight no-hire. I see it as something that should be very easily re-derivable. You certainly will encounter harder things that you need to invent (not just re-invent) during the course of any job.
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.
Sure; but there are a ton of places they can get a job as a "programmer" having only interviewed with a non-technical manager. These people become experts at this type of interview and are able to do what I call, "dazzling with bullshit" quite effectively.
I think I understand what you are trying to say. Maybe you need alternate examples to show what you mean:
Scenario 1)
------------------------
You have 2 candidates 'A' and 'B' in a team. 'A' is actually better than 'B', writes better code, and has the ability to debug issues which 'B' really can't get a handle on. Both
get a call to interview for a company in 2 weeks. 'A' has confidence in his/her abilities, so just goes through an algorithms/data structure book and writes 0 lines of code
in the 2 weeks. 'B' on the other hand, buys couple of programming interview books, goes through common questions (like reversing a linked list) and actually practices coding these questions. On interview day, 'A' is posed a question to merge 2 sorted linked lists. 'A' hasn't worked with linked lists for some time now, takes some time to come up with an answer, and writes up a solution on board that has some syntax errors. The interviewer had other questions to ask, but has no time because 'A' took a lot of time to code this one. ('A' has a cold start, so to speak).'B' when posed with the same question solves it within 15 mins (what with all the practice) With that confidence, 'B' aces the rest of the interviews. 'A' is kind of disturbed, cannot believe linked lists can be so tough, and does OK in the rest of the interviews, but still doesn't exude the confidence of a person who knows his stuff.
No points for guessing who is hired.
Scenario 2)
---------------------------
Instead of short interview times and questions about what everyone calls 'basic data structures', lets say both were given laptops during the interview and were given a program/requirement that neither had seen before and something that did require logical/analytical thinking to solve. Say, instead of 40 mins they were given 2-3 hours to complete the coding/debugging with access to a compiler and to language/API documentation. Who do you think would do better? (If it is not obvious, I back 'A' to do better)
I would really say scenario 2) is a better simulation of actual working conditions. Unfortunately, most interviews are like 1), maybe because 2) is more work for the interviewer. (logistics + framing a good enough problem)
OMG, blink1729, you read my mind. I couldn't have said it better ! Someone from salesforce.com (who I met via HN) told me that software folks are interviewed similarly to Scenario 2)!
It may not be necessary, but a competent developer should be able to do it in their sleep with one hand tied behind their back. If a candidate finds it difficult to do so, that's a really bad sign that they'll find the necessary things difficult as well.
