## Walmart Labs Interview Question for Software Developers

Team: Customer experience
Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

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).

``````C++ Code
--------------
#include <iostream>
#include <stdlib.h>

using namespace std;

// Return true for success and false for failure
// In case of success, (s1,e1) is the start and end index of subArray-1
// and (s2,e2) is subarray-2
bool MaxDOTProduct(int* A, int size, int& s1, int& e1, int& s2, int& e2)
{

bool found = false;

// Prepare dot-product matrix
int** M = new int*[size];
for(int i=0; i<size; i++) {
M[i] = new int[size];
M[i][i] = abs(A[i]);
}

for (int span = 2; span <= size; span++){
// i = start index and j = end index
int i,j;
for (j=span-1, i=j-span+1; j < size; i++, j++) {
M[i][j] = M[i][j-1] * abs(A[j]);
}
}

// Now find the sub-strings
for (int length = size/2; length >= 1; length--) {
for (e1=length-1, s1=e1-length+1; e1<size; s1++, e1++){
for (s2=e1+1,e2=s2+length-1; e2 < size; s2++, e2++) {
if (M[s1][e1] == M[s2][e2]) {
found = true;
break;
}
}

if (found) break;
}

if (found) break;
}

// Clean dot-product matrix
for (int i=0; i < size; i++)
delete M[i];
delete [] M;
return found;
}

int main()
{
int* A = new int[10];
A[0] = 1; A[1] = 2; A[2] = 3; A[3]= 4; A[4] = -44; A[5] = 99; A[6] = 4; A[7] = 3; A[8] = 44; A[9] = 99;
int s1,e1,s2,e2;
if(MaxDOTProduct(A, 10, s1, e1, s2, e2))
{
cout << "s1=" << s1 << " e1=" << e1 << " s2=" << s2 << " e2=" << e2 << endl;
} else {
cout << "No result\n";
}

delete A;
}

Space & Time Complexity
-----------------------------------
We have taken O(n^2) additional space to store dot-product matrix.
The time complexity to prepare dot-matrix is O(n^2) since it is a DP solution.

Sub-string computation has three nested loops.
Outermost loop will iterate (n/2) times.
The two inner loops compare dot-products of all non-overlapping substrings for sub-string length (l).

Total number of comparisons for a particular length (l) is
C = (n-2l+1) + {(n-2l+1)-1} + {(n-2l+1)-2} + … + 2 + 1
i.e. C = (n-2l+1)(n-2l+2)/2 for l = n/2 to 1

Therefore asymptotic upper bound is O(n^3)
Hence Time complexity = O(n^2) + O(n^3) = O(n^3)

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

If I understand it correctly, a dot-product of two subarrays {a,b,c} and {d,e,f}
would be: a*d + b*e + c*f. So I think your algorithm is computing something else.

Indeed, why would the question mention (+ve & -ve) number if the signedness does not matter ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I have one doubt regarding the words "Contiguous Sub arrays".Should the resultant sub arrays be located right next to each other or they can be located anywhere in the given array as soon as they are non-overlapping.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.