15 ms·

Why Linked Lists Are an Interview Staple

219 points by thrower123 7y ago

jldugger 7y ago
This feels very post-hoc justification-ey. glibc has had data structures for a good long while. I don't think they offer linked list, but it's not a particularly useful datastructure compared to say, a hashtable.
- Something1234 7y ago
  But a hash table using separate chaining requires linked lists, so still pretty fundamental.
  - latch 7y ago
    And linked lists are the backbone of most persistent data structures and are commonly used as a build block for a ton of things, like LRU caches, queues, ...
    - deathanatos 7y ago
      I agree w/ the LRU, but isn't a vector more efficient for building a queue? (You use it as a ring-buffer. Push/pop are O(1) (amortized for push), and it interacts well with the CPU cache since the memory is contiguous. And you get O(1) indexing, too.) Then there's the rather interesting datastructure that C++ has, std::deque, which seems to get implemented as a vector of pointers to vectors. Still O(1) push/pop/index.
thinkingkong 7y ago
I love this type of analysis / retrospective. Ive done 100s of technical interviews and so far there are a handful of questions that stand out as highlighting great candidates. - the interviewer writes a simple c program that compiles and asks the candidate what it does. The best example is an app that dereferences null. Good developers see it right away and answer “segfault”. - ask someone to do something requiring managing delays, recursion, and error handling. Its wild how few people can handle this who have been developing for 5+ years.
- RcouF1uZ4gsC 7y ago
  > The best example is an app that dereferences null. Good developers see it right away and answer “segfault”. And more pedantic developers state that it is "undefined behavior" and anything can happen.
  - umanwizard 7y ago
    This sort of standards-purism goes too far, IMHO. The map is not the territory: C compilers are real, concrete things that have real behavior regardless of whether that behavior is defined by an international treaty. "What does the C standard require of an implementation when given this program" and "based on your experience, how might you expect a typical implementation to react to this?" are different questions, but both are interesting. None of this implies, of course, that I think it's a good idea to write UB! But I think an ideal candidate would both know what UB is and also some of the ways it manifests in practice. If you don't know that code often segfaults on null dereference, you are going to have a very hard time debugging segfaults that you see in the real world.
    - Gibbon1 7y ago
      Far as I've seen on systems with MMU's generally you get page fault. And then the OS handles that and issues a seqfault. Which is what happens usually when you start trying to poke at random addresses. On an ARM Cortex, if you try and read a null pointer you get the top of stack address. Least on my machine/compiler. If you try and write, then you get a bus fault. Beacuse flash memory is mapped to that address. On an AVR, I think reading gives you the reset vector. And write to address 0 is useally a nop. I think with some magic though you can write to that page of flash. So yeah. Kinda depends.
    - gravypod 7y ago
      The only correct answer would be "you dereference a null pointer". That is the only part of this equation the c language interacts with. That's the entire reason SIGSEGV is a signal to your process. Page faults or access violations are manifested as interrupts in most systems. In some systems there are no such restrictions. Even in C & x86 within RING 0 you should be able to access ((char )0). I've even made an example branch on an old kernel I was making when I was in highschool to test this and it does work [0]. What is unfortunate is that everyone is looking for a different kind of person. If I'm applying to a job, saying "segfault" might be the right answer OR it will be the wrong answer and the interviewer will leave thinking I don't know how this fundamental functionality (in some industries) works. I could also give the more correct answer and look like a know-it-all which, when I'm trying to sell myself based on what I know, is somehow a bad thing. It's a loss no matter which way I play it. I distinctly remember one interview where someone asked me to define a RESTful API for a chat service. So I naturally defined the different objects (ChatRoom, Message, User) and defined what CREATE, LIST, DELETE on them all did. The interviewer was confused because CREATE&LIST are not HTTP methods and I explained that RESTful design isn't really coupled to HTTP and these objects and the operations we can perform with them could be implemented over an RPC or HTTP/json and I listed the steps for both of these approaches. He cut the interview short and I never heard from that company again. [0] - https://github.com/gravypod/Simple-OS/commit/b7a608500b2e70dc0cc2b939ba1bd6381e555bd8#diff-cdd8f39dc4ace4d761440f54b310f2f6R23 https://github.com/gravypod/Simple-OS/commit/b7a608500b2e70d...
RcouF1uZ4gsC 7y ago
Linked lists were also more applicable during that time. The PC world was just starting to move away from segmented architecture to 32-bit linear addressing. With 64K segments, you were limited in how big an array could be since it required contiguous memory. However, with linked lists, since memory did not have to be contiguous, you were only limited by available memory instead of 64K segments. In addition, during the late 80's, early 90's the relative difference between memory and CPU was much less than it is today. Because of this, iterating a link list did not have quite the cost relative to iterating an array that it does today. Nowadays, linked lists are a much more specialty structure rather than the first thing you reach for when you want to store a bunch of stuff.
yodon 7y ago
Sites like HackerRank and TripleByte do a great job of telling me whether a candidate has been studying to pass interview questions on HackerRank and TripleByte. They do very little to tell me whether, in the words of Joel Spolsky, they are "smart and gets things done."
- mykowebhn 7y ago
  You have me quite interested. What else do sites like HackerRank & TripleByte tell you?
  - yodon 7y ago
    That assessing programmers is like assessing teachers - a much harder problem to solve well than naive commentators expect, complete with detailed measurements of the shape of the top of each iceberg.
- duxup 7y ago
  I'm sort of terrible at terminology and trivia. I finally got an interview with a take home assignment. They asked questions about my work and how I found solutions, most my explanations we're something like: "I just looked some things up and didn't like that approach because it seemed like it wasn't very flexible if things changed, but did like this one so I used it..." I was later told I was not the top candidate, but was the only one who produced an assignment that checked all their boxes and more and showed I could work independently and produce. First job aquired.
- wolfgang42 7y ago
  I'm going through the Triplebyte process right now (I passed their interview last month and have just started the bit where I talk with companies this week) and that is not at all what they seemed to be testing. Their famous quiz seemed to mostly be checking if you have any idea what you're doing[1], and their two-hour interview[2] spent less than ten minutes on data structures. I muddled through that bit by saying things that sounded plausible (with lots of disclaimers that that was what I was doing and that I had no experience with low-level code) and still passed it with flying colors. Having gone through this process I would say that having some experience and being able to write practical code is probably the best way to prepare, and studying interview questions would probably be fairly ineffective. [1] One of the incorrect answers was to use a factory function that passed the data to an assembly line interface which put it in a package class and shipped it to the user interface. [2] https://triplebyte.com/interview_guide https://triplebyte.com/interview_guide
