Linked List Problems (2002) [pdf]
cslibrary.stanford.edu
cslibrary.stanford.edu
A nice way to do this is to start with two pointers to the head to the list, and then advance one by a single node at a time, and the other by two nodes at a time. It is easy to see that they will eventually meet on the cycle. Once that happens, it is easy to count the cycle length.
Now suppose you are running a casino and you are using a random number generator. For any given seed, the generator will eventually cycle, but not necessarily to the seed. You can compute the cycle lengths for a given seed with two variables by analogy with the linked list solution stated above.
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?
(google "Proof of Floyd's Cycle Chasing" for details)
Start with one pointer at node 0, moving with speed 5. Start the second pointer at node 1, with speed 3 which is coprime to 5, the speed of the first pointer.
The pointer positions at each step are:
0 5 2 7 4 1 6 3 repeat
1 4 7 2 5 0 3 6 repeat
We want to prove that the following loop always terminates:
while i % n != j % n:
i += 1
j += 2
(i + t) % n = (j + 2t) % n
(i % n) + (t % n) = (j % n) + (2t % n)
(i % n) - (j % n) = t % n
(i - j) % n = t % n
(i + x*t) % n = (j + y*t) % n
(i % n) + (x*t) % n = (j % n) + (y*t % n)
(i - j) % n = t*(y - x) % n
A trivial case where it doesn't work, for example, is x=2, y=4, n=any even number. Imagine if i starts on an odd number and j starts on an even number. It's clear that i will always be odd and j will always be even. Note that y-x (2 in this case) shares a prime factor (not coprime) with all even numbers.
Your explanation is difficult to follow when you do distributivity of % over +. I mean when you move from
(i + t) % n = (j + 2t) % n
(i % n) + (t % n) = (j % n) + (2t % n)
(5 + x) % 3 = 4
5 % 3 + x % 3 = 4
It's better to express your explanation using "= (mod n)" from the beginning.
(i + t) % n = (j + 2t) % n
i + t = j + 2t (mod n)For particular values of x, y, and loop period there may be values of i and j such that going forward from those they never meet, but it is not possible to get into one of those positions if a past state had i == j.
Proof:
In the following I'll use your notation for the most part, except allowing for a "lead in" of length L from that common starting node to the start of the loop, so the nodes are numbered 0, 1, 2, ..., L-1, L, L+1, ..., L+n-1, with the nodes in the loop being {L, L+1, L+2, ..., L+n-1}.
At time t, i has taken xt steps and j has taken yt steps. Let t >= L/x and t >= L/y, so that i and j are both past the lead in into the loop.
Then i is xt-L steps into the loop, and j is yt-L into the loop. These will be at the same spot in the loop if xt-L = yt-L mod n, which happens whenever (x-y)t = 0 mod n. All multiples of n are solutions of this, so just pick any that are >= L/x and L/y, and you have a solution.
If i and j do not start at the same place, all bets are off. That 0 is replaced with the differences between the starting node numbers, and as your example shows may not have a solution for some combinations of parameters.
Maybe it would be helpful to rewrite the loop with a condition as you described, and %= i and j with n after incrementing (by 1 or by 2) both variables in the loop body.
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.
This is one of those tricks once you know it, you'll remember it forever.
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.
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 or limitations with their first suggestion. I'll probe on these, and see whether they understand those issues as they're pointed out. I'll give hints and see how they assimilate new ideas and information. In the end, 75% of candidates will get to a reasonable solution, and 25% will get to an optimal one, given some hints along the way. I'm much less interested in whether they get to the optimal one, or even in how fast they get there, than in what happens during the discussion along the path to a solution. You learn a lot about how someone thinks from that. It's also useful to learn how someone communicates - this is also an essential part of a PhD - there's a lot of back-and-forth goes on regarding possible research ideas, so seeing how someone communicates their ideas is useful.
In summary, in an interview, such questions can be good as the basis of a dialog, but are useless unless the interviewer understands this is what they're actually trying to achieve.
What this interview question does is confirm your own biases regarding what "algorithmic thinking" is and little more.
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.
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.
If in fact it's for an actual PhD qualifying exam (or something similar), then this question might be OK.
The problem with the current crisis in interviewing is that it's become almost standard practice to ask questions like this (or its siblings: knapsack, outré graph search or sorting questions, etc) for what are basically run-of-the-mill API monkey / grunt finance programming / etc jobs.
As if the message these companies intend to convey is: "Fuck, we have no idea how to assess these candidates, nor do we have the time. So if we just ask a few gee-whiz questions that 75% of them will fail, then that might be an indication that the other 25% just might be a little smarter. Or at least very good at cramming. Because after all, that's how we got through college, too."
This sentence is simply ridiculous. Most engineers aren't able to discover this trick. I wouldn't.
The same goes for the rod cutting problem or the maximum sub-array problem (Kadane algorithm): expecting an engineer to find them, especially in an interview, is totally inane.
In any case, I didn't say “trivial”. If you can only derive trivial things, then you shouldn't be a computer scientist.
I agree that reasoning about the correctness of a binary search algorithm is an important job skill for a computer scientist. Deriving the tortoise and hare algorithm on the fly, though, is not.
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.
Not saying it’s a good interview question, just that most good programmers shoukd be able to come up with some form of answer if they understand linked lists.
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).
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.
The point is that that's an absurd thing to assume. It would almost never come up organically (and has only really come up in the context of awful interview question blogs). It's not a taught/talked about algorithm.
Rote memorization is also a poor metric for job performance.
Excuse me if I don't recall a complete year of Algorithms and Data Structures lectures and evaluation projects done about 25 years ago.
And a horrible interview question. It shows only that the interviewee has heard the question before or not.
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.
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".
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.
Say if you have one list that might be circular from the "starting" element or not circular at all. You simply save the pointer to the first element an compare every subsequent element to that. If you find the end of the list it is not circular. If you find the first element it is circular.
The step from that to a general approach for finding whether a list contains circular references should be simple.
I am however coming from scheme where linked lists are abundant.
Edit: not to say I think it is a good problem for an interview, but I would expect someone to be able to solve the problem in one way or another it without googling. What I am questioning is that it is a hard problem, or a very hard solution.
> this was an open problem in CS for 12 years before someone came up with the tortoise and hare algorithm.
So, empirically, "no".
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 seen in a hash map, keyed to their position, and stop when you encounter the same node twice. This in turn leads to interesting discussions about list size, memory cost, and more general questions about the properties of a hash map.
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.
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.
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.
Is that so?
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 "never use linked lists" view I would like to see a nontrivial program rewritten from lists and references to the "allocate everything at once" approach and measure the performance.
If you want to avoid references and allocate everything in place, it may force your program to do a lot of copying.
Also, not only CPU performance matters - programmer performance is important too. So-called "high-level languages" try to optimise this.
If you read one field of all elements all at once, sure, a structure of arrays is probably right. But what if you instead read all fields of one element at once? Isn’t it advantageous to have those fields adjacent in memory with an array of structures?
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 a game or game engine changed their storage to be more array like and got roughly a 30% boost in performance. Memory locality is usually king, which is why linked lists are rarely used.
Why?
Essentially, many workloads access data sequentially and therefore modern cache architectures have special optimizations to make these memory accesses as fast as possible, by prefetching the next item in the sequence before it is actually needed.
Well, anyways I value code simplicity more than anything.
Maybe CPUs will learn to do cache prefetch for link oriented languages: if a "load and dereference" pattern is detected, CPU could prefetch the data referenced by pointers it has in registers or recently fetched cache line.
BTW, linked list elements are not necessary located far away from each other, if we allocated them one after another chance are they are near each other in memory.
It sounds like you're saying everything will be OK so long as each chunk of 64 bytes (cache line) is used together. But one page is typically 4 KB, and if you use for example all 64 bytes of one cache line, but only one cache line per page, you will suffer from TLB misses.
We are not discussing VM here, I brought it as an analogy just to say cache lines are independent and need not be contineous.
It's not strictly bad, but it's useful to minimize the number of pointer derefrences you have wherever you can. A non-intrusive linked list will have 2 pointer dereferences to access any bit of data. You'll also have n+1 pointer dereferences to access element n. If you have fixed size small objects, then a vector of values is almost always better than a vector of pointers to the small objects. An intrusive linked list will save you a pointer dereference, but you still have the n dereferences to access element n.
>Should we ditch Lisp
Lisp's lists model a linked list with chains of cons cells, but there's no hard requirement for them to actually be implemented as linked lists. A typical approach is to implement lists in terms of Bagwell's VLists, which are a kind of middle ground between linked lists and vectors. You have reduced number of pointer dereferences, plus increased cache locality, whilst still being able to log n index, insert, delete, and not require large up-front allocations.
>and Java
If you subscribe to the "everything is an object" model religiously, then yes, you're probably doing harm. As always, there's no hard rules here and it always depends on your problem and data access requirements. You can usually get performance gains by using memory pools, arrays of structures/primitives, and entity systems instead of inheritance hierarchies.
Likewise Java has primitive types, arrays and eventually will get value types, because they already feel the pressure in FinTech of not having them.
For instance, my current use case is an STM32F, which accesses CCM in a single cycle. And intrusive linked lists are a god send for managing pools in embedded systems without traditional memory management.
[1] shameless plug: https://www.codeproject.com/Articles/1087021/Stable-Iterator...
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
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.
class Foo {
Foo *m_next;
Foo *m_next_mru;
Foo *m_next_sibling;
};
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, no matter the size of the list.
It is not until you do removes/adds far more often, and far from the end of the collection, that the linked list will perform better overall.
class Entry<K,V> {
Entry<K,V> younger; // LRU doubly linked list
Entry<K,V> older; // LRU doubly linked list
Entry<K,V> next; // for hash map bucket chaining
V value;
K key;
}
class MapEntry<K,V> {
Entry<K,V> next;
DoublyLinkedListEntry<MapEntry<K,V>> LruEntry;
K key;
V value;
}
class DoublyLinkedListEntry<T> {
ListEntry<T> prev;
LintEntry<T> next;
T value;
}Although they are so many things that are taught, that should never be used in the real world.
struct node* BuildWithLocalRef() {
struct node* head = NULL;
struct node** lastPtrRef= &head; // Start out pointing to the head pointer
int i;
for (i=1; i<6; i++) {
Push(lastPtrRef, i); // Add node at the last pointer in the list
lastPtrRef= &((*lastPtrRef)->next); // Advance to point to the new last pointer
}
// head == {1, 2, 3, 4, 5};
return(head);
}
> This technique is never required to solve a linked list problem, but it will be one of the alternative solutions presented for some of the advanced problems. The code is shorter this way, but the performance is probably not any better.
This is what Linus Torvalds called "good taste" code and used in Linux kernel. There was some argument about it though: https://news.ycombinator.com/item?id=5030845.
(Incidentally, I found Nginx is written in the same style recently as I read it - manual linked list manipulation with this double pointer technique everywhere..)
LISP is a family of programming languages.