CODEWITHSUNDEEP
algorithm
user1071840
user1071840

Reputation: 3592

Find winner in list of tournament matches

I checked for duplicate questions on stackoverflow. This could be close : find number of tennis matches required

This is an Amazon interview question. I want to know if Θ(log p) operations on critical path is the right answer to this (On the same lines as tournament barrier algorithm -> John Mellor-Crummey), for 'p' players.

Say for example, we have 4 players 1, 2, 3, 4. We can schedule matches between:

 1)  Between (1 & 2)

 2)  Between (3 & 4) 

 3) organize the third match between winners of these two matches.

Similarly for 5 (odd number of) players we could schedule matches between: 

 1) (1 & 2) and (3 & 4) 

 2) Winner from (1&2) OR winner from (3&4) against 5

 3) Winner between winner of not chosen group and winner from previous match

.

Upvotes: 0

Views: 712

Answers (1)

Pieter Geerkens
Pieter Geerkens

Reputation: 11893

Every match eliminates exactly one player. To reduce from p players to 1 player requries p-1 matches..

If you are scheduling a maximal number of matches concurrently, with the constraint that a player can participate in only one match at a time, and want to know haw many rounds are required, that is ceiling(log p).

Upvotes: 4

Related Questions