Uber Interview Question for Software Engineers


Team: Marketplace
Country: United States




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

"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 | Flag Reply
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]))

- vitoralbano January 14, 2018 | Flag Reply
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<>());
            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)
    }

- Anonymous February 05, 2018 | Flag Reply
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);
            result.add(value);
            count++;
        }
        return result;
    }

- Adarsh February 21, 2018 | Flag Reply
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))

- closingtime March 08, 2018 | Flag Reply
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
    
}

- Jer May 25, 2018 | Flag Reply
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]])

- village_warrior July 11, 2018 | Flag Reply
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]

- suz July 11, 2018 | Flag Reply
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
}

- Anonymous July 22, 2018 | Flag Reply
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
}

- Henly July 22, 2018 | Flag Reply
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

}

- Henly July 22, 2018 | Flag Reply
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;
    }

- ashkanxy November 11, 2018 | Flag Reply
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

- prabhat.diwaker January 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Aditya Kumar Sharma May 13, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 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.

- utkarsh.bhatt12 January 04, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More