umanwizard 7y ago
Very interesting thread -- if you're the type of person who comes to the comments before deciding whether to read, I recommend it. I'd also like to point out that today in 2019, linked lists perform like absolute dog shit in many real-world contexts even where they have the best big-O notation. Somebody jumping straight to a solution based on linked lists without at least mentioning memory latency is a sure-fire sign that they have never done detailed CPU performance work. (Which is not necessarily a requirement for most programmers, but it's one piece of signal among others).
- mav3rick 7y ago
  Arrays get you spatial locality :)
  - qtplatypus 7y ago
    So long as they dont span across a page boundary.
    - shereadsthenews 7y ago
      Huh? Spatial locality knows no bounds. The hardware might not automatically prefetch across page boundaries but the application can initiate the fetches itself.
      - XMPPwocky 7y ago
        And, regardless, speculative execution will happily figure out that, hey, the next loop iteration starts with > add rsi, 4; mov rbx, [rsi].d and rsi is 0xDEADBFFC, so rsi+4 is 0xDEADC000, so let's speculatively load that address.... Extra bonus - the compiler may be able to auto-vectorize that. A linked list, on the other hand... hardware can't tell what to prefetch in > mov rsi, [rsi].q; mov rax, [rsi+8].d because it has no idea what rsi is going to be after the first instruction. So it's not just cache locality (which is huge!), it's also the ability of the CPU to actually run things in parallel, instead of serializing everything (and, again, if you're really lucky, the compiler will auto-vectorize the array code)
i_phish_cats 7y ago
Or, is it because it is something that a middle aged middle managers can keep using in their interviews without learning anything new for decades?
- umanwizard 7y ago
  Ageist BS. I know plenty of >40 who are brilliant interviewers and <25 who are useless ones.
  - i_phish_cats 7y ago
    Oh wow that's conclusive data then.
    - dang 7y ago
      Could you please stop posting unsubstantive comments to Hacker News? You've done it repeatedly, and we ban that sort of account. I don't want to ban you, so if you'd review https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html and take the spirit of this site more to heart, we'd appreciate it.
      - i_phish_cats 7y ago
        then ban me
        dang 7y ago
        I'd much rather persuade you to use HN as intended.
- wahern 7y ago
  I'll bite. What new, general purpose data structures have emerged in the past couple of decades? Keep in mind the year is 2019.
  - 7y ago
throwaway987665 7y ago
Citation needed.. Is there any reference showing that this is the reason that people were asking about linked lists? There is the old joke that organic chemistry saved more lives than penicillin by preventing dumb people from reaching med school. It’s a silly joke but it rests on some correlation between the kind of thinking needed for this course and needed to be successful doctor or medical student. If anything there is probably a stronger correlation between the kind of thinking needed for basic algorithms and data structure questions and the thinking needed to be a strong programmer.
- fwip 7y ago
  Not to be a downer on your joke, but if we had more doctors, medical care might be cheaper, which would also save lives.
  - patrick5415 7y ago
    But only if the extra doctors were sufficiently competent.
  - prepend 7y ago
    More doctors who kill people is probably a bad idea. I had a joke about bad PMs...if you can be replaced by a spreadsheet in a shared folder you are probably a bad PM. I think having tons of bad doctors is probably a worse way to solve the high price if medical care than just having better shifting of work within healthcare to apps, therapists, telemedicine, and nurses. Great PMs are awesome and way less important than great doctors since usually people don’t die from non-great PMs.
thethirdone 7y ago
Every time the topic of algorithmic questions in interviews come up I am left wondering if these questions are really as hard as they are made out to be. I would expect most programmers who are not just plumbing together existing technology to be able to implement push,pop,... for linked lists without having to study. You have to do harder things as part of regular programming. > take "determine if a linked list has a cycle in it." I do think that this question if asked without any support if they get stuck is a bad question. You would be relying on the interviewee to either be aware of that research, require that they have the spark of insight, or allow a very suboptimal program. That said, just being aware of the general solution (two pointers moving at different speeds) is enough for me to be confident I could make a solution.
- shados 7y ago
  > I am left wondering if these questions are really as hard as they are made out to be It's not really about how hard they are, and more about: "Ive never once in my career had to use this on the job, why is it asked in an interview, thats stupid!". That's usually the answer you'll get. But I think that answer contains a lot more info than what we can gather from it at first glance. First, good places will give you hints about what the interview might contain long before you show up. If it's for one of the well known big techs, the questions are all over the internet. They know this. The question essentially amounts to: "Can you make sure you know something about computer science if we ask you to know it". If your answer is "No, that's not worth my time, I'm better than this!", well, I can see why someone wouldn't hire you. The second part, is that it is a self fulfilling prophecy. 20 years ago, a typical team was mostly CS majors, with the occasional odd one out who didn't (I was one of those odd ones out). That means if you didn't know it, it didn't really matter. You could just turn around and bounce it off one of your colleagues. If you made a mistake, they'd catch it. Today however, especially in fields like frontend development, its extremely likely ZERO person in the team has a CS background, or the 1-2 people who did don't remember anything from their college years. That means some problems quickly fall in the category of "This isn't worth trying, let's use a 3rd party solution or wait until the one expert in the company does it for us". Thus, self fulfilling prophecy: you don't need to know these things because the industry punted on the problems you'd need these things to solve, or deferred them to other departments. Web apps, for example, are often very animation light, or low on more advanced graphics, because no one knows the math to make these things happen anymore aside from using a library to make a pretty chart. Since your competitors are in the same boat, there's no pressure to change that. And then those folks feel its dumb to ask these questions in interviews (They don't need it!), and the cycle keeps going. "Why would I need these if Im building forms in javascript all day!". Well, maybe if more people in the team knew how to do more than build forms, we could try and build something fancier than forms.
yardstick 7y ago
For developer roles these days I tend to ask candidates what are the main differences between Lists and Sets. It’s an quick question to weed out most weaker candidates, and is more relevant to the nature of our development: using data structures rather than reinventing them.
- BurningFrog 7y ago
  What are the most common/amusing bad answers?
  - Grue3 7y ago
    I've been interviewing Python programmers and asked about the differences Python list and set (and also tuple) specifically. - a lot of people think Python list is a linked list - a lot of people can't name any difference between a list of different values and a set - a lot of people can't answer what can be an element of a set - a lot of people never had to care about performance so can't explain performance characteristics of these data structures at all - (regarding list/tuple) a lot of people can't explain why immutable data structures are necessary in Python
    - WorldMaker 7y ago
      > a lot of people think Python list is a linked list Well, the Python list is designed to present the operational complexity and API of a linked list in worst case, as that makes it easiest to reason with without knowing/leaking the internal structure details. (This is something of a very classic Lisp tradeoff where "everything is a linked list", but sometimes things are optimized as best as possible as an implementation detail.) The fact that the internal implementation is closer to an array in best case and is in the general case sometimes more like a linked list of array buckets (whether by CDR coding [0] or Unrolled link lists [1], maybe something as recent as Skip List [2] in some implementation cases, or other Linked List variations) is an implementation detail that Python says in its API design shouldn't be important to the consumer. Skimming through Python's own documentation as a refresher for this discussion, the first obvious signal that I can find that Python's lists might not be implemented as basic Linked Lists is all the way down in 5.1.2 (Using Lists as Queues): > It is also possible to use a list as a queue, where the first element added is the first element retrieved (“first-in, first-out”); however, lists are not efficient for this purpose. It still doesn't state what the lists actually are, though, because again Python wants the consumer to treat it as a black box and to know only the risks of the worst case performance. So it is entirely correct from the perspective of a consumer of Python lists to treat them as Linked Lists, because that's what Python presents them as an API (for good black box reasons, including that the implementation could change) and what Python tells you is the absolute worst case for working with them. (Just an unlikely worst case, because Python works hard to optimize away from it.) From the perspective of a Python implementer, yes, it is a huge mistake to build Python lists out of strict, basic introductory textbook Linked Lists without flipping a few more pages to more optimized data structures. All of the above discussion of which would be nearly impossible, especially citing even the relatively few sources as I have, in the context of an interview. It doesn't take into account people that take Python's black boxing of its implementation details at its word. It doesn't take into account the decades old functional programming philosophy (that Python essentially inherits here) that "everything is a linked list until proven otherwise" as a part of the Zen of Lisp. It does seem to point back to the C/C++ centricity of asking Linked List questions the Twitter thread alludes to, because in assuming "Python list is a linked list" is a wrong answer probably does show more of a bias to C/C++-style data structure design and low level concerns than Lisp data structure design and low level concerns. (All of which is fascinating at a meta level, but terrifying to me in the context of actual interviews. There's an increasing feeling that more I know about the field the worse I do on interview "basic" questions because interviewers don't even know which assumptions to check at the door.) [0] https://en.wikipedia.org/wiki/CDR_coding https://en.wikipedia.org/wiki/CDR_coding [1] https://en.wikipedia.org/wiki/Unrolled_linked_list https://en.wikipedia.org/wiki/Unrolled_linked_list [2] https://en.wikipedia.org/wiki/Skip_list https://en.wikipedia.org/wiki/Skip_list
temp129038 7y ago
I don’t really see a problem with LL questions. There’s only so many linked list question variations and they are a simpler subset of trees/graphs, which are useful and have more real world applications. If I was interviewing I would be much happier if I was asked a LL question over a tree or graph problem.
gregmac 7y ago
To those who ask this type of question: What's been your experience with people you hired this way? Did everyone you hired who did well on these questions turn out to be good hires? If not, why not? If you took a chance and hired someone that maybe didn't do a great job on these questions, did they turn out to be a good hire anyway? If so, why?
- taneq 7y ago
  In my limited experience, they're a good screening test. Even something FizzBuzz level is valuable to weed out applicants who interview well but lack basic competence. Doing well is necessary but not sufficient, mind you. (I interviewed someone who fundamentally failed to understand a trivial question, they were hired despite my negative assessment, and while in all fairness they did better than I expected, they were still an overall liability.)
- prepend 7y ago
  I don’t know with just this one question compared to others, but as part of a suite of what I classify as “technical thinking questions” I think it’s predicted well programmers who are mid level and up who can figure out problems independent from languages or vendor solutions. I never actually care about the literal code written and usually just ask for pseudo code to understand the logic of how walk through it. So it will fit on a white board or maybe sheet of paper and take maybe 5 minutes or 10 minutes with commentary. I think it’s better if the candidate has never actually written a linked list. Similar questions I ask are “write a database connection pool” or fizz buzz. They are parts screening as a surprising number of applicants can’t write loops or even if statements, which is weird. And part seeing how they ask questions to figure out what’s important requirements or assumptions or limitations. It’s probably worse, in my mind, to write out amazing code without asking questions than to sketch out simple statements asking “how important is multi-threading” or “what libraries can I use” or “where will this get called from?” I don’t have an empirical litmus test from this, but for a few candidates who sucked at this but still got the job, I regretted it. Although one or two moved within the org out of programming to business analysis and project management and did, I think, a good job.
