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.