## Amazon Interview Question for SDE-2s

• -2

Country: India

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

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.

I guess there will be some condition on array or may be array is sorted then only we can get less then O(N)

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

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

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

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

}

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

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

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

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

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

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

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

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

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

You can't unless you have extra information about the array. If the input is sorted and rotated, (first example), you can a modified binary search. But even that solution will still have a worst case time complexity of O(n) for your second example.

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

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

}

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

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

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

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

}

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

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

}

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

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

}``````

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

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

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

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

}

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

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

}``````

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

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

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

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)

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

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

}

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

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

}

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

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

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

``````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.");
}
}``````

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.