## Amazon Interview Question for Quality Assurance Engineers

Team: MP3 mobile team
Country: India
Interview Type: Phone Interview

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

I think we can
(i) store the occurence of every element using maps in C++
(ii) build a Max-heap in linear time of the occurences(or frequence) of element and then extract upto the N-th element,
Each extraction takes log(n) time to heapify.
(iii) we will get the frequency of the N-th most frequent number
(iv) then we can linear search through the hash to find the element having this frequency.

Time - O(NlogN)
Space - O(N)

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

Your time complexity doesn't take into account the traversal through the entire array to store occurrence of every element in Maps, which would be O(n).
So, the total time should be = O(n) + O(n log n).

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

Your time complexity doesn't take into account the traversal through the entire array to store occurrence of every element in Maps, which would be O(n).
So, the total time should be = O(n) + O(n log n).

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

``O(n) + O(nlogn)``

is same as O(n) as we only consider the maximum in case of running time

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

O(n) + O(nlogn) is same as O(n) as we only consider the maximum in case of running time

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

What about other elements in the array ?? They may also repeated in the array ??

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

array may be following form.
{3,3,3,5,10,44,11,44,100,102,102,102}

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

I think the easiest way is to go for hashing with selection. Use hash to get frequent dataset and then use that frequent dataset for O(n) time selection .

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

@ mdfirozansari : for your given array if the 2nd most freq is asked Op is 102 or 44.. Since 3 will be the 1st most freq no ?

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

1. add to map with number as the key and its frequency as the value O(n)
2. get the values from the map as list and do kth select algorithm O(log n);

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

We have to get both Keys and values. Get the Values list and do the nth order statistic algo O(n) and get that index value. keys[index] should give the nth most frequent element.
Space : O(n) Time : O(n) - using kth order statistic in values list

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

@Siva: select algorithm for kth element takes O(n*k) time complexity.

rather than going to select algorithm we can just traverse thru the hashmap and the first encountered key with value n will be our answer. Hence total time complexity is O(array_size)

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

Vaishnavi.. please read the q again.. n is not the no of occurences of a number in the array

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

This comment has been deleted.

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

hey why have you made frequency as Key?

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

Since we don't know what is size of Array, Hashing will be tedious and space consuming.
I think we can create a augumented tree of field key as frequency and Value storing number.

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

@Vyshanvi : How you are constructing map with frequency as a key ????

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

Hi Ram,

Yes, I could get my mistake of making frequency as a key. I made frequency as key to make the nth frequent number retrieval as O(1). But I could see the solution I gave is not possible.

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

hmm..ok

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

Maintain a HashMap<Integer, Integer> to store the number as key with its count as value. Use two other variables to keep track of the max count and its corresponding key.

For ex:

``````public static void main(String[] args) {
int[] a = {3,3,3,5,10,44,11,44,100,102,102,102};
System.out.println(getNthMostFrequent(a));
}
/**
* @param a - array of integers
* @return most frequent number in the given array. returns -1, if the array is empty.
*/
public static int getNthMostFrequent(int[] a) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int maxCount=0, freqValue = -1;
for(int i=0; i < a.length; i++) {
if(map.get(a[i]) == null) { //Insert new.
map.put(a[i], 1);
}else { //Already exists. Just increment the count.
int count = map.get(a[i])+1;
map.put(a[i], count);
if(count < maxCount) {
maxCount = count;
freqValue = a[i];
}
}
}
//incase all numbers are unique.
if(freqValue == -1 && a.length>0)
return a[0];
return maxValue;
}``````

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

This solution finds the most frequent key, whereas the problem asks for the nth most frequent key.

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

Sorting the keys based on values will be the answer to your question.

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

Your solution isnt implemented correctly. Here is the corrected implementation.

