Output Contest Matches

Output Contest Matches

What is this problem about?

The Output Contest Matches problem gives you n teams (a power of 2). In the first round, teams are paired as (1, n), (2, n-1), etc. Winners play in the next round the same way. Generate the bracket string showing all matchups. This coding problem uses recursive simulation. The recursion, string, and simulation interview pattern is the core.

Why is this asked in interviews?

Google asks this to test recursive bracket construction and string formatting. The structure is naturally recursive: build n/2 pairs in each round, then recurse on the winners. Clean recursive string building demonstrates solid recursive thinking.

Algorithmic pattern used

Recursive halving. Start with teams array [1, 2, ..., n]. Each round: pair teams[i] with teams[n-1-i] for i=0..n/2-1, forming "(team_i,team_{n-1-i})". Recurse on the n/2 pair strings. Repeat until 1 team remains.

Example explanation

n=4. Teams=[1,2,3,4]. Round 1: pairs → ["(1,4)","(2,3)"]. 2 pairs remain. Round 2: pair "(1,4)" with "(2,3)" → "((1,4),(2,3))".

n=8. Teams=[1,...,8]. Round 1: 4 pairs ["(1,8)","(2,7)","(3,6)","(4,5)"]. Round 2: [("(1,8)","(4,5)"), ("(2,7)","(3,6)")]. Round 3: Final: "((((1,8),(4,5)),((2,7),(3,6))))".

Common mistakes candidates make

• Using iteration instead of recursion (harder to implement cleanly).
• Wrong pairing order (first teams[0] with teams[n-1], not teams[0] with teams[1]).
• Not wrapping pairs in parentheses at each round.
• Off-by-one in halving (n must be a power of 2).

Interview preparation tip

Recursive bracket problems follow a "pair and recurse" structure. Each call processes the current level by forming pairs, then recurses on the results. The base case is a single-element array. Practice similar tournament bracket generation and recursive string building — they test clean recursive design and string concatenation.