Uber Interview Question
Software EngineersTeam: Marketplace
Country: United States
Over my interpretation, most frequent is different of longest sequence.
And i have a question, if there is more elements with the same frequency? Should return a list of them?
from collections import Iterable
def get_most_frequent(input_list):
max_sequence = 0
most_frequent = None
numbers_frequence = {}
if(not isinstance(input_list, Iterable)):
return most_frequent
for n in input_list:
if(numbers_frequence.get(n, False) is not False):
numbers_frequence[n] += 1
else:
numbers_frequence[n] = 1
if(numbers_frequence[n] > max_sequence):
max_sequence = numbers_frequence[n]
most_frequent = [n]
elif(numbers_frequence[n] is max_sequence):
most_frequent.append(n)
return most_frequent
print(get_most_frequent([0,1,2,3,4,4,4]))
print(get_most_frequent([5,5,5,7,7,7,8,9]))
print(get_most_frequent([0]))
Not overly efficient, but this should get the job done (java):
public static void findKthMostFrequent(int[] arr, int k) {
Map<Integer, Integer> intToFrequency = new HashMap<>(arr.length);
// O(n)
for (int i=0; i<arr.length; i++) {
int elem = arr[i];
int freq = 0;
if (intToFrequency.containsKey(elem)) {
freq = intToFrequency.get(elem);
}
intToFrequency.put(elem, freq + 1);
}
// O(n)
Map<Integer, List<Integer>> frequencyToInts = new HashMap<>();
for (Integer elem : intToFrequency.keySet()) {
Integer freq = intToFrequency.get(elem);
List<Integer> intsForFrequency = frequencyToInts.getOrDefault(freq, new ArrayList<>());
intsForFrequency.add(elem);
frequencyToInts.put(freq, intsForFrequency);
}
// Sort the keys: O(nlogn) worst case
List<Integer> frequenciesAscending = new ArrayList<>(frequencyToInts.keySet()); // another O(n) to convert to list, there might be some Set sorting function to avoid this
Collections.sort(frequenciesAscending); // O(nlogn), merge sort
int kthFrequency = frequenciesAscending.get(frequenciesAscending.size()-k);
System.out.println("Kth most frequent element(s)" + frequencyToInts.get(kthFrequency));
// time complexity: O(n + n + nlogn) = O(nlogn)
}
public List<Integer> topKFrequent(int[] nums, int k) {
//k most frequent element
int count = 0;
Map<Integer,Integer> map = new HashMap<>();
List<Integer> result = new ArrayList<>();
for(int i = 0; i < nums.length;i++){
if(map.containsKey(nums[i])){
map.put(nums[i],map.get(nums[i])+1);
}else
map.put(nums[i],1);
}
while(count < k){
int max = 0;
int value = 0;
for(Map.Entry<Integer, Integer> entry: map.entrySet()){
max = Math.max(max, entry.getValue());
if(entry.getValue() >= max){
max = entry.getValue();
value = entry.getKey();
}
}
map.remove(value);
result.add(value);
count++;
}
return result;
}
Count each number, and put into hashmap. Dump the hashmap contents into an auxiliary array. Perform quickselect on that array. Total O(n) time and O(n) space.
from collections import defaultdict
def helper(aux, lo, hi, c):
pivot_count, _ = aux[hi]
i = lo # i represents the exclusive upper bound on count < pivot_count
k = hi # k represents the exclusive lower bound on count > pivot_count
j = lo # i < j < k; (j, k) is the interval where count == pivot_count
while j <= k:
count, num = aux[j]
if count < pivot_count:
aux[i], aux[j] = aux[j], aux[i]
i += 1
j += 1
elif count > pivot_count:
aux[j], aux[k] = aux[k], aux[j]
k -= 1
else:
j += 1
aux[k + 1], aux[hi] = aux[hi], aux[k + 1]
left, right = i, k + 1
if c - 1 < left:
return helper(aux, lo, left - 1, c)
elif left <= c - 1 <= right:
return aux[left][1]
else:
return helper(aux, right + 1, hi, c)
def kthMostFrequentNumber(nums, k):
assert k > 0, f'k must be greater than 0: {k}'
assert len(nums) > 0, f'nums must be non-empty'
counts = defaultdict(int)
for num in nums:
counts[num] += 1
assert k <= len(counts), f'k must be between 1 and {len(counts)}: {k}'
aux = [(counts[num], num) for num in nums]
return helper(aux, 0, len(nums) - 1, k)
print(kthMostFrequentNumber([1, 1, 1, 1, 2, 2, 2, 2, 3, 3], 1))
print(kthMostFrequentNumber([1, 2, 3, 2, 1, 2, 2, 2, 3], 2))
print(kthMostFrequentNumber([1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 5, 5], 4))
func findKthFrequentNumber(input: [Int], num: Int) -> Int? {
var dic:[Int:Int] = [:]
var results:[Int] = []
for item in input {
if let count = dic[item] {
dic[item] = count + 1
} else {
dic[item] = 1
}
}
results = dic.map { $0.1 }.sorted().reversed()
let kthResult = results[num-1]
let result = dic.filter { $0.1 == kthResult }.map { $0.0 }.first
return result
}
def find_kth_most_frequent_number(arr,k):
"""
Overall, runtime O(KlogK), where K<N, N-length of arr
"""
# if N is the length of arr
# this is O(N)
dict_num = {}
for num in arr:
if num in dict_num:
dict_num[num] += 1
else:
dict_num[num] = 1
#reverse dict
reverse_dict = {}
frequencies = []
for key, val in dict_num.items():
reverse_dict[val] = key
frequencies.append(val)
# sort the frequecies
frequencies = sorted(frequencies) # this is O(K.logK) where K length of unique numbers and K < N
print("kth most frequent number: ", reverse_dict[frequencies[len(frequencies)-k]])
func findKthHightestNum(_ arr : [Int], _ k : Int) -> Int {
let sortedArr = arr.sorted()
let set = Set(sortedArr)
var items = [[Int]]()
for item in Array(set) {
var numItems = [Int]()
for numArr in sortedArr {
if numArr == item {
numItems.append(numArr)
}
}
items.append(numItems)
}
items = items.sorted(by: { (firstNumArr, secondNumArr) -> Bool in
return firstNumArr.count > secondNumArr.count
})
print(items)
for (index, mainNum) in items.enumerated() {
if index == (k - 1) {
return mainNum.first!
}
}
return -1
}
func findKthHightestNum(_ arr : [Int], _ k : Int) -> Int {
let sortedArr = arr.sorted()
let set = Set(sortedArr)
var items = [[Int]]()
for item in Array(set) {
var numItems = [Int]()
for numArr in sortedArr {
if numArr == item {
numItems.append(numArr)
}
}
items.append(numItems)
}
items = items.sorted(by: { (firstNumArr, secondNumArr) -> Bool in
return firstNumArr.count > secondNumArr.count
})
print(items)
for (index, mainNum) in items.enumerated() {
if index == (k - 1) {
return mainNum.first!
}
}
return -1
}
func findKthHightestNum(_ arr : [Int], _ k : Int) -> Int {
let sortedArr = arr.sorted()
let set = Set(sortedArr)
var items = [[Int]]()
for item in Array(set) {
var numItems = [Int]()
for numArr in sortedArr {
if numArr == item {
numItems.append(numArr)
}
}
items.append(numItems)
}
items = items.sorted(by: { (firstNumArr, secondNumArr) -> Bool in
return firstNumArr.count > secondNumArr.count
})
print(items)
for (index, mainNum) in items.enumerated() {
if index == (k - 1) {
return mainNum.first!
}
}
return -1
}
The answer would be a combination of using a hash and min_heap.
First we count how many times each items is repeated in array and store them in hash. Then, based on the frequency of each item generate a min_heap.
However, to make it easier to return the result, we can store a pair value in heap <freq,actual#>.
For example for the given input {1,2,3,2,1,2,1,2,3}, we store the following pairs in min_heap structure:
<2,3>, <3,1>, <4,2>
Then while making the min_heap we make sure to delete the root of tree if the size of heap reaches the value of queue.
In this case we only keep track of k most frequent values in array in min_heap, while the root of tree is the answer.
Here is C++ code implementation using STL:
int findKthMostFrequent(vector<int>& nums, int k) {
map <int,int> hash;
priority_queue < pair< int, int > , vector< pair< int, int> >, greater< pair< int, int> > > min_heap;
for (auto i: nums) {
hash[i]++;
}
for (auto it : hash) {
min_heap.push(make_pair(it.second, it.first) );
if (min_heap.size()>k)
min_heap.pop();
}
return min_heap.top().second;
}
This Code will Work absolutely fine and can work for both if it is a string or if the numbers are given in a list
test_str = "1309384872597128"
# using dict.get() to get count
# of each element in string
res = {}
for keys in test_str:
res[keys] = res.get(keys, 0) + 1
l = []
for i in sorted (res.keys()) :
l.append(res[i])
l.sort(reverse=True)
# print(l)
k = 3
p = []
for i in range(len(l)):
if i == 0 :
p.append(l[i])
c = l[i]
elif l[i] != c :
p.append(l[i])
c = l[i]
# print(p)
for i in range(len(p)):
if i == k-1:
x = p[i]
# print(x)
for i in sorted (res.keys()) :
if res[i] == x:
print(i)
break
# printing result
# print(type(res))
print ("Count of all characters in GeeksforGeeks is : \n" )
# print(res)
I'll give you a hint. You can use hash tables for this.
Simply iterate over the array and store the element and the number of occurrence in that array.
Now return the element which has the highest number of occurrences in your hash table. This should be O(n) solution.
Please correct me if I've made any mistakes.
"element which has the highest number of occurrences in your hash table". that will give you the first one. not the Kth one.
- pascal January 11, 2018