## Amazon Interview Question for Interns

• 0

Country: India
Interview Type: In-Person

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

logn
perform binary search

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

But the binary search stops when it finds the element... how would you guarantee that it would be the first instance of the element????

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

``````Let k be the given number then code would be similar to the following

int starting_index(int *a,int start,int end)
{
int mid=(start+end)/2;
if(end!=mid)
{
if(a[mid-1]<k && a[mid]==k)
return mid;
else if(a[mid]<k)
starting_index(a,mid+1,end);
else
starting_index(a,start,mid-1);
}
else
{
if(a[mid]==k)
return mid;
else
return -1;
}
}

-1 is returned when there is no occurence of given number.``````

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

Binary Search to find an instance of the given number, then scan backward to find the first instance of the given number, as the array is sorted.
Time complexity is O(n).

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

Then why don't you just scan forward without Binary Search to find the first instance with the same time complexity?

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

O(n) is worse-case complexity here for a edge case when entire array consists of the same number.

Therefore I think it's safe to assume that average complexity will be O(log n).

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

Here is the code for the above

``````int findFirst(int a[],int l,int r,int key){
int mid=(l+r)/2;
if(l>=r)
return -1;
if(a[mid]==key){
while(a[mid]==key)mid--;
return mid+1;
}
else if(a[(l+r)/2]>key)
return findFirst(a,l,(l+r)/2,key);
else
return findFirst(a,(l+r)/2,r,key);
}``````

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

Perform binary search.

``````int findFirstOccurrence(int* arr,int l,int h,int tofind)
{
int mid;
if(l>h) return INT_MIN;
if(l==h)
return arr[l]==tofind?l:-1;
mid=(l+h)>>1;

if(arr[mid]==tofind && (mid==l || arr[mid]>arr[mid-1]))
return mid;
if(tofind<=arr[mid])
return findFirstOccurrence(arr,l,mid-1,tofind);
return findFirstOccurrence(arr,mid+1,h,tofind);
}``````

Complete code here: ideone.com/8q91s

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

``````public class BinarySearch {

//both from and to are inclusive.
static int minOccurance(int[] array, int from, int to, int v) {
if(from == to) {
if(v == array[from]) {
return from;
} else {
return -1;
}
}

int middle = (from + to) >> 1;
if(v < array[middle]) {
return minOccurance(array, from, middle-1, v);
} else if (v > array[middle]) {
return minOccurance(array, middle + 1, to, v);
} else {
int left = minOccurance(array, from, middle-1, v);
if(left == -1 ) {
return middle;
} else {
return left;
}
}
}

public static void main(String[] args) {
int[] arr = new int[] {1,1,1,1,1,1,1,1,1, 2, 2,2, 4,4,5,5,5,5,5,5,5};

System.out.println(minOccurance(arr, 0, arr.length - 1, 1));
System.out.println(minOccurance(arr, 0, arr.length - 1, 2));
System.out.println(minOccurance(arr, 0, arr.length - 1, 3));
System.out.println(minOccurance(arr, 0, arr.length - 1, 4));
System.out.println(minOccurance(arr, 0, arr.length - 1, 5));
}
}``````

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

``````//using binary search
int findIndex(int *arr, int low, int high, int data)
{
int mid = (low+high)/2;

if(arr[low] == data)
return low;
else if(arr[mid] >= data)
return findIndex(arr, low , mid, data);
else
return findIndex(arr, mid+1, high, data);
}
//assumed that number is present in array``````

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

``````public static int findFirstNum(int[] input,int start,int end,int target)
{
if(start>end)
return -1;
else
{
int middle=(start+end)/2;
if(target<=input[middle])
{
int index=findFirstNum(input,start,middle-1,target);
if(index==-1)
{
if(input[middle]==target)
{
return middle;
}
else
return -1;
}
else
return index;

}
else
{
return findFirstNum(input,middle+1,end,target);
}
}
}``````

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

Complexity O(lgN)

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

