Walmart Labs Interview Question
Developer Program EngineersCountry: India
Interview Type: Phone Interview
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.
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)
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)
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 !
the sequence: 100, 56, 1, 32, 10, 20, 22, 30, 31 will make this algorithm fail because of the local minima 1, 32
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}.
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}.
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();
}
}
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.
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.
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
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.
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
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
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.
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;
}
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.
- Anonymous May 16, 2012Finally 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]