Amazon Interview Question Quality Assurance Engineers
0of 0 votesFind the nth most frequent number in array
Team: MP3 mobile team
Country: India
Interview Type: Phone Interview
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).
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).
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 .
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);
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
@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)
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.
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;
}
This solution finds the most frequent key, whereas the problem asks for the nth most frequent key.
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;
}
}
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
}
#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;
}
#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;
}
#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;
}
}
}
/**
* 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());
}
}
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;
}
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)
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)
# 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();
}
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.
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.");
}}
}
}}
}
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.");
}}
}
}}
}
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.
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.
I agree with tarutrehan. Can Anonymous explain how exactly BST is useful compared to others?
I think we can
- alexander June 10, 2012(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)