mycall 7y ago
In the 80s, I overused double link-lists in Turbo Pascal. It was my quick-and-dirty database block-storage of choice (minimize memory usage). Then I learned about indexing and switched to dictionaries, btrees or red-black trees for most things.
optymizer 7y ago
I personally find this content delivery method, where a small essay is split into tweet blocks with links and unrelated imagery, very annoying to read and ultimately disrespectful to the reader.
- ken 7y ago
  Normally I find it frustrating to read a blog post as a sequence of tweets, too, but in this case it seems appropriate. (It doubles as a metaphor for why linked lists are generally a poorly performing data structure on modern architectures.)
- ramraj07 7y ago
  One advantage I appreciate is there's no filler. At least the good streams have flow and not a single word is used needlessly.
deleted 7y ago
[deleted]
shereadsthenews 7y ago
I like how he casually asserts that most of "us" don't program in C even though C and C++ are the #2 and #3 languages in the TIOBE Index today, after Java. It's fifty times more popular than Rust or whatever trend he thinks his friends are chasing.
- actuator 7y ago
  The way TIOBE index ranks, a lot of C and C++ numbers are due to uni courses dealing with it. But it is definitely much more used than something like than Rust.
  - shereadsthenews 7y ago
    Sure the TIOBE Index is flawed. I wouldn't have even mentioned it but it forms the basis of his argument.
    - hwayne 7y ago
      Yeah it absolutely sucks as a measure. You're better off manually counting languages that appear in job postings. That gives you a better breakdown of what people were actually hiring for.
curtis 7y ago
The basic linked list algorithms are simple enough that a software engineer -- certainly one with a CS degree -- ought to be able to implement them from first principles. And the point of the interview question isn't specifically whether the interviewee can implement a simple linked list algorithm from first principles, it's whether the interviewee can implement anything from first principles.
- umanwizard 7y ago
  Sure, but I think the thread attempts to answer why linked lists specifically are so popular in interview questions, as opposed to some other relatively simple data structure like e.g. ring buffers.
- Jach 7y ago
  The question on the interviewee's mind is whether the interview is a proxy for first principles ability or whether they really want you to implement such-and-such exactly correctly. In principle I agree with you -- I had the conversation recently that I have no idea how to implement a red-black tree anymore and would probably fail a "balance a red-black tree when inserting X" type of question, even though I had to do it perfectly in C++ in school. I'm not even sure which color has which constraint by convention. But I more or less remember the constraints, and as I talked through it I sort of remembered how the constraints leads to self-balancing (and an approach to do it). Given time and a responsive interviewer who can answer even dumb questions like "red-black trees are defined to be binary trees right?" I could probably produce something on a whiteboard, but I have my C++ code somewhere and I'm pretty certain I couldn't reproduce that precisely on a whiteboard. What I could do would satisfy some interviewers probably, but would not satisfy others. On the interviewer side of the table, if there's a particular property I want to test for, then I'll try and test for it directly if it's possible. One such property was "ability to make changes to a program one didn't write and can't fit entirely in one's head" since that's the majority of employed work (especially at larger companies) and I've had successes testing that directly on intern candidates by having them do just that in a stripped down version of part of some front-end code. There are a lot of employed devs who seem to struggle with first principles. I don't think it's a good thing and would want to filter on it for a company I controlled from the start... But if we want to test for that specifically, I'm not convinced data structure questions are a good way to do it. Since discrete math should be a standard part of the curricula, I think asking for some proofs of certain theorems given certain axioms and reminders of the rules of inference would be more fruitful. But that would likely be even less popular than linked list style questions. In the limit what I'd really be most satisfied by in terms of having nice proxy measures on cognitive abilities like first-principles reasoning, (system|task|...) decomposition, etc. would be testing IQ and big-5 personality traits directly, plus interviewees should only have to do it once (or at infrequent intervals) rather than every company having their own process, though I think legally you'd have to pay the Wonderlic tax to do it.
alaaibrahim 7y ago
I've interviewed a lot of people, and I've asked LL questions, besides other algorithmic questions, and mostly I ask these questions to new grads with no much experience. The reason is, if you don't have much work experience, what else would I ask you, it's something that you've been learning about recently in your CS degree, and I want to see if you can apply what you learned. If you have work experience that is relevant, or don't have a CS degree, I'll ask something else. For me I feel that a lot of people don't understand that an interview is a conversation, feel free to think out loud, ask questions, and ask for help. I want to see your thinking process, I don't really care about the actual solution.
- ramraj07 7y ago
  Thanks. Unfortunately this is not the case always. I explicitly start interviews telling I'm not academically trained in CS even though I've been practically coding for decades, and I tell them if they ask some "in paper" CS question, I might not answer well. People still ask me to do merge sort - which frankly isn't even in theory that hard - but I think I've subconsciously refused to learn a sorting algorithm just so I can answer a stupid interview question (the day I need to optimize a sorting problem myself I'll learn it hopefully). Whenever the person still insists on asking this without any help, he also comes off as a douche who can only see in black and white. Should I suck it up and learn these things to do better in interviews? Maybe. But thankfully this handicap became a nice filter and I'm in a nice job where people value real experience and "getting things done" more than linked lists and merge sort, so won't need to worry about dealing with these folk for a long time hopefully.
  - valtism 7y ago
    This is why I'm not going to apply for Google any time soon. Their entire hiring process seems to revolve around how much CS trivia you memorised at school.
  - mark-r 7y ago
    Merge sort is incredibly practical though, any time you have to sort a data set that doesn't all fit in memory at once. I've used it a couple of times. As you say, it's not that hard.
bitwize 7y ago
Because they're pretty much babby's first data structure. When I was a kid and I needed to store the bag o' sprites for my first Windows 3.x game engine (don't ask), I had the BRILLIANT idea to store pointers to the previous and next sprite in each sprite, thus creating a doubly linked list with no formal CS experience, nor exposure to that particular data structure. If somebody knows thing one about programming that isn't dinking around in BASIC, it's going to be linked lists.
sadness2 7y ago
Getting asked to do any kind of fancy datastructure algorithm from memory would put me off your company. It has very little correlation with any real-world task. I'm very experienced and get a lot of shit done with high-load systems requiring careful resource management, but I couldn't be bothered with this. My portfolio should show you that I can do things.
- temp129038 7y ago
  Curious...assuming you’re employed in a technical role did your interview not include a technical interview that with data structure or algorithm qs?
  - sadness2 7y ago
    The last 3 technical roles I've been in over the last 8 years or so used realistic technical tasks for the technical tests. It was grounded in actually making something useful work. Intensive CPU/memory optimization is usually the last thing to optimize in a system which is inefficient. When you do get to it, you do it on a case-by-case basis with careful reference to the latest work on efficiency in that particular sub-domain, not by instantly recalling university lectures from 20 years ago. And by the way, the right solution for CPU/Memory optimizations is never linked lists. I think the best technical test you can do is pay your potential candidate to come and do a ticket with your team. You actually get to see what working with them is like, as well as practical ability. Failing that, give them some time to create a practical solution to something a bit tricky, and see what their overall approach is like, when given time to do it with stackoverflow etc. available to them, because that's what real life is like.
    - actuator 7y ago
      Calling someone to work with your team is not scalable. It usually is preceded by resume filtering which can be influenced by human biases.
hwayne 7y ago
Yo, author here. One thing I should really clarify is that while it's a nice sounding argument, my research was pretty haphazard- looking at TIOBE and C programming and extrapolating from there. I recently started doing more thorough research- interviewing people, reading way too many Usenet archives, stuff like that. Based on that I'm _pretty sure_ the main argument still holds, but the story is a bit more complex than the tweetstorm makes it seem. And there's a few sources I haven't dug into yet. Who knows, maybe one of them will completely refute me! I plan on doing a full writeup, but I gotta finish the research first! And if it turns out that I was completely wrong, then I'll write a postmortem instead :)
- wayoutthere 7y ago
  I suspect it was also a way to make sure people had and remembered a formal CS education. Data structures classes were standard in CS curriculum until at least the late-2000s, and linked lists were definitely one of the topics. To that end, I’ve been asked other data structure questions around trees and stacks as well — I view all those as a proxy for “so prove to me you remember your second year CS classes.”
  - cylentwolf 7y ago
    What does that help prove though? That I have a good memory? There are better data structures in pretty much all standard libraries out there for your flavor of language. I am sure that my 2nd year CS class didn't go into the nuances of the coding of the linked list. If I remember correctly it was just make sure you can write one by the end of the week and turn it in.
    - dragonwriter 7y ago
      > What does that help prove though? It's a weak filter for “recent grad”, and along with other individually weak filters a tool for under-the-radar age discrimination.
      - umanwizard 7y ago
