Why Linked Lists Are an Interview Staple(twitter.com)
twitter.com
Why Linked Lists Are an Interview Staple
https://twitter.com/hillelogram/status/962424365819277312
206 comments
I can't read the link, because twitter links never work on my phone... always 'something went wrong' and saying I am rate limited.
As far as I can tell, this is some sort of thing that Twitter does to Safari users because it can't fingerprint them well and thinks it might be abuse.
No, it's not exclusive to Safari. It happens all the time for me in Chrome on Android.
Thanks for the hint. That could be the reason I get this on nightly since .. about four weeks (or six weeks? something like that). Seems to concede with the time the new privacy protections went on by default.
It's not recent - I've had this for years.
I've only just noticed it, but mostly because I've forced myself not to install the Twitter app nor login to my account on the particular device I've been experiencing all these "Something Went Wrong" errors. I assumed it was a "feature" to encourage people to login to the app caused from a bug somewhere in the ad stack, and this seems to corroborate that hunch.
Based on referrer I think. Links from big sites like reddit or hn are often rate limited. Reloading the page wipes referrer and fixes it.
Same thing happens to me frequently. Try reloading? That usually works for me.
I block 3p JavaScript and I never seem to be able to use Twitter without multiple re-loads. So, I usually unroll threads via threadreader.
Here's the current one: https://threadreaderapp.com/thread/962424365819277312.html
Here's the current one: https://threadreaderapp.com/thread/962424365819277312.html
This happens to me every time but if I request desktop mode it always works 100%. Might be worth a try.
This is exactly why I stopped using twitter (that and no matter how many thousands of people I have in my blocklist there is a Trump tweet/comment/quote in their all the time. You can’t ever escape it).
I wonder what kind of product decisions have led to “we rather piss off and lose thousands of customers than fixing our problems”
I wonder what kind of product decisions have led to “we rather piss off and lose thousands of customers than fixing our problems”
I looked through the linux source net code and their usage is actually ubiquitous, but they are paired with hashes and trees. Storing your entire data in a linked list, I agree is horrible, but using linked lists within a hash bucket for keeping entries was acceptable, but because of collision attack causing DDOS susceptibilities, trees were preferred moving forward.
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.
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.
On the otherhand for many applications memory latency isnt an issue. If network and disk io is your bottelneck investing time in optimising that part of the code.
Very true, which is why I said "many real-world contexts" and not "always", and "CPU performance" and not "network-bound performance".
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.
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.
>...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?
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?
How does the debugger know that?
Short-answer: The debugger (in Windows) sits between the first and second and chances, if I recall correctly, to "help" the user by displaying a dialogue notifying them that 'x' is unhandled. Anything in second chance has reached the kernel for handling and is no longer in the user space.
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...
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...
Cache is also an extremely limited resource and the more you waste the less other programs have to work with, slowing them down too, some of what your program pushes out of the cache could be slowing down disk and network processing. There's a tragedy of the commons effect happening in our CPU's.
That doesn't mean it's always worth otimising for, but it's worth remembering yours isn't the only process running.
That doesn't mean it's always worth otimising for, but it's worth remembering yours isn't the only process running.
The Linux kernel is almost entirely built off of linked lists. Are they the best fit for every siuation? No. Have the rumors of their demise been greatly overstated? Yes.
Sure they are widely used, but are they the main data structure in any CPU-bound hot loops? I'd be surprised.
More often than you'd think. The simplification of memory management when you have intrusive linked lists is a huge win, both for perf and correctness.
Arrays get you spatial locality :)
So long as they dont span across a page boundary.
Huh? Spatial locality knows no bounds. The hardware might not automatically prefetch across page boundaries but the application can initiate the fetches itself.
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)
> 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 think Sandybridge or Skylake, made this exact optimization that in turn speeds up execution of vtables and interpreters by reading through a pointer so it might indeed be faster on some architectures.
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.
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.
That works for vtables and interpreters because the vtable/interpreter jump table will be hot and in cache. It doesn't help for linked list iteration unless the next element in the list is in L1 cache.
Indeed, speculative loads from pages that you don't even own has been a big big topic on this site for over a year. There's no respect for page boundaries in the hardware.
That’s why I include a LL question in my code interviews. But, my question is about the simplest possible LL algo:
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?
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?
> 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".
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".
True. Managing the nervousness of awkward engineers during interviews is a whole topic in itself.
In fact, I'd wager that one of an interviewer's primary goals should to find a way to fully disregard someone's interviewing skill. Search hard for questions that a sweaty super-nervous introvert would be able to do just as well as a confident natural talker. Find wording that lets you give hints / explain the question better without the interviewee going "oh no, a hint, that means i failed this step!".
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.
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.
I would have hated this problem. There are so many things unclearly specified. What allocator is used to allocate this linked list? Did you use a small-object pooled allocator that essentially places the nodes of a linked list sequentially in memory? Did you permute the order of the nodes afterwards? Is each node even located in separate pages, using up the TLB as you dereference? Could there be page faults when you deref the next field? Without knowing how the nodes are laid out in memory, it is impossible to answer.
Unless of course, you merely use this question as a ruse to elicit a discussion about low-level systems programming.
Unless of course, you merely use this question as a ruse to elicit a discussion about low-level systems programming.
> 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?
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?
So why not ask exactly that? "What are some of the factors and tradeoffs to consider when implementing X / deciding between X and Y, etc.?"
You would have done great with this question :)
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.
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.
Personally, I tend to get the impression I might not actually enjoy the work at a company that concentrates on low-level questions like that.
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.
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.
The candidates were applying for positions in game development at a company that made high-end 3D mobile games. Raw performance translated directly to retention and therefore revenue there.
The steps to iterate the array should impose no overhead on a superscalar processor. It’s a different situation on a simple embedded processor, but the range of possible answers for memory:ALU ratios, cache line size, cache latency, allocation patterns, MMU behavior and some other factors make this an ill-posed question.
Pedantic nitpick: that is not the simplest LL algorithm. It is more complex than empty().
Pedantic nitpick: that is not the simplest LL algorithm. It is more complex than empty().
Working on embedded with 1 cycle sram and a cpu with minimal/no concept of pre-fetch has the advantage that linked lists become nearly as fast as arrays, just 2x slower!
But outside of that use case, yeah, Linked Lists are generally bad.
But outside of that use case, yeah, Linked Lists are generally bad.
It seems more appropriate to say, Linked Lists are generally bad [when used as replacement for arrays].
LL aren't generally bad at doing what only linked lists can.
LL aren't generally bad at doing what only linked lists can.
I have never done detailed CPU performance work.
I am however not Spartacus!
I am however not Spartacus!
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 :)
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 :)
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.”
> Data structures classes were standard in CS curriculum standard in CS curriculum until at least the late-2000s
Are they not still standard? I graduated in 2017, and "Data structures and Algorithms" was certainly on my mandatory course list. (Ahh, EECS 281...)
Are they not still standard? I graduated in 2017, and "Data structures and Algorithms" was certainly on my mandatory course list. (Ahh, EECS 281...)
No idea; I haven’t been anywhere near a CS department since the late 2000s so I can only vouch until then :)
I wish the project descriptions were public so I could check that the contents match what I remember, but at the very least UMich is still requiring that course: (course requirements guide on page 3 [0], syllabus [1])
0: https://www.eecs.umich.edu/eecs/undergraduate/computer-scien...
1: https://www.eecs.umich.edu/courses/eecs281/syllabus
0: https://www.eecs.umich.edu/eecs/undergraduate/computer-scien...
1: https://www.eecs.umich.edu/courses/eecs281/syllabus
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.
> 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.
It's a weak filter for “recent grad”, and along with other individually weak filters a tool for under-the-radar age discrimination.
Well it is correlated with being a recent CS grad, just like, for example, knowing that d(sin(x))/dx = cos(x) is correlated with being a recent math or engineering grad.
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.
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.
I don’t think I would want to hire someone couldn’t code: a linked list, hash table, and binary tree.
If you can do a AVL or RB tree from memory, that would be a bonus as well.
If you can do a AVL or RB tree from memory, that would be a bonus as well.
I'm a big fan of testing basic CS knowledge in technical interviews, which puts me against the dominant narrative on HN.
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.
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.
This is definitely a possibility! I've interviewed a couple of people and it seems like linked list questions were already traditional by the mid-90's. If "do you remember your formal CS education" was a part of the origin, we'd want to 1) look at CS syllabi from the 80's to see what they focused on, and 2) look at job postings from that time to see if they expected a degree. That'd provide some evidence for this being the case and suggest other predictions (were other common CS topics interviewed?)
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”
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”
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.
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.
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.
Apparently three quarters of previous applicants hadn't even managed that, so it was a great filter for non coders.
This is a fantastic idea, except I would print some real code rather than a toy project. Unlike natural languages there's no way you'll be able to understand a piece of non-trivial code deeply without also being able to write it. And any developer reads many times more code than they write, if only because they have to re-read every time they want to modify anything.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
This has been my approach as well. I always make sure to talk about the experience with projects new grads may have encountered during their CS degree, but it’s hard to have an in-depth talk about your experience if you don’t have much.
Being on the interviewer side of the table more than the interviewee side, I like to think that almost all complaints about the terrible way "the industry" interviews are still valid, but that for the people I've interviewed, even if they share many of the complaints, I like to think most of them also think "well except with that guy, that wasn't so bad." Even though I've always been frustrated about not being able to really try the interview styles I want to try and have to somewhat conform to a terrible mold.
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 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.
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.
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.
"determine if a linked list has a cycle in it."
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.
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.
In my opinion, it doesn’t matter what they ask at all. Give me a question about Kubernetes deploys for a shader programming job if you want. I’m a programmer, my job is to solve coding problems both inside and outside my sphere of knowledge.
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.
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.
> If you “get stuck”, what are you going to do when you bump up against your limitations at work?
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.
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.
What do you do when Google doesn’t have a good answer?
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.
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.
Realistically, you'd walk the list with a visited set and validate you didn't visit a node twice.
This would solve your problem in any realistic use case and you'd never even recognize a constant space solution was possible.
This would solve your problem in any realistic use case and you'd never even recognize a constant space solution was possible.
What are you going to do when the solution to your problem is not on Google/Stack Overflow? Give up? If you're only going to code things that have already been coded, and can be accessed merely by Googling, then what's the point of your job?
> "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."
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)
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)
[deleted]
[deleted]
I agree that "getting yourself unstuck" is part of the job, but interviews also try to get an idea of how well you will do on average.
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.
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.
+1. I 100% agree and this is a great way of putting it.
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).
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).
Programming problems are not solved in about 30 minutes, which is a very typical amount of time in my experience.
> 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.
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.
>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.
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.
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.
This isn't worth trying, let's use a 3rd party solution
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.
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.
> The last thing I want is another bespoke logging solution or ORM.
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...
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...
> act as if this is bad thing. The last thing I want is another bespoke logging solution or ORM.
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)
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)
Business decisions are often made based on forcing requirements onto a commercial third party solution that gets you 90% there instead of spending money up front and in ongoing maintenance to get 100% there. If your company isn’t going to have a competitive advantage, make enough money or save enough money to make that 10% difference worth it, the sacrifice is often worth it.
How many companies adjust their entire process around Salesforce, some Oracle enterprise solution, or project management software?
How many companies adjust their entire process around Salesforce, some Oracle enterprise solution, or project management software?
I think there's some of that, but... no, part of it is because straight logic problems are... hard. And lots of candidates, even solid candidates who have held jobs in software engineering, can't write code with simple-yet-non-trivial logic requirements reliably.
"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.
"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.
> 20 years ago, a typical team was mostly CS majors [...] Today however, especially in fields like frontend development, its extremely likely ZERO person in the team has a CS background
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.
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.
> complex animations & advanced graphics
No please don't. I'm very happy with everyone just building normal boring predictable easy-to-use forms.
No please don't. I'm very happy with everyone just building normal boring predictable easy-to-use forms.
[deleted]
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.
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.
Here is the unroll.
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.
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.
Thanks. I find it annoying when people write essays on Twitter.
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.
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.
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.
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.
So where do I fit? (Very) High IQ, max openness, min consciensouseness.
You can also game big 5 and IQ.
You can also game big 5 and IQ.
If you could game big 5 and IQ the way people game other things, the world would look a lot different... this isn't to say that on an old static test like http://iqtest.dk/main.swf you couldn't give someone the answers or train them to perform better on raven matrices but active researchers and I assume companies like Wonderlic aren't asleep on that sort of thing.
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.
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.
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.
Curious...assuming you’re employed in a technical role did your interview not include a technical interview that with data structure or algorithm qs?
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.
Calling someone to work with your team is not scalable. It usually is preceded by resume filtering which can be influenced by human biases.
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.
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.
Sure the TIOBE Index is flawed. I wouldn't have even mentioned it but it forms the basis of his argument.
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.
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."
They do very little to tell me whether, in the words of Joel Spolsky, they are "smart and gets things done."
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
[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
Thanks for this - I'm actually more familiar with more pure coder test approaches like HackerRank and just mentioned TripleByte in the same breath because they've been advertising their coding test heavily in parts of SF I see (proving that at least some ad dollars do work to some extent).
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.
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.
You have me quite interested. What else do sites like HackerRank & TripleByte tell you?
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.
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.
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.)
(It doubles as a metaphor for why linked lists are generally a poorly performing data structure on modern architectures.)
One advantage I appreciate is there's no filler. At least the good streams have flow and not a single word is used needlessly.
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.
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.
Are you looking for a mathematical difference or differences in their implementation?
These type of broad questions are a good conversation starter.
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?
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?
Exactly this.
What are the most common/amusing bad answers?
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
- 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
Thanks!
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.
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.
> 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
[1] https://en.wikipedia.org/wiki/Unrolled_linked_list
[2] https://en.wikipedia.org/wiki/Skip_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
[1] https://en.wikipedia.org/wiki/Unrolled_linked_list
[2] https://en.wikipedia.org/wiki/Skip_list
People get this wrong? Like CS majors??
Interview enough people and you'll get people with Masters or PhDs in computer science failing what seem to be trivial problems. Like FizzBuzz trivial. You can find anecdotes on HN and other places...
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 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.
I once asked a person with an MSCS what a string was and they didn’t know. I think it might be a language barrier thing so I asked the difference between an array of characters and a string and again, no answer.
Yes, I'd believe it. At a previous employer, our phone screen was "implement min()" for a long time, and it weeded out way too many candidates.
(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.)
(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.)
I usually start with, "In JavaScript what 6 values evaluate to false?" ... almost nobody gets it, but it's usually an excellent barometer for how well they know JS as a language and guides the rest of the questions.
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.
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.
... well now I feel dumb, I guessed 5 ... except for false itself!
false, 0, null, undefined, "", NaN
Everything else is truthy. If you think about the original use of JS as mostly input validation, the values above make total sense.
Everything else is truthy. If you think about the original use of JS as mostly input validation, the values above make total sense.
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?
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 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.
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.
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.)
(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.)
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.
You wouldn't do it if beginner coding wasn't required for the job.
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.?
Given the high demand for software devs, why on earth would you accept an interview at a company and role you feel are generic?
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.
- 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.
I think its potentially bad the common thinking I've seen where an interviewer ( and I've fallen into this trap ) thinks "whoa! X years of development and they can't do that! shakes head slowly". It's more a failure of the interviewer to find out what the X years of experience entailed. They could be insanely good at something really useful and just haven't coded many things like your random coding problem.
At a technical but non programming job someone once told me "Man he doesn't know what X is!"
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.
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.
It can also just be nerves. It sucks, but it happens, and your brain just freezes up and kicks itself later in the evening for looking so stupid.
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.
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.
[deleted]
Agreed! Its super important to make sure the job, job description, candidates, and interview questions are aligned.
it really depends on the that although I get the intention that you are trying to convey.
It's also worth bearing in mind the old refrain about X*Y years of experience vs X years of experience repeated Y times.
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 here's something I've been thinking about recently. I'm 2.5 years into my first job out of college and I think I'm starting to pick up on things like "oh let me guard against something that could return null" or "let me guard against calling .at() out of bounds". I'm starting to feel really thankful that my work has me thinking like this, because I can actually see it as a sign of getting better as a developer.
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?
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?
I'm not that far ahead of you years-wise (5 years post graduation though I had a combined 3.5 or so years of paid work during/before that) and while I think defensive programming is great and keep it in mind I also have recently been thinking we need more champions of pure reason. Instead of "let me guard against this possibly being null", go and actually look: can it really ever be null? Or, can you make it not ever be null? Or "do I even care if it's null?" In many cases, the guarding is just paranoia or a band-aid against spending a little effort to go look and maybe change. In the worst cases the guarding becomes itself a failed guard. One piece of advice is know your programming language pretty well. e.g. in Java I've caught a few people "guarding" against null by wrapping the thing in Optional.of(), except that throws if the thing is null. They need Optional.ofNullable().
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...
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...
Run your code in as many sanitizers and UB detectors as you can (ubsan, ASAN, valgrind, ...). Send code reviews to smart and detail-oriented people on your team.
> 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.
And more pedantic developers state that it is "undefined behavior" and anything can happen.
Interesting go to response!
"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'?"
"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'?"
You can define this behavior if you want to. I did that on an embedded system where location zero was mapped and it was a complete pain in the fundament to arrange things so it would generate a fault. So I put on my wizard hat, intoned "Indirecting through NULL yields the value <some-reset-vector-or-something>, so mote it be!" and sure enough, a few weeks later one of the Q/A folks wrote a test that indirected through zero and filed a bug when it didn't explode.
"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.
"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.
The issue is that it is a C program, and according to the C standard, dereferencing (void * )0 is undefined behaviour. If you actually want to get at memory address 0 in a C program, you need to use some other mechanism or use a compiler that explicitly defines dereferencing NULL.
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.
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.
This doesn't remove UB though. Your compiler still can assume that null-dereference never happens and generates code with this assumption.
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.
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.
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/b7a608500b2e70d...
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...
You make it sound like there is no right answer, but why couldn't you just explain to the interviewer everything you wrote in this post?
"Well, according to the C standard it is undefined behavior. In context X it performs like Y" and so on.
"Well, according to the C standard it is undefined behavior. In context X it performs like Y" and so on.
An ideal candidate would have been bitten by bugs where the segfualt never happens because the offending code got optimized away. Once you've been bitten by that once, it become hard to answer with just "segfault".
I'm not sure it even has to get optimized away. Stuff like,
Foo *ptr = NULL;
ptr->member...
I am not suggesting someone should answer with "segfault" and in fact I think that might be a worse answer than just "UB".
A good answer would be something like "UB according to the standard, but often segfault in real-world code on x86"...
A good answer would be something like "UB according to the standard, but often segfault in real-world code on x86"...
How about “are you aware that this ‘segfault’ may be turned into RCE by a clever compiler plus a clever attacker”?
This may not be such a good interview question but, in most industries, C programmers should internalize this.
This may not be such a good interview question but, in most industries, C programmers should internalize this.
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.
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.
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.
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.
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.
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.
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.
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.
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.
If I was interviewing I would be much happier if I was asked a LL question over a tree or graph problem.
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.
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.
But a hash table using separate chaining requires linked lists, so still pretty fundamental.
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, ...
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.
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.
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.
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.
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.
Not to be a downer on your joke, but if we had more doctors, medical care might be cheaper, which would also save lives.
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.
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.
But only if the extra doctors were sufficiently competent.
> 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-braintease...
[2] https://www.teamblind.com/article/DP-questions-at-Facebook-i...
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...
This is great
[deleted]
I think it's interesting that "can you write a LL" allegedly made for a "hard to fake" signal.
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/ 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
> 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
There’s a big difference between testing whether someone already knows something vs. whether they can figure it out on the fly.
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.
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.
Sure. The problem with the argument I wanted to highlight wasn't the puzzle nature of the solution, but the fact that the OP chose to instead focus on the research angle. I mean CSP, Actor Model, Lisp have strong foundations that took a lot of research... as did everything else from Type Systems to Linkers to Compilers. That said, I get your point too, I might have misunderstood OP.
> > 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.
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
> 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
Thanks. I agree. I also wanted to highlight that OP might be wrong to dismiss interview problems just because it took someone decades to figure out an answer to.
i_phish_cats(3)
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.
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).