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.

Puzzle 4: Find the duplicate one out.

Puzzle 4: Suppose there are elements from 1,2,3......n-1 which is to be inserted in an array of size n in such a way that every element is inserted atleast once.
Now as per the Pigeonhole Principle definitely there must be one element which occur twice in the array.
Aim is to find the element and the index which is entered twice in complexity of O(n) and memory utilization can be O(log n)

NOTE: The elements can be entered in random ordered.

Hint: This puzzle will use the same approach which is being used in the previous puzzle 3


Solution: Let's take an example to solve the problem:
Array values: { 2,3,6,8,2,1,9,7,5,4}
Here also we will take 2 pointers one start from index 0 to n-1
And other will jump based on the current value at any index.
The generalize formula for p1 and p2 will be:
p1 = i where i ranges from i = 1 to n-1
p2 = Array[0] -> p2 = Array[Array[0]] and so on.

By doing so, once the value of p1 and p2 become equal then we found the faulty value with index.

Refer the following table to see how values of p1 and p2 varies for each iteration.

Output: p2 is the faulty node.
Note: If p1 reaches at end without exit condition then there is no duplicity at all. Which can't be case.

Problem 3: Detect a loop and delete in Linked List

Problem 3: Detect a loop and delete in Linked List.

Solution: There will be two task to solve the issue.

1. To check whether there is any loop in the linked list, if not then there is nothing to do.
2. If loop is found in Step 1 then we have to remove that.

Find the loop in linked list:

1. Take two pointers p1 and p2, where p1 -> head of the list and p2 -> next element after head.
2. Increment p1 by one every iteration and p2 by two.
3. And after each iteration check whether they are pointing to same memory if so then there is a loop.
4. In case there is no loop then p1 will reach at end and there is nothing to solve.

Now let's consider we found the loop:

The above algo will work as following iteration:

So now p1 and p2 is pointing to D and we found a loop.

By doing this we are sure that D is definitely part of the loop elements.

Delete the loop in the linked list:

     1. Find the number of elements which are part of the loop, in the above case count will be 4 as follows:

           a) Keep p1 at D only and reset p2 to head.

           b) Increment p2 by one till it reaches to p1 (i.e. D)

           c) Number of increment done will be the count of elements in the loop

     2. Now we know that there is a loop in the list and the number of elements present in the loop. The faulty node( where the loop exists i.e. F) can be founded by following steps:

           a) Keep p1 at head and p2 at head + count.

           b) Increment both p1 and p2 at same pace, the moment when p2 equal to p1 stop there.

           c) Node visited before p2 is the faulty node.

Problem 2: Student Counting Problem

Problem 2: How will you count the number of students in a classroom in quickest possible manner.

Solution: Perform the following steps:

1. Ask the class to stand up and make pairs.
2. If one student is left out write '1' else write 0.
3. Tell the left out student to sit down and ask one person in each group to sit down.
4. Repeat the process and append '1' or '0' to your number, until no student is left standing. 

You will get the binary representation of the number of students in reverse order.

Example: Lets say there are 23 students in the class
Students standing 23 11 5 2 1 0
Solution 1 1 1 0 1 0

we have a string 111010, and the binary representation of 23 is 010111.

Complexity: This is just using divide and conquer O(lg n)

Probblem 1: Count Sort Problem

Problem 1: Given an array of 100000 elements with numbers 15, 25, 35, 45 repeating. No other numbers are in the array. Sort the array with minimal space n time.

Solution: Find number of 15s, 25s, 35s and 45s in 4 different counters -> a, b, c, d.
Sorted array = [ { a times 15} ; { b times 25 } ; { c times 35 } ; { d times 45 } ]

time = O(n) ; 

space = n + 4