``````public static int getNthMostFrequent(int[] a) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int maxCount=0, freqValue = -1;
for(int i=0; i < a.length; i++) {
if(map.get(a[i]) == null) { //Insert new.
map.put(a[i], 1);
}else { //Already exists. Just increment the count.
int count = map.get(a[i])+1;
map.put(a[i], count);
if(count > maxCount) {
maxCount = count;
freqValue = a[i];
}

}

}
//incase all numbers are unique.
if(freqValue == -1 && a.length>0)
return a[0];
return freqValue;
}

}``````

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

int a[10]={1,2,3,2,5,6,1,2,3,4};
map<int,int> mymap;
map<int,int>::iterator itr;

for(int i=0;i<10;i++)
{
itr = mymap.find(a[i]);
if(itr != mymap.end()) //already element is saved
{
//increament count for occurence
mymap[a[i]]=itr->second + 1;
}
else
mymap.insert(pair<int,int>(a[i],1)); // first time inserting in map
}

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

HashMap solutions looks promising since the complexity is o(n) + o(logn).. if we are using a BST, it is a complex process to fetch the highest frequency element at last..

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

#include<stdio.h>
#include<limits.h>
int a[]={1,2,3,3,1,1,1,1,3,2,2,};
void count()
{int i,max=INT_MIN;
int n=sizeof(a)/sizeof(int);
int *b=calloc(sizeof(int),n);
for(i=0;i<n;i++)
{
b[a[i]]=b[a[i]]++;
if(max < b[a[i]] )
{

max=b[a[i]];
}

}
printf("%d\n",max);
}

int main()
{
count();
return 0;
}

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

``````#include<stdio.h>
#include<stdlib.h>

struct rec
{
int num;
unsigned int count;
};

int arr[]={2,4,2,1,0,4,4,5,5,4,4,0,2};

void qsortX(int*a,int low,int high)
{
int i,j;
int key;
int mid=(low+high)/2;

key=a[mid];
i=low;j=high;

do
{
while(a[i]<key)i++;
while(a[j]>key)j--;
if(i<=j)
{
int tmp=a[i];
a[i]=a[j];
a[j]=tmp;
i++;j--;
}
}while(i<=j);

if(i<high) qsortX(a,i,high);
if(j>low) qsortX(a,0,j);

return;
}

void sort(int* a, int l)
{
qsortX(a,0,l-1);

return;
}

void qsortS(struct rec* a,int low,int high)
{
int i,j;
int key;
int mid=(low+high)/2;

key=a[mid].count;
i=low;j=high;

do
{
while(a[i].count>key)i++;
while(a[j].count<key)j--;
if(i<=j)
{
int tmp=a[i].count;
a[i].count=a[j].count;
a[j].count=tmp;

tmp=a[i].num;
a[i].num=a[j].num;
a[j].num=tmp;
i++;j--;
}
}while(i<=j);

if(i<high) qsortS(a,i,high);
if(j>low) qsortS(a,0,j);

return;
}

void sortS(struct rec* a, int l)
{
qsortS(a,0,l-1);

return;
}

void printarr(int* a,int l)
{
int i;

for(i=0;i<l;i++)
{
printf(" %d ",a[i]);
}
printf("\n");

return;
}

int main()
{
int len=sizeof(arr)/sizeof(arr[0]);
sort(arr,len);
printarr(arr,len);

int i,j;
int n=4;

struct rec* rec_arr;

rec_arr=(struct rec*)calloc(n,sizeof(struct rec));
if(!rec_arr)
return -1;

j=0;
rec_arr[j].num=arr[0];
rec_arr[j].count=1;

int last=arr[0];
for(i=1;i<len;i++)
{
if(	arr[i]!=last)
{
rec_arr[++j].num=arr[i];
rec_arr[j].count=1;
last=arr[i];
}
else
{
rec_arr[j].count++;
}
}

if(j>=n)
{
sortS(rec_arr,j);
printf("%d occurence is of number %d %d times\n",n,rec_arr[n-1].num,rec_arr[n-1].count);
}
else
printf("the number given dosen't exist\n");

return 0;
}``````

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

