CODEWITHSUNDEEP
algorithmhashtable
Sergey Chepurnov
Sergey Chepurnov

Reputation: 1447

algorithm - find the index of minimum element in subarray

I've failed the interview. Question was:

You have an array. Also, you have the start index i and end index j of subarray. It is possible to do some initialization steps once. You need return the index of minimum element in subarray for particular i, j in O(1) of time.

Does it possible to resolve this task with a HashTable? Or may be you give me the better way to solve it.

Upvotes: 3

Views: 1309

Answers (3)

Óscar López
Óscar López

Reputation: 235984

If it's possible to "do some initialization steps once", we can simply precompute a two-dimensional matrix (a hash table is an overkill for this case) with all the minimum indexes for all possible pairs of subarray indexes. This is an O(n^2) operation and once it's done, retrieving the minimum index in any subarray will be O(1). As correctly stated in the comments this is an instance of the range minimum query problem, and here's my proof of concept in Python:

def init_table(array):
    n = len(array)
    # create an NxN matrix
    table = [[0] * n for _ in xrange(n)]
    for i in xrange(0, n):
        minIdx, minVal = i, array[i]
        for j in xrange(i, n):
            if array[j] < minVal:
                minIdx = j
                minVal = array[j]
            table[i][j] = minIdx
    return table

Another alternative, an equivalent solution using dynamic programming:

def init_table(array):
    n = len(array)
    # create an NxN matrix, initializing values in the diagonal
    table = [[0 if i != j else i for j in xrange(n)] for i in xrange(n)]
    for i in xrange(0, n):
        for j in xrange(i+1, n):
            if array[j] < array[table[i][j-1]]:
                table[i][j] = j
            else:
                table[i][j] = table[i][j-1]
    return table

Either way, we start by creating the 2D matrix for a given array:

array = [1, 2, 4, 6, 1, 3, 5, 7]
table = init_table(array)

Let's say that we want to examine the range between i=2 and j=6:

i = 2
j = 6
array[i:j+1]
=> [4, 6, 1, 3, 5]

In the above range, the minimum element is 1, which is at index 4 in the original array. Let's see if our matrix works:

table[i][j]
=> 4

If we need the index relative to the sub-array, simply subtract i from the result:

table[i][j] - i
=> 2

Upvotes: 2

Aprillion
Aprillion

Reputation: 22304

I would proceed as normal and memoize the function.

Requirement of O(1) is stupidly formulated, because it is not explained what is actually needed, only an implementation detail is forced upon you.

In order to comply, I would simply call my function for each possible sub-array as the "initialization step" - I could then easily compare performance and resource usage of the solution with and without the initialization to show to stakeholders whether O(1) given big up-front cost is actually beneficial or not for particular circumstances.

Of course there might be 1 use case - that the array is static, very big and performance is of the utmost importance - when the results should be precomputed and stored in a database (presumably they cannot be pushed into memory as the array is too big, but caching and proper indexing can make the retrieval time of O(log n) indistinguishable from O(1) in any practical application).

as an implementation detail, the memoization can involve either a hash table (as most memoize libraries use as far as I'm aware) or you could manually store data as a 2D array, first dimension being i, second being j, e.g.:

# indexex:     0  1  2  3
input_array = [3, 2, 1, 4]
x = NaN  # assuming j >= i
cache = [[0, 1, 2, 2],
         [x, 1, 2, 2],
         [x, x, 2, 2],
         [x, x, x, 3]]

Upvotes: 1

Adam
Adam

Reputation: 3778

The purpose of this question isn't so much to test your knowledge of any particular algorithm (though such knowledge helps), it is to see if you are able to think creatively under pressure.

The asymptotic notation constraint of O(1) has very few possible solutions. Considering that you are allowed to pre-process the arrays, my approach would be one of two: either create a new array that is the same length as the super array and store the index of the smallest elements in each sub-array in it as elements are inserted, or sort each sub-array and simply return i, the index of the start of the target sub array.

When answering such questions, speak your thoughts out loud so that the interviewer can follow your thought processes. If you don't know something, say as much, but don't panic. Look for assumptions you are making and either make more assumptions that can make the task easier, or remove assumptions that are in your way.

I note that the question seems a little ambiguous. This is on purpose. You don't often get exact instructions while on the job, and will often be forced to make unimportant assumptions on your own and double-check assumptions with stakeholders when they are more important.

The mistake you probably made on this interview probably had far less to do with the algorithm and more to do with getting too nervous. Practice, my friend, makes perfect.

Upvotes: 1

Related Questions