morkfromork 7y ago
Nothing like having to spend most of a time-limited interview going over beginner coding and not touch on the actual skills required for the position.
- taneq 7y ago
  You wouldn't do it if beginner coding wasn't required for the job.
  - morkfromork 7y ago
    It's a generic interview for a generic job at a generic company and then they ask you why you want to work there. What do you love about Generic Inc.?
    - kthejoker2 7y ago
      Given the high demand for software devs, why on earth would you accept an interview at a company and role you feel are generic?
chanux 7y ago
Here is the unroll. https://threadreaderapp.com/thread/962424365819277312.html https://threadreaderapp.com/thread/962424365819277312.html PS: After twitter started suffocating their app ecosystem, I can not find an app that does threads well (at least on Android). So unroll helps a lot in worthy threads.
- penguin_booze 7y ago
  Thanks. I find it annoying when people write essays on Twitter.
libria 7y ago
> I suspect this is because a large block of programmers were asked it and continued to ask it, unaware of how deeply tied to the historical context the question actually was. Bad hires are expensive and false negatives are lost opportunity. The industry is constantly looking for ways to improve its hiring. No old practice is off limits. Google no longer asks brainteasers [1]. Rumor has it Facebook discourages dynamic programming now [2]. Yet somehow the author assumes that nobody ever thought to question the Linked List because tee-hee unlike him we're all naive lemmings. No, we do iterate on all our questions and remove the ones that don't correlate well with results. We just continue to find linked lists to be a decent predictor for now, at least no worse than other DS. I do agree that all-or-nothing questions like cycle detection are poor, but those kinds can be found in all data structures. [1] https://qz.com/96206/google-admits-those-infamous-brainteasers-were-completely-useless-for-hiring/ https://qz.com/96206/google-admits-those-infamous-braintease... [2] https://www.teamblind.com/article/DP-questions-at-Facebook-interview-rKhirgq2 https://www.teamblind.com/article/DP-questions-at-Facebook-i...
- Sonnol53 7y ago
  This is great
piinbinary 7y ago
I like to ask questions that involve implementing some small bit of logic on top of a tree or graph data structure. Like the linked list questions, these questions aren't as much testing problem solving or data structures as they are testing whether you've recognized the trees/graphs in the data you worked with recently || you remember working with those data structures from college (which side of the || you fall on depends on your experience level). They're a "can you code" question with a little bit of abstract thinking thrown in.
deepGem 7y ago
Genuine question - who builds linked lists from scratch today ? The only place I found where you had to build a linked list was in LRU cache. Also who writes LRU cache from scratch as you have it already available in Redis ? What exactly does the understanding of LinkedLists prove - I mean I love linked lists not because of their usefulness, because they are easy to reason about and learn in somewhat an adaptive way. Other than that I'm curious to know the actual usefulness of this skill as mostly you are using lists, deques etc.
- kd5bjo 7y ago
  Linked lists allow you to keep track of the order of items when you can’t control their location for one reason or another, and tend to show up as one part of a more complex structure— For example, many garbage collectors use them to keep track of memory regions that have been freed and can now be reused. I expect that they’re used extensively in file system design to keep track of which blocks belong to which file (if any). Maybe you need to keep track of multiple different sort orders over a single set of objects.
ignoramous 7y ago
To play the devil's advocate: > In other words, back in the 90's "how do you reverse a linked list" isn't about "algorithmic thinking" or "data structures", it's _have you coded in C_. If you have, the question is trivial. If you haven't, the question was (ideally) impossible. It is still an interesting excercise to see if someone can code reversing a string (array) and a linked-list, because they form the basic building block of many other data structures, like hash-maps and trees. I doubt it has anything to do with clang, per second, than a fizzbuzz to relatively difficult problems of solving for Graphs, for instance. So absolutely, reversing a linked-list does have everything to do with data-structures. > Take "determine if a linked list has a cycle in it." The solution people are supposed to come up with, "Tortoise and Hare", was AFAICT published in a heavily-cited 1967 research paper. You're asking a candidate to reinvent CS research in 30 minutes! Well, multi-threading was a decade long research, if not more. Do you then expect folks interviewing for Android Development, say, not know about critical sections, race conditions, mutual exclusion, re-entrant locks et al because these were ironed out over decades and decades of research? Guess not. > Removed from the historical context, linked lists got rebranded as "problem solving skills". But this seems the opposite of what you'd expect from the original questions: if you're testing language familiarity, you DON'T want people to be able to fake it! Sure, except if people got interviewed for language familiarity, one would open a different can of worms. For instance, here's the internal details abt trees and lists in Clojure (iirc): https://idea.popcount.org/2012-07-25-introduction-to-hamt/ https://idea.popcount.org/2012-07-25-introduction-to-hamt/ and Rust's HashTable: https://abseil.io/blog/20180927-swisstables https://abseil.io/blog/20180927-swisstables How many folks could answer that? But I bet if we were testing for language familiarity, these are the kinds of questions that'd creep in, which are even arduous than the linked-lists. Be careful for what you wish for. Solving the great tech interview problem isn't straight forward, given by the numerous heated discussions over it over the years, even here on news.yc: "How to not hire a software engineer" https://news.ycombinator.com/item?id=19541617 https://news.ycombinator.com/item?id=19541617 "60m interviews aren't enough" https://news.ycombinator.com/item?id=19811063 https://news.ycombinator.com/item?id=19811063 "What do best interviewers have in common" https://news.ycombinator.com/item?id=15819198 https://news.ycombinator.com/item?id=15819198
- comex 7y ago
xondono 7y ago
I’ve always thought that in that aspect hardware interviews are much better. The typical approach I’ve seen is to give someone a PCB and just ask them “tell me everything you can figure out from this device”. I’ve always wanted to test how well that would work for software interviews: - print some pages with the source file of a toy project - give the interviewee a pen and just ask “tell me all you can about this code”
- pandapower2 7y ago
  that actually sounds like quite a good idea. At least it would serve as a good conversation starter and provide insight into how they think. I'd caution against a toy project however. Just find something small and contained. Toy projects typically don't have enough warts to lead to a really interesting conversation.
- AndrewDucker 7y ago
  I once had an interview where I was handed some source code to explain. Apparently three quarters of previous applicants hadn't even managed that, so it was a great filter for non coders.
- cableshaft 7y ago
  One of my best interview experiences was exactly that. The interviewer handed me a printed out class and said "tell me what this does, any mistakes you see, and any little improvements that you think could be made." I got the job and later confirmed it was a class that was actually in the software I would be working on, not some toy class he came up with. He also asked me a handful of technical questions and had me go over some source code I brought in, but that was about it. At one point he even said, "I know enough to know you can do the job, but now I'm curious what you really know." And asked me some no pressure really low level questions. When I said I didn't know the answer to something he'd spend a couple of minutes explaining the concept to me. I walked out of that interview having learned a few new things about my field. A couple of them have stuck with me over a decade later. And the guy was a grizzled veteran who was the lead on some massive mainstream projects I pretty much guarantee you've heard of. He's probably the most knowledgeable programmer I've ever met. I've never had anyone try going over actual with me since, in probably a couple dozen interviews, and I don't understand why. It seemed very effective.
rgoulter 7y ago
I think it's interesting that "can you write a LL" allegedly made for a "hard to fake" signal.
thraxil 7y ago
This all tracks with my memory and experience (dev since the 90s). The other point that's missing to explain why it is so common is that one of the early Spolsky articles that got a lot of attention at the time (early 2000's) and was very influential asserted that the two areas of programming that seemed to "separate the men from the boys", so to speak, were pointers and recursion. Ie, independent of how long someone had been programming or what language/domain they mostly worked in, there was a tangible rift between developers who deeply understood and could use those concepts and those who didn't. If someone was comfortable with pointers and recursion, it was considered a safe bet that they could pick up pretty much any other concept/language/whatever without much trouble. Implementing linked lists was a good demonstration that you could probably deal with the basic concept of pointers. Spolsky's argument was probably also born from the same experience of the industry at the time. Before the first big dotcom boom, pretty much anyone applying for a programming job who had a CS degree or previous job as a programmer could mostly be assumed to be basically competent. It wasn't a lucrative field so it self-selected for people who could understand "difficult" concepts like that. Anyone who struggled too hard with those would've changed majors or found easier work for better pay. It was mostly HR and managers doing hiring and it mostly worked out because of that natural filtering. After the dotcom boom, when programmers were seen to have high salaries or become early millionaires, the market was flooded with developers with inflated resumes that could talk their way past non-technical interviewers but really had only "programmed" some HTML before and would struggle to write a hello world program in Perl.

