> 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:
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.
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.
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.
> 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