Four Dots..

Question :

How do you arrange four dots such that they are equidistant from each other. The distance between any two dots should be same..


Answer :

Think 3 dimensional...

Arrange the four dots so that they form a pyramid..




...





..

Array of numbers... One for the common sense !!

Question : Let A be an array of integers of size 100. This array consists of numbers 0-99 randomly distributed over it. Write an algorithm / Propose a method to sort the array ?

...
...





...
...

Answer : Since the numbers are from 0-99, Simply go through the array and replace the first element with 0, the second with 1, ..so on.. replace the last one with 99..

It just requires some common sense.. and the question can be twisted .. instead of array we could have the linked list.. instead of 0-99 we could have numbers 1,4,9,16....so on..

Prob of 100th person sitting in 100th seat ....

Question :

A line of 100 airline passengers is waiting to board a plane. they each hold a ticket to one of the 100 seats on that flight. (for convenience, let's say that the nth passenger in line has a ticket for the seat number n.)

Unfortunately, the first person in line is crazy, and will ignore the seat number on their ticket, picking a random seat to occupy. all of the other passengers are quite normal, and will go to their proper seat unless it is already occupied. if it is occupied, they will then find a free seat to sit in, at random.
What is the probability that the last (100th) person to board the plane will sit in their proper seat (#100)?

Solution :

There are two ways of solving the problem..

Method 1 :

The prob of 100th person to sit in 100th seat = 1 - ( the prob of one of 1-99 sitting in the 100th desk)

= 1 - ( prob of 1st person sitting in 100th desk + prob of 2nd person sitting in 100th desk + … + prob of 99th person sitting in 100th desk)

= 1 - [ (1/100) + ( (1/100) * (1/99) ) + ( 1/100 + (1/100 + (1/100 * 1/99) ) * (1/98) + ….. ]

= 1 - [ This turns out to be 1/2 ]

= 1 - [1/2] = 1/2 .

Note for method 1 :

The prob of 1st person sitting in 100th desk = 1/100 ( Since he is crazy he can pick up any seat at random )

The prob of 2nd person sitting in 100th desk = combined prob of 1st person sitting in 2nd seat and 2nd person sitting @ 100th seat = (1/100 * 1/99)

The prob of 3rd person sitting in 100th desk = combined prob of 1st / 2nd person sitting in seat 3 and 3rd person sitting @ 100th seat = ( 1/100 + (1/100 + (1/100 * 1/99) ) ) * 1/98 …


Method 2 :


A much more elegant way of solving the same problem…

The question is for 100 passengers.

If there is only one passenger.

P(1) = 1

If there are 2 passengers

P(2) = Pass1 gets seat 1 = 1/2

If there are 3 passengers

P(3) = Pass1 gets seat 1 + (Pass1 gets seat 2 and P(2))

= 1/3 + 1/3 (P(2)) = 1/3 (1 +P(2)) = 1/2 (1 + 1/2) = 1/2

(after pass1 gets seat 2, pass2 only have 2 seats left where 1 now becomes his right seat, so it is a P(2) problem).


If there are 4 passengers

P(4) = Pass1 gets seat 1 + (Pass1 gets seat 2 and P(3)) + (Pass1 gets seat 3 and P(2))

= 1/4 + 1/4 (P(3)) + 1/4 (P(2)) = 1/4 (1 + P(2) + P(3)) = 1/4 (2) = 1/2


(after pass1 gets seat 2, pass2 has only 3 seats left where 1 now becomes his right seat, so it is a P(3) problem).

after pass1 gets seat 3, pass2 will take seat2. pass3 has only 2 seats left where 1 now becomes his right seat, so it is a P(2) problem).


It can deduced that if there are n passengers,

P(n) = 1/n (1 + P(2) + P(3) + ...P(n-1))

= 1/n (1 + 1/2 + ...+1/2) = 1/n ( 1+ (n-2)/2) = 1/n (n/2) = 1/2



So, I also think it is 1/2

The number puzzle

In the above diagram.. arrange the numbers 1..8 in the boxes such that, no two adjacent numbers (like 2 & 3 ) are horizontally/vertically/diagonally adjacent to each other.



Solution :




Explanation :

1 & 8 are the number with least neighbors.. ( i.e. just one ) Put them in the center two boxes, and arrange the other numbers around them..

Linked lists - Common element

Question : Find if two linked lists contain a common suffix given their start pointers and lengths, identify the first common element.

Answer :

1. Traverse through the first linkedlist ( LL 1 ) to find it's length. Let's say it is m. Keep track of it's last pointer. (the one before null).

2. Traverse through the second linkedlist ( LL 2 ) to find it's length. Let's say it is n. If the last pointer here is same as the one in step 1, then both linkedlists are intersecting. And go to step 3

3. Now compare m and n. Let's say m > n. Then the first point where the intersection "is possible" is at position m-n. Simply traverse through the first linkedlist till m-n positions. As you continue to traverse LL1 from this position, start traversal of LL2 and compare the pointers @ each position. Wherever the pointers equate that is where the two lists intersect.

Complexity : In the worst case it requires traversing through the two linkedlists twice. O(4n) ~ O(n). So it is O(n) algorithm.