1. 75

  2. 71

    So that they can easily add and reorder questions during the interview.

    1. 14

      “It tests CS fundamentals.” “It tests reasoning through a new problem.” These answers are contradictory

      They aren’t really – they’re alternative answers to the same question, and they both describe a useful outcome. Put together, they give you an idea if the interviewee knows the CS fundamentals and/or can figure them out as they go along.

      Interview at one of the clients I work with involves implementing a binary tree (just the basics, here’s the API, implement adding a new element to it – not even lookups). People we interview generally know what a binary tree is, and usually they have no trouble implementing it – it’s trivial enough that you shouldn’t have a problem with it even if you last saw it at university 10 years ago. We recently had a candidate who was a self-taught programmer with a mathematics degree. We started off showing her a linear search function to code review. She described it well, suggested improvements. The list in the example was sorted, and we asked if the search could be improved somewhat given the patterns in example data. “Well, you could split the list into two halves…” and she described binary search. “Cool, that does algorithm have a name you’re familiar with?” “No, I don’t think so”. Okay then.

      So then there’s the binary tree. The looks at the drawing of it, describes the properties, the implements in in one go, correctly, calling the Node a Knot (translated to Polish they’re the same word). Again, she had no idea if this data structure had any specific name. Naturally she got the job.

      Linked lists may be useless in all applications nowadays (given that CPU caches generally make it an inferior choice in almost every scenario) (bad generalization, see comments below), but they do have a value on interviews imho: they tell you if the candidate knows what the data structures and algorithms lie beyond the APIs they use in their code every day, and if they don’t – even better! It’s easy enough figure it out and to write on the spot – and even if what you write isn’t fully correct, seeing the process and discussing their bugs is still valuable.

      That’s actually a bit offtopic from this article – which is well worth reading in full indeed, and makes sense if you think about it. I think the Spolsky quote actually nails it, even without the historical context – people would still prefer (or think that they’d prefer) to hire Real Programmers [tm] who can deal with pointers rather than “script jocks” who just copy code around.

      1. 19

        Linked lists may be useless in all applications nowadays (given that CPU caches generally make it an inferior choice in almost every scenario)

        This is not the first time I heard this (I recall a specific rust tutorial expressing this in particular), but this is such a weird take to me.

        I work on high-performance datapath in software-defined networking. Those are highly optimized network stack using the usual low-latency/high-io architectures. In all of them, linked-list were fundamental as a data structure.

        One example: a thoroughly optimized hash-table using cuckoo hash, with open addressing and concurrent lookup. It implements buckets as a linked-list of arrays of elements, each cell taking exactly one cache-line. The link-list is so fundamental as a construct there that arguably it is eclipsed by the other elements.

        Another example: a lockless list of elements to collect after the next RCU sync round. Either the RCU allocates arrays of callbacks + arguments to call once synchronized, or the garbage collector consist in a list of nodes embedded in other objects and the reclaiming thread will jump from object to object to free them. The array-based one has issues as each thread will need to reallocate a growing array of callbacks, requiring bigger and bigger spans of contiguous memory when attempting to free elements.

        Another example: when doing TSO on TCP segments, those are linked together and passed to the NIC to offload the merging. To avoid copying around segments of data during forwarding, they must be linked together.

        There are countless other examples, where the high-performance requirement makes the linked-list a good solution actually. It avoid allocated large swath of memory in contiguous chunks, and allows being much more nimble in how memory is managed.

        That being said of course, at the source of those elements (when new packets are received), everything must be done to attempt to pack the maximum of useful data for a fastpath in contiguous memory (using hugepages). But as you go higher in the stack it becomes more and more untenable. Then simple structures will allow building ancillary modules for specific cases.

        I don’t see how linked-list will ever become completely useless. Maybe I’m just too far gone in my specific branch of software?

        1. 10

          Software is full of rules of thumb, some of them are true. I’m pretty sure someone wrote an article years ago on mechanical sympathy where they pointed out that a CPU can chew through contiguous memory a bunch faster than it can chase unknown pointers and since then “everyone knows” that linked lists are slow.

          The reality is always more complicated and your experience optimizing real world systems definitely trumps the more general recommendations.

          1. 1

            I’m pretty sure someone wrote an article years ago

            Bjarne Stroustroup did! https://m.youtube.com/watch?v=YQs6IC-vgmo

          2. 6

            Linked lists make sense in reality because solutions to real problems are bigger than benchmarks. Complicated custom datastructures with linked lists threaded through them are everywhere, but nobody looks at them when they’re looking to make a blanket statement about how fast linked lists are. (Such statements seem to rest on shaky foundations anyway; linked lists aren’t a thing that is fast or slow, but a technique that is more or less applicable).

            I use linked lists mainly for bookkeeping where objects are only iterated occasionally, but created and deleted often, where they appeal mostly because they avoid headaches; their constant factors may not be great, but they scale to infinity in an uncomplicated way (and if I’m creating or deleting an object I’m allocating something in any event). I don’t often see linked list operations in flame graphs, and when I do it’s normally accidentally-quadratic behaviour, so I replace them with things that aren’t list-like at all.

            Final idle thought: not scientific at all, but I note that linked list nodes can live inside the element itself without problems, while array elements are often indirected through an extra pointer to deal with move issues. While it doesn’t absolutely have to, code using such arrays often looks like it suffers from the same data dependency issues linked lists tend to.

            1. 2

              People like to make performance claims without ever generating any numbers to backup their assertions.

              1. 2

                True – same is true for “linked list are faster at insertions/deletions” though. I brought it up because I’ve heard it mentioned time and time again in my university days, and now time and time again at interviews etc, always at a scale where it doesn’t matter or is straight up incorrect. I’m sure they’ll always (or: for the foreseeable future) have their place, even if that place is not the common case. All the more reason to understand them even if you won’t often use them.

                1. 1

                  There seems to be a long tradition of this kind of garbage. Decades ago I used to hear things like “malloc is slow” from my senior colleagues with nobody being able to explain to me (the young punk) what lead to the assertion.

              2. 7

                people would still prefer (or think that they’d prefer) to hire Real Programmers [tm] who can deal with pointers rather than “script jocks” who just copy code around.

                Real Programmers™ is already a fallacy though that tends to amplify the issues on teams by hiring a group of people with very similar strengths, flaws, and viewpoints.

                Put together, they give you an idea if the interviewee knows the CS fundamentals and/or can figure them out as they go along.

                This may be true for some questions, like your binary search example, but I don’t think it’s true of the majority of linked list and pointer type questions that are asked in an interview setting. Linked list cycle finding (i.e. tortoise and the hare) comes to mind—a lot of people in the early 2010’s were defending this as something that either tested if you knew fundamentals or if you could piece them together, but it’s been pointed out half to death by now that the algorithm itself wasn’t developed until years after cycle finding was a known problem with people trying to solve it—almost everyone who passed a tortoise and the hare question either knew it in advance or was given hints by the interviewer that led them there without the interviewer believing they’d given it away (which is a pretty fraught and unnormalized thing).

                In general, I think this is a high ideal that is really hard to build for and people convince themselves they have solved for it at far too high a rate. When I first started interviewing for software jobs (~2010), I learned quickly that if you knew the answer or had seen the question before, the right thing to do was to pretend you hadn’t and perform discovering the answer. This is a problem with nearly all knowledge-based interview questions; there will always be a degree to which you’re testing if the candidate is connected enough to know what the questions will look like ahead of time and what kinds of things will be tested.

              3. 14

                Speaking as someone who went to community college: linked lists were the only data structure they taught us 🙄

                1. 11

                  Well they want you to pass interviews.

                  1. 8

                    I get the feeling that’s what they were optimizing for!

                2. 5

                  The cynic in me says it’s a question for which interviewers can anticipate/learn the answer. Same with most of the IQ and textbook questions asked these days.

                  1. 16

                    I’ve seen some people on HN argue that this is a good thing, because this way you only end up with the really motivated candidates willing to spend untold hours of their spare time studying all these interview questions 🤷

                    Personally, I’d rather do something actually useful.

                    1. 15

                      Yes… you really want a workforce that learns the answers to rote questions. That’s the ticket to success.

                      1. 13

                        I don’t even think that’s necessarily the worst; your selection will be biased towards people who:

                        • have no family/children;
                        • have fewer interests or hobbies outside of programming;
                        • have no (potentially busy/stressful) job with a lot of responsibility;
                        • would rather “land a good job” than work on stuff they really enjoy (the wrong kind of ambition IMO).

                        Of course not every person you hire will fit in to this, but in general your selection will probably be rather biased.

                        1. 3

                          For startups (such as HN covets), the first three are probably considered A+ attributes, aren’t they?

                    2. 1

                      I like asking linked list questions (construct one, add / remove elements, maybe reverse the list) because the relevant algorithms are relatively straightforward to come up with even if you don’t remember them from school. I get to see the candidate solve a problem, but there isn’t any special domain knowledge or tricky brain teaser nonsense to get in the way.

                    3. 5

                      Maclisp: (list . 1)

                      This is wrong, isn’t it? If you have a typical LISP list: (1 . (2 . (3 . (4 . nil))), then (list . 5) would give you ((1 . (2 . (3 . (4 . nil))) . 5) instead of the expected (1 (2 (3 (4 (5 nil)))))

                      1. 4

                        Yep; you’re right; this won’t append to the end of a list. I think the author was probably thinking of (1 . lst) which will put it on the head rather than the tail; putting it on the tail requires (setcdr (last lst) '(4)), or just (append lst '(1)).

                        The point the article is making here is that this is trivial compared to C and Pascal, and while it’s a slight overstatement, it doesn’t seem invalidate the point.

                        1. 1

                          I think so. It should be more like a push: (1 . list)

                        2. 4

                          Based on what developers actually use today, I wonder whether our industry would be better off asking us how to safely build a SQL query for an HTML form, which requires knowledge of parameterized queries and SQL injection; or how to search and replace some text in the DOM, which requires knowledge of JS string-handling.

                          The last time I interviewed for a job (which I happened to get), I was given a Django application and asked to add a new route and corresponding backend functionality. This was for a job where I would be writing Python and maintaining Django applications. Our industry does have some awareness of which sorts of questions are appropriate.

                          1. 5

                            An interview question that feels like it generates good data for me (though I don’t want to claim methodological rigor) is “What do you dislike about your favorite [language/framework/whatever]?”. Anyone who doesn’t have something they can complain about probably hasn’t used it enough in-depth.

                            1. 3

                              I have a coworker who asks this question and am surprised at how many otherwise qualified candidates it trips up. Sometimes I think it betrays a lack of deep knowledge about the language and/or lack of exposure to any others. I do wonder, though, if maybe some people are hesitant to criticize the language used in the role because there is some other language they wish that language looked more like and are unsure just how sympathetic we’re going to be to their preferences.

                              The language we happen to be using is JavaScript, and there’s plenty to criticize, from unintuitive type coercions to inconsistent semicolon insertion. But most sensible JS shops have resolved these with linting rules. The really substantial frustrations that a JS dev wrestles with day-to-day stem from its hedge between different paradigms. That’s where things get political and perhaps the most tactful answer is none at all.

                            2. 1

                              I’m a big fan of that type of interview, and have helped design a few such sessions for various employers. Though to be honest I don’t even tend to do it as Django-specific despite working at a Django shop; people who already understand at least a bit about how web applications work can generally pick up Django or other frameworks quickly enough anyway.

                              Generally I like to structure as two parts: first see whether they do understand how web applications work, then let them go a bit deeper into one area of the example problem to show that their knowledge isn’t just theoretical and it’s a thing they actually could do on the job.

                            3. 4

                              Fantastic, worth reading in full. My personal tl;dr is: because C and Pascal are rubbish, so is Joel Spolsky, and companies under invest in the interviewing process.

                              1. 4

                                Great analysis and exploration, and it makes a lot of sense that these questions emerged from an era where they were actually practical and common concerns!

                                I do think that Spolsky and Cracking the Coding Interview probably have less influence here than the overall power of inertia does; it’s the classic answer of “I ask the interview questions I already learned to ask, which happen to be ones that I’m familiar with anyways because I was asked them.” People move around in the tech industry and bring their questions and interview training with them, and startups often have a lot to think about and “how do we design an interview process” is an easy thing to put on a back-burner: just use the one you already learned at Google (it was good enough for Google). Spolsky’s article feels more like a rationalization of an existing behavior than a push to change or introduce a new one.

                                1. 3

                                  Honestly I’ve never been asked it, but assuming you’re interviewing a new grad or pre-grad intern I’ve assumed it was just meant to be the easy opener.

                                  It can also help filter out some very basic “it isn’t worth interviewing in person” - in my time interviewing I’ve encountered people who didn’t really understand what a pointer is, through to people who didn’t know what hex was (one with a phd). Ours not to reason why people have certain gaps in their knowledge, but if those gaps are in core concepts that sets off alarms.

                                  1. 3

                                    When I started in school/industry (early ‘80s) it was a pretty common notion that you can judge someone’s aptitude for programming by how comfortable they are with pointers and recursion. One of my standard whiteboard questions at Microsoft in the ‘90s was deep-cloning a tree-like structure (and if there’s extra time, a DAG), because it involves both (well, typically…recursion is naturally optional). This had the advantage of not seeming like the question was just to reimplement a standard data structure.

                                    I think nowadays there’s probably a legitimate gap between systems programmers who need to care how computers actually work (what we used to call just “programmers”), and application (?) programmers who focus on business logic and glue code. So there’s probably some similar, but different, notion of judging aptitude for application (?) programming. I still have a very hard time being comfortable with that gap, though.

                                    1. 2

                                      Seems like a plausible history, though I imagine that someone using F77 would be able to generate a linked list with POINTER(p, v)s to STRUCTUREs.

                                      1. 2

                                        Speaking as someone who did interview for programming jobs in the early 1990s – it was actually not entirely common to be asked to do any coding at all. This may be a point of difference with the PC job market vs the Unix world, but for me it was more common to be quizzed on general esoterica about PC architecture. (What’s the memory address range of the 8086? the 80286? the 80386? If you could answer such questions, I guess it was just assumed that you could figure out how to code if you didn’t already.) If there was any coding, it was extremely basic (e.g. implement atoi()), clearly done just to verify that you hadn’t completely padded your resume.

                                        1. 2

                                          Can confirm. Only once was I ever asked to code anything back then and it was super basic (circa 1990). Afterward, when I said that was pretty easy, the interviewer admitted that he had previously been burned by candidates not knowing how to deal with a shell prompt, use vi or how to invoke the compiler. ¯\(ツ)

                                        2. 2

                                          I remember learning about linked lists in Pascal! Never had to use them in real life though.

                                          Also I’ve forgotten all about them except for a mental image of boxes with lines with arrows connected to them.