1

The question is long, so I will paraphrase it briefly

Q: There are n people voting to choose the chair of the committee. Each person can vote for one person that has unique id (it is positive integer and vote will be stored in array). Chair will be the one with the most vote. Design algorithm to determine who is the chair and what would be the time complexity? Then if there are m < n candidates for the chair and we know value of m, what would be the algorithm to determine who is the chair and its time complexity?

(Edit: okay so no boyer-moore algorithm)

For the second part, I'm not sure why the fact that I know the value of m makes a difference. The last part of the question sounds like there are more efficient way of solving the problem when m is known.

4
  • 2
    Either I don't understand what you are asking at all, or you are way overthinking this. Oct 20 '16 at 3:40
  • @WinstonEwert I rechecked the question and the information I need is all in there. Which part do you not understand? It is a problem designed to be challenging.
    – johnkiko
    Oct 20 '16 at 3:46
  • Counting votes and determining the winner is amongst the most trivial of trivial algorithms. Are you really just figuring out which candidate has the most votes? Why in the world would you even be thinking about Boyer-More? The problem you describe is really really easy, but you are discussing more advanced algorithms, which leaves me utterly unclear about what you are trying to do. Oct 20 '16 at 4:19
  • 1
    I have no idea what this has to do with Boyer-Moore. Boyer-Moore is a string matching algorithm, there is neither a string nor matching here. There is also no sorting involved, so why is this question tagged with sorting? Oct 20 '16 at 8:46
2

There is a trivial solution to the problem as you ask it: create an array of counters for the candidates, and for each vote increment that candidate's counter; at the end of the voting, scan through the list and find the highest value. O(n) time complexity under the assumption n >> m (which would be a prerequisite for making a voting system like this realistically feasible), or O(n + m) if you can't assume m is small. O(m) storage.

If your candidates ids are not sequentially allocated, the solution is a little harder, but you can simply use a hashtable to map the ids to their indices in the array. This doesn't affect complexity as hashtables have O(1) [typical] lookup.

The only reason you would realistically want anything other than this implementation is if you expect 'm' to be large, but that would be a very unusual situation.

2
  • 1
    Since m < n as per the question, The worst case for O(n+m) is O(2n), but of course constants don't matter so it's still O(n). Or in the general case when there's no known relation between n and m: O(max(n, m)).
    – amon
    Oct 20 '16 at 9:23
  • True. Missed the note that m<n in the question. Oct 20 '16 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.