Walmart Labs Interview Question for Developer Program Engineers


Country: India
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
7
of 9 vote

Build two arrays of size of input array and call them lessThan and greaterThan. lessThan[i] will contain index of an element that is less than element arr[i] or -1. It is built by traversing original array from left to right and keeping track of the minSoFar and comparing it with current element. greaterThan[i] will contain index of an element that is greater then element arr[i]. It is built just like lessThan, except it is traversed from right to left and looks at maxSoFar and compares with current element.

Finally you traverse through the two arrays and check whether lessThan[i] and greaterThan[i] have positive values. If they do then number less then arr[i] is pointed to by lessThan[i] and number greater then arr[i] is pointed to by number greaterThan[i]

- Anonymous May 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

this looks like a O(n2) in worst case to me. Also, we need not do it
for all the numbers and maintain array. Just look for the first no with a less than and greater than. This is what question asks to do.

- anonymous July 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Nice. This can be done in O(n) like this.
1) Traverse array from l->r once and create array Min[] such that Min[i] is the min element till ith place. - O(n)
2) Traverse array from r -> l and create array Max[] such that Max[i] is max element from i to n. - O(n)
3) Travese all three arrays again and find a index i such that
Min[i]<A[i]<Max[i]. At this point output Min[i], A[i], Max[i] - O(n)

- Yoda July 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
5
of 5 vote

int a,triplet[3];
a=triplet[0]=list[0];
triplet[1]=triplet[2]=INT_MAX;
for(i=1;i<list.length;i++){
 if(list[i]<a)
  a=list[i];
 else if(list[i]<triplet[1]){
  triplet[0]=a;
  triplet[1]=list[i];
 }
 else{
  triplet[2]=list[i];
  break;
 }
}

complexity O(n)

- Sathya May 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The case where it would fail is
1. When your list also has INT_MAX in it
2. When list size is < 3
But I see where you are going with the logic. Good job !

- RiTZ May 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the sequence: 100, 56, 1, 32, 10, 20, 22, 30, 31 will make this algorithm fail because of the local minima 1, 32

- mbaise May 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@mbaise No. It works correctly for ur given sequence too.

- nix May 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

nope, your algorithm is searching for global
minimum in the array which does not always give the correct answer.

Consider: {5,1,6,1,1,7} then your will return: {1,1,1}.

- oops June 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

int a,triplet[3];
a=triplet[0]=list[0];
triplet[1]=triplet[2]=INT_MAX;
for(i=1;i<list.length;i++){
if(list[i]<=a)
a=list[i];
else if(list[i]<=triplet[1]){
triplet[0]=a;
triplet[1]=list[i];
}
else{
triplet[2]=list[i];
break;
}
}

Above modification with if else condition can fix such bugs i.e. to handle duplicate entries if present in array as mentioned here e.g.. {5,1,6,1,1,7} then your will return: {1,1,1}.

- Sonu September 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice solution

- Anonymous March 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this solution wont work for:
7,8,3,6,1,9

- aashima333 August 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

It can be done in O(N logN) using two binary indexed tree or segment tree.

#include <iostream>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>

using namespace std;
typedef unsigned long long ull;
ull seg1[1010010];
ull seg2[1010010];
ull dp[210010];

void upd(ull *a, int root, int s, int e, int index, int value){
		//cout << "upd" << " " << root << " " << s << " " << e << endl;
		if(s==e && s==index){
			a[root] = value;
			return;
		}
		int m = (s+e) / 2;
		if( index >= s && index <= m )
			upd(a, 2*root, s, m, index, value);
		else if( index >= m+1 && index <= e )
			upd(a, 2*root+1, m+1, e, index, value);
		a[root] = a[2*root] + a[2*root+1];	
}

ull query(ull *a, int root, int s, int e, int s1, int e1){
		//cout << "upd" << " " << root << " " << s << " " << e << " "<< s1 << " " << e1 << endl;
		if(s1<s || e1 >e || e1 < s || s1>e) 
			return 0;
		if(s==s1 && e==e1){
			return a[root];
		}
		ull res = 0;
		int m = (s+e) / 2;
		if(e1<=m){
				res += query(a, 2*root, s, m, s1, e1);
		}else if(s1>m){
				res += query(a, 2*root+1, m+1, e, s1, e1);
		}else{
			if( s1 >= s && s1 <= m )
				res += query(a, 2*root, s, m, s1, m);
			if( e1 <= e && e1 > m )
				res += query(a, 2*root+1, m+1, e, m+1, e1);
		}
		return res;
}


int sol(){
/*
	upd(seg1, 1, 1, 100, 100, 1);
	upd(seg1, 1, 1, 100, 50, 1);
	cout <<  query(seg1, 1, 1, 100, 1, 100) <<endl;
	return 0;
*/	
	int N,a;
	cin >> N;
	typedef pair<int, int> pii;
	vector<pii> lp, lp1;
	for(int i=0;i<N;i++){
		cin >> a;
		lp.push_back(pii(a,i));
	}
	sort(lp.begin(), lp.end());
	lp1.push_back(pii(lp[0].second, 1));
	for(int i=1;i<N;i++){
		if(lp[i].first == lp[i-1].first)
			lp1.push_back(pii(lp[i].second, lp1[i-1].second)); //take prev value
		else
			lp1.push_back(pii(lp[i].second, i+1));
	}
	sort(lp1.begin(), lp1.end());
	ull res =0;
	for(int i=0;i<N;i++){
		int x = lp1[i].second;
		upd(seg1, 1, 1, N, x, 1);
		ull q1 = query(seg1, 1, 1, N, 1, x-1);
		upd(seg2, 1, 1, N, x, q1);
		ull q2 = query(seg2, 1, 1, N, 1, x-1);
		res += (q2-dp[x]);
		dp[x] = q2;
		//cout << x << " " << q1 << " " << q2 << " " << res << endl;
	}	
	cout << res << endl;
}

