Array list algorithm - Interview

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();

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.

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?