219 points by thrower123 7y ago

This feels very post-hoc justification-ey. glibc has had data structures for a good long while. I don't think they offer linked list, but it's not a particularly useful datastructure compared to say, a hashtable.

Something1234 7y ago
But a hash table using separate chaining requires linked lists, so still pretty fundamental.
- latch 7y ago
  And linked lists are the backbone of most persistent data structures and are commonly used as a build block for a ton of things, like LRU caches, queues, ...
  - deathanatos 7y ago
    I agree w/ the LRU, but isn't a vector more efficient for building a queue? (You use it as a ring-buffer. Push/pop are O(1) (amortized for push), and it interacts well with the CPU cache since the memory is contiguous. And you get O(1) indexing, too.) Then there's the rather interesting datastructure that C++ has, std::deque, which seems to get implemented as a vector of pointers to vectors. Still O(1) push/pop/index.

thinkingkong 7y ago

I love this type of analysis / retrospective. Ive done 100s of technical interviews and so far there are a handful of questions that stand out as highlighting great candidates. - the interviewer writes a simple c program that compiles and asks the candidate what it does. The best example is an app that dereferences null. Good developers see it right away and answer “segfault”. - ask someone to do something requiring managing delays, recursion, and error handling. Its wild how few people can handle this who have been developing for 5+ years.

RcouF1uZ4gsC 7y ago
> The best example is an app that dereferences null. Good developers see it right away and answer “segfault”. And more pedantic developers state that it is "undefined behavior" and anything can happen.
- umanwizard 7y ago
  This sort of standards-purism goes too far, IMHO. The map is not the territory: C compilers are real, concrete things that have real behavior regardless of whether that behavior is defined by an international treaty. "What does the C standard require of an implementation when given this program" and "based on your experience, how might you expect a typical implementation to react to this?" are different questions, but both are interesting. None of this implies, of course, that I think it's a good idea to write UB! But I think an ideal candidate would both know what UB is and also some of the ways it manifests in practice. If you don't know that code often segfaults on null dereference, you are going to have a very hard time debugging segfaults that you see in the real world.
  - Gibbon1 7y ago
    Far as I've seen on systems with MMU's generally you get page fault. And then the OS handles that and issues a seqfault. Which is what happens usually when you start trying to poke at random addresses. On an ARM Cortex, if you try and read a null pointer you get the top of stack address. Least on my machine/compiler. If you try and write, then you get a bus fault. Beacuse flash memory is mapped to that address. On an AVR, I think reading gives you the reset vector. And write to address 0 is useally a nop. I think with some magic though you can write to that page of flash. So yeah. Kinda depends.
  - gravypod 7y ago
    The only correct answer would be "you dereference a null pointer". That is the only part of this equation the c language interacts with. That's the entire reason SIGSEGV is a signal to your process. Page faults or access violations are manifested as interrupts in most systems. In some systems there are no such restrictions. Even in C & x86 within RING 0 you should be able to access ((char )0). I've even made an example branch on an old kernel I was making when I was in highschool to test this and it does work [0]. What is unfortunate is that everyone is looking for a different kind of person. If I'm applying to a job, saying "segfault" might be the right answer OR it will be the wrong answer and the interviewer will leave thinking I don't know how this fundamental functionality (in some industries) works. I could also give the more correct answer and look like a know-it-all which, when I'm trying to sell myself based on what I know, is somehow a bad thing. It's a loss no matter which way I play it. I distinctly remember one interview where someone asked me to define a RESTful API for a chat service. So I naturally defined the different objects (ChatRoom, Message, User) and defined what CREATE, LIST, DELETE on them all did. The interviewer was confused because CREATE&LIST are not HTTP methods and I explained that RESTful design isn't really coupled to HTTP and these objects and the operations we can perform with them could be implemented over an RPC or HTTP/json and I listed the steps for both of these approaches. He cut the interview short and I never heard from that company again. [0] - https://github.com/gravypod/Simple-OS/commit/b7a608500b2e70dc0cc2b939ba1bd6381e555bd8#diff-cdd8f39dc4ace4d761440f54b310f2f6R23 https://github.com/gravypod/Simple-OS/commit/b7a608500b2e70d...

RcouF1uZ4gsC 7y ago

Linked lists were also more applicable during that time. The PC world was just starting to move away from segmented architecture to 32-bit linear addressing. With 64K segments, you were limited in how big an array could be since it required contiguous memory. However, with linked lists, since memory did not have to be contiguous, you were only limited by available memory instead of 64K segments. In addition, during the late 80's, early 90's the relative difference between memory and CPU was much less than it is today. Because of this, iterating a link list did not have quite the cost relative to iterating an array that it does today. Nowadays, linked lists are a much more specialty structure rather than the first thing you reach for when you want to store a bunch of stuff.

yodon 7y ago

Sites like HackerRank and TripleByte do a great job of telling me whether a candidate has been studying to pass interview questions on HackerRank and TripleByte. They do very little to tell me whether, in the words of Joel Spolsky, they are "smart and gets things done."

mykowebhn 7y ago
You have me quite interested. What else do sites like HackerRank & TripleByte tell you?
- yodon 7y ago
  That assessing programmers is like assessing teachers - a much harder problem to solve well than naive commentators expect, complete with detailed measurements of the shape of the top of each iceberg.
duxup 7y ago
I'm sort of terrible at terminology and trivia. I finally got an interview with a take home assignment. They asked questions about my work and how I found solutions, most my explanations we're something like: "I just looked some things up and didn't like that approach because it seemed like it wasn't very flexible if things changed, but did like this one so I used it..." I was later told I was not the top candidate, but was the only one who produced an assignment that checked all their boxes and more and showed I could work independently and produce. First job aquired.
wolfgang42 7y ago
I'm going through the Triplebyte process right now (I passed their interview last month and have just started the bit where I talk with companies this week) and that is not at all what they seemed to be testing. Their famous quiz seemed to mostly be checking if you have any idea what you're doing[1], and their two-hour interview[2] spent less than ten minutes on data structures. I muddled through that bit by saying things that sounded plausible (with lots of disclaimers that that was what I was doing and that I had no experience with low-level code) and still passed it with flying colors. Having gone through this process I would say that having some experience and being able to write practical code is probably the best way to prepare, and studying interview questions would probably be fairly ineffective. [1] One of the incorrect answers was to use a factory function that passed the data to an assembly line interface which put it in a package class and shipped it to the user interface. [2] https://triplebyte.com/interview_guide https://triplebyte.com/interview_guide

umanwizard 7y ago

