Alex Rivera | Logout

An interesting Google interview algorithm I found online that requires linear time

Asked 2011-12-02T20:15:09.167
9

So I found this Google interview algorithm question online. It's really interesting and I still have not come up with a good solution yet. Please have a look, and give me a hint/solution, it would be great if you can write the code in Java :).

"Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time. (n >=0 ) You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo"

java algorithm frequency
Edit
Report

1 Answer

7

Hint: Look at Boyer and Moore's Linear Time Voting Algorithm

Better Hint: Think about solving the majority problem first. That is, try to find an element that occurs at least n/2 times. The basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist until the end if it is a majority element.

findCandidate(a[], size)
    //Initialize index and count of majority element
    maj_index = 0;
    count = 1;

    for i = 1 to n–1 {
      if a[maj_index] == a[i]
          count++;
      else
          count--;

      if count == 0 {
          maj_index = i;
          count = 1;
      }
    }
    return a[maj_index]

This algorithm loops through each element and maintains a count of a[maj_index]. If the next element is same then increments the count, if next element is not same then decrements the count, and if the count reaches 0 then changes the maj_index to the current element and sets count to 1.

Next you need to check that this element indeed occurs at least n/2 times, but that can be done in one pass.

answered 2011-12-02T20:22:53.567

Your Answer