Amazon Interview Question SDE-2s
Country: India
public class BinarySearch {
//Time Complexity O(logn)
public int searchFirstOccurrence(int a[], int target) {
int low = 0;
int high = a.length - 1;
int result = -1;
while (low <= high) {
int mid = (high + low) / 2;
if(target == a[mid]) {
result = mid;
high = mid - 1;
}
else if(target > a[mid]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
//Time Complexity O(logn)
public int searchLastOccurrence(int a[], int target) {
int low = 0;
int high = a.length - 1;
int result = -1;
while (low <= high) {
int mid = (high + low) / 2;
if(target == a[mid]) {
result = mid;
low = mid + 1;
} else if(target > a[mid]) {
low = mid +1;
} else {
high = mid - 1;
}
}
return result;
}
//Time Complexity O(logn)
public int countOccurrence(int a[], int target) {
return searchLastOccurrence(a, target) - searchFirstOccurrence(a,target) + 1;
}
public static void main(String[] args) {
int b[] = {2,2,2,2,2,2,4,4,4,4,10,10,10,18,18,20,20,20,20,20};
System.out.println("First occurrence of 10: " + binarySearch.searchFirstOccurrence(b, 10));
System.out.println("Last occurrence of 10: " + binarySearch.searchLastOccurrence(b, 10));
System.out.println("Count total occurrences of 10: " + binarySearch.countOccurrence(b, 10));
System.out.println("First occurrence of 2: " + binarySearch.searchFirstOccurrence(b, 2));
System.out.println("Last occurrence of 2: " + binarySearch.searchLastOccurrence(b, 2));
System.out.println("Count total occurrences of 2: " + binarySearch.countOccurrence(b, 2));
}
}
Assuming the problem is: Given a sorted array, find how many times an element occurs in sublinear time. Here's some code to do just that in O(logn) which uses a modified binary search to find the left most occurrence of the element and the rightmost occurrence and taking the difference plus one to get total occurences.
int binarySearch(vector<int> arr, int left, int right, int x, bool go_left) {
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
if (arr[mid] == x) {
if (go_left && mid-1 >= 0 && arr[mid-1] == x) {
return binarySearch(arr, left, mid - 1, x, go_left);
}
else if(!go_left && mid + 1 < arr.size() && arr[mid + 1] == x) {
return binarySearch(arr, mid + 1, right, x, go_left);
}
else {
return mid;
}
}
else {
if (arr[mid] > x) {
return binarySearch(arr, left, mid - 1, x, go_left);
}
else {
return binarySearch(arr, mid + 1, right, x, go_left);
}
}
return -1;
}
int main() {
int N,X;
cin >> N >> X;
vector<int> a(N);
for (int i = 0; i < N; i++) {
cin >> a[i];
}
int left_index = binarySearch(a, 0, a.size() - 1, X, true);
int right_index = binarySearch(a, 0, a.size() - 1, X, false);
if (right_index == -1 || left_index == -1) {
cout << -1 << endl;
}
else {
cout << right_index - left_index + 1 << endl;
}
}
public static int FindFrequency(int[] a, int x)
{
if (a == null || a.Length == 0)
return 0;
int index = BinarySearch(a, x);
if (index == -1)
return 0;
int firstIndex = GetFirstOcurrence(a, index);
int lastIndex = GetLastOccurrence(a, index);
return lastIndex - firstIndex + 1;
}
// Binari Search to find any occurence of item
private static int BinarySearch(int[] a, int x)
{
int start = 0;
int end = a.Length - 1;
while (start <= end)
{
int midle = (start + end) / 2;
if (a[midle] == x)
return midle;
if (a[midle] > x)
end = midle - 1;
else
start = midle + 1;
}
return -1;
}
private static int GetLastOccurrence(int[] a, int index)
{
int x = a[index];
int start = index;
int end = a.Length - 1;
while (start <= end)
{
int midle = (start + end) / 2;
if (a[midle] == x)
{
index = midle;
start = midle + 1;
}
else
{
end = midle - 1;
}
}
return index;
}
private static int GetFirstOcurrence(int[] a, int index)
{
int x = a[index];
int start = 0;
int end = index;
while (start <= end)
{
int midle = (start + end) / 2;
if (a[midle] == x)
{
index = midle;
end = midle - 1;
}
else
{
start = midle + 1;
}
}
return index;
}
@anandsh1990 : - This is normal linear search which runs in O(n) .... The question talks about a solution in less than O(n) .
We can do it in O(1) ... by using an extra space (map) and storing the number as key and frequency as value . But even this way first time the run time would be O(n) but subsequent finds will be run in O(1) ...
#include<iostream>
#include<string>
using namespace std;
void findFrequency(string myarray, char find)
{
int count = 0;
int i = 0;
for(i = 0; i < myarray.length(); i++ )
{
if( (myarray.length() - i) <= i )
break;
if( myarray[i] == find )
{
count += 1;
}
if( ((myarray.length()-1 - i) != i) && myarray[ myarray.length()-1 - i ] == find )
{
count += 1;
}
}
cout<<"Frequency of "<< find <<" in "<< i << " cycles of an array of "<<myarray.length()<< " is "<<count<<endl;
}
int main()
{
string digits;
char findChar;
cout<<"Enter digits: ";
while(getline(cin, digits ) )
{
cout<<"Enter digit find frequenc: ";
cin>>findChar;
findFrequency( digits, findChar );
cin.get();
cout<<"Enter digits: ";
}
return 0;
}
#include<iostream>
#include<string>
using namespace std;
void findFrequency(string myarray, char find)
{
int count = 0;
int i = 0;
for(i = 0; i < myarray.length(); i++ )
{
if( (myarray.length() - i) <= i )
break;
if( myarray[i] == find )
{
count += 1;
}
if( ((myarray.length()-1 - i) != i) && myarray[ myarray.length()-1 - i ] == find )
{
count += 1;
}
}
cout<<"Frequency of "<< find <<" in "<< i << " cycles of an array of "<<myarray.length()<< " is "<<count<<endl;
}
int main()
{
string digits;
char findChar;
cout<<"Enter digits: ";
while(getline(cin, digits ) )
{
cout<<"Enter digit find frequenc: ";
cin>>findChar;
findFrequency( digits, findChar );
cin.get();
cout<<"Enter digits: ";
}
return 0;
}
public class Reped_string {
public static void main(String[] args) {
Scanner inp =new Scanner(System.in);
int tmp=0;
System.out.println("Enter array with comma ");
String ary = inp.next();
System.out.println("Enter digit find frequenc ");
String pval=inp.next();
String[] splitary = ary.split(",");
for(int i=0;i<splitary.length ;i++)
{
if(pval.equals(splitary[i]))
{
tmp+=1;
}
}
System.out.println("frequenc Times :"+tmp);
}
}
public class Reped_string {
public static void main(String[] args) {
Scanner inp =new Scanner(System.in);
int tmp=0;
System.out.println("Enter array with comma ");
String ary = inp.next();
System.out.println("Enter digit find frequenc ");
String pval=inp.next();
String[] splitary = ary.split(",");
for(int i=0;i<splitary.length ;i++)
{
if(pval.equals(splitary[i]))
{
tmp+=1;
}
}
System.out.println("frequenc Times :"+tmp);
}
}
import java.util.Scanner;
public class Reped_string {
public static void main(String[] args) {
Scanner inp =new Scanner(System.in);
int tmp=0;
System.out.println("Enter array with comma ");
String ary = inp.next();
System.out.println("Enter digit find frequenc ");
String pval=inp.next();
String[] splitary = ary.split(",");
for(int i=0;i<splitary.length ;i++)
{
if(pval.equals(splitary[i]))
{
tmp+=1;
}
}
System.out.println("frequenc Times :"+tmp);
}
}
import java.util.Scanner;
public class Reped_string {
public static void main(String[] args) {
Scanner inp =new Scanner(System.in);
int tmp=0;
System.out.println("Enter array with comma ");
String ary = inp.next();
System.out.println("Enter digit find frequenc ");
String pval=inp.next();
String[] splitary = ary.split(",");
for(int i=0;i<splitary.length ;i++)
{
if(pval.equals(splitary[i]))
{
tmp+=1;
}
}
System.out.println("frequenc Times :"+tmp);
}
}
import java.util.Scanner;
public class Reped_string {
public static void main(String[] args) {
Scanner inp =new Scanner(System.in);
int tmp=0;
System.out.println("Enter array with comma ");
String ary = inp.next();
System.out.println("Enter digit find frequenc ");
String pval=inp.next();
String[] splitary = ary.split(",");
for(int i=0;i<splitary.length ;i++)
{
if(pval.equals(splitary[i]))
{
tmp+=1;
}
}
System.out.println("frequenc Times :"+tmp);
}
}
import java.util.Scanner;
public class Reped_string {
public static void main(String[] args) {
Scanner inp =new Scanner(System.in);
int tmp=0;
System.out.println("Enter array with comma ");
String ary = inp.next();
System.out.println("Enter digit find frequenc ");
String pval=inp.next();
String[] splitary = ary.split(",");
for(int i=0;i<splitary.length ;i++)
{
if(pval.equals(splitary[i]))
{
tmp+=1;
}
}
System.out.println("frequenc Times :"+tmp);
}
}
and
import java.util.Scanner;
public class Reped_string {
public static void main(String[] args) {
Scanner inp =new Scanner(System.in);
int tmp=0;
System.out.println("Enter array with comma ");
String ary = inp.next();
System.out.println("Enter digit find frequenc ");
String pval=inp.next();
String[] splitary = ary.split(",");
for(int i=0;i<splitary.length ;i++)
{
if(pval.equals(splitary[i]))
{
tmp+=1;
}
}
System.out.println("frequenc Times :"+tmp);
}
}
and
import java.util.Scanner;
public class Reped_string {
public static void main(String[] args) {
Scanner inp =new Scanner(System.in);
int tmp=0;
System.out.println("Enter array with comma ");
String ary = inp.next();
System.out.println("Enter digit find frequenc ");
String pval=inp.next();
String[] splitary = ary.split(",");
for(int i=0;i<splitary.length ;i++)
{
if(pval.equals(splitary[i]))
{
tmp+=1;
}
}
System.out.println("frequenc Times :"+tmp);
}
}
import java.util.Scanner;
public class Reped_string {
public static void main(String[] args) {
Scanner inp =new Scanner(System.in);
int tmp=0;
System.out.println("Enter array with comma ");
String ary = inp.next();
System.out.println("Enter digit find frequenc ");
String pval=inp.next();
String[] splitary = ary.split(",");
for(int i=0;i<splitary.length ;i++)
{
if(pval.equals(splitary[i]))
{
tmp+=1;
}
}
System.out.println("frequenc Times :"+tmp);
}
}
1. Keep a new counter count=0
2. Initialize two variables i = 0 and j = size of array - 1
3. Increment count if an occurrence of element is found at position j or i
4. Increment i and decrement j.
5. Repeat step 3 - 4 and exit as soon as i > j
Take care of edge case when i == j, this occurs when array length is odd. in this case increment count only once.
Worst case time complexity is O(N/2) which is less than O(N). Space complexity O(1)
Solution in java script
function binary(arr, s,e,v) {
while (s <= e) {
var m = (s+e) >> 1;
if(arr[m] === v) {
return m
} else if(v >= arr[m]) {
s = m+1;
} else {
e = m - 1;
}
}
return -1;
}
var arr = [2,2,2,2,2,2,4,4,4,4,10,10,10,18,18,20,20,20,20,20];
var inp = 4;
var i = binary(arr, 0, arr.length-1, inp);
console.log(i)
if(i != -1) {
var l = (i-1);
var j= (i+1);
var count=1;
while(j < arr.length && arr[i] === arr[j]) {
count++;
j++;
}
while(l >=0 && arr[i] === arr[l] ) {
count++;
l--;
}
console.log(count);
}
function binary(a,b,c,d){for(;b<=c;){var e=b+c>>1;if(a[e]===d)return e;d>=a[e]?b=e+1:c=e-1}return-1}var arr=[2,2,2,2,2,2,4,4,4,4,10,10,10,18,18,20,20,20,20,20],inp=4,i=binary(arr,0,arr.length-1,inp);if(console.log(i),-1!=i){for(var l=i-1,j=i+1,count=1;j<arr.length&&arr[i]===arr[j];)count++,j++;for(;l>=0&&arr[i]===arr[l];)count++,l--;console.log(count)
}
Assuming array is sorted
if right most index of the number is subtracted from the left most index then we get the frequency of that number.
wrote two modified binary search functions, which give left most and right most index of number.
complexity O(log(n))
static int find_left_most_index_of_number(int[] array, int l, int r, int num)
{
if(l <= r)
{
int mid = (l+r)/2;
if(array[l] == num)
return l;
else if(array[mid] == num)
return find_left_most_index_of_number(array, l+1, mid, num);
if(num < array[mid])
return find_left_most_index_of_number(array, l, mid - 1, num);
else if(num > array[mid])
return find_left_most_index_of_number(array, mid + 1, r, num);
}
return -1;
}
static int find_right_most_index_of_number(int[] array, int l, int r, int num)
{
if(l <= r)
{
int mid = (l+r)/2;
if(array[r] == num)
return r;
else if(array[mid] == num)
return find_right_most_index_of_number(array, mid, r-1, num);
if(num < array[mid])
return find_right_most_index_of_number(array, l, mid - 1, num);
else if(num > array[mid])
return find_right_most_index_of_number(array, mid + 1, r, num);
}
return -1;
}
public static void main(String args[])
{
int[] array = {1, 2, 2, 3, 4, 5, 5, 5};
for(int i=0; i<5; i++)
{
int left = find_left_most_index_of_number(array, 0, array.length - 1, i+1);
int right = find_right_most_index_of_number(array, 0, array.length - 1, i+1);
System.out.println("frequency of " + (i+1) + ": " + ((right - left) + 1));
}
}
import java.util.Scanner;
public class FindFrequencyArray {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter a number of Elements : ");
int n = sc.nextInt();
int arr[] = new int[n];
System.out.println("Enter the Elements : ");
for(int i=0;i<n;i++)
{
arr[i]=sc.nextInt();
}
System.out.println("Enter a number to find : ");
int findNum=sc.nextInt();
int count=0;
for(int i=0;i<n;i++)
{
if(arr[i]==findNum)
count=count+1;
}
System.out.println(findNum+" is present "+count+" times in array.");
}
}
If Only Array given without any condition like "sorted" or "some pattern", then less then O(N) is not possible. Less then N means you don't go to all N address location but still gets the answer. This we can do if we can proof, the location we are skipping is NOT having our required key. And for this we need some condition.
- Manish April 01, 2017I guess there will be some condition on array or may be array is sorted then only we can get less then O(N)