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.

Subscribe to:
Posts
(
Atom
)