#include<stdio.h>
main()
{
int i,j,b,n,count=1;
int a[100];
printf("given the array size\n");
scanf("%d",&n);

printf("given array elements\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);

for(i=1;i<=n;i++)

for(j=0;j<n-i;j++)
{
if(a[j]>a[j+1])
{
b=a[j+1];
a[j+1]=a[j];
a[j]=b;
}
}

for(i=0;i<n;i++)
{
if(a[i]==a[i+1])

count++;

else
{
printf("frequence of element %d == %d\n",a[i],count);

count=1;
}
}

}

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

/**
* 1. Stored array of values into TreeMap with key as value and value as count of that occurances
* 2. Get the the list of values from TreeMap and stored them in TreeSet
* 3. All the values will store in desending order
* 4. With the TreeSet , you have the value and get the key from the value using EntryMap.
*/

int array[]={12,12,13,14,133,155,166,134,123,123,1234,12345};

SortedMap<Integer, Integer> sMap = new TreeMap<Integer, Integer>();
sMap.put(array[0], 1);
int temp;
for (int i = 1; i < array.length; i++) {

if(sMap.get(array[i])!=null){
temp=sMap.get(array[i]);
sMap.put(array[i],temp+1);
}else{
sMap.put(array[i],1);
}
temp=0;
}
System.out.println(sMap);

TreeSet<Integer> treeSet=new TreeSet<Integer>(sMap.values());
System.out.println(treeSet.toArray()[1]);

for (Entry<Integer, Integer> entry : sMap.entrySet()) {
if (entry.getValue().equals(treeSet.toArray()[1])) {
System.out.println("1st higest value is"+ entry.getKey());
}
}

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

``````public static int FrequentNumber(int[] a, int frequency) {

HashMap<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();
int temp;
for (int i = 0; i < a.length; i++) {
temp = 1;
if (frequencyMap.containsKey(a[i])) {
temp = frequencyMap.get(a[i]) + 1;
frequencyMap.put(a[i], temp);
} else {
frequencyMap.put(a[i], temp);
}
}

ArrayList<Integer> values = new ArrayList<Integer>(
frequencyMap.values());
Collections.sort(values);

int index = values.get(values.size() - frequency);
for (Entry<Integer, Integer> e : frequencyMap.entrySet()) {
if (e.getValue().equals(index))
return (int) e.getKey();
}
return 0;
}``````

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

count = input("Enter the count")
index = 0
numarray = []
for index in range(count):
numarray.append(input())
#number = input("Enter the number")
number = 0

def nthOccurence(arr, num):
arrlen = len(arr)
for index in range(arrlen):
index2 = index +1
count = 1
for index2 in range(index2,arrlen):
if arr[index] == arr[index2]:
count=count+1
arr[index2]=' '
if arr[index]!=' ':
print "occurence (%s,%s)" % (arr[index],count)

nthOccurence(numarray,number)

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

``````count = input("Enter the count")
index = 0
numarray = []
for index in range(count):
numarray.append(input())
#number = input("Enter the number")
number = 0

def nthOccurence(arr, num):
arrlen = len(arr)
for index in range(arrlen):
index2 = index +1
count  = 1
for index2 in range(index2,arrlen):
if arr[index] == arr[index2]:
count=count+1
arr[index2]=' '
if arr[index]!=' ':
print "occurence (%s,%s)"  % (arr[index],count)

nthOccurence(numarray,number)``````

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

I came up with a solution by only using array and nothing else.. Please try it and post ur comments

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

``````# include <stdio.h>
# include <conio.h>

void main ()
{
int i,j,arr[256],size;
char *text;

printf("Enter the text : ");
scanf("%s",text);
i = 0;

for (i=0;i<255;i++)
{
arr[i]=0;

}
i=0;

while(text[i] != '\0')
{
arr[(int)text[i]]++;
i++;
}

for(i=0;i<255;i++)
{
if( arr[i]>0)
{
printf("%c : %d\n",(char)i,arr[i]);
}
}

printf("\n%s",text);

getch ();
clrscr();
}``````

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

In Java, I think we use hashtable and O(n) by keeping the first and second frequent elements.

During the construction of hashtable, we update the count and update the first and second frequent elements.

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

i) Iterate through the unordered array to build a hashmap of the numbers with frequency.
O(n) time, O(k) space

