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

101–110 of 113 posts

Re: Linked List Problems (2002) [pdf]

#101

Post by microtherion »

simooooo wrote: post #76
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. Once that happens, it is easy to count the cycle length." Is that so?

The second part of this confused me as well, because the algorithm only detects the existence of the cycle, not its length. However, once you know a node in the cycle (which this algorithm will provide), you simply go around the cycle once more and you have the length.

Re: Linked List Problems (2002) [pdf]

#102

Post by saywatnow »

duneroadrunner wrote: post #18
dgquintas wrote: post #2

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

The problem with trying to substitute lists with vectors is that their iterators behave differently. I.e. vector iterators point to positions rather than elements and are prone to being invalidated. So sometimes it's nice to have a vector that supports iterators that behave like list iterators[1]. [1] shameless plug: https://www.codeproject.com/Articles/1087021/Stable-Iterator...

Can you briefly describe how the msevector + ipointer works? I tried to look at the code but dense C++ is not my forte.

Re: Linked List Problems (2002) [pdf]

#103

Post by barrkel »

haeffin wrote: post #23
panic wrote: post #22

Earlier quoted context omitted.

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.

A data structure with the linked list inline is the other way around, e.g.:

    class Foo {
      Foo *m_next;
      Foo *m_next_mru;
      Foo *m_next_sibling;
    };
With the STL implementation, only one list can have the item inlined; all the other linked lists need two indirections to get to the next element.

Re: Linked List Problems (2002) [pdf]

#104

Post by sidlls »

Bromskloss wrote: post #80
sidlls wrote: post #62

Earlier quoted context omitted.

By working with them on a number of non-trivial problems over the course of some time, usually measurable in weeks or months at least.

OK, I wholeheartedly agree with that. I was thinking, though, that discussing a problem such as the one with the linked list at least would give one sample point of the candidate's ability to reason. In any case, what are you supposed to do if you are restricted to making your decision based on interviews?

It is a data point, but of questionable value generally. Consider this: even academic settings give students multiple chances to demonstrate their true level of competence over a course of months in a very constrained subject and a highly controlled setting. I don't think it's rational to think a panel of interviewers can do it in a matter of hours.

I think interviews are basically just a way we fool ourselves into thinking what is essentially a random chance biased by a self-selected set of applicants is (relatively) more objective.

I don't know that there is a good alternative. I am quite sure the status quo is thoroughly broken.

Re: Linked List Problems (2002) [pdf]

#105

Post by duneroadrunner »

saywatnow wrote: post #102
duneroadrunner wrote: post #18

Earlier quoted context omitted.

The problem with trying to substitute lists with vectors is that their iterators behave differently. I.e. vector iterators point to positions rather than elements and are prone to being invalidated. So sometimes it's nice to have a vector that supports iterators that behave like list iterators[1]. [1] shameless plug: https://www.codeproject.com/Articles/1087021/Stable-Iterator...

Can you briefly describe how the msevector + ipointer works? I tried to look at the code but dense C++ is not my forte.

You mean how it's implemented? Umm, well it's been a while, but basically an ipointer is a proxy for an iterator that is stored internally by the msevector. These "internally stored" iterators are updated when necessary. For example, when insert() or erase() is called.

One nice thing about it is that it roughly conforms to the principle of "only pay for what you use". That is, the run-time cost is roughly proportional to the number of ipointers you have and the frequency of operations that modify the size of the vector.

One caveat is that this mechanism is not thread safe. But whenever you need to share the vector among threads, you can swap it with a vector that is safe to share[1].

And for those that are into memory safety, there is also a memory-safe vector[2] that supports ipointers.

Is this the sort of explanation you're looking for?

[1] https://github.com/duneroadrunner/SaferCPlusPlus#nii_vector

[2] https://github.com/duneroadrunner/SaferCPlusPlus#ivector

Re: Linked List Problems (2002) [pdf]

#106

Post by Spivak »

microtherion wrote: post #101
simooooo wrote: post #76

Earlier quoted context omitted.

"It is easy to see that they will eventually meet on the cycle. Once that happens, it is easy to count the cycle length." Is that so?

The second part of this confused me as well, because the algorithm only detects the existence of the cycle, not its length. However, once you know a node in the cycle (which this algorithm will provide), you simply go around the cycle once more and you have the length.

More specifically you stop moving the hare and send the tortoise around again until it meets the hare counting your steps along the way.

Re: Linked List Problems (2002) [pdf]

#107

Post by Spivak »

tzs wrote: post #31
RomanPushkin wrote: post #8

Earlier quoted context omitted.

3 will also work. People pick 2 intuitively, and it minimizes the overall runtime of the algorithm. (google "Proof of Floyd's Cycle Chasing" for details)

Another advantage of 2 is that it works even if the two pointers do not start on the same element.

It's not specifically 2, any two speeds that are coprime will have the same property.

Re: Linked List Problems (2002) [pdf]

#108

Post by AzzieElbab »

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…

I was asked this exact question during an interview for a senior scala dev position and nearly walked out. I asked the guy to show me how one would go about implementing a cycle with prepend only api and of course did not get an answer or the job

Re: Linked List Problems (2002) [pdf]

#110

Post by saywatnow »

duneroadrunner wrote: post #105
saywatnow wrote: post #102

Earlier quoted context omitted.

Can you briefly describe how the msevector + ipointer works? I tried to look at the code but dense C++ is not my forte.

You mean how it's implemented? Umm, well it's been a while, but basically an ipointer is a proxy for an iterator that is stored internally by the msevector. These "internally stored" iterators are updated when necessary. For example, when insert() or erase() is called. One nice thing about it is that it roughly conforms to the principle of "only pay for what you use". That is, the run-time cost is roughly proportiona…

Thanks, that's clear enough :-). In hindsight I can't imagine what alternative I was thinking of .. I had some idea you might have put the additional cost in the iterator by maintaining only an epoch counter in the vector, but that's obviously not enough to do the right thing in the presence of insert and erase.

Your library looks like a good toolset. While I still find the code pretty impenetrable, the number of tests I can see give me confidence. Bookmarked for reference when I'm using C++ again.

Post reply on HN