display | more...
This is a solution to problem 31 on the hard interview questions node. If you have not read the question, the following will make no sense to you:

Starting at the beginning of the array, test consecutive pairs for equality. If, for example, a(j) == a(j+1), continue by testing a(j+1) == a(j+2), etc. As soon as a(j) != a(j+1), remove those two elements from the array (suppose it’s a linked list) and continue by testing a(j-1) == a(j) (which used to be a(j+2)). Note that removing the two elements maintains the invariant that more than half of the elements have the same value. Once j is greater than half of the length of the remaining list, the element aj is the element we’re looking for, since a(0) == a(1) == ... == a(j). This runs in O(n) since no element appears on the right hand side of an equality test more than once.

This problem is similar to problem 30 on the hard interview questions node, and so is the solution.

Assuming it's a linked list seems like a bit of a cheat to do it in linear time. Pairing off mismatched elements to preserve the invariant is the right approach, but we only need to keep track of one "candidate value", and how many times we've seen it.

So, initialize the count to zero. Now, consider each array element in turn. If your count is zero, set it to one and set the candidate value to that of the current element. Otherwise, compare the current element's value to the candidate value. If they match, increment the count, and if they don't, decrement it. You'll be left with a non-zero count and the candidate value will be the one that appeared more than n/2 times.

Log in or register to write something here or to contact authors.