Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
2
of 2 vote

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.

So recheck your O(log m + log n) solution. There is a mistake somewhere. The interviewer seems to be quite ignorant.

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

very true, there exist no way to do better than linear time, its proven

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

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..

- sreemana@buffalo.edu March 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

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

@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.

- sreemana@buffalo.edu March 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i meant 'next' row in the last line above.

- sreemana@buffalo.edu March 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

now it all makes sense :)
probably should add that example in the problem statement so no one else gets confused

- smashs April 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

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

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.

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

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.

- yossee March 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Is it possible to send the reference arr[][]. This way you could make transformations to the array without using an external class.

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

Is it possible to send the reference

arr[][]

. This way you could make transformations to the array without using an external class.

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

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.

- yossee April 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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".

- Sudo Man March 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Naresh Bansal March 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- sreemana@buffalo.edu March 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

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

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?

- sreemana@buffalo.edu April 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- rookie.coder April 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Laplace April 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Laplace April 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Laplace April 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 :)

- geeks March 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How can you find 11 in your case within O(m+n) time?

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

@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 .

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

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 March 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think it is logm*logn

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

@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..

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

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

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

that is correct..but please can you tell me...copying 2d array to 1d will also have its own time complexity.Are we supposed to ignore it?

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

method 1
garimaa.blogspot.in/2012/04/program-15th-in-c-version-1.html

method 2
garimaa.blogspot.in/2012/04/program-15th-in-c-version-2.html

- Solution April 12, 2012 | 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