Interview Question
Country: India
Interview Type: Written Test
Hash Table, one iteration over the array.
For each index, we insert the value to the Hash Table, if it exists, we increase the counter (for each value/entry in the Hash Table we save a counter).
A max variable is saved aside and updated once the counter is bigger.
Amortized time O(n)
O(n) space memory
SORRY I had a big mistake here is the correct one...
// solution for max arr value: 0x3ff (1K)
// inputs: arr, size
uint8_t HashTbl[ 0x3ff ] = {0};
most_repeated = 0;
max_val = 0;
for (i=0; i<size; i++ ) {
val = arr[i];
HashTbl[ val ]++;
if (HashTbl[ val ]>max_val) {
max_val = HashTbl[ val ];
most_repeated=val;
}
}
Hash Table, one iteration over the array.
- Anonymous March 08, 2012For each index, we insert the value to the Hash Table, if it exists, we increase the counter (for each value/entry in the Hash Table we save a counter).
A max variable is saved aside and updated once the counter is bigger.
Amortized time O(n)
O(n) space memory