You are reading a stream of integers and you cannot look back to the stream once it is passed. At any instant you have to find the kth largest element(if the stream is less than k you need to report smallest element) from the stream read so far. What is data structure you will use and approach to find the same.

## Monday, December 27, 2010

## Sunday, December 26, 2010

### Compute the Power(x,n) in log(n) steps

Implement the power(x,n) which finds the value of x^n efficiently.

Power of x^n can be naively computed by multiplying 'x' n times.

We can divide the problem in smaller similar problems.

x^n = x^(n/2) * x^(n/2) //If n is even

x^n = x^(n/2) * x^(n/2) * x // If x is odd

Using the above result, we can recursively reduce the problem to log(n) steps only.

**Approach:**Power of x^n can be naively computed by multiplying 'x' n times.

void power(int x, int n) { int r = 1; for (int i=0;i<n;i++) r *= x; return r; }

We can divide the problem in smaller similar problems.

x^n = x^(n/2) * x^(n/2) //If n is even

x^n = x^(n/2) * x^(n/2) * x // If x is odd

Using the above result, we can recursively reduce the problem to log(n) steps only.

int power(int x, int y) { int r; if(!y) return 1; r = power(x, y/2); if (y%2 == 0) return r*r; else return r*r*x; }

## Saturday, December 18, 2010

### Subsequence again !!!

You are given a text string S, your task is to determine how many times a particular string T appears as a sub-sequence of the given string S i.e number of sub-sequences of the string S forming the string T.

## Tuesday, November 30, 2010

### Biased game

2 players were playing a game in which they have n number of balls. In each chance a player can pick a ball in between a number 1 to k both inclusive. The player making the last move wins the game.

Given the number n & k and said that both players are clever enough and wish to win, predict the result of the game.

All the biased games are predominately based on the symmetrical moves, this is no exception. How can one ensure the win ?

Lets start with the base case of (n+1) coins (Obviously with coins < n the first player has to win :))

Now irrespective of the number of coins picked by player 1, the second player can clear out all the coins. So if the 2nd player can ensure that the number of coins is n+1 at the end he is destined to win.

Now what if the coins > n+1

The player should ensure that when the turn of the other player comes there should be n + 1 coins. This can be safely ensure by having 2* (n+1) coins

So in short if the coins are of the factor of n + 1 then the 2nd player will win, else the 1st player will win

Given the number n & k and said that both players are clever enough and wish to win, predict the result of the game.

__Approach:__All the biased games are predominately based on the symmetrical moves, this is no exception. How can one ensure the win ?

Lets start with the base case of (n+1) coins (Obviously with coins < n the first player has to win :))

Now irrespective of the number of coins picked by player 1, the second player can clear out all the coins. So if the 2nd player can ensure that the number of coins is n+1 at the end he is destined to win.

Now what if the coins > n+1

The player should ensure that when the turn of the other player comes there should be n + 1 coins. This can be safely ensure by having 2* (n+1) coins

So in short if the coins are of the factor of n + 1 then the 2nd player will win, else the 1st player will win

## Monday, October 4, 2010

### BIT Hacks

Write a single line of code for the below operations

1. Set the nth bit to 1.

x = x | (1 << n);

2. Reset the nth bit of number

x = x & ~(1 << n);

3. Toggle the nth bit of the number.

x = x ^ (1 << n);

4. Convert the (right adjusted) n-bit field of x that begins at position p x =(x >> (p+1-n)) & ~(~0 << n);

An important point to note is that none of your operation should overflow the variable in use.

1. Set the nth bit to 1.

x = x | (1 << n);

2. Reset the nth bit of number

x = x & ~(1 << n);

3. Toggle the nth bit of the number.

x = x ^ (1 << n);

4. Convert the (right adjusted) n-bit field of x that begins at position p x =(x >> (p+1-n)) & ~(~0 << n);

An important point to note is that none of your operation should overflow the variable in use.

## Sunday, October 3, 2010

### Given a number is power of 2?

Write 1 line code to find whether a number is a power of 2 or not?

To clear the rightmost bit of a number the below utility can be used

n = n & (n-1) (Since n-1 turns off the right most bit and turns on all the bit lower than the rightmost bit)

Now to find the number is power of 2 or not is trivial

if n & (n-1) == 0

but there is a catch for the number of 0 :)

so a simple one liner code will be

return n && !(n & (n - 1));

**Approach:**To clear the rightmost bit of a number the below utility can be used

n = n & (n-1) (Since n-1 turns off the right most bit and turns on all the bit lower than the rightmost bit)

Now to find the number is power of 2 or not is trivial

if n & (n-1) == 0

but there is a catch for the number of 0 :)

so a simple one liner code will be

return n && !(n & (n - 1));

### Count the number of ways .

Lets start with a simple but a tricky one :)

You have n number of chocolates. Your best friend asks for the chocolate but you say that he can take only 1 or maximum 2 chocolates at a time.

Find the number of ways in which your friend can take all the chocolates in any number of times.

The first thing to note is that how can you take n chocolates ?

Before having n chocolates you need to have either n-1 or n-2 chocolates (as you can only pick 1 or 2 chocolates).

So if f(n) denotes the number of ways to pick n chocolates then

f(n) = f(n-1) + f(n-2)

Wow it turns out to be a Fibonacci series !!!

Base cases you can work it out :)

Try the extension of this problem here

You have n number of chocolates. Your best friend asks for the chocolate but you say that he can take only 1 or maximum 2 chocolates at a time.

Find the number of ways in which your friend can take all the chocolates in any number of times.

**Approach :**The first thing to note is that how can you take n chocolates ?

Before having n chocolates you need to have either n-1 or n-2 chocolates (as you can only pick 1 or 2 chocolates).

So if f(n) denotes the number of ways to pick n chocolates then

f(n) = f(n-1) + f(n-2)

Wow it turns out to be a Fibonacci series !!!

Base cases you can work it out :)

Try the extension of this problem here

### Welcome Everybody

Well this is the the first post of this blog. This blog will provide myraid number of programming puzzles often useful in interviews in many top software companies. This blog will provoke to think differently and logical bend of mind. Will try to cover the standard as well as the variations of the programming questions.

The aim of of the blog will not be to provide the straightforward answers but to have a discussion and know various approaches to the problem(and also some of the wrong approaches :P)

Last but not the least any suggestions, comments or feedback are welcomed. Also if if you wish to contribute something to this blog or any concerns then you can reach me at aviral.nit@gmail.com

Happy browsing !!!

The aim of of the blog will not be to provide the straightforward answers but to have a discussion and know various approaches to the problem(and also some of the wrong approaches :P)

Last but not the least any suggestions, comments or feedback are welcomed. Also if if you wish to contribute something to this blog or any concerns then you can reach me at aviral.nit@gmail.com

Happy browsing !!!

Subscribe to:
Posts
(
Atom
)