Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
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();
}
}
}
// 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;
}
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;
}
#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;
}
/**
* 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));
}
}
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;
}
}
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);
}
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);
}
find most left and most right occurrences of given number with binary search and return {{right - left + 1}}
- Darkhan.Imangaliev November 25, 2015