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)

For more info refer: imdiba.blogspot.in

- diba.bec June 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous July 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ?

- pavel.em October 04, 2015 | Flag
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.

- diba.bec July 05, 2015 | Flag Reply
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.

- Klaus July 14, 2015 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More