Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Linked List Problems (2002) [pdf]

cslibrary.stanford.edu

Post reply on HN
Print view View original

81–90 of 113 posts

Re: Linked List Problems (2002) [pdf]

#81

Post by trhway »

marcus_chang wrote: post #38
abalone wrote: post #30

Earlier quoted context omitted.

I mostly agree with this, however if the job requires a C.S. degree or equivalent and you assume all qualified candidates have been exposed to this, then perhaps it can be a useful question for testing how well you can explain a solution. Just look at how varied and complicated some of the explanations are for this out there. Some take mathematical approaches, others (me) try to boil it down to a few intuitive senten…

Unless you're interviewing Dijkstra, it's a ridiculous question to ask. Anyone who's heard it before knows the answer instantly (I knew the answer before I even finished reading the description) and anyone unfamiliar with it will likely flail.

>Unless you're interviewing Dijkstra, it's a ridiculous question to ask.

like many ridiculously looking interview questions, they are actually a filter. For this particular types of questions young people tend to quickly solve them. In 1987, in 9th grade, during one of the first computer classes, never before seeing or touching programming (previous years of school in a small town in USSR), I myself came up with Dijkstra algorithm in less than 10 minutes when we were assigned task of finding shortest path. I remember the teacher looking impressed :) These days i treat it more like a signal - if people asks such puzzles a lot then they either intentionally filtering or even don't understand that and seriously think it is important CS(cience).

Re: Linked List Problems (2002) [pdf]

#82

Post by bjoli »

auxym wrote: post #75
bjoli wrote: post #73

Earlier quoted context omitted.

Who couldn't figure out the idea behind tortoise and the hare? Maybe not the implementation, but the concept is probably the simplest way of going about it. I am no programmer, and I managed to implement it not too long ago all on my own. It took no more than 10 minutes from idea to working implementation.

As the linked article in parent post points out, this was an open problem in CS for 12 years before someone came up with the tortoise and hare algorithm. You really expect a candidate to come up with it from the top of their head, in a few minutes, during a stressful interview?

No not the specific solution, but the concept of having to pointers moving at different speeds did be pretty clear no?

It is really not a hard problem. If you are dealing with cirular lists you will end up having to solve it sooner or later. The "open question in CS for 12 years" is probably easier explained by "nobody could be bothered" than "it is hard".

Re: Linked List Problems (2002) [pdf]

#84

Post by winstonewert »

praptak wrote: post #72
jackmott wrote: post #40

Earlier quoted context omitted.

If you iterate over the list within an order of magnitude as often as you remove an element from the middle, an array will still be faster despite not having constant time removal, no matter the size of the list. To restate, if you have a workload where you iterate over your collection ~500 times, and remove an element from the middle ~1000 times, an array will usually outperform a linked list on a modern computer, n…

That's why I mentioned the LRU implementation. It does not iterate over the list, only adds elements to the front, deletes from the back and moves from the middle to the front. Refs to nodes are stored in a map, so iteration is not necessary to find an element.

But how do you find the element to be moved from the middle if not by iterating over the list?

Re: Linked List Problems (2002) [pdf]

#85

Post by lucio »

delta1 wrote: post #57
lucio wrote: post #24

What is LISP

In case you're serious, and too lazy to google it... [1] LISP is a family of programming languages. [1] https://www.google.com/search?q=LISP

It was sort of a Jeopardy response. I'm sorry if it was too opaque. The OP's article just brought LISP into my mind.

Re: Linked List Problems (2002) [pdf]

#86

Post by abalone »

marcus_chang wrote: post #38
abalone wrote: post #30

Earlier quoted context omitted.

I mostly agree with this, however if the job requires a C.S. degree or equivalent and you assume all qualified candidates have been exposed to this, then perhaps it can be a useful question for testing how well you can explain a solution. Just look at how varied and complicated some of the explanations are for this out there. Some take mathematical approaches, others (me) try to boil it down to a few intuitive senten…

Unless you're interviewing Dijkstra, it's a ridiculous question to ask. Anyone who's heard it before knows the answer instantly (I knew the answer before I even finished reading the description) and anyone unfamiliar with it will likely flail.

Nah, I wouldn't say everyone would flail but Dijkstra. There are simpler solutions to cycle detection.. maybe not as efficient as Floyd, but you could answer the question. For example you could start with something basic and unoptimized like keep a data structure of all the nodes you walk, and when you hit one that's in the structure then you've encountered a cycle. This is a fair approach to engineering solutions to novel problems -- don't panic, get something working, then optimize where necessary.

And if you already know the best practice, like I said, it's not just about whether you know the answer -- it's how simply you can explain it to a teammate and the theory behind why it works. That's also a useful skill to interview for, especially for more experienced candidates.

Re: Linked List Problems (2002) [pdf]

#87

Post by codefined »

bjoli wrote: post #82
auxym wrote: post #75

Earlier quoted context omitted.

As the linked article in parent post points out, this was an open problem in CS for 12 years before someone came up with the tortoise and hare algorithm. You really expect a candidate to come up with it from the top of their head, in a few minutes, during a stressful interview?

No not the specific solution, but the concept of having to pointers moving at different speeds did be pretty clear no? It is really not a hard problem. If you are dealing with cirular lists you will end up having to solve it sooner or later. The "open question in CS for 12 years" is probably easier explained by "nobody could be bothered" than "it is hard".

Considering there are limited use cases for pointers moving at different speeds in other fields, no, I wouldn't say it would be easy.

The idea itself, once you hear it, instantly makes sense. But having the ingenuity to thinking of it during a stressful period shouldn't be used as a measure of how good a candidate would be for a position. Especially considering there are hundreds of different ways of approaching such problems.

Re: Linked List Problems (2002) [pdf]

#88

Post by baddox »

winstonewert wrote: post #84
praptak wrote: post #72

Earlier quoted context omitted.

That's why I mentioned the LRU implementation. It does not iterate over the list, only adds elements to the front, deletes from the back and moves from the middle to the front. Refs to nodes are stored in a map, so iteration is not necessary to find an element.

But how do you find the element to be moved from the middle if not by iterating over the list?

The commenter mentions that in the last sentence. There is some separate data structure that also has references to nodes in the middle of the linked list.

Re: Linked List Problems (2002) [pdf]

#89

Post by winstonewert »

baddox wrote: post #88
winstonewert wrote: post #84

Earlier quoted context omitted.

But how do you find the element to be moved from the middle if not by iterating over the list?

The commenter mentions that in the last sentence. There is some separate data structure that also has references to nodes in the middle of the linked list.

Oy! I can't believe I missed that.

Re: Linked List Problems (2002) [pdf]

#90

Post by itissid »

Retr0spectrum wrote: post #51
herodotus wrote: post #5

One of my all-time favourites is this: suppose you have a linked list that eventually cycles: that is, the link of one of the nodes in the list points to a previous node in the list, but not necessarily the first node. Write a function to compute the cycle length of the cycle. Now if it was just a simple circular list, this would be trivial: set a pointer to a node, and move another pointer a node at a time until the…

This algorithm can also be used for integer factorisation: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm

I always wonder if odd(and perhaps pointless) interview Q like this have been contorted from the original(much useful) problem like pollard's rho or it just happened to reduce to more useful ones.

Digging deeper into such questions yields fun observations which may be the only useful thing that comes from questions like these. Like the length of the Longest Increasing Subsequence of a sequence A, has a fun fact to do with the Chromatic Number of a graph derived formed from a matching between A and sorted(A).

Theoretical Math is beautiful and the answer to so many things.

Post reply on HN