Thursday, November 1, 2012

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.

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.
  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.



Wednesday, October 24, 2012

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)

Tuesday, October 23, 2012

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