Recursion part -2
- Posted by Nandini
- ON 18 June 2016
Recursion part -2
Warm-up
- Use the elements of a sorted array to create a balanced binary search tree
- Hint: What is the most intuitive location to palce the median element of the array in the tree?
Practice
- Two players take turns to play a game. Each player picks a random number from 1 to 3. The numbers picked by the players are added to a cumilative sum. The first player to cause the cumilative sum to exceed K is the winner. Assuming both players play optimally, find if the first player can win the game for a given K
- Hint: Draw the recursion tree! Can you spot who will be the winner?
- Feel free to read about min-max trees.
- Repeat the two player question, except that the players can pick numbers from 1 to 100. However, once a number is picked by one player, neither of the players can use the same number again.
- Hint: nothing yet!
Challenge (Optional)
Check out our upcoming interview prep bootcamp starting September 23/24 weekend