Linked List Problems (2002) [pdf]

Post by Bromskloss » Sat, Nov 25, 2017, 4:54 PM UTC

sidlls wrote: post #49

mhandley wrote: post #37

Earlier quoted context omitted.

Whether it is a good or a bad interview question depends on how you use it. I've used a variant of this when interviewing CS PhD candidates. I don't expect anyone to know how to solve this immediately. If anyone did, I'd assume they'd seen it before, and ask something else. What I want is to see how someone thinks about algorithmic problems. As they talk through what they're thinking, there are certain to be problems…

You're not getting any insight into the candidate's problem solving ability in general, though. You may be getting insight into how they think about a specific class of algorithmic problems, and possibly (although it's unlikely) algorithmic problems in general. What this interview question does is confirm your own biases regarding what "algorithmic thinking" is and little more.

Post by xroche » Sat, Nov 25, 2017, 5:31 PM UTC

catnaroek wrote: post #58

xroche wrote: post #25

Earlier quoted context omitted.

This is the tortoise and the hare ( https://en.wikipedia.org/wiki/Cycle_detection ) Expecting a candidate to actually know this trick is however condoning the fact that the technical interview is just a matter of cheating and cramming.

It's essentially impossible to require candidates not to prepare for a technical interview, but someone who can't discover the tortoise and hare algorithm on their own probably shouldn't have a computer science degree.

Post by bastawhiz » Sat, Nov 25, 2017, 5:42 PM UTC

caseymarquis wrote: post #44

greenleafjacob wrote: post #26

Earlier quoted context omitted.

As others have said, this is actually a, perhaps the best, canonical example of a terrible interview question [1]. [1] https://news.ycombinator.com/item?id=7953725

Only if you're looking for that specific answer? Seems pretty trivial to write a memory heavy solution with an array or hash which simply asks: "Have I seen this node before? Is it the first node?"

Post by coliveira » Sat, Nov 25, 2017, 6:11 PM UTC

SunnySkies wrote: post #13

avodonosov wrote: post #6

Earlier quoted context omitted.

He says because of cache misses due to each element being allocated individually. But then working with references is bad in general? If your vector stores references to objects it's bad? Your object fields point to strings - bad too. Should we ditch Lisp and Java? Note, data should not be continuous to stay in cache. Cache is more like paged virtual memory, it consists of cache lines. Before subscribing to the "neve…

You're misunderstanding the advice about contiguous. It's not that it's more likely to stay in cache, but if you're accessing data sequentially it's more likely the data you're going to access next is already in cache. Most (all I've read/looked at) benchmarks in Java have data structures backed by linked lists utterly smashed by things implemented by an array. There was in the last year or two a good c++ talk where…

Post by adamwk » Sat, Nov 25, 2017, 6:36 PM UTC

catnaroek wrote: post #58

xroche wrote: post #25

Earlier quoted context omitted.

This is the tortoise and the hare ( https://en.wikipedia.org/wiki/Cycle_detection ) Expecting a candidate to actually know this trick is however condoning the fact that the technical interview is just a matter of cheating and cramming.

It's essentially impossible to require candidates not to prepare for a technical interview, but someone who can't discover the tortoise and hare algorithm on their own probably shouldn't have a computer science degree.