Puzzle 6: Rotate the array with the given number of intervals.

Puzzle 6: Rotate the array with the given number of intervals.
Example: 

             Input: 1,2,3,4,5,6,7,8,9

                          Rotate it by 3 position

             Output: 4,5,6,7,8,9,1,2,3

Solution:

There can be number of approaches to do this, I will try to explain some any new approach will be really appreciable.

Approach 1

Brute force method

Method: Rotate each element by one position for k - times, where k is the interval by which array need to be rotated.
Example: Input -> 1,2,3,4,5,6,7,8,9
k = 3
Run a loop to rotate each element by one place
Iteration 1, Array becomes:                                       2,3,4,5,6,7,8,9,1
Iteration 2, Array becomes:                                       3,4,5,6,7,8,9,1,2
Iteration 3, Array becomes:                                       4,5,6,7,8,9,1,2,3
Complexity: nk
where 'n' is the number of elements 'k' is the interval by which array need to be rotated.
Space Complexity: 0

Approach 2

Using extra memory

Method: 

1. Take an extra memory buffer which size is equal to 'k'
2. Copy the elements from '0' to 'k-1' to the temporary memory buffer.
3. Start moving the elements as 'k' to '0' , 'k + 1' to '1' and so on.
4. Copy the temporary buffer data from 'n-k' position in the actual data array.

Explanation: Input -> 1,2,3,4,5,6,7,8,9
k = 3
Allocate a temporary buffer of size k = 3;
Copy data from the input array to temporary buffer upto 'k' position.
Array becomes:                               -, - , - ,4,5,6,7,8,9
Start moving the data by 'k' position, array becomes:
Array becomes:                               4,5,6,7,8,9, - , - , -
Copy the data from the temporary buffer to the actual data.
Array becomes:                               4,5,6,7,8,9,1,2,3
Complexity: n
Space Complexity: k
where k is the interval size.

Approach 3

Better Approach, without extra space

Method: 

1. Divide the array in two subset of size 'k' and 'n-k'.
2. Rotate each subset which will take n time.
3. Rotate the whole data again and you will get the desired output.

Explanation: Input -> 1,2,3,4,5,6,7,8,9
k = 3

Divide the data in two subset as follows:
{1,2,3}  , {4,5,6,7,8,9}

Rotate each subset individually, the output will be
{3,2,1}  , {9,8,7,6,5,4}

Rotate the whole data data at once now.
4,5,6,7,8,9,1,2,3

Complexity: n
Space Complexity: 0

Puzzle 5: Find the 5th largest element in Balanced tree

Puzzle 5: You are given with a balanced tree. Find the 5th largest element in optimal way.

Solution:

Here we will use modified In-Order travesal.

In normal in-order traversal we visit the Left -> Root -> Right and it will produce the sorted list.

So, in order to get the descending list we can reverese the In-Order traversal i.e. visit the Right -> Root- > Left.

Now keep a counter, which counts number of root visited, as soon as counter reachs 5 we will be on the node which is 5th largest.

Here is the example for the same.

Explanation: Here the visited flow will be Right -> Root- > Left.

                                  

So 50 will be the answer.