Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
What in the world are you talking about man? Did you even read my solution? Please explain again what you are trying to get at..
In short
M =
0 0 0 X
0 0 X N
0 X N N
X N N N
is a sorted matrix, where N is a very large number (choose infinity if you like) the element we are looking for(say '5') can be in any of the 'X' s. any algorithm has to search at-least those 'X' elements on the diagonal, because there are no ordering imposed on those elements by the definition of the matrix. simply put there can be no algorithm that takes less than linear time
@Smash:
I see your point here. Maybe I should have mentioned in the post that the matrix given to me was
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
and the interviewer was pressing for the logm + logn solution to this specific case. You can do much much better than linear if the matrix satisfies the property that the last element in each row is smaller than the first element in the best row. Log(mn) = logm + logn in this case.
Thanks.
If the question is that a[i][n-1] < a[i+1][0] for all i's than apply binary_search(array, m*n)
that return position of the element found or -1 if not found. Return position/m = rows and position%n as column. In this case the complexity is O(logm*n) = O(logm) + O(logn).
In case, the former condition above does not apply, then the solution is to find a range that may potentially include the element to be searched and apply binary search in that row. The problem is that each row could potentially contain the element and that we end up searching each row. This can be reversed so that we search a range from each column and then apply search on column. In this case the complexity will be O(m*logn) or O(n*logm), we can compare mlogn with nlogm before applying the search to minimize the complexity.
if any has the this solution above please ignore it my suggestion is try diagonal path from last to first if it is less than the key ,lets say {i,j} then start binary search from {i,j}to {i,col} and not find then again binary search {i+1,0} to {i+1 ,j} i have not mentioned boundary conditions that u imagine. please comment on this if wrong or any other best solution avail.
Yes, I did a lot of stupidity with this one myself. Finally after the interview I designed a class just to play with multiple coordinates and returned it's object. That is the Java way. Hate this lack of multiple returns in Java. In C and C++ you can do it using pointers or references. Guess what, even C# has an "out" keyword for specifying a return argument in your methods.
Is it possible to send the reference arr[][]. This way you could make transformations to the array without using an external class.
Is it possible to send the reference
arr[][]
. This way you could make transformations to the array without using an external class.
Yes, you can. Even a single dimensional array satisfies. But that is not how you want to do it in an interview. That is not a coding practice in use. A person reading your code would never know you are making the array just so you can get output from a method. While interviewing they are really looking for your object oriented skills. So it much more advisable to make a class and use it's object.
You see the '&' after int?
void find(int A[][10], int m, int n, int target,int& row, int col)
That's your output variable, samething with the col, therefore should be:
void find(int A[][10], int m, int n, int target,int& row, int& col)
you already see the return type is void, and reference type variable, so (I believe) he meant to have you put output into row and col.
As for the algorithm, I think doing a dual binary may not be super impressive but will get the job done.
Maybe when you get to the row, subtract the first element and use that as the index, since they are already sorted within the row. I think that might be what he meant in "using the fact that the rows are already sorted".
I am totally agree with you.
In any language there is no way to return multiple value instead u can just return one single object or value.
The signature given denotes that it is written in C that accepts the reference of the variable.
@Sudo Man:
Thanks for replying with exactly what I was looking for. Can you explain a little better how I use those two pointers (row, col) to return 2 values. Im kinda unable to get my mind around this.
Thanks a ton.
Suppose you have all these variables declared and initialized.
int m,n,target;
int[][] A;
int r,c; // for row and column
// initialize here
//calling the method
find(int A, m, n, target, r, c);
//Now r and c will have the changed values
Just the fact that there is an '&' in the method signature makes it a reference. If you are really interested I would suggest further reading on pointers and references. However, if C/C++ is not your primary language, you should mention that in your interview. The interviewer should not really be expecting that knowledge.
Hey,
Im pretty fluent with pointers. What I don't know is how i can return the final (row,col) pair using the signature
void find(int A[][10], int m, int n, int target,int& row, int &col).
The example you have mentioned passes r and c by value and not by reference. Care to explain?
I am pretty sure that the signature needs to be
find(int A, m, n, target, &r, &c);
for r and c to reflect values in the main function, thus indirectly returning 2 values from the function. Are you sure that the interviewer did not have a reference for both variables?
C++ Only:
#include <stdio.h>
void swapnum(int &i, int &j) {
int temp = i;
i = j;
j = temp;
}
int main(void) {
int a = 10;
int b = 20;
swapnum(a, b);
printf("A is %d and B is %d\n", a, b);
return 0;
}
C Only:
#include <stdio.h>
void swapnum(int *i, int *j) {
int temp = i;
i = j;
j = temp;
}
int main(void) {
int a = 10;
int b = 20;
swapnum(&a, &b);
printf("A is %d and B is %d\n", a, b);
return 0;
}
When the function swapnum() is called, the actual values of the variables a and b are exchanged because they are passed by reference. The output is:
A is 20 and B is 10
Good Example:
C++ Only:
#include <stdio.h>
void swapnum(int &i, int &j) {
int temp = i;
i = j;
j = temp;
}
int main(void) {
int a = 10;
int b = 20;
swapnum(a, b);
printf("A is %d and B is %d\n", a, b);
return 0;
}
C Only:
#include <stdio.h>
void swapnum(int *i, int *j) {
int temp = i;
i = j;
j = temp;
}
int main(void) {
int a = 10;
int b = 20;
swapnum(&a, &b);
printf("A is %d and B is %d\n", a, b);
return 0;
}
When the function swapnum() is called, the actual values of the variables a and b are exchanged because they are passed by reference. The output is:
A is 20 and B is 10
Good Example:
C++ Only:
#include <stdio.h>
void swapnum(int &i, int &j) {
int temp = i;
i = j;
j = temp;
}
int main(void) {
int a = 10;
int b = 20;
swapnum(a, b);
printf("A is %d and B is %d\n", a, b);
return 0;
}
C Only:
#include <stdio.h>
void swapnum(int *i, int *j) {
int temp = i;
i = j;
j = temp;
}
int main(void) {
int a = 10;
int b = 20;
swapnum(&a, &b);
printf("A is %d and B is %d\n", a, b);
return 0;
}
When the function swapnum() is called, the actual values of the variables a and b are exchanged because they are passed by reference. The output is:
A is 20 and B is 10
its seems totally wrong how u can do it in lgn+lgm not possible at all . take thsi case
:
|7 8 9 14|
|11 12 13 15|
|14 16 17 18|
|15 18 19 20|
|17 19 21 22|
search 11 on this ur method will fail . but O(n+m) will works fine here :)
@Lugi in O(m+n) its really easy just start with right corner thats is form 14 now because 14 >11 go left you reached at 9 now
again check 9<11
so to move downwords you reached 12
now 12>11 so move left now you reched at 11
so just the simiar procedure u can search any number .
I think O(log m+log n) is possible (and his interviewer said so too). Use a binary search algorithm on first element of every row and you can find the row in logarithmic time.
Log(m+n) isn't even a solution and "It seems totally wrong" are harsh words. Please do validate your reasoning before putting someone off like that.
@Sudo Man: it's been already said several times that the only possible solution to this problem has O(m+n) running time.
for a simple counterexample to your idea, imagine that
the first column of the matrix contains the *same* elements, hence your binary search won't help
and you would have to check every row separately..
Well actually u can search the element in the 1d array(i.e. convert the 2d array into a single array like (0,0)->(0) , (0,1)->(1)) using the binary tree search the corresponding element running time would O(log(m*n)) i.e. log(m)+log(n) then using some simple logic to find out the corresponding place in 2d array i.e if the element place is x(eg 6) then r=x/m and c=x%n here 'm' is row and 'n' is column of 2d array. Hope this helps..give me some feedback if it is correct or not
You cannot do better than min{m,n}. This is well known. It is proven by showing that given an arbitrary set of min{m,n} numbers, you can construct an mxn matrix such that those min{m,n} numbers are along the diagonal. Searching for an element among those is necessarily linear.
- Anonymous March 31, 2012So recheck your O(log m + log n) solution. There is a mistake somewhere. The interviewer seems to be quite ignorant.