3 ms·
There are other simple algorithms you could come up with that have the same big-O.
by SamReidHughes 7y ago
There are other simple algorithms you could come up with that have the same big-O.
- saagarjha 7y agoI’d be happy to hear about them if you know any!
- SamReidHughes 7y agoTake the naive n^2 algorithm, but test only the nodes whose distance from the start is a power of two.
- saagarjha 7y agoThis seems just as magical as the original algorithm. Do you have insight as to why it works and what though process is necessary to arrive to it?
- gunnihinn 7y ago> This seems just as magical as the original algorithm. If you do a "change of coordinates" the original algorithm becomes trivial: If you know that any loop in the list doesn't begin after the node you're on, you can just mark where that is, run ahead, and check if you ever come back. In the general case, "change coordinates" so that with every step, the origin advances one step. Now you'll eventually be in the previous case.
- SamReidHughes 7y agoIt's an act of logification.
- pps43 7y agoIterate over the list, re-tying it backwards as you go. If you reach the end, there's no loop. If the order is important, you can re-tie again, still in O(N) time. If you end up at the head, there's a loop.
- saagarjha 7y ago> Iterate over the list, re-tying it backwards as you go. What does "re-tying backwards" mean?
- pps43 7y agoBefore: a->b->c After: a<-b<-c
- smcl 7y agoWhat if you end up at head+1, not head?
- pps43 7y agoHow would you end up there? With a loop, head+1 would point to head after the first pass, so you'll end up at the head. With no loop, head+1 would only be passed once.
- lolc 7y agoFun and really dirty solution! I would never come up with this because I would not dare to modify a passed data structure unless this was the purpose of the procedure. One could use that answer to gauge the humour of the interviewer :-) For me the expected reaction of a peer to this would be "Cute! Now explain the problems I could encounter when using it." If they can't deal with some fun, well, their loss.
- pps43 7y agoIf you can't modify the original list, you can create another as you iterate. But that will require extra O(N) memory, so is worse than the textbook solution with two pointers.
- lolc 7y agoInteresting! I didn't know the solution with two pointers and would have assumed O(n) memory as a lower boundary. I must admit I didn't follow the bytecode too closely. So thanks for pointing that out.
- jfoutz 7y agosince it's java, you have access to a Set. add each node to the set if it is not present, O(1). A bit more aggressive, check System.Runtime.heapSize() calculate how many nodes can fit in the heap, and subtract 1 for each element visited. Still O(1) With lower level access, recognize that pointers are always powers of 2, so go ahead and tag that pointer (p = p | 1, if *p & 1, it's a cycle.) you'll build up a stack, and have to fix the tagged pointers, but also O(1). I dunno. the double advance is a cute trick, but if the fast moving pointer doesn't do the check, you can easily spin into an infinite loop. It's not a _hard_ problem. You just have to keep your wits about you. Lots of ways to solve it.
- saagarjha 7y ago> add each node to the set if it is not present, O(1). Not in space complexity. > A bit more aggressive, check System.Runtime.heapSize() calculate how many nodes can fit in the heap, and subtract 1 for each element visited. This one will take quite a while… > recognize that pointers are always powers of 2, so go ahead and tag that pointer They're not always, and this is also technically uses extra space.