## Amazon Interview Question

Country: India

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

``````public static ArrayList<Integer> getTopThree(ArrayList<Integer> numArray, Hashtable<Integer, Integer> h) {
int firstPlace = 0;
int firstPlaceNum = 0;
int secondPlace = 0;
int secondPlaceNum = 0;
int thirdPlace = 0;
int thirdPlaceNum = 0;

for(int i = 0; i < numArray.size(); i++) {
int num = numArray.get(i);
int value;

if(h.get(num) != null) {
value = h.get(num);
h.put(num, value + 1);
int newValue = value + 1;
if(newValue > firstPlace) {
firstPlace = newValue;
firstPlaceNum = num;
} else if(newValue <= firstPlace && newValue > secondPlace) {
secondPlace = newValue;
secondPlaceNum = num;
} else if(newValue <= secondPlace && newValue > thirdPlace) {
thirdPlace = newValue;
thirdPlaceNum = num;
}
} else {
h.put(num, 1);
if(firstPlace == 0) {
firstPlace = 1;
firstPlaceNum = num;
} else if(secondPlace == 0) {
secondPlace = 1;
secondPlaceNum = num;
} else if(thirdPlace == 0) {
thirdPlace = 1;
thirdPlaceNum = num;
}
}
}

ArrayList<Integer> topThree = new ArrayList<Integer>();

}``````

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

if(newValue > firstPlace) {
firstPlace = newValue;
firstPlaceNum = num;
}
I suppose this happens when second place occured the same number of times as the first place, and you updated the firstPlaceNum to be the old second place number, but second place also points to this same number. Did I misunderstand the code somewhere?

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

Questions like this must be answered by giving various approaches:-
1> As suggested, Hashtable with key as value from array and value being the count.
Then sort the hashtable.(Min Heap of size 3 , iterate thorugh all the keys and in accordance through count put them in heap)
2>similarly Balanced BST with frequency as additional value in node. then inorder traversal and putting values in heap

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

Min Heap or Max Heap of size 3?
Min heap will give you smallest 3 - correct?

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

Bounded heap concept. Basically at each frequency you check min of the heap and then if your frequency happens to be greater than min you insert it into heap(b4 delete the min). So this way you will always have the maximum 3 .

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

If frequency is just an additional value and not the key value, the in-order traversal will take place on the key value and not the frequency

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

@aztec It has to be a min heap of 3 highest ferq element so that you can compare the next element's from the top of min heap and decide if it belongs to the min heap(of highest freq elements) or not(in which case you can just move to next element)

However you can avoid all this post processing of creating heap by tracking which 3 elements has the largest count while creating the hash itself which has been show in code by Will_In_Seattle's post

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

use strict;
use warnings;

my @array = (20,20,20,20,3,4,2,4,2,2,3,1,4,5,7,5,3,9);
my %hash;
my \$len;
\$len = scalar(@array);
my \$i;
foreach(@array)
{
\$hash{\$_}++;
}
my @arr;
@arr = (sort { \$hash{\$b} <=> \$hash{\$a} } keys %hash)[0..3];
foreach(@arr)
{
print \$_ ."=>". \$hash{\$_}."\n";
}

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

Make a vector <pair<number, count>> (O(n) - space and O(n) time)
then do quickselect on this vector with k = size of the vector, size - 1, size - 2. (all 3 take O(n) time).

Thus, O(n) space and O(n) time

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

if the numbers are not very large we can use an array of length = the max of the numbers.
for each element in the given array increment the value from the position "element" in the new array. Now go 3 times and pick the max value from our array, putting an invalid value in its place and memorizing the position of the max.

return those 3 positions.

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

I think my code could solve some what of this problem.
public static void main(String args[]){
int RAM[] ={20,8,3,7,8,9,20,6,4,6,20,8,20};

for(int i=0;i<RAM.length;i++){
int count = 0;
for(int j=0;j<RAM.length;j++){

if(RAM[i]==RAM[j]){
count = count+1;
}
}

if(count >= 2){
System.out.println(RAM[i]+ " :) " + count + " :) ");
}
}
}

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

Hashmap. The array elements will be the keys and count will be the value. Get the 3 highest values and print corresponding keys.

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

May be a HashMap with keyvalue pairs

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

``````import java.util.HashMap;
import java.util.Iterator;

public class Repeat {
public static void main(String args[]){
final int RAM[] = {20,8,3,7,8,9,20,6,4,6,20,8,20};
topRepeat(RAM);
}

public static int[] topRepeat(int input[]){
int times[] = {0,0,0};
int output[] = {0,0,0};

for(int i : input){
if(list.contains(i))
continue;
}

HashMap<Integer, Integer> hashMap =
new HashMap<Integer, Integer>();
for(int i : input){
if(hashMap.containsKey(i))
hashMap.put(i, hashMap.get(i) + 1);
else
hashMap.put(i, 1);
}

Iterator<Integer> it = list.iterator();

while(it.hasNext()){
int i = it.next();
int time = hashMap.get(i);
if(time > times[2]){
if(time > times[1]){
if(time > times[0]){
times[2] = times[1];
times[1] = times[0];
times[0] = time;
output[0] = i;
continue;
}
times[2] = times[1];
times[1] = time;
output[1] = i;
continue;
}
times[2] = time;
output[2] = i;
}
}

for(int i = 0; i < 3; i++)
System.out.printf("%d is repeated %d times\n", output[i], times[i]);
return output;
}
}``````

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

.

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.