Saturday, October 19, 2013

LCA for a binary tree

Given a binary tree(not a binary search tree) find the LCA of the 2 given nodes.

The lowest common ancestor(LCA) for the nodes u and v is defined as the lowest node w in tree  that has both u and v as the descendants (where a node can be a descendant of itself).


Lets consider the below tree

LCA of node 30, 5 is 100
LCA of node 15, 50 is 50
and so on

Wednesday, October 16, 2013

A closer look at Coin Change

Coin change has been a very famous computing problem which can be easily solved by Dynamic programming.

So what is coin change ?
If we want to make change for N cents, and we have infinite supply of each of S = \{ S_1, S_2, \ldots, S_m \} valued coins, how many ways can we make the change? (The order does not matter.)

For example, for N = 4,S = {1,2,3}, there are 7 possible solutions: {1,1,1,1},{1,1,2}, {1, 2, 1}, {2, 1, 1}, {2,2},{1,3}, {3, 1}.

So how to compute the number of ways efficiently?

Friday, July 5, 2013

Largest area in a Histogram

Find the maximum area of a rectangle that fits entirely in the Histogram.

For e.g in the below histogram the maximum area of the rectangle is 2 * 80  = 160

The length of each bar will be the input, and the width of each bar is same, 1
The naive approach can be to select one histogram at a time, find the maximum area which can be formed with this, finally return the maximum value over all the histogram.
Time Complexity O(n^2), Space Complexity O(1)
Can we do better. Lets have a look if we are computing some of the results over and over or if any of the computations are unnecessary.

Sunday, June 2, 2013

[Amazon Online test] Sort an array containing 0, 1 & 2

Given that an array consists of only 0s 1s and 2s sort the array in one pass.


Lets view the problem if the constraint of one pass wouldn't have been there
Scan over the array and count the number of 0, 1, and 2.
Now initialise the array with the 0, 1, 2 with the number of elements, the idea is similar to the counting sort.

To solve the above problem in one pass we can use the famous Dutch national flag algorithm.
The basic idea is to traverse over the array and keep track of the current 0s and 2s and the read pointers(initialised with -1, n and 0). Now traverse the array and keep swapping the current element in the respective buckets of interest.

[Expedia Interview] Intersection of two link list

Given two link lists intersecting in the following manner

 check whether the two list intersect or not, if it does find the point of intersection.

Saturday, June 1, 2013

Cumulative Sums of elements in an array[Binary Indexed Tree]

Given a array and with below possible operations
Update: Add a value to a index a
Query: Get a cumulative sum from a range a to b
 What is the data structure you would employ and what will be the time complexity of the update and query operations.

The basic idea of any of the algorithm is to store/update the sum of the subparts and compute the sum in a range by adding up the relevant subparts.So for e.g a common data structure Segment tree creates a tree where the parent stores the sum of the child elements.

Saturday, February 23, 2013

Fibonacci Series Part II

In the last post we discussed about evaluating the nth Fibonacci number in logarithmic time O(logn).

Lets us look at another problem on the similar lines.
Given a series
F(n) = F(n-1) + 2*F(n-2) + 3*F(n-3) + F(n-4)

Lets try to solve the problem in the similar fashion,

The matrix multiplication looks like below,

The running time to compute the nth term of the series will be 
(sizeof(M) ^3) * log(n) = 64*log(n)

Can we optimize it further ?

Lets again go over the series once more
F(n) = F(n-1) + 2*F(n-2) + 3*F(n-3) + F(n-4)
F(n-1) = F(n-2) + 2*F(n-3) + 3*F(n-4) + F(n-5)
F(n) - F(n-1) = F(n-1) + F(n-2) + F(n-3)  - 2*F(n-4) - F(n-5)
After some more rearrangement it reduces to
F(n) = 2* F(n-1) + F(n-2)
Some of you must have recognized it as Pell's number.

So the matrix multiplication reduces to

So the final runtime reduces to O(8* log(n))

Fibonacci numbers [Matrix exponentiation]

Fibonacci numbers has been a very famous sequence represented as:

F(n) = F(n-1) + F(n-2)
with F(0) = 0, F(1) =1
So what if you need to find the nth term of the series. Its easy to view the recursive nature of the problem.

The code snippet would look something like

int fib(int n) {
    if(n<1) return 0;
    if(n == 1) return 1;
    return fib(n-1) + fib(n-2);

Monday, January 14, 2013

[Google Interview] Query the most frequent element

Design a data structure which supports the below operation
Insertion of an integer
Deletion removes the element with highest frequency at that instant. In case of tie, go by the FIFO startegy.

For e.g

Insert 5,6,5,7,5,7
1st removal -- 5,6,5.7,7
2nd removal -- 5,6,5,7,
3rd removal -- 5,6,7
and so on

Perform both the operations in O(1).