NVIDIA Interview Question Software Engineer / Developers
if we are known the range in which numbers in a given array exists. then we can simply make the bucket for each no .. initially making the bucket value of each no is -1 taking a var Max_repetition =0 and we will traverse the whole array if any number is encounter corresponding number bucket is incremented . and each time of updation of bucket we will check the updated value to the max_repetition value and update accordingly
if range is not known . then we can sort d array in nlogn time and find max repetition.
if any bdy knows more optimal solution please add to it
if we sort the list, didn't we destroy the list?
if we really really care about space, we can only keep a number and counter, go throught the list N times, find the max occurrence.
Max Count is required.
I would compare : Max Heap and HashTable
Max Heap : Search for Max element O(1), insertion log(n) , space will total unique elements
HashTable: Search will be O(n) in worst case, insertion O(1) and space will be total unique elements.
BST: you can use bst everything will be O(log N) and spac will be total unique element.s
//Find the majority element in O(n) by maintaining two pointers in array.
findCandidate(a[], size)
1. Initialize index and count of majority element
maj_index = 0, count = 1
2. Loop for i = 1 to size – 1
(a)If a[maj_index] == a[i]
count++
(b)Else
count--;
(c)If count == 0
maj_index = i;
count = 1
3. Return a[maj_index]
Find the maximum repeating number in O(n) time and O(1) extra space
- Anonymous August 13, 2017Given an array of size n, the array contains numbers in range from 0 to k-1 where k is a positive integer and k <= n. Find the maximum repeating number in this array. For example, let k be 10 the given array be arr[] = {1, 2, 2, 2, 0, 2, 0, 2, 3, 8, 0, 9, 2, 3}, the maximum repeating number would be 2. Expected time complexity is O(n) and extra space allowed is O(1). Modifications to array are allowed.
Recommended: Please solve it on “PRACTICE ” first, before moving on to the solution.
The naive approach is to run two loops, the outer loop picks an element one by one, the inner loop counts number of occurrences of the picked element. Finally return the element with maximum count. Time complexity of this approach is O(n^2).
A better approach is to create a count array of size k and initialize all elements of count[] as 0. Iterate through all elements of input array, and for every element arr[i], increment count[arr[i]]. Finally, iterate through count[] and return the index with maximum value. This approach takes O(n) time, but requires O(k) space.
Following is the O(n) time and O(1) extra space approach. Let us understand the approach with a simple example where arr[] = {2, 3, 3, 5, 3, 4, 1, 7}, k = 8, n = 8 (number of elements in arr[]).
1) Iterate though input array arr[], for every element arr[i], increment arr[arr[i]%k] by k (arr[] becomes {2, 11, 11, 29, 11, 12, 1, 15 })
2) Find the maximum value in the modified array (maximum value is 29). Index of the maximum value is the maximum repeating element (index of 29 is 3).
3) If we want to get the original array back, we can iterate through the array one more time and do arr[i] = arr[i] % k where i varies from 0 to n-1.
How does the above algorithm work? Since we use arr[i]%k as index and add value k at the index arr[i]%k, the index which is equal to maximum repeating element will have the maximum value in the end. Note that k is added maximum number of times at the index equal to maximum repeating element and all array elements are smaller than k.
Following is C++ implementation of the above algorithm.