Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Choose max of arrary[i][0] and min of array[i][N] (i.e. maximum of first element and minimum of last element)., Now the answer (list of common numnbers) has to lie beteen these numbers.
Choose the array which contains maximum of first element, and for each element of this array search them in other arrays using binary search, If it is found then add them into the final list. We need to perform this search till the minimum of the last element is reached.
time: n2 log(n)
@suresh ... coolguy's solution is better as u need to modify the original data neither u can use extra space and since the arrays are sorted then
Time taken = n(to find max start element)+
n(elements of that array) * n (number of arrays)* logn(binary search for each element)
=n+n2logn = n2logn
However your's would be O(n3) ... if the arrays would have been unsorted then your solution would be the valid one but here we can take advantage of sorted arrays
so let's do a dry run based on CoolGuy Solution:
1. 10 160 200 500 500
2. 4 150 160 170 500
3. 2 160 200 202 203
4. 3 150 155 160 300
5. 3 150 155 160 301
Maximum of first column is 10
Minimum of last column is 203
So the common element among all these rows will be between 10 and 203
10 < common element < 203
So start picking one by one all the element of row where 10 was found.In this case it was found in row 0.So let's pick 10 and search 10 in all the rows.
First iteration: 10 not found in all the rows.
Second iteration: 160 found in all the rows -keep in the final list.
Third iteration: 200 not found in all the rows.
Next number is 500 which is greater than 203.So there is no point in seraching rest of the row elements as
10 < common element < 203
So answer is 160 which we had put in final list.
If the minimum complexity possible looks like to be O(n2logn) we could simply do this:
for each element v in row-1
do binary search in rest (N-1) rows
We could improve this by comparing the min and max of each row and decide based on that whether we want to perform binary search or not, i.e. whether it is possible for a number 'num' to fall between 'min_num' and 'max_num' of that row.
Binary search -> O(log n)
For searching 1 num in n-1 rows : O(nlogn)
Binary search for each number in first row : O(n2logn)
I selected first row, we can pick any row and if a no element of the row picked is found in any of the (N-1) rows then we don't really have common data.
of 0 vote
Q:
1. 10 160 200 500 500
2. 4 150 160 170 500
3. 2 160 200 202 203
4. 3 150 155 160 300
5. 3 150 155 160 301
A:
Step one: compare 1. and 2. (common 160 , 500). remove other elements from Array 1.
Step two: compare new 1. (160, 500) and 3. ( common 160) remove other elements from this array i.e. 500
Step next : compare 160 with other rows .. if 160 is not there then no common data else 160 is the common data.
while i understand the solution for O(nlogn) , unable to get the n^2 solution. can you explain/give clue?
It's O(n^2) no matter the numbers are pos or neg. By tracking the largest value (say it's 'x') among the first items of n arrays, go ahead (just check the items one by one in the other n-1 arrays, binary search can be used for speeding up, but need careful design -- "parallelly" run with simple go-through) to find the items that >= x in all arrays. If all item == x, then we find a common value; otherwise, start a new iteration. It's O(n^2) because each item was checked only by once.
if the element is common..we then we should be able to find it in the 1st row also.
so we need to lookup for each element in 1st row and search the same in all (n-1) row.
so it will be n* n logn time
for each element in row1
{
for each row upto N-1 rows
{
found = B_search ();
if (!found)
break;
}
}
10 160 200 500 500
4 150 160 170 500
2 160 200 202 203
3 150 155 160 300
3 150 155 160 301
what is the answer for this?
Obviously to find the result we have to go through all the data . So lets consider that the result will be kept in the first array. Start from the position n in the first and second array with 2 iterators: first = n and second = n;
while (second >=0 && first>=0){
if(B[second] == A[first]) first--;
second--;
}
remove(A,0,first); // remove all the elements in A from index 0 to first
go do the same for the first and third array, first and fourth and so on.
At the end return A (the first array).
Hi all,
I think it should be the straight forward problem of - "Intersection of K-arrays"
Going ahead with the concept of "Intersection of 2 arrays" , apply the same for K-array i.e
1) you will need K pointers for these arrays.
2) find the max of first elements of these arrays.
3) Increment the pointers if AnthArray[i] < Max{A1[0],A2[0] .... An[0]} {KnthPointer++ }
4) Repeat steps 2 & 3 unless any of the array pointers reaches to end at which point you return with all of the recorded common elements
Kindly correct / comment suggestions on this ..
Two solutions possible.
1. Choose smallest array. Iterate over this array and do binary search for each value in other arrays. time: O(n*n*lgN), space: O(1)
2. Suppose we have arrays[][]. Choose largest value from arrays[i][0].
Do binary search, if all arrays contain this value add this value to common list,
otherwise choose as a next search value, biggest from all found.
private List<Integer> findCommonElements( int[][] arrays ){
final List<Integer> commonElements = new ArrayList<>();
int maxSoFar = Integer.MIN_VALUE;
while( true ){
int maxValueToSearchNext = Integer.MIN_VALUE;
boolean allEqual = true;
for( int j = 0; j < arrays.length; j++ ){
int pos = Arrays.binarySearch( arrays[j], maxSoFar );
if( pos < 0 ){
allEqual = false;
pos = Math.abs(pos) - 1;
if( pos >= arrays[j].length ){
break;
}
int curValue = arrays[j][pos];
maxValueToSearchNext = Math.max( maxValueToSearchNext, curValue );
}
else {
if( pos + 1 < arrays[j].length ){
int nextValue = arrays[j][pos+1];
if( nextValue != maxSoFar ){
maxValueToSearchNext = Math.max( maxValueToSearchNext, arrays[j][pos+1] );
}
}
}
}
if( allEqual ){
commonElements.add( maxSoFar );
if( maxValueToSearchNext == maxSoFar ){
break;
}
}
if( maxValueToSearchNext == Integer.MIN_VALUE ){
break;
}
maxSoFar = maxValueToSearchNext;
}
return commonElements;
}
int N;
int findCommonElements( int[][] arrays ){
int res=N, p0=0, p1=0, pCur=0;
for(int i=1; i<N; i++){
p0=0; p1=0; pCur=0;
while(p0<N && p1 < N && pCur < res){
if(arrays[0][p0] ==arrays[i][p1]){
arrays[0][pCur++]=arrays[0][p0];
p0++; p1++;
}
else if(arrays[0][p0] >arrays[i][p1]){
p1++;
}
else p0++;
}
res = pCur;
}
return res;
}
I can think of n*n*logn solution with some optimization.
1. Find the maximum of a[i][0] for all the i {0, n-1}. Let this be curMax.
2. Clearly all the values less than curMax can not be in the common set.
3. Search for curMax in all the rows using binary search such that binary search returns the next highest value index if curMax is not present. <This is the caveat, we will need nextBeginIndex[n] to store these index values. If this is not allowed, then this optimization is not possible. > Store next highest index in nextBeginIndex[n]
4. If all the rows return successful result, curMax is common.
5. Now find maximum of a[i][nextBeginIndex[i]] for all i {0, n-1}
6. Repeat the same steps.
Given that all arrays are sorted following code can do it O(n2) time
for(i=0 ; i< (N-1); i++)
{
p = q = 0;
while(p < N && q < N)
{
if(a[i][p] == NOT_DEFINED || a[i][p] < a[i+1][q] )
{
p++;
}
else if(a[i+1][q] < a[i][p])
{
a[i+1][q] = NOT_DEFINED;
q++;
}
else
{
p++;
q++;
}
}
while(q< N)
{
a[i+1][q] = NOT_DEFINED;
q++;
}
}
for(i = 0 ; i< N; i++)
{
if(a[N-1][i] != NOT_DEFINED)
printf("%d ", a[N-1][i]);
}
Divide and conquer paradigm;
There are N arrays.
1. Apply divide till u reach base problen that is 2 arrays. we can find the common elements in O(N) time without any extra space. The return type of this function is the array which list only the common elements.(we know that we don't need a separate array to store this, i.e if we have two arrays A and B the number of common elements will be less than or equal to size of A and B , and all we need to do is return one array A or B which just contains the common elements )
2. The splitting takes O(logN) time.
Hence the run time is O(NlogN) . Anybody came with a O(N) algorithm please let me know
Adding my name
- Suresh February 05, 2013Q:
1. 10 160 200 500 500
2. 4 150 160 170 500
3. 2 160 200 202 203
4. 3 150 155 160 300
5. 3 150 155 160 301
A:
Step one: compare 1. and 2. (common 160 , 500). remove other elements from Array 1.
Step two: compare new 1. (160, 500) and 3. ( common 160) remove other elements from this array i.e. 500
Step next : compare 160 with other rows .. if 160 is not there then no common data else 160 is the common data.