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).

Approach:

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?