Amazon Interview Question
InternsCountry: United States
Interview Type: Phone Interview
you can emloy part of counting sort, just implement the fist two loop in counting sort.
time is O(n), space is O(k)
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)
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.
- Zero October 25, 2012