int main(){
	int t=1;
	while(t--){
		sol();
	}
}

- Weak Learner November 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Ex: 1 8 7 6 2 5 4 3

Take an auxiliary array. temp[]

Traverse first from left to right. We will count if for a given element arr[i] , there exist an element to its left which is less than it.
Keep track of min. element till i , and keep updating temp.

Now , traverse again from right to left. Here we will count that for a given elem arr[i] , there exists an element which is greater then it , on its right. Now as we see any value in temp is 2 , then we found our element.

- deam0n May 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am not able to understand your answer. Can you please use an example and explain it. Thanks.

- Raghavendra May 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Using quick sort to divide the array into two parts - smaller subarray and subarray with all values greater than pivot can help.
for each element in the input array, create one such subarray (all elements greater than pivot or the element).
Now we have multiple subarrays corresponding to each element which contains all elements greater than the element.
One small note, make sure we quick sort the array i+1 to n-1 for the element at index i.
for each combination of elements we can have such triplets.

- perk June 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we can use extra space. I think we can solve this as a problem similar to longest increasing sequence.
We can even print all such pairs.
Please refer Longest Increasing Sequence problem in Wikipedia

- Wolverine May 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can solve this problem in O(n) instead of O(nlogn) as longest increasing sequence algo.

- Nam May 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] n;
int[] max;
int[] min;

-- first input n array
n = n.length;
max[n] := 0;
for (int i = n - 1; i >= 0; i--)
{
max[i] := MAX(max[i + 1], n[i-1]);
}

min[0] := MAX_INT;
for (int i = 1; i <= n; i++)
{
min[i] := MIN(min[i - 1], n[i - 1]);
}

for (int i = 1; i < n; i++)
{
if (min[i] < n[i] && n[i] < max[i])
{
-- i is the position that we have to find.
}
}

If you need to find the position before and after i, you can add 2 array to trace when calculate max, min arrays.

- Conde May 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming input array is A[]
1. Take an auxiliary array of same length as A and fill it with 1, 2, 3,...N
2. Sort array A[], and perform the same swapping operations on B[] irrespective of content
3. Look for all the triplets < A[i],A[i+1], A[i+2] > in the sorted array and check for condition < A[i] < A[i+1] < A[i+2] and indices of B[i] < B[i+1] < B[i+2]. Triplets satisfying both the conditions are the resultant triplets
Example:
Before sorting : A[] = {5 2 3 6 7} and B[] = {1, 2, 3, 4, 5}
After sorting : A[] = {2 3 5 6 7} and B[] = {2, 3, 1, 4, 5}

Only triplet <5, 6, 7> satisfy both the condition mentioned in [3] above

- Anonymous May 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In addition above method works out to be O(nlogn)

- Anonymous May 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, the above algorithm doesn't work..!! Foolish of me..

- Anonymous May 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

patience sorting algorithm can find it in O(nloglog(n))
wiki/Patience_sorting

- Anonymous May 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Scan the elements from left to right. Maintain at most two list .
Say my input is 50,100,40,...
At this instant my lists will be
50-100 and 40.
for the next input (x).
if x<40, update the second list: discard 40 save x.
if 40<x<50 update the second list to 40- x. first list can be discarded as x<100.
if 50<x <100 update the first list. to 50-x.
if 100<x. append x to first list.

complexity O(n). constant space reqd at most 3 elements needs to be stored

- nitin November 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have a solution which assumes that we just need to find if such a triplet exists or not. It will not print all such triplets.

Create another array which stores the position of each element. Let's call it the "index array". Sort the original array in increasing order in O(nlogn).
After sorting, check the index array. Check if the index of the minimum element <= Length(Array) - 3. If it is, then such a triplet exist, otherwise go to the next element and perform the same check. We perform this check until we get a required element or till the position Length(Array) - 4, which ever is minimum. This will take O(n) time. Hence the total time will be O(nlogn) + O(n).

We can find one triplet in another O(n), but finding all the triplets will take O(n^2) worst case.

- Anurag Singh December 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static int[] getAscendingTripletsAlt (int[] givenArray) {
		//Time complexity: O(3n)
		//Space complexity: O(3 + n)
		
		int[] triplets = new int[3];
		
		for (int i=1; i< givenArray.length-1; i++) {
			if (givenArray[i-1] < givenArray[i] && givenArray[i] < givenArray[i+1]) {
				triplets[0] = givenArray[i-1];
				triplets[1] = givenArray[i];
				triplets[2] = givenArray[i+1];
				return triplets;
			}
		}
		
		return null;

}

- freewor1d December 26, 2013 | 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