Very interesting thread -- if you're the type of person who comes to the comments before deciding whether to read, I recommend it. I'd also like to point out that today in 2019, linked lists perform like absolute dog shit in many real-world contexts even where they have the best big-O notation. Somebody jumping straight to a solution based on linked lists without at least mentioning memory latency is a sure-fire sign that they have never done detailed CPU performance work. (Which is not necessarily a requirement for most programmers, but it's one piece of signal among others).

mav3rick 7y ago
Arrays get you spatial locality :)
- qtplatypus 7y ago
  So long as they dont span across a page boundary.
  - shereadsthenews 7y ago
    Huh? Spatial locality knows no bounds. The hardware might not automatically prefetch across page boundaries but the application can initiate the fetches itself.
    - XMPPwocky 7y ago
      And, regardless, speculative execution will happily figure out that, hey, the next loop iteration starts with > add rsi, 4; mov rbx, [rsi].d and rsi is 0xDEADBFFC, so rsi+4 is 0xDEADC000, so let's speculatively load that address.... Extra bonus - the compiler may be able to auto-vectorize that. A linked list, on the other hand... hardware can't tell what to prefetch in > mov rsi, [rsi].q; mov rax, [rsi+8].d because it has no idea what rsi is going to be after the first instruction. So it's not just cache locality (which is huge!), it's also the ability of the CPU to actually run things in parallel, instead of serializing everything (and, again, if you're really lucky, the compiler will auto-vectorize the array code)

i_phish_cats 7y ago

Or, is it because it is something that a middle aged middle managers can keep using in their interviews without learning anything new for decades?

umanwizard 7y ago
Ageist BS. I know plenty of >40 who are brilliant interviewers and <25 who are useless ones.
- i_phish_cats 7y ago
  Oh wow that's conclusive data then.
  - dang 7y ago
    Could you please stop posting unsubstantive comments to Hacker News? You've done it repeatedly, and we ban that sort of account. I don't want to ban you, so if you'd review https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html and take the spirit of this site more to heart, we'd appreciate it.
    - i_phish_cats 7y ago
      then ban me
      - dang 7y ago
        I'd much rather persuade you to use HN as intended.
wahern 7y ago
I'll bite. What new, general purpose data structures have emerged in the past couple of decades? Keep in mind the year is 2019.
- 7y ago

throwaway987665 7y ago

Citation needed.. Is there any reference showing that this is the reason that people were asking about linked lists? There is the old joke that organic chemistry saved more lives than penicillin by preventing dumb people from reaching med school. It’s a silly joke but it rests on some correlation between the kind of thinking needed for this course and needed to be successful doctor or medical student. If anything there is probably a stronger correlation between the kind of thinking needed for basic algorithms and data structure questions and the thinking needed to be a strong programmer.

fwip 7y ago
Not to be a downer on your joke, but if we had more doctors, medical care might be cheaper, which would also save lives.
- patrick5415 7y ago
  But only if the extra doctors were sufficiently competent.
- prepend 7y ago
  More doctors who kill people is probably a bad idea. I had a joke about bad PMs...if you can be replaced by a spreadsheet in a shared folder you are probably a bad PM. I think having tons of bad doctors is probably a worse way to solve the high price if medical care than just having better shifting of work within healthcare to apps, therapists, telemedicine, and nurses. Great PMs are awesome and way less important than great doctors since usually people don’t die from non-great PMs.

thethirdone 7y ago

Every time the topic of algorithmic questions in interviews come up I am left wondering if these questions are really as hard as they are made out to be. I would expect most programmers who are not just plumbing together existing technology to be able to implement push,pop,... for linked lists without having to study. You have to do harder things as part of regular programming. > take "determine if a linked list has a cycle in it." I do think that this question if asked without any support if they get stuck is a bad question. You would be relying on the interviewee to either be aware of that research, require that they have the spark of insight, or allow a very suboptimal program. That said, just being aware of the general solution (two pointers moving at different speeds) is enough for me to be confident I could make a solution.

shados 7y ago
> I am left wondering if these questions are really as hard as they are made out to be It's not really about how hard they are, and more about: "Ive never once in my career had to use this on the job, why is it asked in an interview, thats stupid!". That's usually the answer you'll get. But I think that answer contains a lot more info than what we can gather from it at first glance. First, good places will give you hints about what the interview might contain long before you show up. If it's for one of the well known big techs, the questions are all over the internet. They know this. The question essentially amounts to: "Can you make sure you know something about computer science if we ask you to know it". If your answer is "No, that's not worth my time, I'm better than this!", well, I can see why someone wouldn't hire you. The second part, is that it is a self fulfilling prophecy. 20 years ago, a typical team was mostly CS majors, with the occasional odd one out who didn't (I was one of those odd ones out). That means if you didn't know it, it didn't really matter. You could just turn around and bounce it off one of your colleagues. If you made a mistake, they'd catch it. Today however, especially in fields like frontend development, its extremely likely ZERO person in the team has a CS background, or the 1-2 people who did don't remember anything from their college years. That means some problems quickly fall in the category of "This isn't worth trying, let's use a 3rd party solution or wait until the one expert in the company does it for us". Thus, self fulfilling prophecy: you don't need to know these things because the industry punted on the problems you'd need these things to solve, or deferred them to other departments. Web apps, for example, are often very animation light, or low on more advanced graphics, because no one knows the math to make these things happen anymore aside from using a library to make a pretty chart. Since your competitors are in the same boat, there's no pressure to change that. And then those folks feel its dumb to ask these questions in interviews (They don't need it!), and the cycle keeps going. "Why would I need these if Im building forms in javascript all day!". Well, maybe if more people in the team knew how to do more than build forms, we could try and build something fancier than forms.

yardstick 7y ago

For developer roles these days I tend to ask candidates what are the main differences between Lists and Sets. It’s an quick question to weed out most weaker candidates, and is more relevant to the nature of our development: using data structures rather than reinventing them.

BurningFrog 7y ago
What are the most common/amusing bad answers?
- Grue3 7y ago
  I've been interviewing Python programmers and asked about the differences Python list and set (and also tuple) specifically. - a lot of people think Python list is a linked list - a lot of people can't name any difference between a list of different values and a set - a lot of people can't answer what can be an element of a set - a lot of people never had to care about performance so can't explain performance characteristics of these data structures at all - (regarding list/tuple) a lot of people can't explain why immutable data structures are necessary in Python
  - WorldMaker 7y ago
    > a lot of people think Python list is a linked list Well, the Python list is designed to present the operational complexity and API of a linked list in worst case, as that makes it easiest to reason with without knowing/leaking the internal structure details. (This is something of a very classic Lisp tradeoff where "everything is a linked list", but sometimes things are optimized as best as possible as an implementation detail.) The fact that the internal implementation is closer to an array in best case and is in the general case sometimes more like a linked list of array buckets (whether by CDR coding [0] or Unrolled link lists [1], maybe something as recent as Skip List [2] in some implementation cases, or other Linked List variations) is an implementation detail that Python says in its API design shouldn't be important to the consumer. Skimming through Python's own documentation as a refresher for this discussion, the first obvious signal that I can find that Python's lists might not be implemented as basic Linked Lists is all the way down in 5.1.2 (Using Lists as Queues): > It is also possible to use a list as a queue, where the first element added is the first element retrieved (“first-in, first-out”); however, lists are not efficient for this purpose. It still doesn't state what the lists actually are, though, because again Python wants the consumer to treat it as a black box and to know only the risks of the worst case performance. So it is entirely correct from the perspective of a consumer of Python lists to treat them as Linked Lists, because that's what Python presents them as an API (for good black box reasons, including that the implementation could change) and what Python tells you is the absolute worst case for working with them. (Just an unlikely worst case, because Python works hard to optimize away from it.) From the perspective of a Python implementer, yes, it is a huge mistake to build Python lists out of strict, basic introductory textbook Linked Lists without flipping a few more pages to more optimized data structures. All of the above discussion of which would be nearly impossible, especially citing even the relatively few sources as I have, in the context of an interview. It doesn't take into account people that take Python's black boxing of its implementation details at its word. It doesn't take into account the decades old functional programming philosophy (that Python essentially inherits here) that "everything is a linked list until proven otherwise" as a part of the Zen of Lisp. It does seem to point back to the C/C++ centricity of asking Linked List questions the Twitter thread alludes to, because in assuming "Python list is a linked list" is a wrong answer probably does show more of a bias to C/C++-style data structure design and low level concerns than Lisp data structure design and low level concerns. (All of which is fascinating at a meta level, but terrifying to me in the context of actual interviews. There's an increasing feeling that more I know about the field the worse I do on interview "basic" questions because interviewers don't even know which assumptions to check at the door.) [0] https://en.wikipedia.org/wiki/CDR_coding https://en.wikipedia.org/wiki/CDR_coding [1] https://en.wikipedia.org/wiki/Unrolled_linked_list https://en.wikipedia.org/wiki/Unrolled_linked_list [2] https://en.wikipedia.org/wiki/Skip_list https://en.wikipedia.org/wiki/Skip_list

temp129038 7y ago

I don’t really see a problem with LL questions. There’s only so many linked list question variations and they are a simpler subset of trees/graphs, which are useful and have more real world applications. If I was interviewing I would be much happier if I was asked a LL question over a tree or graph problem.

gregmac 7y ago

To those who ask this type of question: What's been your experience with people you hired this way? Did everyone you hired who did well on these questions turn out to be good hires? If not, why not? If you took a chance and hired someone that maybe didn't do a great job on these questions, did they turn out to be a good hire anyway? If so, why?

taneq 7y ago
In my limited experience, they're a good screening test. Even something FizzBuzz level is valuable to weed out applicants who interview well but lack basic competence. Doing well is necessary but not sufficient, mind you. (I interviewed someone who fundamentally failed to understand a trivial question, they were hired despite my negative assessment, and while in all fairness they did better than I expected, they were still an overall liability.)
prepend 7y ago
I don’t know with just this one question compared to others, but as part of a suite of what I classify as “technical thinking questions” I think it’s predicted well programmers who are mid level and up who can figure out problems independent from languages or vendor solutions. I never actually care about the literal code written and usually just ask for pseudo code to understand the logic of how walk through it. So it will fit on a white board or maybe sheet of paper and take maybe 5 minutes or 10 minutes with commentary. I think it’s better if the candidate has never actually written a linked list. Similar questions I ask are “write a database connection pool” or fizz buzz. They are parts screening as a surprising number of applicants can’t write loops or even if statements, which is weird. And part seeing how they ask questions to figure out what’s important requirements or assumptions or limitations. It’s probably worse, in my mind, to write out amazing code without asking questions than to sketch out simple statements asking “how important is multi-threading” or “what libraries can I use” or “where will this get called from?” I don’t have an empirical litmus test from this, but for a few candidates who sucked at this but still got the job, I regretted it. Although one or two moved within the org out of programming to business analysis and project management and did, I think, a good job.

