Amazon Interview Question for SDE-2s


Country: India
Interview Type: In-Person




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

find most left and most right occurrences of given number with binary search and return {{right - left + 1}}

- Darkhan.Imangaliev November 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Correct, but also handle cases when the element is not present in the array.

- Abhigyan Mehra November 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

c# implementation.

using System;

namespace BinarySearch {

    class Program {

        private static int _bsearchMostLeftIndex( int[] arr, int startIndex, int endIndex, int val ) {

            var index = ( endIndex + startIndex ) / 2;

            if ( _noNearestDuplicates( arr, index, val ) ) { return index; }

            if ( endIndex - startIndex == 1 ) {

                if ( arr[ startIndex ] == val ) {
                    return startIndex;
                }
                if ( arr[ endIndex ] == val ) {
                    return endIndex;
                }
                throw new Exception( $"No such element: {val}" );
            }
            if ( arr[ index ] >= val ) {
                return _bsearchMostLeftIndex( arr, startIndex, index , val );
            }
            if ( arr[ index ] < val ) {
                return _bsearchMostLeftIndex( arr, index, endIndex, val );
            }
            throw new Exception( $"No such element: {val}" );
        }

        private static int _bsearchMostRightIndex( int[] arr, int startIndex, int endIndex, int val ) {

            var index = ( endIndex + startIndex ) / 2;

            if ( _noNearestDuplicates( arr, index, val ) ) { return index; }

            if ( endIndex - startIndex == 1 ) {

                if ( arr[ endIndex ] == val ) {
                    return endIndex;
                }
                if ( arr[ startIndex ] == val ) {
                    return startIndex;
                }
                throw new Exception( $"No such element: {val}" );
            }
            if ( arr[ index ] <= val ) {
                return _bsearchMostRightIndex( arr, index, endIndex, val );
            }
            if ( arr[ index ] > val ) {
                return _bsearchMostRightIndex( arr, startIndex, index , val );
            }
            throw new Exception( $"No such element: {val}" );
        }

        private static bool _noNearestDuplicates( int[] arr, int index, int val ) {
            return arr[ index ] == val && ( ( index > 0 && arr[ index - 1 ] != val ) || index == 0 ) && arr[ index + 1 ] != val;
        }

        private static int GetNumberOfRepeats( int[] arr, int val ) {
            var mostLeftIndex = _bsearchMostLeftIndex( arr, 0, arr.Length - 1, val );
            var mostRightIndex = _bsearchMostRightIndex( arr, 0, arr.Length - 1, val );
            return mostRightIndex - mostLeftIndex + 1;
        }

        static void Main( string[] args ) {
            var bb = GetNumberOfRepeats( new[] {0,1,1,2,3,4,5,5,5,5,5,5,5,5,5,5,5,5,6,7,8,8,9,9,9,9,9,9,9,9,9,9}, 1 );
            Console.WriteLine(bb);
            Console.ReadLine();
        }
    }
}

- zr.roman November 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Implemented in Java
public static int integerFrequency(int[] arr, int k) {
if (null == arr) {
return 0;
}
int lo = leftBinarySearch(arr, k);
if (lo < arr.length && arr[lo] != k) {
return 0;
}
int hi = leftBinarySearch(arr, k + 1);
return hi - lo;
}

public static int leftBinarySearch(int[] arr, int k) {
int lo = 0;
int hi = arr.length - 1;

while (lo <= hi) {
int mid = (lo + hi) / 2;
if (k < arr[mid]) {
hi = mid - 1;
} else if (k > arr[mid]) {
lo = mid + 1;
} else if (mid > 0 && arr[mid - 1] == k) {
hi = mid - 1;
} else {
return mid;
}
}
return lo;
}

- Kaan K November 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int integerFrequency(int[] arr, int k) {
if (null == arr) {
return 0;
}
int lo = leftBinarySearch(arr, k);
if (lo < arr.length && arr[lo] != k) {
return 0;
}
int hi = leftBinarySearch(arr, k + 1);
return hi - lo;
}

public static int leftBinarySearch(int[] arr, int k) {
int lo = 0;
int hi = arr.length - 1;

while (lo <= hi) {
int mid = (lo + hi) / 2;
if (k < arr[mid]) {
hi = mid - 1;
} else if (k > arr[mid]) {
lo = mid + 1;
} else if (mid > 0 && arr[mid - 1] == k) {
hi = mid - 1;
} else {
return mid;
}
}
return lo;
}

