Amazon Interview Question Computer Scientists
-1of 1 votefind the 3 most repeated numbers in a given array.
Country: India
Interview Type: In-Person
Would you please elaborate the last step i.e.
- Iterate through the map to find 3 most repeated elements.
In Java using 3 length array
public void findThreeMostRepeated(int[] ints) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < ints.length; i++) {
int curr = ints[i];
Integer count = 1;
if (map.containsKey(curr)) {
count = map.get(curr);
count++;
}
map.put(curr, count);
}
int[] rep = new int[3];
for (Integer key:map.keySet()) {
Integer count = map.get(key);
if (count > rep[0]) {
rep[0] = key;
Arrays.sort(rep);
}
}
System.out.println(Arrays.toString(rep));
}
Can you detail your solution? How will a 3 element array suffice, there can be n different elements rite?
@guptasunny158,,,, this is subbu2637 here,,I read ur comment..
Why u r making so discomfort to urself and to others by writting a whole code with some difficulties..
here look at this.According to ques..
1)tak 1 array ; int a[]={2,1,3,1,8,8,7,6,8,1,2,5,4,1,9,1,2,2,1,8,8,8,8}
2)tak 2 loops i and j fr iterating(traversing) purpose in array.[[[[it s also done wth one loop.fr better understaning i used 2 loops...]]]]
3)get the count of each element of array
4)declare the 3 elements whose and all are havng TOP(MORE) COUNT..
CODE:
int a[]={2,1,3,1,8,8,7,6,8,1,2,5,4,1,9,1,2,2,1,8,8,8,8};
n=a[].length-1;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]==a[j])//checking for duplicates in array
{
count++;
} //tat s it u r done..
if(count>maxcount) //checking for maxcount..
{
count=maxcount;
}
//do ths fr all elements count..get the most three repeating elements in array..
OUTPUT:
ELEMENT 8=7 counts
ELEMENT 1=6 counts
ELEMENT 2=4 counts.
All other elements other than this are havng count 1(check the count of elements once again in array ,,because i fastly typed and counted all of ths..Sry for any errs.But the concept is fine.If anyone encounter any prob reg this ..feel easy to contact me and reply the post...Sry for err OR COMMENT ME IS THS REALLY USEFUL....
Since you only need the top 3 entries in the HashMap you dont need to sort the whole hashmap. Just iterate thorough the whole set of keys and keep track of the topmost 3 counts. This will reduce the average complexity from O(nlogn) to O(n).
Sorry, I meant with my earlier comment:
* 3 element array for the final sweep of the count-hashTable.
What I meant was, no need for any fancy data structures or algorithms to get the top three frequencies in the final sweep. Some people might try to do a sort or take the counts and put it in a max-heap and then extract-max 3 times or some other priority queue-ing at the end.
@Anonymous
"This will reduce the average complexity from O(nlogn) to O(n)"
I'd try to express O-notation in terms of the worst case.
I express operations on original list in terms of n, and operations in HashMap in terms of m.
Under the scenario of a really big list (10+ millions) where all numbers are different.
If I use sort, I'd have O(n log m), but since all numbers are different, then n = m, so I'd have O(n log n).
On the other hand, if I keep track of the top three, I'd need to iterate HashMap and compare with top three each time, and in the worst case, let's suppose we always compare each item with all three, so I'd have O(n + m*k) where k is the number of items I want to keep track, then because of n = m, we have O (n + n*k).
If I want to keep track of all numbers =) ... (remember we want the worst case), so it'll be O(n + n^2) which reduces to O(n^2).
In a summary, we have O(n log n) vs O(n^2).
In the worst case, it's better to use sort. Maybe in the average (or realistic case), it's better keep track of top 3.
I'm just starting with Algorithms Analysis and I will really appreciate if somebody with more experience give a though about what I just said. Am I drunk? =)
package com.techighost.card;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
public class FindWordCount {
public static void main(String[] args) {
int[] inputArray = { 3, 8, 2, 4, 6, 65, 34, 3, 8, 4, 98, 23, 54, 3, 8,
65, 3 };
int[] output = new FindWordCount()
.findThreeMaxRepetitiveWords(inputArray);
for (int i = 0; i < output.length; i++) {
System.out.println(output[i]);
}
}
public int[] findThreeMaxRepetitiveWords(int[] inputArray) {
int[] ouput = new int[3];
Map<Integer, Integer> numberFrqMap = new HashMap<Integer, Integer>();
for (int i = 0; i < inputArray.length; i++) {
if (numberFrqMap.containsKey(inputArray[i])) {
int count = numberFrqMap.get(inputArray[i]);
numberFrqMap.put(inputArray[i], ++count);
} else {
numberFrqMap.put(inputArray[i], 1);
}
}
Set<Map.Entry<Integer, Integer>> set = numberFrqMap.entrySet();
Iterator<Map.Entry<Integer, Integer>> iterator = set.iterator();
List<Map.Entry<Integer, Integer>> entries = new ArrayList<Map.Entry<Integer, Integer>>();
while (iterator.hasNext()) {
Map.Entry<java.lang.Integer, java.lang.Integer> entry = (Map.Entry<java.lang.Integer, java.lang.Integer>) iterator
.next();
entry.getKey();
entries.add(entry);
}
Collections.sort(entries, new ValueComparator());
int k = 0;
for (Entry<Integer, Integer> entry : entries) {
ouput[k] = entry.getKey();
if (k == 2) {
break;
}
k++;
}
return ouput;
}
class ValueComparator implements Comparator<Map.Entry<Integer, Integer>> {
@Override
public int compare(Entry<Integer, Integer> o1,
Entry<Integer, Integer> o2) {
return o2.getValue() - o1.getValue();
}
}
}
The code above I have written to solve this problem, Anybody with a better solution than this..Or Anybody help me improving my code.
O(n) time and O(n) space algorithm:
- Chander Shivdasani September 22, 2013