Tags: , | Posted by Admin on 2/21/2012 11:10 AM | Comments (0)

 

You have 1 to N-1 array and 1 to N numbers, and one number is missing, you need to find the missing the number. Now you have 1 to N-2 numbers, and two numbers missing. Find them.

Solution:
The question can be elucidated as follows.Given an array of size N-1 containing numbers less than N and with out any duplicates!! We knew that there is a number missing from the array say K .Let S be the sum of the elements of the array.

Sum of first N natural numbers=N*(N+1)/2

and S=N*(N+1)/2 – K.Now putting this other way around we get K=N*(N+1)/2 -S !!

Now the second part of the question says that there are 2 of the first N numbers missing.Let they be X and Y.

We solve this problem by solving 2 essential equations.

They are X+Y=N*(N+1)/2 -S               (1)

X*Y=N!/P             (2) where S and P are the cumulative sum and product of the array entries.

You have cycle in linked list. Find it. Prove that time complexity is linear. Also find the node at which looping takes place.

Solution:
The problem of checking whether there is a cycle or not can be solved using 2 pointers one moving in increments of 1 and the other in increments of 2.If there is a cycle then these 2 pointers meet at some node say N1 inside the cycle otherwise the fast pointer reaches the end of the list.This is a O(N) solution.

Now coming to the identification of the node at which looping took place.After our identification of cycle ,both the pointers P1 and P2 are at node N1.Now iterate the slow pointer to count the no of nodes in the cycle.(After traversing the whole cycle P1 and P2 shall again be at the same node).Let this size be K.Now take one of the pointers to the head node and count the no of nodes till N1.Let this number be X.Now use one of these pointers to reverse the cycle starting from N1.Only the cycle gets reversed.Now again traverse from head node to N1.Let the number of nodes this time be Y.Let the no of nodes from head to the start node of the cycle be Z

Now X+Y=2*Z+K .Hence solve for K and then having figured out the start node N2 of the cycle.Now as the cycle is reversed having figured out this start node its next node is the looping nodes so set the looping nodes next pointer to NULL and reverse the list further till you reach N2.
Questions on my project please be prepare well about your project
How do you search for a word in a large database.
How do you build address bar in say gmail. i.e. if you press ‘r’ then you get all email starting from ‘r’, and if you press ‘ra’ then you will get emails starting from ‘ra’.

 

Add comment




  Country flag
biuquote
  • Comment
  • Preview
Loading