Yahoo Interview Question
Software Engineer / DevelopersWhen the number of teams is not a square of 2, then we need to have byes for some teams. (this is how tournament brackets are constructed).
A binary tree needs to be built and then the number of non-leaf nodes needs to calculated - that will be the number of matches.
Find x where x is the nearest power of 2 less than n.
n-x teams are extra, choose another (n-x) teams from the pool. Remaining teams = n - 2(n-x) = 2x - n. So, 2(n-x) teams will play in the first round while the remaining get a bye. After round 1, we will get 2*(n-x)/2 + (2x-n) = x number of teams. Since x is a perfect square of 2, we can build the binary tree from up there.
The goal is to get to a square of 2 number of teams after round 1.
Number of matches: (n-x) in the first round + (ln(x) + 1)
(Number of non-leaf nodes in a full binary tree is ln(x) + 1 where x is the number of leaves)
Given this, if n = 9, x = 8. So, number of matches = (9-8) + (ln 8 + 1) = 1 + (3 + 1) = 5.
Oops, messed up the number of non-leaf nodes formula, sorry.
Number of non-leaf nodes in a perfect binary tree = 2*(Number of leaf nodes) - 1 - (Number of leaf Nodes)
So, here, the answer is (9 - 8) + (2*8) - 1 - 8 = 8.
For n matches the number of tournaments needs to play is n-1
- Anonymous September 20, 2012Ex:
teams-tournaments
2-1
3-2
4-3
5-4
6-5
7-6