- Kaan K November 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <vector>

using namespace std;

int GetCount(vector<int> &file, int start, int end, const int val)
{
    if((start > end) || (file[start] > val) || (file[end] < val))
    {
        return 0;
    }
    
    if(file[start] == file[end] && file[end] == val)
    {
        return end - start + 1;
    }
    
    int mid = (start + end) / 2;
    return GetCount(file, start, mid - 1, val) 
        + GetCount(file, mid + 1, end, val) 
        + (file[mid] == val ?  1 : 0);
}
    

int GetCount(vector<int> &file, int memLimit, const int val)
{
    int sum = 0;
    for(int offset = 0; offset < file.size(); offset += memLimit)
    {
        sum += GetCount(file, 
                                     offset, min(offset + memLimit, 
                                     (int)file.size()) - 1, 
                                      val);
    }
    return sum;
}

int main()
{
    vector<int> file;
    
    for(int i = 0; i <= 20; ++i)
    {
        file.push_back(i);
    }
    
    file[10] = 10;
    file[11] = 10;
    file[12] = 10;
    file[13] = 10;
    
    for(int i = 0; i <= 20; ++i)
    {
        cout << file[i] << " " ;
    }
    
    cout << endl << "Count = " << GetCount(file, 7, 10);
    getchar();
    return 0;
}

- rishab99999 November 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 * Created by akhil on 12/13/2015.
 */
public class RepeatedNumberCount {

    public static int getCount(int[] arr, int num) {

        int n = getNumber(arr, 0, arr.length - 1, num);

        return n;


    }


    private static int getNumber(int[] arr, int low, int high, int num) {

        int mid = 0;

        int count = 0;

        while (low <= high && num != arr[mid]) {
            mid = (high + low) / 2;

            if (num < arr[mid]) {
                high = mid - 1;
            } else if (num > arr[mid]) {
                low = mid + 1;
            }


        }
        if (num == arr[mid])
            System.out.println(" Element is present " + count++);


        for (int i = mid; i < arr.length - 1; i++) {

            if (num == arr[i + 1]) count++;
//            break;
        }


        for (int i = mid; i > 0; i--) {

            if (num == arr[i - 1]) {
                count++;
                //continue;
            }//  break;
        }

        System.out.println(" count " + count);
        return count;


    }


    public static void main(String args[]) {
        int[] arr = {1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5, 6, 6, 6, 6};
        System.out.println(" Number of times a number is repeated " + getCount(arr, 1));

    }
}

- akkhil2012 December 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int arrLenght = arrays.length();

int indexOfNumToFind = arrays.binarsearch(arr, numToFind)

if(!(indexOfNumToFind<0 || 1 >= arrLenght){
count = 0;
for(indexOfNumToFind, indexOfNumToFind < arraylenght, indexOfNumToFind++)
if(arrays[indexOfNumToFind] != findNumb)
break;
else
count++
}else
//

- Simha December 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Find2 {
	public static void main(String[] args) {
		int[] arr = {0,0,0,1, 1,3, 3, 3, 3, 3, 3, 4, 5, 6, 6, 6, 6};
		Find2 f = new Find2();
		double searchFor = 3;
		System.out.println("start: " + f.bs(arr,searchFor-0.5)+1);
		System.out.println("end: " + f.bs(arr,searchFor+0.5));
	}

	public int bs(int[] arr, double target) {
		int s =0;
		int e = arr.length -1;
		while(s<=e) {
			int mid = (s+e)/2;
			if(arr[mid] == target) {
				return mid;
			}else if(arr[mid] < target) {
				s = mid+1;
			}else {
				e = mid-1;
			}
		}
		//System.out.println(s + " " + e);
		return s-1;
	}

}

- Harika January 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int noOfRepetitions(int array[],int start, int end,int number){
if(start > end)
return 0;
if(start == end)
return array[start] == number? 1:0;

int mid = (start + end)/2;
return (array[mid] == number? 1:0) + noOfRepetitions(array,start,mid-1,number) + noOfRepetitions(array,mid+1,end,number);

}

- sandy February 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int noOfRepetitions(int array[],int start, int end,int number){
if(start > end)
return 0;
if(start == end)
return array[start] == number? 1:0;

int mid = (start + end)/2;
return (array[mid] == number? 1:0) + noOfRepetitions(array,start,mid-1,number) + noOfRepetitions(array,mid+1,end,number);

}

- sandy February 25, 2016 | 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