mycall 7y ago

In the 80s, I overused double link-lists in Turbo Pascal. It was my quick-and-dirty database block-storage of choice (minimize memory usage). Then I learned about indexing and switched to dictionaries, btrees or red-black trees for most things.

optymizer 7y ago

I personally find this content delivery method, where a small essay is split into tweet blocks with links and unrelated imagery, very annoying to read and ultimately disrespectful to the reader.

ken 7y ago
Normally I find it frustrating to read a blog post as a sequence of tweets, too, but in this case it seems appropriate. (It doubles as a metaphor for why linked lists are generally a poorly performing data structure on modern architectures.)
ramraj07 7y ago
One advantage I appreciate is there's no filler. At least the good streams have flow and not a single word is used needlessly.

deleted 7y ago

[deleted]

shereadsthenews 7y ago

I like how he casually asserts that most of "us" don't program in C even though C and C++ are the #2 and #3 languages in the TIOBE Index today, after Java. It's fifty times more popular than Rust or whatever trend he thinks his friends are chasing.

actuator 7y ago
The way TIOBE index ranks, a lot of C and C++ numbers are due to uni courses dealing with it. But it is definitely much more used than something like than Rust.
- shereadsthenews 7y ago
  Sure the TIOBE Index is flawed. I wouldn't have even mentioned it but it forms the basis of his argument.
  - hwayne 7y ago
    Yeah it absolutely sucks as a measure. You're better off manually counting languages that appear in job postings. That gives you a better breakdown of what people were actually hiring for.

curtis 7y ago

The basic linked list algorithms are simple enough that a software engineer -- certainly one with a CS degree -- ought to be able to implement them from first principles. And the point of the interview question isn't specifically whether the interviewee can implement a simple linked list algorithm from first principles, it's whether the interviewee can implement anything from first principles.

umanwizard 7y ago
Sure, but I think the thread attempts to answer why linked lists specifically are so popular in interview questions, as opposed to some other relatively simple data structure like e.g. ring buffers.
Jach 7y ago
The question on the interviewee's mind is whether the interview is a proxy for first principles ability or whether they really want you to implement such-and-such exactly correctly. In principle I agree with you -- I had the conversation recently that I have no idea how to implement a red-black tree anymore and would probably fail a "balance a red-black tree when inserting X" type of question, even though I had to do it perfectly in C++ in school. I'm not even sure which color has which constraint by convention. But I more or less remember the constraints, and as I talked through it I sort of remembered how the constraints leads to self-balancing (and an approach to do it). Given time and a responsive interviewer who can answer even dumb questions like "red-black trees are defined to be binary trees right?" I could probably produce something on a whiteboard, but I have my C++ code somewhere and I'm pretty certain I couldn't reproduce that precisely on a whiteboard. What I could do would satisfy some interviewers probably, but would not satisfy others. On the interviewer side of the table, if there's a particular property I want to test for, then I'll try and test for it directly if it's possible. One such property was "ability to make changes to a program one didn't write and can't fit entirely in one's head" since that's the majority of employed work (especially at larger companies) and I've had successes testing that directly on intern candidates by having them do just that in a stripped down version of part of some front-end code. There are a lot of employed devs who seem to struggle with first principles. I don't think it's a good thing and would want to filter on it for a company I controlled from the start... But if we want to test for that specifically, I'm not convinced data structure questions are a good way to do it. Since discrete math should be a standard part of the curricula, I think asking for some proofs of certain theorems given certain axioms and reminders of the rules of inference would be more fruitful. But that would likely be even less popular than linked list style questions. In the limit what I'd really be most satisfied by in terms of having nice proxy measures on cognitive abilities like first-principles reasoning, (system|task|...) decomposition, etc. would be testing IQ and big-5 personality traits directly, plus interviewees should only have to do it once (or at infrequent intervals) rather than every company having their own process, though I think legally you'd have to pay the Wonderlic tax to do it.

alaaibrahim 7y ago

I've interviewed a lot of people, and I've asked LL questions, besides other algorithmic questions, and mostly I ask these questions to new grads with no much experience. The reason is, if you don't have much work experience, what else would I ask you, it's something that you've been learning about recently in your CS degree, and I want to see if you can apply what you learned. If you have work experience that is relevant, or don't have a CS degree, I'll ask something else. For me I feel that a lot of people don't understand that an interview is a conversation, feel free to think out loud, ask questions, and ask for help. I want to see your thinking process, I don't really care about the actual solution.

ramraj07 7y ago
Thanks. Unfortunately this is not the case always. I explicitly start interviews telling I'm not academically trained in CS even though I've been practically coding for decades, and I tell them if they ask some "in paper" CS question, I might not answer well. People still ask me to do merge sort - which frankly isn't even in theory that hard - but I think I've subconsciously refused to learn a sorting algorithm just so I can answer a stupid interview question (the day I need to optimize a sorting problem myself I'll learn it hopefully). Whenever the person still insists on asking this without any help, he also comes off as a douche who can only see in black and white. Should I suck it up and learn these things to do better in interviews? Maybe. But thankfully this handicap became a nice filter and I'm in a nice job where people value real experience and "getting things done" more than linked lists and merge sort, so won't need to worry about dealing with these folk for a long time hopefully.
- valtism 7y ago
  This is why I'm not going to apply for Google any time soon. Their entire hiring process seems to revolve around how much CS trivia you memorised at school.
- mark-r 7y ago
  Merge sort is incredibly practical though, any time you have to sort a data set that doesn't all fit in memory at once. I've used it a couple of times. As you say, it's not that hard.

bitwize 7y ago

Because they're pretty much babby's first data structure. When I was a kid and I needed to store the bag o' sprites for my first Windows 3.x game engine (don't ask), I had the BRILLIANT idea to store pointers to the previous and next sprite in each sprite, thus creating a doubly linked list with no formal CS experience, nor exposure to that particular data structure. If somebody knows thing one about programming that isn't dinking around in BASIC, it's going to be linked lists.

sadness2 7y ago

Getting asked to do any kind of fancy datastructure algorithm from memory would put me off your company. It has very little correlation with any real-world task. I'm very experienced and get a lot of shit done with high-load systems requiring careful resource management, but I couldn't be bothered with this. My portfolio should show you that I can do things.

temp129038 7y ago
Curious...assuming you’re employed in a technical role did your interview not include a technical interview that with data structure or algorithm qs?
- sadness2 7y ago
  The last 3 technical roles I've been in over the last 8 years or so used realistic technical tasks for the technical tests. It was grounded in actually making something useful work. Intensive CPU/memory optimization is usually the last thing to optimize in a system which is inefficient. When you do get to it, you do it on a case-by-case basis with careful reference to the latest work on efficiency in that particular sub-domain, not by instantly recalling university lectures from 20 years ago. And by the way, the right solution for CPU/Memory optimizations is never linked lists. I think the best technical test you can do is pay your potential candidate to come and do a ticket with your team. You actually get to see what working with them is like, as well as practical ability. Failing that, give them some time to create a practical solution to something a bit tricky, and see what their overall approach is like, when given time to do it with stackoverflow etc. available to them, because that's what real life is like.
  - actuator 7y ago
    Calling someone to work with your team is not scalable. It usually is preceded by resume filtering which can be influenced by human biases.

hwayne 7y ago

Yo, author here. One thing I should really clarify is that while it's a nice sounding argument, my research was pretty haphazard- looking at TIOBE and C programming and extrapolating from there. I recently started doing more thorough research- interviewing people, reading way too many Usenet archives, stuff like that. Based on that I'm _pretty sure_ the main argument still holds, but the story is a bit more complex than the tweetstorm makes it seem. And there's a few sources I haven't dug into yet. Who knows, maybe one of them will completely refute me! I plan on doing a full writeup, but I gotta finish the research first! And if it turns out that I was completely wrong, then I'll write a postmortem instead :)

wayoutthere 7y ago
I suspect it was also a way to make sure people had and remembered a formal CS education. Data structures classes were standard in CS curriculum until at least the late-2000s, and linked lists were definitely one of the topics. To that end, I’ve been asked other data structure questions around trees and stacks as well — I view all those as a proxy for “so prove to me you remember your second year CS classes.”
- cylentwolf 7y ago
  What does that help prove though? That I have a good memory? There are better data structures in pretty much all standard libraries out there for your flavor of language. I am sure that my 2nd year CS class didn't go into the nuances of the coding of the linked list. If I remember correctly it was just make sure you can write one by the end of the week and turn it in.
  - dragonwriter 7y ago
    > What does that help prove though? It's a weak filter for “recent grad”, and along with other individually weak filters a tool for under-the-radar age discrimination.
    - umanwizard 7y ago

