From my personal experience, "usual answer" #2 is bogus—in general, if something is explicitly taught in classes, it's because it required the expertise and insight of CS researchers (often from...
From my personal experience, "usual answer" #2 is bogus—in general, if something is explicitly taught in classes, it's because it required the expertise and insight of CS researchers (often from early in the field's development), and cannot reasonably be expected to be figured out by a student over the course of a problem set—or a job applicant in an hour-long interview.
(Random example: the tortoise and hare algorithm for finding cycles in a linked list—at one point a darling "gotcha" algorithm interview question, though to the best of my knowledge now thankfully out of style—is trivial once explained, but deeply clever and incredibly unlikely to be re-invented. If Knuth's attribution is to be believed, it was first developed by Turing-award winner Robert Floyd, who has his name on multiple famous algorithms; certainly not a benchmark to which you should try to hold even your most brilliant, talented applicants.)
Therefore, the people who ask linked list questions in interviews and know why they're asking, are asking to test the applicant's theoretical CS knowledge—essentially, to establish a benchmark on their schooling, as the now-massive performance gap between main memory and CPU cache means non-local data structures have little use if they don't deliver a significant big-O improvement, and linked lists in particular have almost no practical benefit over a resizable array and are therefore seldom used in practice and unlikely to be self-taught. Modulo questions about the appropriateness of required credentials for programming jobs¹, this seems okay to me, though I imagine better questions are easily possible.
And, of course, the number of people who clearly don't know why they're asking linked list questions in interviews is a problem. Rote questions which the interviewer doesn't themselves understand measure a number of things—the interviewer's pronunciation, for instance, and whether the applicant learned the same terminology used in the question—but the signal for the applicant's knowledge and talent is very faint.
¹ Just to put my biases on the table, I lean towards credentialing being beneficial, though I don't think it matters much either way to this overall conversation.
I honestly can't remember ever using a linked list in practice in 30 years of professional programming in Pascal, C, C++, and related languages. I've used things that were probably implemented...
I honestly can't remember ever using a linked list in practice in 30 years of professional programming in Pascal, C, C++, and related languages. I've used things that were probably implemented under the hood as a linked list, like a double-ended queue, on occasion, but I've never directly needed a linked list for anything as far as I can remember.
I have much less experience than you - a few years of hobbyist C++ (video game) programming, but in there I have found use cases for linked lists as data structures where even if they change,...
I have much less experience than you - a few years of hobbyist C++ (video game) programming, but in there I have found use cases for linked lists as data structures where even if they change, references/pointers/iterators to elements within it are still valid. That said, there are other data structures with the same guarantee, that aren't even implemented as linked lists, and overall this is not a common need.
I don't think #2 has to be bogus. Yeah, expecting someone to get tortoise and hare is obnoxious, but that doesn't need to be the success state of the interview. There's also a O(n) time but O(n)...
I don't think #2 has to be bogus. Yeah, expecting someone to get tortoise and hare is obnoxious, but that doesn't need to be the success state of the interview. There's also a O(n) time but O(n) memory solution - if the interviewee succesfully got that one, and their logic and thought process were sound, that would be perfectly fine.
It's happened to me before. I got the max in a slinding window question without knowing the problem - there's a clever double queue solution that gets it in O(n) - and did an unoptimal nlogn solution with a priority queue. I got the offer afterwards, so evidently I passed.
I completely agree with the conclusion of the post. The first thing I thought when I read #1 and #2 were, "Nah, this stuff is asked to make sure that the candidate groks pointers." How important...
I completely agree with the conclusion of the post. The first thing I thought when I read #1 and #2 were, "Nah, this stuff is asked to make sure that the candidate groks pointers."
How important is this in real life? As always, it depends!
From my personal experience, "usual answer" #2 is bogus—in general, if something is explicitly taught in classes, it's because it required the expertise and insight of CS researchers (often from early in the field's development), and cannot reasonably be expected to be figured out by a student over the course of a problem set—or a job applicant in an hour-long interview.
(Random example: the tortoise and hare algorithm for finding cycles in a linked list—at one point a darling "gotcha" algorithm interview question, though to the best of my knowledge now thankfully out of style—is trivial once explained, but deeply clever and incredibly unlikely to be re-invented. If Knuth's attribution is to be believed, it was first developed by Turing-award winner Robert Floyd, who has his name on multiple famous algorithms; certainly not a benchmark to which you should try to hold even your most brilliant, talented applicants.)
Therefore, the people who ask linked list questions in interviews and know why they're asking, are asking to test the applicant's theoretical CS knowledge—essentially, to establish a benchmark on their schooling, as the now-massive performance gap between main memory and CPU cache means non-local data structures have little use if they don't deliver a significant big-O improvement, and linked lists in particular have almost no practical benefit over a resizable array and are therefore seldom used in practice and unlikely to be self-taught. Modulo questions about the appropriateness of required credentials for programming jobs¹, this seems okay to me, though I imagine better questions are easily possible.
And, of course, the number of people who clearly don't know why they're asking linked list questions in interviews is a problem. Rote questions which the interviewer doesn't themselves understand measure a number of things—the interviewer's pronunciation, for instance, and whether the applicant learned the same terminology used in the question—but the signal for the applicant's knowledge and talent is very faint.
¹ Just to put my biases on the table, I lean towards credentialing being beneficial, though I don't think it matters much either way to this overall conversation.
I honestly can't remember ever using a linked list in practice in 30 years of professional programming in Pascal, C, C++, and related languages. I've used things that were probably implemented under the hood as a linked list, like a double-ended queue, on occasion, but I've never directly needed a linked list for anything as far as I can remember.
I have much less experience than you - a few years of hobbyist C++ (video game) programming, but in there I have found use cases for linked lists as data structures where even if they change, references/pointers/iterators to elements within it are still valid. That said, there are other data structures with the same guarantee, that aren't even implemented as linked lists, and overall this is not a common need.
EDIT: wording/typos
I don't think #2 has to be bogus. Yeah, expecting someone to get tortoise and hare is obnoxious, but that doesn't need to be the success state of the interview. There's also a O(n) time but O(n) memory solution - if the interviewee succesfully got that one, and their logic and thought process were sound, that would be perfectly fine.
It's happened to me before. I got the max in a slinding window question without knowing the problem - there's a clever double queue solution that gets it in O(n) - and did an unoptimal nlogn solution with a priority queue. I got the offer afterwards, so evidently I passed.
I completely agree with the conclusion of the post. The first thing I thought when I read #1 and #2 were, "Nah, this stuff is asked to make sure that the candidate groks pointers."
How important is this in real life? As always, it depends!