Why Linked Lists Are an Interview Staple
twitter.com
twitter.com
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).
> 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)
Your point stands though, that linear array access will have similar performance everywhere. Where as LL will have a wider envelope due to speculative loads.
Anyway, a candidate who mentioned all (or even some) of this to me and then went on to write a linked-list solution after explaining the tradeoffs would be well ahead of the curve, for me, relative to someone who has just grinded Leetcode and not thought much about what is going on under the hood.
This doesn't make sense to me, the way you've worded this. A person needn't have ever been exposed to linked lists to understand "what's going on under the hood" - which is a far bigger picture than you're trying to get something as confined as linked lists to fill.
You're seemingly saying, "You don't know fruit because you know fuck-all about dragonfruit," and that - to me - is a pretty myopic take on things; especially, in a growing cloud-centric world.
For example, I would expect that someone who could tell me how the debugger knows where their exception handler is (to be able to handle their exception) would be a better caliber for determining whether they've "thought much about what is going on under the hood" than someone who could just tell me how performant a linked list is, yeah? In the former, it's actually having had to understand what it's doing. In the latter, it's just 'x' type that - maybe - you get exposure to because of uni settings.
...but, to give credit, maybe I'm misunderstanding your intentions, as you've worded them?
You'll often see this (second chance) as exception entries in the Windows Event Log for things like kernelbase.dll, which points to the offending instruction set. The handler in this space typically invokes Watson to generate Watson reports because it was unhandled elsewhere.
The debugger prevents all of that.
Of course, in JIT, you have things like read-ahead for first-chance exceptions...
A good book, in the Windows space, that cannot recommend enough, is Windows Internals[0]. They include how the managed and user spaces interact and coincide with the native and kernel spaces and how all of that transpires, such as how an exception in user mode transitions to kernel before Watson report is created.
There's other in-depth resources[1], as well, if books aren't your thing.
[0] - https://docs.microsoft.com/en-us/sysinternals/learn/windows-...
[1] - https://doar-e.github.io/blog/2013/10/12/having-a-look-at-th...
That doesn't mean it's always worth otimising for, but it's worth remembering yours isn't the only process running.
I am however not Spartacus!
Here's the current one: https://threadreaderapp.com/thread/962424365819277312.html
I wonder what kind of product decisions have led to “we rather piss off and lose thousands of customers than fixing our problems”
Assume I have the simplest possible linked list of integers in basic C. Just struct Node { int data; Node *next; }; Assume I also have a plain old C array of ints.
I can trivially iterate through both of these data structures and sum up the ints they contain. Either way it’s a linear, O(n) operation. However, everyone knows linked lists are slower than arrays. The question is: How much slower?
The most common answer I get is “2x”. This is always after working carefully through the steps to iterate a list and ignoring steps to iterate an array.
I like the question because it tests 2 things: 1) Are you aware of the existence of cache? Many people I’ve interviewed have only heard of it vaguely. 2) If you don’t know the answer, are you at least curious enough to ask what the answer is and have a conversation about it?
This is a bad test. People might be too nervous to ask, especially if they just feel like they've failed a test.
You're testing for "is this person comfortable in an interview setting", not for "is this person curious enough".
I personally think this is very hard to get right, but it has to be a top prio. It's much harder (and much more valuable) than cooking up a sufficiently difficult whiteboard coding question.
Unless of course, you merely use this question as a ruse to elicit a discussion about low-level systems programming.
Didn't OP already imply that the point of the question was not as much to get a specific answer, but to probe whether or not the interviewee knows about all the factors that need to be considered?
Asking "Do you know the magic answer I happen to know?" questions is the great sin of technical interviews. Instead the goal is to keep the candidate comfortable and semi-confident while digging out their mindset about relevant technical issues.
Pedantic nitpick: that is not the simplest LL algorithm. It is more complex than empty().
I happen to like JS and node a lot, for very pragmatic reasons. I've also dabbled in Go and Rust for equally pragmatic reasons. It does help to understand some of the things under the covers when you need them. That said, for a LOT of jobs, code that works and is business rule correct is more important than if it takes a blink of an eye or three.
I tend to prefer a first pass in node/js, and then break things off or optimize as needed in practice. Scale !== raw performance and is often more important.
But outside of that use case, yeah, Linked Lists are generally bad.
LL aren't generally bad at doing what only linked lists can.
When we talk about drivers, from my little exposure (mainly fixing kernel panics), DMA, and cyclical arrays for buffers, I don't recall seeing any linked lists in performant codepaths (it's common to use linked lists for an object pool, like descriptors, but these are O(1) because of tail operations (doubly linked)). But I did see descriptors being put onto cyclical buffers and deferenced, which is the same cost of a pointer deference in a linked list step traversal.
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 :)
It's a weak filter for “recent grad”, and along with other individually weak filters a tool for under-the-radar age discrimination.
But that's certainly not what it actually measures, which is basic knowledge about data structures. It just so happens that being a recent CS grad is statistically correlated with knowledge about data structures.
But it's certainly not a necessary condition. I am not any sort of CS grad, recent or otherwise, and I still know how to implement a linked list, because I learn things on my own, and refresh my memory about things I forget over time.
If you can do a AVL or RB tree from memory, that would be a bonus as well.
But even I think knowing how to implement an RB tree off the top of your head is more about having prepared for whiteboard interviews than about actual knowledge or skill.
I'd say it'd be a bonus for me to have a general understanding of how some sort of self-balancing tree works. For example, for red-black trees I'd be happy with stating the invariant about same number of black nodes along any given path and no two red nodes in a row, explaining why this guarantees O(log(n)) worst-case lookups, and also mentioning the basic notion that you can bubble rotations up the tree so the time it takes to do an update or delete is proportional to path length and so again O(log(n)).
I don't think that remembering off the top of your head the exact code for all 7 (or however many it is, idk) different rotation cases provides any additional signal.
Are they not still standard? I graduated in 2017, and "Data structures and Algorithms" was certainly on my mandatory course list. (Ahh, EECS 281...)
0: https://www.eecs.umich.edu/eecs/undergraduate/computer-scien...
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”
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.
Apparently three quarters of previous applicants hadn't even managed that, so it was a great filter for non coders.
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.
Just make sure the code is linted and idiomatic unless you want the poor interviewee to be bogged down by a bunch of irrelevant details.
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.
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.
I may be kidding myself but I do think having an interviewer who gives a damn and recognizes "the industry" standard sucks is key. I disagree with you in that I do actually care about (aspects of) the solution, but that's not all I care about. Interviewers disagree with each other all the time on better ways to interview, but there's a whole class of interviewers who just don't care and will perform whatever HR or their manager or some other interviewer tells them to do. I think these also get the most complaints from interviewees. The possible exception is if you actually have a robust work-sample test with objective metrics.
Whatever the case interviewers should strive to make sure interviewees understand the parameters of the interview rather than hope the interviewees can read minds. Not all interviewers believe "it's a conversation" and some will penalize you if you ask questions, some will penalize you if you don't ask questions... As an interviewee it's an adversarial experience and without any indication from the interviewer to set expectations to the contrary it's no wonder interviewees will be guarded or choke or whatever else.
I don't like to give straight-up algorithm problems like "implement this data structure and one or two common client use cases for testing". But interviewees should prepare for it, even if they're not fresh grads, because "the industry" sucks at interviewing. What if you're forced to give an algorithm-type problem by someone higher up? I think interviewers who give a damn even a little can make this significantly better than the default archetype characterized by complaints.
For the interview I got hired from most recently I had the fortune of having interviewers who weren't robotic, they said "use any language you like, can you implement a stack?" and I typed "In python, stack = []". They had me elaborate a little, then we talked a bit about Python, I mentioned it can also be a queue if they wanted as the built-in array is quite flexible, then they had me do some other stuff. Having brainfarted "implement a stack with plain native arrays holding ints in Java (and the clever implementation of a stack with memory by self-referencing an object of itself)" in a prior interview I'm aware that even basic stuff can end up taking many minutes of time, I'm sure my interviewers thought that most candidates would take a certain number of minutes for the stack question, but they were dynamic and could ask other things rather than waste both our time. Meanwhile another interviewer I worked with did an interview where he gave someone a "standard" "reverse this string" problem and the person responded in Python with something like "str[::-1]" or similarly concise, but coworker made them do it again in the "standard" way. No, instead that should have been an indication to move on to a more interesting problem.
If I were made to give a linked list problem and someone responded with a good old (cons) from 1959 we'd be done. I wouldn't make them (defstruct) and (defun) their poor equivalent but instead move on to a more interesting algorithm problem that can use linked lists as a building block, e.g. something involving a BFS or DFS (and even though I like iterative versions of such they might very well hit me with a recursive solution, and that'd be fine). Back to the twitter thread I don't think the reason the linked list has endured has anything to do with lower power computers back in the day, since it was a common abstraction on much weaker hardware and came built-in with a variety of popular languages long predating C and long after C.
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.
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.
"Write a linked list" won't tell you someone is a genius. But it will weed out a lot of people who can do "development" but can't hack.
And if you have a job that needs hackers (not all do!), these questions make for cheap filters that save everyone time.
I've heard a lot of post-hoc rationalizations for why the "google style academic interviewing fetish" is more rational than "ask interviewee to perform tasks or answer questions relevant to their job" but using it a justification for continuing the tradition of wheel reinvention in the javascript ecosystem has to be the best.
>"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.
Sadly for the aspiring academic fetishist, building non-fancy forms all day is what a lot of businesses want.
No please don't. I'm very happy with everyone just building normal boring predictable easy-to-use forms.
You act as if this is bad thing. The last thing I want is another bespoke logging solution or ORM.
You can’t imagine the times I gladly ripped out my own bespoke solution for a third party one after finding one was available.
No sane company hires experienced developers to “develop”. They hire developers to have a breadth of industry knowledge to know when to build and when to outsource the “undifferentiated heavy lifting”. During the last few years, both companies I’ve worked for both in an architect level positions have never blinked at solutions that cost money over costing developer time in both development and maintenance.
Web apps, for example, are often very animation light, or low on more advanced graphics.... 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.
Again you act like this is a bad thing. I came into a company where the dev leads were younger and relatively fresh CS grads and even the manager of the department was relatively young. He was the founder of the company before it got acquired.
They had so many ideas about the “right” way to do things and spent so much time arguing about how many angels can dance on the head of a pin they couldn’t ship software for crap.
You see the same thing at Google. After two decades, billions of dollars, untold cancelled projects and with all the smart people they have, almost all of their revenue still comes from advertising.
I saw so many head scratching overengineered custom developed systems that could have been done a lot simpler if they had had any real world experience.
On the opposite end, I was hired two years ago with a mandate partially to migrate all of the bespoke, complicated systems and use managed services/use third party packages where ever possible.
A recent place I worked had a home-grown ORM -and- Object Model written in Perl by one "dedicated" person many years ago. The root cause of many problems...
I didn't quite capture the nuance of what I meant. Sorry about that. Of course if a third party does what you want go for it. But in the situations I'm thinking of, sometimes it's not and people just force their requirements into a suboptimal model. Form validation libs are an obvious example. High level chart libs are another think highchart vs D3)
How many companies adjust their entire process around Salesforce, some Oracle enterprise solution, or project management software?
A commercially successful frontend development requires visual design skills much more than anything else, or no-one will visit the site if it looks bad. I disagree with you about software development teams in other fields having no CS background. The CS majors write backend code and frameworks for frontend developers to use.
If you “get stuck”, what are you going to do when you bump up against your limitations at work?
Part of the job is getting yourself unstuck. If you can show you have ways of making progress when you are out of your depth then you aced the interview, even if you were nowhere near the correct solution.
Being able to think through how you would approach something is infinitely better than having memorized some details (although job-specific details are important too).
So a previous graphics driver implementer may be a great fit for the shader programming job, but be beat in Kubernetes deployment by someone who has done multiplayer web based 3dgames.
If I got stuck on finding whether a linked list had a cycle in it, I would Google for "how to determine whether a linked list has a cycle in it". Ironically, that's the one thing I'm not allowed to do in a coding interview.
In fact, trying to invent something from first principles as you're theoretically supposed to do in an interview would be a waste of my employer's time.
The point is I can easily fill an hour applying different debugging and learning techniques that have a chance at getting me unstuck. That’s one of the things that makes me a good programmer.
This would solve your problem in any realistic use case and you'd never even recognize a constant space solution was possible.
In my extensive experience on both sides of the interview table, this only works for open ended questions, notably architecture/design. With something like architecture, you can grasp what the candidate's baseline knowledge is, see how they acquire information (asking you questions), and how well they are able to synthesize a solution within their knowledge level/parameters specified. So to your point about Kubernetes deploys for a shader programming job, well, yah, that can be a solid architecture question, but you'll have the freedom to ask me all the questions you want.
I have almost never seen a candidate be deemed as "acing" an algorithms question when they were "nowhere" near the correct solution. This is in part due to the large empathy gap existing in algo questions -- it's not obvious to me what baseline info the candidate knows and doesn't know. I mean if I tell you to do detect if a linked list cycles on itself in constant space and O(n) time, what sort of partial solution is there? If you are able to have the insight that this type of problem is in the general class of "two pointer" problems, there's a damn good chance you are going to solve the problem. Absent that, you are just grinding your wheels because the solution space is so large.
(Because of this fact, I generally find whiteboard algo ("leetcode") coding makes for poor interviews. The only types of whiteboarding coding questions I see as useful (for systems engineers) are hybrid architecture/coding questions and/or multithreaded programming, which more become tests of actual programming ability and less so of did you do 50 leetcode questions)
That's only hard if you can't put a depth count field in each list node, and can't use much memory outside the list. If you can do either of those things, it's easy.
Many of the classic list algorithms assume that memory is expensive but random access is free. Today, memory is cheap but random access to a lot of it is expensive.
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.
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.
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.
You can also game big 5 and IQ.
If it were my company I'd take all the high IQ people I could get. I'd probably learn to filter on other things too at the risk of everything blowing up, but getting a lot of smart people together can also lead to amazing stuff (that may not benefit me/the company, but hey). High conscientiousness is a bonus for get-(business-relevant)-stuff-done efficiency, but I don't think it's a hard requirement. I'm not "min" in conscientiousness but I am a slacker below average, nevertheless I seem to get by and have generally kept bosses/teams happy with my output levels.
I think you fit at a lot of companies that don't take those things into account, too. High IQ alone is a big advantage for a lot of the other measures (or gaming such measures) companies like to use. Though you might find a lot of the work dull and/or feel lonely if there aren't any local peers to chat with at your level. On the other hand tech salaries are high; I used to think I might fall into a pattern of "work 1-3 years, take a year or two off depleting savings, go back to work..." but then I realized if I just stretch myself for a long enough continuous period (which isn't actually that long) I ought to be able to "retire" and only go back to working for the Man by choice.
They do very little to tell me whether, in the words of Joel Spolsky, they are "smart and gets things done."
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.
[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.
(It doubles as a metaphor for why linked lists are generally a poorly performing data structure on modern architectures.)
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.
- 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
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
Most of these make me feel smart, though I can't explain the last one either :)
I mean, I like immutable data structures, but the tuple always seemed like a random addition to the language.
How the person goes about leveling their answer is very telling. Is it collaborative with the interviewer to figure out what level of detail is appropriate? Do they immediately interpret the question one of several ways and shoot off an answer? When asked to go into more detail, are they annoyed, happy go give in depth technical explanations, talk about where they would go for answers?
My own personal worst experience is limited to a Masters in Physics who couldn't code at all, code-like experience was limited to some sort of software tool that some PMs might use to create acceptance tests. Though I think a lot of these cases are just indications of a bigger problem higher up, like HR or the hiring manager not adequately setting expectations of the job role, or just not doing basic screening.
(My questions have often been tailored around "get the candidate to implement something that would require a for loop" and that is typically enough to start weeding people out, particularly at the phone screen.)
Aside: I tend to prefer people who have worked with multiple languages that are different from each other, regardless of language. Also, way too many people look down on JS without actually knowing JS.
Everything else is truthy. If you think about the original use of JS as mostly input validation, the values above make total sense.
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?
(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.)
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.
- 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.
And more pedantic developers state that it is "undefined behavior" and anything can happen.
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.
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.
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/b7a608500b2e70d...
"Well, according to the C standard it is undefined behavior. In context X it performs like Y" and so on.
This may not be such a good interview question but, in most industries, C programmers should internalize this.
A good answer would be something like "UB according to the standard, but often segfault in real-world code on x86"...
Foo *ptr = NULL;
ptr->member...
"But it's supposed to generate an exception!"
"Says who?"
"Uh... it just does, right? It's in the CPU or something."
"Really? How do you think that works?" I took the opportunity to explain the mechanisms that were in play on various platforms, including ours, because the engineer in question had always treated indirection through zero as something just universally and magically fatal somehow, and there is no magic, just details.
It's still a darned good idea to keep the first 64K or 1MB or whatever of your address space unmapped (as well as similar guards at the top of your address space) because it catches interesting mistakes, but it's not like this stuff was handed down to us on stone tablets.
I believe the other mechanism could be as simple as pointer arithmetic, and not involve any compiler specific construct, but I would want to check the spec carefully before assuming that. Also, I would yell at whoever thought it was a good idea to store data at 0.
"So what does this code do?"
"Undefined behavior"
"Well, actually, it just prints out 'Hello World'"
"How can you be sure? Will the universe exist at that point? Will your computer not spontaneously combust? Will not a cosmic ray strike and flip the bits just-so, to make it print out 'Hello Girls'?"
My response, "The only reason I know that is because of that bug of ours that keeps coming up..."
Some things just happen more some places and other things don't.
Besides general strategies of trying to lower the adversarial atmosphere I think the only full solution to this problem is to be open for them re-applying after some number of months. That at least codifies a second (or more) chance for candidates who really want to work for your company specifically.
It's also worth bearing in mind the old refrain about X*Y years of experience vs X years of experience repeated Y times.
So -- instead of wondering what kinds of problems will get me through interviews, do you think some way I can train myself to be able to see things like that more often? "Defensive programming" or something?
Similarly while I think unit tests (and other tests) are great, there's a notion of "I can't refactor without tests" that I don't agree with. You can use pure reason! And other tools. Michael Feathers has a whole book showing how to refactor legacy code without tests in order to make it possible to get it covered by tests at all.
Try starting or joining a book club at work (and even better if you can get the company to pay for copies, and maybe lunches for weekly or every-other-week meetings :)) since working with other coworkers (might not even be on your team!) who want to improve will be pretty stimulating and you can learn things from each other. There are lots of great technical books written by programmers with many years of industry experience. Don't take books dogmatically, but many usually have something worthwhile in them.
Writing good code from the software engineering standpoint is something that seems largely missing from the interviewing processes, but it's pretty important for lots of jobs...
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.
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.
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.
If I was interviewing I would be much happier if I was asked a LL question over a tree or graph problem.
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.
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.
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.
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-braintease...
[2] https://www.teamblind.com/article/DP-questions-at-Facebook-i...
> 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/ and Rust's HashTable: 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
"60m interviews aren't enough" https://news.ycombinator.com/item?id=19811063
"What do best interviewers have in common" https://news.ycombinator.com/item?id=15819198
> 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.
You have a point, but the other concepts you mentioned are useful in real-world development. Determining whether a linked list has a cycle in it is not. At most, you could say that similar algorithms are occasionally useful in cryptography[1], where you're looking for cycles in repeated application of a mathematical function. But for an actual linked list in memory, you usually know in advance whether it's supposed to be circular. I guess it could be used as a debugging aid in case the invariant is violated, but in practice you're more likely to end up with invalid pointers, or (for doubly linked lists) mismatched previous/next pointers, or any number of other messy conditions, than with an otherwise valid list that happens to have a cycle.
[1] https://en.wikipedia.org/wiki/Cycle_detection#Applications
The tortise-and-hare algorithm conflates the two: if you’ve already heard of it, it’s quite simple to implement. If not, it takes a flash of insight to consider having two pointers chase each other through the list, one moving multiplicatively faster than the other. I’d bet that flash didn’t come to Floyd in the first 15 minutes he spent on the problem—-which certainly wasn’t under pressure in an interview.