Algorithm - find the index of the minimum element in a subarray
I failed the interview. Question:
You have an array. Also, you have a start index i and an end index j of the subarray. You can perform some initialization steps once. You need to return the index of the minimum element in the subarray for a specific i, j in O (1) time.
Is it possible to solve this problem with a HashTable? Or maybe you are giving me a better way to solve this problem.
source to share
If it is possible to "perform some initialization steps once", we can simply pre-copy the 2D matrix (a hash table is a surplus for this case) with all minimum indices for all possible pairs of subarray indices. This is an operation O(n^2)
, and once it's done, getting the minimum index in any subarray will be O(1)
. As correctly pointed out in the comments, this is an example of a minimum query range 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
In any case, we start by creating a 2D matrix for a given array:
array = [1, 2, 4, 6, 1, 3, 5, 7]
table = init_table(array)
Let's say we want to explore 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 smallest element 1
that is at the index 4
in the original array. Let's see if our matrix works:
table[i][j]
=> 4
If we want an index relative to a submatrix, just subtract i
from the result:
table[i][j] - i
=> 2
source to share
The purpose of this question is not so much to test your knowledge of any particular algorithm (although such knowledge helps), it is to see if you can think creatively under pressure.
The O (1) asymptotic notation constraint has very few possible solutions. Given that you are allowed to preprocess arrays, my approach would be one of two things: either create a new array with the same length as the super-array and store the index of the smallest elements in each sub-array in it, as the elements are inserted or sorted each sub-array an array and just return i, the index of the beginning of the target sub-array.
When answering these questions, speak your thoughts out loud so that the interviewer can follow your thought processes. If you don't know anything, say so much, but don't panic. Look at the assumptions you make and make more assumptions that make things easier, or remove the assumptions that get in your way.
I note that the question seems a bit ambiguous. This is on purpose. You often don't get precise instructions on the fly and are often forced to make unimportant assumptions yourself and double-check with stakeholders when they matter more.
The mistake you probably made in this interview probably had much less to do with the algorithm and more to do with being overly nervous. Practice, my friend, makes perfect.
source to share
I would proceed as usual and memoize the functions.
The O (1) requirement is stupidly worded because it has not been explained what is actually needed, only an implementation detail is imposed on you.
To be consistent, I would simply name my function for each possible submatrix as an "initialization step" - then I could easily compare performance and resource usage with and without initialization to show interested parties whether O (1) given that the large upfront costs are really beneficial or not for specific circumstances.
Of course, there can be one use case - the array is static, very large and performance is paramount - when the results have to be precomputed and stored in the database (apparently they cannot be moved into memory as the array is too large, but caching and correct indexing can make the search time O (log n) indistinguishable from O (1) in any practical application).
as an implementation detail, memoization can include either a hash table (as most memoize libraries use, as far as I know), or you can manually store the data as a 2D array, with the first dimension i
, the second one j
like:
# 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]]
source to share