Amazon Interview Question Interns


Country: India
Interview Type: In-Person


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

logn
perform binary search

- Anonymous on August 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- nitish712 on August 05, 2012 | Flag
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.

- maverick on August 05, 2012 | Flag
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).

- onpduo on August 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

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

- Malluce on August 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- expert on August 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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);
}

- isandesh7 on January 23, 2013 | Flag
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

- Aashish on August 05, 2012 | Flag Reply
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));
    }
}

- Anonymous on August 05, 2012 | Flag Reply
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

- Aalok on August 05, 2012 | Flag Reply
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);
			}
		}
	}

- Vincent on August 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Complexity O(lgN)

- Vincent on August 05, 2012 | Flag
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);

}

}

- Chengyun Zuo on August 06, 2012 | Flag Reply
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

- loveCoding on August 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think it should be log n + log n

- error_404 on August 06, 2012 | Flag
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)

- code4life on August 06, 2012 | Flag Reply
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...

- atul gupta on August 07, 2012 | Flag Reply
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;
}

- Abhijeet Rokade on August 07, 2012 | Flag Reply
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)

- Anonymous on August 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- Piyush on August 07, 2012 | Flag
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.

- Malluce on August 07, 2012 | Flag Reply
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)

- Anonymous on August 08, 2012 | Flag Reply
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.

- Anonymous on August 08, 2012 | Flag Reply
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!");
    }
}

- ethioer on August 10, 2012 | Flag Reply
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)

- sunny on September 26, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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