Thursday, May 19, 2016

#codingexercise
Find minimum number of coins to make a sum
int GetMin(List<int> coins, int sum) // sorted coins
{
if (sum == 0) return 0;
if (coins.sum() == sum) return coins.count();
if (coins.sum()  < sum ) return INT_MAX;
return min(GetMin(coins.Range(1, coins.count-1), sum),  GetMin(coins.Range(1, coins.count-1), sum-coins[coins.count-1])+1);
}
Find maximum number of ways to make a sum from coins with infinite supply
int GetMaxWays(List<int> denominations, int sum)
{
if (sum == 0) return 0;
if (denominations.count() == 0) return 0;
return GetMaxWays(denominations.Range(1,denominations.count-1), sum) +
          GetMaxWays(denominations.Range(1,denominations.count-1), sum-denominations[denominations.Count-1]);
}
void TREE-DELETE(Node root, Node z)
{
if (z.left == null)
      TRANSPLANT(T,z,z.right);
else if (z.right == null)
      TRANSPLANT(T,z,z.left)
else{
      y = TREE-MINIMUM(z,right);
      if (y.parent != z)
           TRANSPLANT(T, y, y.right)
           y.right = z.right;
           y.right.parent = y;
      TRANSPLANT(T,z,y)
      y.left = z.left;
      y.left.p = y;
}
}

No comments:

Post a Comment