31–40 of 113 posts
Earlier quoted context omitted.
> 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?
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)
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.
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…
Earlier quoted context omitted.
> 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?
Consider a cycle of length n. Consider two integers, i and j that have arbitrary initial values in [0, n). We want to prove that the following loop always terminates: while i % n != j % n: i += 1 j += 2 If we represent this as an equation over time, where t is the number of loops, we want to prove that for some t the following is true: (i + t) % n = (j + 2t) % n Solving for t: (i % n) + (t % n) = (j % n) + (2t % n) (…
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)"Just say no to linked lists!" https://youtu.be/fHNmRkzxHWs?t=2099
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…
Why?
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.
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.
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…
Earlier quoted context omitted.
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…
> if you're accessing data sequentially it's more likely the data you're going to access next is already in cache 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.
"Just say no to linked lists!" https://youtu.be/fHNmRkzxHWs?t=2099
Yeah, until you need to remove an element from the middle in constant time - this is sometimes useful for things like the implementation of an LRU cache.
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.