How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Simulate and Construct Tournament Rankings

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given a single-elimination tournament represented by an array of ranks. The array is a permutation of the integers `1..n`, where a smaller number means a stronger player. In each round: - Players are paired by adjacent indices: `(0, 1)`, `(2, 3)`, `(4, 5)`, and so on. - The player with the smaller rank number wins the pair and advances. - If the number of players in a round is odd, the last unpaired player advances automatically. - The process repeats until only one player remains. Solve both parts: 1. **Simulation**: Given an initial ranking array, output the list of remaining ranks after each round. Example: ```text input = [1, 2, 3, 4, 5, 6, 7, 8] round 1 -> [1, 3, 5, 7] round 2 -> [1, 5] round 3 -> [1] ``` 2. **Construction**: Given `n`, construct an initial permutation of `1..n` such that stronger players are eliminated strictly later than weaker players. In other words, for any two ranks `a < b`, rank `a` must be eliminated in a later round than rank `b`, or rank `a` must be the champion. The solution must work for any positive integer `n`, not only when `n` is a power of two. Example for `n = 8`: ```text initial = [1, 8, 4, 7, 2, 6, 3, 5] round 1 -> [1, 4, 2, 3] round 2 -> [1, 2] round 3 -> [1] ``` Here, ranks `5, 6, 7, 8` are eliminated in round 1, ranks `3, 4` are eliminated in round 2, rank `2` is eliminated in round 3, and rank `1` wins the tournament.

Quick Answer: This question evaluates understanding of tournament simulation and constructive permutation design, testing skills in array manipulation, sequential pairwise elimination reasoning, and combinatorial ordering of eliminations.

Part 1: Simulate Tournament Rounds

You are given a single-elimination tournament as a list ranks, where ranks is a permutation of 1..n and a smaller number means a stronger player. In each round, players are paired by adjacent indices: (0, 1), (2, 3), and so on. The smaller rank in each pair wins and advances. If a round has an odd number of players, the last unpaired player advances automatically. Return the list of remaining ranks after each round until only one player is left. Do not include the initial arrangement in the output.

Constraints

1 <= len(ranks) <= 2 * 10^5
ranks is a permutation of 1..len(ranks)
The total number of values across all returned rounds is O(n)

Examples

Input: [1, 2, 3, 4, 5, 6, 7, 8]

Expected Output: [[1, 3, 5, 7], [1, 5], [1]]

Explanation: Each adjacent pair keeps the smaller rank. Repeating that process produces the three rounds shown.

Input: [5, 1, 4, 2, 3]

Expected Output: [[1, 2, 3], [1, 3], [1]]

Explanation: Round 1 winners are 1 and 2, and rank 3 gets a bye. In round 2, rank 1 beats rank 2 and rank 3 gets another bye.

Input: [3, 2]

Expected Output: [[2]]

Explanation: There is only one match, and the smaller rank wins.

Input: [1]

Expected Output: []

Explanation: With only one player, no rounds are played.

Hints

Build the next round by scanning the current round two players at a time.
If there is no partner for the last player in a round, copy that player directly into the next round.

Part 2: Construct Tournament Rankings with Monotonic Survival

You are given a positive integer n. Construct an initial ranking array, a permutation of 1..n, for the same tournament rules: adjacent players are paired each round, the smaller rank advances, and the last player gets a bye if the count is odd. Your goal is to make stronger players never be eliminated earlier than weaker players. Formally, if a < b, then player a must survive at least as many rounds as player b; rank 1 may be the champion. If multiple valid answers exist, return any one of them. The sample outputs below show the deterministic permutation returned by the reference solution.

Constraints

1 <= n <= 2 * 10^5
The returned list must be a permutation of 1..n
For any ranks a < b, player a must survive at least as many rounds as player b

Examples

Input: 1

Expected Output: [1]

Explanation: Only one player exists, so the permutation is forced.

Input: 2

Expected Output: [1, 2]

Explanation: Rank 1 defeats rank 2 in the only match.

Input: 5

Expected Output: [1, 5, 3, 4, 2]

Explanation: Round 1 survivors are [1, 3, 2], then [1, 2], then [1]. Stronger ranks never leave earlier than weaker ones.

Input: 7

Expected Output: [1, 7, 4, 6, 2, 5, 3]

Explanation: Round 1 survivors are [1, 4, 2, 3], then [1, 2], then [1].

Input: 8

Expected Output: [1, 8, 4, 7, 2, 6, 3, 5]

Explanation: Ranks 5 through 8 fall in round 1, ranks 3 and 4 fall in round 2, rank 2 falls in round 3, and rank 1 is champion.

Hints

After the first round, exactly ceil(n / 2) players remain. If stronger players can never leave earlier than weaker ones, which ranks should those survivors be?
Once you choose the first-round survivors, the same construction problem appears again on a smaller tournament.

Quick Overview

This question evaluates understanding of tournament simulation and constructive permutation design, testing skills in array manipulation, sequential pairwise elimination reasoning, and combinatorial ordering of eliminations.