Array list algorithm - Interview

Question

I was asked this question in an interview today. I have tried a solution but would like to know if there's a better way to solve this:

Question: I have an arraylist say of 500,000 elements such that the value of each element of the arraylist is same as the index. For ex: list.get(0) = 0; list.get(1) = 1 ...etc. But only one element is out of sync with this ordering [i.e list.get(i) != i]. How do you find that element.

My Answer: Iterate over the list using multiple threads each thread handling a certain splice of the arraylist each time comparing list.get(i) with i. When the element is found, set some boolean variable to indicate to other threads that the element has been found.

Is there a way to solve this problem without iterating over the list? Or a better way?

Answer 1

In the worst case you have to examine each element, so you can't improve on the O(n) time complexity.

With this in mind, the best algorithm is to scan the array list from start to finish. This way you're making best use of the available memory bandwidth.

It is not entirely clear to me how or why threading has entered the picture. It seems out of place. Was it part of the question?

Answer 2

The answer is: one iteration. Your mention of concurrency of cause is something they are fishing for.

In fact since java 8, the solution whether parallel or not is simple. I think the most would have brought:

OptionalInt foundInt = IntStream.range(0, list.size())
    .parallelStream()
    .filter(i -> i != list.get(i))
    .findAny();

Answer 3

You can't do better than O(n).

And secondly, I think it's a bad idea to talk about threads and multithreading in those problems. They are not of interest at all. In the end you have a runtime of O(whatever) where your constant is removed anyway.

Maybe the interviewer meant a sorted array with elements from 0 to n-1 with index 0 to n-1. And then move one element to a different position. But that means that all the remaining elements have different indexes! In this scenario you can improve your search with binary search:

Then you can get the element in O(log n). Start in the middle and check whether the index equals the element. If it is equal do the same with the upper part of the half, if not use the other part.