5 ms·
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 t
by grayhairmomma 16y ago
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.
- newobj 16y agoFair 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.
- grayhairmomma 16y agoWell, I guess you'd never hire me then. Which is OK. I can't be anything but honest. Sorry. It's who I am.
- r00k 16y agoCouldn't you learn this concept, grow as a programmer, and become more hirable in the process? It seems like you've decided you're not capable of teaching yourself through it.
- grayhairmomma 16y agoOf 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.
- silentbicycle 16y agoRather 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/ http://mitpress.mit.edu/algorithms/), it's even a pretty short book.
- kunjaan 16y agoExactly. 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.
- kenjackson 16y agoI'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.
- silentbicycle 16y agoI 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.
- jodrellblank 16y agoI've been reading through this lately: http://ask.metafilter.com/158740/You-were-doing-it-wrong http://ask.metafilter.com/158740/You-were-doing-it-wrong Somewhere in there, about half way down, is Was 30 before I realized that it's not cheating to study to learn something or to work hard at something to get better at it.
- newobj 16y agoI 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.
- grayhairmomma 16y agoI 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.
- yummyfajitas 16y agoWould you do better if asked to write it in $YOUR_FAVORITE_EDITOR rather than a whiteboard? If so, just ask the interviewer to write in emacs, tell him you are uncomfortable with a whiteboard. If not, find a new career.
- evilduck 16y agoWhen 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.
- jacquesm 16y ago> 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.
- barrkel 16y agoYou'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.
- neild 16y agoPerhaps 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.
- barrkel 16y agoIt'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.
- kenjackson 16y agoI 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.
- mquander 16y agoThis 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.
- grayhairmomma 16y agoI 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.
- anthuswilliams 16y agoMaybe 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.
- mquander 16y agoI 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.
- ryanwaggoner 16y agoYou certainly will encounter harder things that you need to invent (not just re-invent) during the course of any job. Ha! You'd be surprised at how many "programmers" spend years just cutting and pasting code without really understanding any of it.
- silentbicycle 16y agoYeah, but aren't some interview questions specifically intended to screen out those kinds of programmers before they do too much damage?
- bcrescimanno 16y agoSure; 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.
- sofuture 16y agoYou 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.
- juiceandjuice 16y agoI did this once in assembly and ended up with a ton of desserts. (push pops)
- silentbicycle 16y agoI'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. It's a linked list, people.
- capstone 16y agoTo play the devil's advocate, and I am speaking specifically within the context of web development, what is a practical example of a linked list?
- sofuture 16y ago1) 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.
- bhousel 16y agoWrite a webcrawler that doesn't get stuck crawling in circles. You need to maintain history somehow.
- jemfinch 16y agoIt 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.
- deleted 16y ago[deleted]
- blink1729 16y agoI 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)
- grayhairmomma 16y agoOMG, 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)!