ii) Build a primitive array length equal to number of keys in hashmap. Iterate through the hashmap values and append them to the array
O(k) time, O(k) space

ii) You could sort the primitive array in k*log(k) time OR access the j-th largest frequency in O(k) using quickselect algorithm (google quickselect algorithm)

iii) Iterate through the hashmap looking for the j-th largest frequency and thats the number to return.
O(n) time

Overall: O(n) time, O(k) space where k is the number of unique instances of the n integers.

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

I am in agreement with pretty much everything that you mentioned entirely! Excellent website document! bedgecdafbfackdd

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

import java.util.*;
public class CC10 {

public static void main(String[] args) {
int[] arr={0,1,2,3,4,5};
int len=arr.length;
int count=1;
int frequency=0;
int maxfreq=0;
HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
if(len==0){
System.out.println("The given array is empty");
}
else if(len==1){
System.out.println("The array contains only one element");
}
else{

for(int i=0;i<len;i++){
if(hm.containsKey(arr[i])){
count=(hm.get(arr[i])) + 1;
hm.put(arr[i],count);

if(count>frequency){
frequency=count;
maxfreq=arr[i];
}
}
else{
hm.put(arr[i], 1);
}
}
if(frequency==0){

System.out.println("No duplicate elements");

}

else{
Set<Map.Entry<Integer, Integer>> me=hm.entrySet();
for(Map.Entry<Integer, Integer> me1:me){
if(me1.getValue()==frequency) {

System.out.println("The most frequent element is: " + me1.getKey() + " occurring " + me1.getValue() +" times.");
}}

}
}}

}

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

``````import java.util.*;
public class CC10 {

public static void main(String[] args) {
int[] arr={0,1,2,3,4,5};
int len=arr.length;
int count=1;
int frequency=0;
int maxfreq=0;
HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
if(len==0){
System.out.println("The given array is empty");
}
else if(len==1){
System.out.println("The array contains only one element");
}
else{

for(int i=0;i<len;i++){
if(hm.containsKey(arr[i])){
count=(hm.get(arr[i])) + 1;
hm.put(arr[i],count);

if(count>frequency){
frequency=count;
maxfreq=arr[i];
}
}
else{
hm.put(arr[i], 1);
}
}
if(frequency==0){

System.out.println("No duplicate elements");

}

else{
Set<Map.Entry<Integer, Integer>> me=hm.entrySet();
for(Map.Entry<Integer, Integer> me1:me){
if(me1.getValue()==frequency)	{

System.out.println("The most frequent element is: " + me1.getKey() + " occurring " + me1.getValue() +" times.");
}}

}
}}

}``````

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

I agree with Rishi, Since we don't know size of array and range of numbers in array its better to use tree with field Value and frequency. Traverse each element of array and add in BST with frequency 1 if it does not exits already. In case if that number already exist then just increase its frequency by 1. Once all array traversed, we can use Traverse mathod to find the number with hightest frequency.

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

Using this tree we can find number with nth highest frequency.

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

How can we use this BST tree to find the nth highest frequency element? We are inserting the elements in the tree based on the value of the element and not its frequency. so after constructing the complete tree we can determine the element with highest frequency logically but not the element with highest frequency. We will need to go through each element in the tree to find it and its as good as finding from a link list or any other data structure. BST have no particular advantage in this case.

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

I agree with tarutrehan. Can Anonymous explain how exactly BST is useful compared to others?

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

one solution willl be after the bst is created use heapify function to create a max heap on the frequency of each element and extract the nth most frequent element

creating bst O(nlogn)
creating heap O(nlogn)
so overall O(nlogn)

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.