Even across rows and columns..

In the above arrangement, how can you remove 6 balls such that in the resulting arrangement, every row and every column has even number of balls.


Solution

.
.
.
.
.



.
.
.

N linkedlists of K elements each....

Question :

Let us say there are N linked lists of K elements each. Each of the linked lists are sorted. Then give an algorithm to merge N linked lists to form another sorted linked list.

Solution 1 :

Take the first element of each linked list and create a sorted linkedlist of these elements. Call it X. Each element of X would contain a ( ptr, value ) pair. And X would be sorted by value.

Let the first element of X be A.

A ('s value) would be the first element of the result list Y. Find the next element from the list to which A belongs. and insert that element into the list X at appropriate location. ( insert it such that X would be still sorted).

Now the first element of X would be second element of result list Y. and the same process can be repeated for NK times to get the result list Y.

Time complexity : Time complexity to create X + Time complexity of the rest operations.

= O ( N * log(N) ) + (N*K) * O (N) [ Time complexity to insert an element into a sorted linked list is O(N) ]

= ( N*K ) * O (N)

Space complexity : Need another linked list of size N

Solution 2 :

Similar to the above sln.. but to use an additional heap instead of the linkedlist. Create a heap of (size N) first elements from all the lists - X . Pop the smallest element ( let's say A ) from the heap. and that would be the first element of the result list. Find the next element of the list from which A came. and insert it into the heap. For each element inserted into heap it takes O(log N) time.

So, Time complexity = Create a heap + rest operations

= O(N) + ( N*K ) * O (log N)

= O ( (N*K) * (log N) )

Space Compexity: A heap of size N

Using the right data structure is the key..

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.

Write an algorithm to remove balls out of a box....

Q : Given a box with n number of balls. Write an algorithm to remove the balls from the box.

Answer :

public class Box
{
Ball[] balls;
int ballCount;
public Box(int ballCount)
{
this.ballCount = ballCount;
balls = new Ball[ballCount];
}
public bool RemoveBall()
{
if(0 < this.ballCount)
{
int deleteThis = Random() % this.ballCount;
for(int index = deleteThis; index < this.ballCount - 1; index++)
{
a[index] = a[index + 1];
}
this.ballCount--;
return true;
}
else
{
return false;
}
}
}

public class Ball
{
int id;
public Ball(int id)
{
this.id = id;
}
public int ID
{
get { return this.id; }
set { this.id = value; }
}
}
static void Main()
{
Box box = new Box(100);
while(true == box.RemoveBall());
}

Note : int rand(void) is the function used in C++ to generate random numbers…..which returns a psuedo-random integral number in the range of 0 to RAND_MAX ( ~ 32767 )
To generate any random number in the range of a to a+x ...
( ( Value % x ) + a ) where value is rand()

Find if a string s2 is a substring of string s1

Let s1 be the string in which we are looking for s2..
boolean Find(char *s1, char *s2) {
// Make a check to see if length of s2 is less than or equal to length of s1.. If not return false…
int i, j=0;
char flag = false;
int len = strlen(s2) - 1;
for(i=0;i{

if(flag = true && s2[j] != s1[i])
{
i--;
j=0;
flag = false;
}
else {

if(s2[j] == s1[i])
{
i++;
j++;
flag = true;
}
else
{
if(flag = false)
i++;
}
}
if(j == len)
{
return true;
}
}
return flag;
}

Zig Zag Traversal of a tree...

Q : Given a binary tree.. Print the elements from the 1st row to the last row (each row corresponding to one set of siblings in the tree) such that

For every odd row : print the elements from left to right
For every even row : print the elements from right to left.

Answer :


Use two stacks. One stack to store the even row pointers and another to store the odd row pointers
Let root be the root element of the tree - lets say the row is even - 0

stack1 - contains the even pointers
stack2 - contains the odd pointers

flag = true;
while( flag !=false)
{
push root into stack1
while( ( s1_current = pop(stack1)) ! = null )
{
print(s1_current->element);
push(s1_current->left) into stack2; //if the element is not null
push(s1_current->right) into stack2; //if the element is not null
}
while( (s2_current = pop(stack2)) != null)
{
print(s2_current->element);
push(s2_current -> right) into stack1; // if the element is not null
push(s2_current -> left) into stack1; // if the element is not null
}
if(top(stack1) != null) // basically to check if stack1 is empty
{
flag = true;
}

}

Time Complexity : O(n)

Space Complexity : The worst case space complexity for this problem would be 2 ^ log(n) since log(n) corresponds to the height of the tree.