Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
3
of 5 vote

The worst case here is O(n).
In order to search for the desired element we have to achieve less than n complexity, which essentially means we cant afford to make sequential search. Now 3 cases may arise in the given array:
1. it may be in increasing order eg: 3,4,5,6,7,8,9,10
2. it may be in decreasing order eg: 3,2,1,0,-1,-2,-3
3. it must allow repetition eg: 3,4,5,4,3,2,3,4,5,6,7,8,9,10,9

Lets take the 3rd case and search for 7.

//number to be searched is p
bool found = 0;
for (i=0; i<arr.length; i=i+p-arr[i])
{
   if (arr[i]==p)
   {found = 1;
    break;
   }
}
if(found == 1)
   return (i);
else
   return(NULL);

- Tiscaaao! October 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice algo! small improvement is that you also have to take care
of boundary cases, i.e.,
if you search for '2' in {5,4,3,2,1}, the index i can become
negative, this can be fixed as follows:

for (i=0; i<arr.length;)
{
   if (arr[i]==p)
   {found = 1;
    break;
   }
   i += abs(p - arr[i]);
}

- pavel.em October 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice :-)

- Thinker October 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

you cannot do divide and conquer per se. The solution is not log n. It is just a heuristic approach which is better than O(n).

Since the numbers differ from each other in the magnitude of one. Take the first number and find the difference of it with the search number. move that many positions and check if that has the required number. Repeat this process until either u get the number or run out of length.

- msramachandran October 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would be nice if you gave the answer please.

- Anonymous October 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Consider the array a[0...n] Let i , j (i<j) be two indices. and you are looking for P

a[i]...a[j] can contain P if and only if

P > MIN( a[i] - (j-i) , a[j] - (j-i) )
and P < MAX( a[i] + (j-i) , a[j] + (j-i) )

Now you can do some kind of divide and conquer and reject ranges in which P cannot lie. Worst case will still be O(N).

- Anonymous October 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I can't catch the meaning of this question.
Can anybody explain it?

- Anonymous October 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the array, each of its entry differs from its neighboring entry by one..
Example(as Tiscaaao mentioned)-
1. it may be in increasing order eg: 3,4,5,6,7,8,9,10
2. it may be in decreasing order eg: 3,2,1,0,-1,-2,-3
3. it must allow repetition eg: 3,4,5,4,3,2,3,4,5,6,7,8,9,10,9

- abhimng October 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

the array could be like this also: 1,2,1,2,1,2...

- andy October 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

how about

int[] a={2,2,2,2,2,2,2,2,3,4,5,5,5,5,6,7,7,7,7,7,7,7,7,7,6,5,4,3,2

}

- megaMind December 07, 2011 | 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