Uber Interview Data Structures and Algorithm

Round 1

Questions: You are given an array with numbers, each round, half of the elements are deleted, the lower number stays, the higher number goes. Comparison is only among consecutive elements.

Example 1: 1,2,3,4,5,6,7,8
Round 1: 1,2,3,4,5,6,7,8
Round 2: 1,3,5,7
Round 3: 1,5
Round 4: 1
1 is winner

Example 2:
1,2,3,4,5,6,7
1,3,5,7
1,5
1
1 is winner

Note: if number is odd, last element just moves to the next round.
Print these rounds.

Round 2

Questions: Now you have this algorithm. Generate the configuration of the original array such that lower elements are eliminated later.

Example 1:
Given, n = 7
generated answer:
1,7,3,5,2,6,4

Example 2:
n = 8
1,7,3,5,2,6,4,8

Example 3:
n = 9
1,9,5,8,3,7,4,6,2