How would you cross a linked list in O (n ^ 0.5)?

Question

This is an Apple interview question. I have not yet found convincing arguments in support or against it.

Answer 1

A crawl more efficient than O (n) is not possible, since a crawl requires accessing each node in turn.

You can make random access faster than O (n), although by maintaining a second linked list that stores links to intermediate nodes; the costs of adding, removing and adding are increased, although due to the increased complexity of servicing the second list.

Answer 2

Impossible.

This means that you mean looking at each node in a linked list of n nodes. This is probably a trick to find out if you can understand that this is not possible.

Answer 3

When I first came across this question, I thought about the same thing as most people here: it is impossible, a trick, a psychological test. I was wrong.

The real answer is that you can iterate over the list faster than O (N), at least theoretically, using a quantum computer.

Check out the Wikipedia article for the Grover algorithm here .

They describe the amortized operating time O (n ^ 0.5) and the space O (log n). It should also be noted that it is not deterministic. This means that there is a high probability that the algorithm will return the correct result, but it is not guaranteed.

I suppose this is enough to convey the question, but everything else is above my head.

Good luck.

Answer 4

It is possible if each node has a connection with the next element, the previous element and the central element (where the center is the midpoint between the current element and the end of the list).

Thoughts?