morkfromork 7y ago

Nothing like having to spend most of a time-limited interview going over beginner coding and not touch on the actual skills required for the position.

taneq 7y ago
You wouldn't do it if beginner coding wasn't required for the job.
- morkfromork 7y ago
  It's a generic interview for a generic job at a generic company and then they ask you why you want to work there. What do you love about Generic Inc.?
  - kthejoker2 7y ago
    Given the high demand for software devs, why on earth would you accept an interview at a company and role you feel are generic?

chanux 7y ago

Here is the unroll. https://threadreaderapp.com/thread/962424365819277312.html https://threadreaderapp.com/thread/962424365819277312.html PS: After twitter started suffocating their app ecosystem, I can not find an app that does threads well (at least on Android). So unroll helps a lot in worthy threads.

penguin_booze 7y ago
Thanks. I find it annoying when people write essays on Twitter.

libria 7y ago

> I suspect this is because a large block of programmers were asked it and continued to ask it, unaware of how deeply tied to the historical context the question actually was. Bad hires are expensive and false negatives are lost opportunity. The industry is constantly looking for ways to improve its hiring. No old practice is off limits. Google no longer asks brainteasers [1]. Rumor has it Facebook discourages dynamic programming now [2]. Yet somehow the author assumes that nobody ever thought to question the Linked List because tee-hee unlike him we're all naive lemmings. No, we do iterate on all our questions and remove the ones that don't correlate well with results. We just continue to find linked lists to be a decent predictor for now, at least no worse than other DS. I do agree that all-or-nothing questions like cycle detection are poor, but those kinds can be found in all data structures. [1] https://qz.com/96206/google-admits-those-infamous-brainteasers-were-completely-useless-for-hiring/ https://qz.com/96206/google-admits-those-infamous-braintease... [2] https://www.teamblind.com/article/DP-questions-at-Facebook-interview-rKhirgq2 https://www.teamblind.com/article/DP-questions-at-Facebook-i...

Sonnol53 7y ago
This is great

piinbinary 7y ago

I like to ask questions that involve implementing some small bit of logic on top of a tree or graph data structure. Like the linked list questions, these questions aren't as much testing problem solving or data structures as they are testing whether you've recognized the trees/graphs in the data you worked with recently || you remember working with those data structures from college (which side of the || you fall on depends on your experience level). They're a "can you code" question with a little bit of abstract thinking thrown in.

deepGem 7y ago

Genuine question - who builds linked lists from scratch today ? The only place I found where you had to build a linked list was in LRU cache. Also who writes LRU cache from scratch as you have it already available in Redis ? What exactly does the understanding of LinkedLists prove - I mean I love linked lists not because of their usefulness, because they are easy to reason about and learn in somewhat an adaptive way. Other than that I'm curious to know the actual usefulness of this skill as mostly you are using lists, deques etc.

kd5bjo 7y ago
Linked lists allow you to keep track of the order of items when you can’t control their location for one reason or another, and tend to show up as one part of a more complex structure— For example, many garbage collectors use them to keep track of memory regions that have been freed and can now be reused. I expect that they’re used extensively in file system design to keep track of which blocks belong to which file (if any). Maybe you need to keep track of multiple different sort orders over a single set of objects.

ignoramous 7y ago

To play the devil's advocate: > In other words, back in the 90's "how do you reverse a linked list" isn't about "algorithmic thinking" or "data structures", it's _have you coded in C_. If you have, the question is trivial. If you haven't, the question was (ideally) impossible. It is still an interesting excercise to see if someone can code reversing a string (array) and a linked-list, because they form the basic building block of many other data structures, like hash-maps and trees. I doubt it has anything to do with clang, per second, than a fizzbuzz to relatively difficult problems of solving for Graphs, for instance. So absolutely, reversing a linked-list does have everything to do with data-structures. > Take "determine if a linked list has a cycle in it." The solution people are supposed to come up with, "Tortoise and Hare", was AFAICT published in a heavily-cited 1967 research paper. You're asking a candidate to reinvent CS research in 30 minutes! Well, multi-threading was a decade long research, if not more. Do you then expect folks interviewing for Android Development, say, not know about critical sections, race conditions, mutual exclusion, re-entrant locks et al because these were ironed out over decades and decades of research? Guess not. > Removed from the historical context, linked lists got rebranded as "problem solving skills". But this seems the opposite of what you'd expect from the original questions: if you're testing language familiarity, you DON'T want people to be able to fake it! Sure, except if people got interviewed for language familiarity, one would open a different can of worms. For instance, here's the internal details abt trees and lists in Clojure (iirc): https://idea.popcount.org/2012-07-25-introduction-to-hamt/ https://idea.popcount.org/2012-07-25-introduction-to-hamt/ and Rust's HashTable: https://abseil.io/blog/20180927-swisstables https://abseil.io/blog/20180927-swisstables How many folks could answer that? But I bet if we were testing for language familiarity, these are the kinds of questions that'd creep in, which are even arduous than the linked-lists. Be careful for what you wish for. Solving the great tech interview problem isn't straight forward, given by the numerous heated discussions over it over the years, even here on news.yc: "How to not hire a software engineer" https://news.ycombinator.com/item?id=19541617 https://news.ycombinator.com/item?id=19541617 "60m interviews aren't enough" https://news.ycombinator.com/item?id=19811063 https://news.ycombinator.com/item?id=19811063 "What do best interviewers have in common" https://news.ycombinator.com/item?id=15819198 https://news.ycombinator.com/item?id=15819198

comex 7y ago

xondono 7y ago

I’ve always thought that in that aspect hardware interviews are much better. The typical approach I’ve seen is to give someone a PCB and just ask them “tell me everything you can figure out from this device”. I’ve always wanted to test how well that would work for software interviews: - print some pages with the source file of a toy project - give the interviewee a pen and just ask “tell me all you can about this code”

pandapower2 7y ago
that actually sounds like quite a good idea. At least it would serve as a good conversation starter and provide insight into how they think. I'd caution against a toy project however. Just find something small and contained. Toy projects typically don't have enough warts to lead to a really interesting conversation.
AndrewDucker 7y ago
I once had an interview where I was handed some source code to explain. Apparently three quarters of previous applicants hadn't even managed that, so it was a great filter for non coders.
cableshaft 7y ago
One of my best interview experiences was exactly that. The interviewer handed me a printed out class and said "tell me what this does, any mistakes you see, and any little improvements that you think could be made." I got the job and later confirmed it was a class that was actually in the software I would be working on, not some toy class he came up with. He also asked me a handful of technical questions and had me go over some source code I brought in, but that was about it. At one point he even said, "I know enough to know you can do the job, but now I'm curious what you really know." And asked me some no pressure really low level questions. When I said I didn't know the answer to something he'd spend a couple of minutes explaining the concept to me. I walked out of that interview having learned a few new things about my field. A couple of them have stuck with me over a decade later. And the guy was a grizzled veteran who was the lead on some massive mainstream projects I pretty much guarantee you've heard of. He's probably the most knowledgeable programmer I've ever met. I've never had anyone try going over actual with me since, in probably a couple dozen interviews, and I don't understand why. It seemed very effective.

rgoulter 7y ago

I think it's interesting that "can you write a LL" allegedly made for a "hard to fake" signal.

thraxil 7y ago

This all tracks with my memory and experience (dev since the 90s). The other point that's missing to explain why it is so common is that one of the early Spolsky articles that got a lot of attention at the time (early 2000's) and was very influential asserted that the two areas of programming that seemed to "separate the men from the boys", so to speak, were pointers and recursion. Ie, independent of how long someone had been programming or what language/domain they mostly worked in, there was a tangible rift between developers who deeply understood and could use those concepts and those who didn't. If someone was comfortable with pointers and recursion, it was considered a safe bet that they could pick up pretty much any other concept/language/whatever without much trouble. Implementing linked lists was a good demonstration that you could probably deal with the basic concept of pointers. Spolsky's argument was probably also born from the same experience of the industry at the time. Before the first big dotcom boom, pretty much anyone applying for a programming job who had a CS degree or previous job as a programmer could mostly be assumed to be basically competent. It wasn't a lucrative field so it self-selected for people who could understand "difficult" concepts like that. Anyone who struggled too hard with those would've changed majors or found easier work for better pay. It was mostly HR and managers doing hiring and it mostly worked out because of that natural filtering. After the dotcom boom, when programmers were seen to have high salaries or become early millionaires, the market was flooded with developers with inflated resumes that could talk their way past non-technical interviewers but really had only "programmed" some HTML before and would struggle to write a hello world program in Perl.