Friday, September 13, 2013

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

             Input: 1,2,3,4,5,6,7,8,9
                          Rotate it by 3 position

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

  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

  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.

Complexity: n
Space Complexity: 0

Thursday, January 31, 2013

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.

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.

Thursday, November 1, 2012

Puzzle 4: Find the duplicate one out.


NOTE: The elements can be entered in random ordered.


Solution: Let's take an example to solve the problem:
Array values: { 2,3,6,8,2,1,9,7,5,4}
The generalize formula for p1 and p2 will be:



Output: p2 is the faulty node.

Wednesday, October 31, 2012

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.
Find the loop in linked list:
Now let's consider we found the loop:
The above algo will work as following iteration:


Delete the loop in the linked list:

           c) Node visited before p2 is the faulty node.

Wednesday, October 24, 2012

Problem 2: Student Counting Problem


Solution: Perform the following steps:

  1. Ask the class to stand up and make pairs.

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

Tuesday, October 23, 2012

Probblem 1: Count Sort Problem


time = O(n) ; 
space = n + 4