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

51–60 of 113 posts

Re: Linked List Problems (2002) [pdf]

#51

Post by Retr0spectrum »

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

Re: Linked List Problems (2002) [pdf]

#52

Post by pjmlp »

abalone wrote: post #30
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

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…

My CS degree had a duration of 5 years, and I graduated during the 90's.

Excuse me if I don't recall a complete year of Algorithms and Data Structures lectures and evaluation projects done about 25 years ago.

Re: Linked List Problems (2002) [pdf]

#53

Post by linkpoint1 »

avodonosov wrote: post #47
linkpoint1 wrote: post #29

Earlier quoted context omitted.

A proof that the algorithm detects the existence of a cycle. If there is a cycle of length n then eventually both pointers get into the cycle. Since at each step the distance between the two pointers is increased by one module n then the distance becomes zero. Also the time to detect the loop is bounded by the time it takes both pointers to get into the loop plus the cycle length. Also this proof shows that the key i…

Thank you, super.

if you program in Lisp the function list-length gives nil for circular lists. Ninety-nine problems contains similar problems with lists.

I should have said that the difference between increments must be coprime with n to guarantee that the differece becomes 0 module n, that is both pointers get equal.

Re: Linked List Problems (2002) [pdf]

#54

Post by rayiner »

hota_mazi wrote: post #50
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

Totally agree. If I ask this question (I never would) and I get the "tortoise and the hare" answer, it's much more likely that the candidate already knew the answer rather than deduced it themselves. And I have learned exactly nothing about that candidate, except that they probably looked up common interview questions before coming. A more reasonable answer to this question would be to store the nodes you've already…

Plus, someone should be able to get the hash table brute force answer coming in cold.

Re: Linked List Problems (2002) [pdf]

#55

Post by rayiner »

dgquintas wrote: post #2

"Just say no to linked lists!" https://youtu.be/fHNmRkzxHWs?t=2099

Look in the Linux kernel to see how often linked lists are used. The list of a process’s memory mapping are, for example, maintained as linked list in parallel with a balanced tree. Lots of queues are maintained as linked lists. Free slabs in the slab allocator are kept in a linked list. The list goes on.

Re: Linked List Problems (2002) [pdf]

#58

Post by catnaroek »

xroche wrote: post #25
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 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.

Re: Linked List Problems (2002) [pdf]

#60

Post by mhandley »

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.

Of course you're correct, and this is why such a question only forms a part of such an interview. I'm much more interested in what someone has built. We'll have a good discussion about any software they've built, and what they found interesting or difficult about that. Or basically anything where they showed creativity.

Still, in my area of CS, algorithmic thinking is an important aspect of the sort of systems we design, so this sort of question does help me build up a picture of the person's skills and approach to problems.

I have found though that there's pretty good correlation between how someone goes about answering this question (the mental process they follow, not whether they can jump to a solution), and how interesting the systems they've previously built are. And, although my sample size is small, the people who did best on this question also did best over the next few years on the systems they built and analyzed during their PhD.

Post reply on HN