## Amazon Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: Phone Interview

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

the problem can be solved in two steps
1: find the range in which k exists.
2: find the index of k

traverse the array in power of 2
1:2^1<K<2^2 then the range is 2^1 and 2^2 apply binary search in this range
2:2^2<K<2^4 then the range is 2^2 and 2^4 apply binary search in this range
3:2^4<K<2^8 then the range is 2^4 and 2^8 apply binary search in this range
.
.
.
and so on.

Comment hidden because of low score. Click to expand.
0

if the numbers can be repetitive and can have -ve values, ur method isn't gonna work, and in case, if numbers are not repetitive or say the nos are unique then, the best way would be to just deduct first number from K, and apply binary search on the array with length = resulting value, starting from zero..

Comment hidden because of low score. Click to expand.
0

even if there are duplicates... as the array is sorted , they should be consecutive and fall in the same range... and so the specified algorithm is sure gonna find atleast one index of K.

Comment hidden because of low score. Click to expand.
0

Yes, This solution defiantly will work.

Comment hidden because of low score. Click to expand.
0

If there are duplicates, this solution won't have log(K) performance. Consider the performance of this algorithm on an array that is filled with 2^n of each element for each value n >= 0. The first instance of every value K is at index 2^K-1. Your algo will take log (2^K - 1) time, so about K time.

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

Does n here refer to the interviewers IQ?

Comment hidden because of low score. Click to expand.
0

good one

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

Is the question supposed to be in O(log(K)) time with an assumption that all integers in the array are unique?

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

Consider the case in which the whole array is composed of an infinite number of 1s, and k is 2. I think no algorithm will stop searching, as it cannot find 2 among all the numbers it has visited, while it cannot make sure 2 does not exist in the array and have to keep searching. In all, I think the numbers in the array should be distinctive

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

Since you know the maximum buffer size of your system.
take a file input having maximum size = Lmax.

now check value in which interval of value of K lies on.
like 0 to Lmaax,
Lmax+1 to 2*Lmax,
2*Lmax+1 to 3*Lmax
so on...............
for checking value ,we dont need to copy elements in the array...
we simply check value of (i-1)*Lmax and i*Lamx,if K lies between these range of value then we will copy all (i-1)*Lmax to i*Lamx within buffer;
now 'll perform Binary Search and will get the required solution.

if given numbers are in the file having total size T_size,
maximum buffer size = buf_size
then worst case = ((T_size/buf_size) -1) + log(buf_size)

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

// arr is the name of infinite array
int i = 1<<0x1;
while (arr[i]<k)
{
i = i << 1;
}

// jump out the while loop means that the 'k' locates between arr[i/2] and arr[i]
// then binary search k between arr[i/2] and arr[i]

oh, seems the same as 'kamal' said.
but the time complexity of this method seems not log(k).
em, thinking...

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

I am thinking like we have to do binary search by dividing the the number of elements. i.e. take a set of k elements try to do binary search this takes logk for k elements.. In that way it goes like this logk + log k + logk + ....... = constant* logk
which inturn would become logk.. what is your opinion on this ?

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

Let me clarify here about infinite array.
We are not going to run our program on hypothetical machine where there is infinite space.

So infinite here means that we don't know the size of the array.

Now you have got two ways either find out the size of array which I guess according to interviewer is not allowed.
I was asked the similar question and after asking he said that if we are trying to access an element that is not in array bound it will return an error code.

So , the solution will come up as exponential jump.

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

//arr is the infinite array
int a=0; n=arr.lenght(); // start and end of the array

while(arr[mid]==k)
{

mid =(n+a)/2; //lower bound
if ( arr[mod] < k)
a=mid + 1;
else
n=mid-1;

}
print 'mid';

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.

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