## Uber Interview Question for Software Engineers

• 0

Team: Marketplace
Country: United States

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

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.

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

"element which has the highest number of occurrences in your hash table". that will give you the first one. not the Kth one.

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

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]))``````

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

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<>());

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)
}``````

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

``````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);
count++;
}
return result;
}``````

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

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))``````

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

``````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

}``````

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

``````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]])``````

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

``````def count_inputs(input):
input_count = {}
for i in input:
input_count[i] = input_count.get(i, 0) + 1
return input_count

def find_kth_most_frequent(input, k):
input_count = count_inputs(input)
s = sorted(input_count, key=lambda (item): input_count[item], reverse=True)
return s[k-1]``````

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

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
}

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

``````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
}``````

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

``````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``````

}

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

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;
}``````

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

``````arr = [1, 2, 3, 2, 1, 2, 2, 2, 3]
k = 2

uniq = set(arr)

res ={i:0 for  i in uniq}

for i in uniq:
count = 0
for j in arr:
if i == j:
count = count + 1
res[i]=count

for i,j in res.items():
if j == k:
print i``````

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.