Monday, December 27, 2010

Kth largest element for a stream of integers

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.

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.

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.

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.

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?

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.

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