Finding minimum value in a sorted array that was rotated, using concurrency

user_5410948 0
Viewed 95

This is an interview question.

In the first part I was asked for finding a minimum value in a sorted array that was rotated (for example, the sorted array [1,2,3,4] was rotated to [3,4,1,2] ). The algorithm for doing it can be found here.

Then I was asked for improving the algorithm by using parallel computing. That was my suggestion:

  1. Assuming we can run k threads in parallel, divide the array into k equal size sub arrays (besides perhaps the last part).
  2. Perform the algorithm above on each of the k sub arrays.
  3. Return the minimum value from the k algorithm runnings.

The interviewer said the algorithm run time isn’t good enough. Do you know a better solution?

time-complexity arrays algorithm performance
1 Answers

Let's suppose you have n+1 hardware threads. You can have n threads process the array, each thread "responsible" for 1 entry and completing in O(1) time, and the remaining thread waiting for the result. For efficiency, the threads should be started beforehand and initialized with an index variable (i), otherwise the initialization itself will be O(n) time. The process in each thread could be:

if arr[i] > arr[(i + 1) mod n]
  SharedMemResult = arr[(i + 1) mod n]

This is obviously O(1) time, and all the "master" thread had to do is read SharedMemResult till it changes (of course this needs to be initialized to some extreme value, and memory barriers should be used to prevent reordering...).

Using the same concept, we could utilize m threads where each thread finds the minimum in the range (n*i/m) -> (n*(i+1)/m - 1) in O(log(n/m)) time, and then verifies this to be the true minimum (only relevant of the first item on the range is the minimum, but this will be the case for most ranges).

The result is an algorithm that solves the problem in O(log(n/m)) time.

user_38875160
Related