The votes are in, and it’s time (for you) to count them! Unfortunately, someone’s stolen the memory from your computer, and the deadline is approaching.
The votes are given as a mutable array of length n containing integer entries.
a. Suppose that some integer appears at least n/2 + 1 times in the array (some candidate received a majority of the vote). Can you find an algorithm which takes the array as input, runs in O(n) time and no additional space (you’re allowed comparisons and if-statements, etc. but no new variables), and outputs the frequently appearing entry?
b. There are at most 5 different entries in the array, but none of them is guaranteed a majority. (Someone could win with only 21% of the vote!) Can you find a randomized algorithm which takes the array, runs in O(n) expected time and no additional space and outputs the frequently appearing entry?
Did you love challenges? Then you will love LiveRamp. Apply now to join our team.