public class Find_First_Instance_In_Sorted_Array {

public static int find_first(int[] test,int aim){
int result_index=find(test,aim,0,test.length-1);
return result_index;
}
public static int find(int[] test,int aim,int begin,int end){
if(begin==end){
if(test[begin]==aim){
return begin;
}
else{
return -1;
}
}
if(begin==end-1){
if((test[begin]==aim)||(test[end]==aim)){
if(test[begin]==aim){
return begin;
}
if(test[end]==aim){
return end;
}
}
else{
return -1;
}
}

int mid=(begin+end)/2;
if(test[mid]>aim){
return find(test,aim,begin,mid-1);
}
if(test[mid]<aim){
return find(test,aim,mid+1,end);
}
if(test[mid]==aim){
return find(test,aim,begin,mid-1)!=-1?find(test,aim,begin,mid-1):mid;
}

return -1;
}
public static void main(String[] args) {
int[] test=new int[]{1,2,3,3,3,3,4,5,6,7,7,8};
int aim=3;
int result_index=find_first(test,aim);
System.out.println(result_index);

}

}

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

The complexity can be 2*logn first to find the number then next binary search to find the first instance

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

I think it should be log n + log n

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

In worse case you have to make (n/2) comparision.so the time complexity is o(n)

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

1. find the index of a number just less then the required number by bin search.
2. find the index of the given number.
3.now max &min limit we got we can find the 1st occurrence in O(logn) time now...

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

Time Complexity: O(log n)

int First_Instance(int A[], int min, int max, int k){
int mid = (min+ max)/2;
int index, temp;

if(min<=max){
if(k< A[mid])
index= First_Instance(A, min, mid- 1, k);
else if(k> A[mid])
index= First_Instance(A, min, mid- 1, k);
else
while(A[mid]!= k){
temp= mid;
mid++;
}
return temp;
}
return -1;
}

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

i1 = 0, i2= arr_end
Loop till (mod(i1 - i2) != 1)
1. Binary search from i1 to i2, ill the number is found: - store the index - i2
2. Continue the binary search on the left, till the next lower number is found- if no number is lower, return 0.
else store index - i1

return i2;

P.S : Not a very clear algo but hope its explanatory.

Complexity will be log(n)

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

int find_first(int arr[], int start, int end, int num)
{
static int count;
count++;
int low, large;
int mid = (start+end)/2;

while(arr[mid] > num)
{
if(mid == start)
return -1;
mid = (start + mid)/2;
}
if(arr[mid] == num)
{
large = mid;
while(arr[mid] >= num)
{
if(mid == start)
return start;
mid = (start + mid)/2;
}
low = mid;
}
else
{
large = end;
low = mid;
}
if(large - low == 1)
{
if(arr[large] == num)
return large;
else
return -1;
}
return find_first(arr, low, large, num);
}

int main()
{
int arr[]={1,1,1,5,5,5,5,5,5,7,7,7,8,9,12,13,15,16,17,17};
int val = find_first(arr,0,19,8);
return 0;
}

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

I'm not sure if I'm missing anything or misunderstood the question. If you just do a Binary Search, this will only find the "target", i.e., the value it's looking for, but it is not guarantee the first occurance. As someone mentioned up there that we still have to do a backward scan to make sure that is the first occurance, why can't we just do a forward scan at the first place and return the first one it sees. This way we don't have to do a Binary Search and the run time will be O(n), which is equals to O(logn)+O(n).
Please let me know if I'm wrong, maybe I misread this problem.

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

-> Perform Binary Search
-> Continue binary search until we get first occurrence.

Important point : If data is sorted in increasing order then we need to move the index towards left direction. However Middle index could be also termination point.

Order : Log(n)

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

if it is sorted, then next element is same or previous element is same ... you simply increment its index or decrement to find. first decrement and then increment.

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

Here is the code with complexity log(n)

``````#include <stdio.h>

/*
* Find the first occurence of the given number in index.
*/
void main()
{
int nums[] = {1,1,3,5,8,8,8,10,12,23,23,55};
int len = sizeof(nums)/sizeof(int);
int start = 0, end = len-1, search = 8;
int found_right = -1;
while ((end - start) > 1)
{
if (found_right != -1)
{
if (nums[end] != search)
{
break;
}
found_right = end;
end -= 1;
continue;
}
int mid = (end + start)/2;
int val = nums[mid];
if (val == search)
{
end = mid-1;
found_right = mid;
}
else if(val < search)
{
start = mid;
}
else
{
end = mid;
}
}
if (found_right != -1)
{
printf("found at %d", found_right);
}
else
{
printf("Sorry!");
}
}``````

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

Implement binary search to find the required number ,then compare it with the number on the left ,if it is different this position is your answer or else binary search on the remaining part ,,so it cannot be more than O(logn)

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.