Walmart Labs Interview Question
Software DevelopersTeam: Customer experience
Country: United States
Interview Type: In-Person
If we wanted to solve in O (n^3), it seems that we could use a much simpler approach. Just iterate over every pair of indexes i and j, and for each pair, run a linear loop to see for which k a[i...i+k] dot a [j...j+k] will be maximized.
The interesting thing is to get a solution better than n^3.
If you run linear loop for every pair of indexes, then you are no more with O(n^3) complexity.
It is exponential. The complexity will lead to Catalan number.
If we want to solve this problem with lower complexity, we need more attributes of the input
array which will help us in further optimization.
Sometimes, apparently O(n^3) sounds high, since we like to talk about O(n) or lg(n) but
unfortunately O(n^3) is optimal; you can't go further down.
For more details, refer matrix chain multiplication problem from CRLS book.
Also note that, O(n^3) is worst case asymptotic complexity.
In average case, the program will terminate much before than that.
However, I will love to see a faster algorithm; but for that we need more attributes
which I might have missed.
Algorithm
-------------
The problem provides couple of attributes to the input and output requirements which provide a hint towards the solution.
1. We need to find subarrays with maximum dot-product. Dot product or scalar product only accounts magnitude of vectors. For our case, it means that, we will only deal with absolute value of integers ignoring the sign.
2. We will deal with dot-product of sub-arrays of input string where we will have to compute product of sub-arrays repetitively. To optimize the dot-product computation of arrays, we will use dynamic programming (DP) and store the results in a 2-dimensional array for further processing.
We define array M[][] where M[i][j] stores dot-product for sub-array starting at index i and ending at index j.
If the input array is A[size], ∀ 0 ≤ i,j < size & i ≤ j
M[i][j] = A[i] for i = j
= M[i][j-1] . |A[j]| for i < j
= Invalid (-1) for i > j
3. Once we have calculated dot-product matrix, now it’s time to compute the intended sub-arrays.
a. Since we have array of integers, any array will have larger dot-product compared to its sub-arrays.
b. We need non-overlapping sub-arrays. The maximum non-overlapping sub-array length = size/2
Therefore, we start finding sub-arrays of length size/2 until 1. We will terminate our iteration once we find one based on property (a).
- diba.bec June 28, 2015