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

21–30 of 113 posts

Re: Linked List Problems (2002) [pdf]

#21

Post by stochastic_monk »

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…

Vectors are also usually more memory-efficient, period. A singly-linked list uses a pointer for each element an a doubly-linked uses two, while a vector has constant [a pointer and two integers (size and capacity)] overhead. (Unless the vector was dynamically resized and isn't near capacity.)

Re: Linked List Problems (2002) [pdf]

#22

Post by panic »

dgquintas wrote: post #2

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

C++ folks tend to dislike linked lists because it's awkward to make C++ lists intrusive. The STL list containers store the pointers in a separate allocation from the object itself, so they're slower than they ought to be.

Re: Linked List Problems (2002) [pdf]

#23

Post by haeffin »

panic wrote: post #22
dgquintas wrote: post #2

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

C++ folks tend to dislike linked lists because it's awkward to make C++ lists intrusive. The STL list containers store the pointers in a separate allocation from the object itself, so they're slower than they ought to be.

Where did you get that? The STL implementations I know definitely don't. See https://github.com/llvm-mirror/libcxx/blob/master/include/li... for an example - __list_node_base contains the pointers, __list_node contains the object and derives from __list_node_base, so allocating the node with object and pointers is one allocation.

Re: Linked List Problems (2002) [pdf]

#25

Post by xroche »

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.

Re: Linked List Problems (2002) [pdf]

#26

Post by greenleafjacob »

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…

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

Re: Linked List Problems (2002) [pdf]

#27

Post by abalone »

avodonosov wrote: post #7
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…

> It is easy to see that they will eventually meet on the cycle. Not easy for me, but thanks for the algorithm, maybe I will find time and energy to understand and believe. Why by two at a time and not by 3?

Intuitive explanation: Once the pointers enter the cycle the fast one will eventually approach the slow one from behind like runners on a stadium track. If it's one node behind the slow one, then they'll meet on the next move (slow advances one, fast advances two). And if the fast one is two nodes behind, on the next move it'll be one node behind.

Re: Linked List Problems (2002) [pdf]

#28

Post by simonh »

avodonosov wrote: post #7
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…

> It is easy to see that they will eventually meet on the cycle. Not easy for me, but thanks for the algorithm, maybe I will find time and energy to understand and believe. Why by two at a time and not by 3?

Off the top of my head, because if you don’t know where the last element points back to, and there’s an even chance it could be any previous element, the median element is the one on the middle. Two at a time means when you reach the last element and loop back. The lagging pointer will point to the middle element so. Across a population on lists, it will perform better that ratios that favour the lagging pointer being closer to ge back end of the list when the leading pointer loops.

Also, with a 3 skip you could jump 2 ahead of the lagging pointer when you loop back behind and jump over it, which means when it advances it won’t catch you so they won’t meet.

Re: Linked List Problems (2002) [pdf]

#29

Post by linkpoint1 »

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…

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 ingredient is that the difference between the pointers must be coprime with n but still n steps are required to guarantee that the difference eventually becomes zero. So there is no advantage in choosing other values for the increment of the pointers except to achieve that the slowest get faster into the cycle.

Re: Linked List Problems (2002) [pdf]

#30

Post by abalone »

greenleafjacob wrote: post #26
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…

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 sentences... I can see it giving some insight into a candidate.

Post reply on HN