## Amazon Interview Question for Interns

Country: United States
Interview Type: Phone Interview

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

Method 1: Extra space is allowed. So use HashMap with array elements being key and the count (frequency) being value.
Method 2: Extra space is not allowed. So sort the array, then iterate through the array. For each element, keep iterating forward till u get different element. This way, u can count the number of occurrences of each element.

``````// Time - O(n)
// Space - O(n)
static void modeWithSpace(int[] arr) {
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();

for(int temp: arr) {
if(hm.containsKey(temp))
hm.put(temp, hm.get(temp)+1);
else
hm.put(temp, 1);
}
System.out.println(hm);
}``````

``````// Time - O(nlogn) + O(n) => O(logn)
// Space - O(1)
static void modeNoSpace(int[] arr) {
Arrays.sort(arr);

int temp, count, j;
for(int i=0; i<arr.length; i++) {
temp = arr[i];
count = 0;

j = i;
while(temp == arr[j]) {
count++;
j++;
if(j == arr.length) break;
}
i = j-1;

System.out.print("\n"+ temp +" => "+ count);
}
}``````

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

you can emloy part of counting sort, just implement the fist two loop in counting sort.
time is O(n), space is O(k)

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

How can we implement counting sort if the range of the numbers is too high.Ex: {1,999999,4}

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

typo
Method 2: time - O(nlogn) + O(n) => O(nlogn)

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

Yes. If extra memory is allowed, place all elements with their frequencies O(n). Now, traverse the hashmap and print all keys with their frequenciesO(n), In the same traversal find the max frequency. Total cost is O(n).

If memory is not allowed. use quicksort or heap sort to sort the elements. Average cost is O(nlogn). No traverse through the array to find frequencies as well as max frequency and it's associated number.
O(nLogn)

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

``hey dude...how will u remove the collision when two different key will have same hash key?``

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.