Tag Archives: C++

C++ important links

  1. http://www.learncpp.com/cpp-tutorial/121-pointers-and-references-to-the-base-class-of-derived-objects/ (array animal example)
  2. http://www.learncpp.com/cpp-tutorial/122-virtual-functions/ (array animal example)

Left:

When do we pass arguments by reference or pointer?

Initializer list: when to use?

More about default constructor

Virtual destructors prevent memory leak !

Multiple inheritance in C++ (Initialization list process: 2nd problem)

RTTI

Advanced C conversion operators

* * * * *

Advertisements

Leave a comment

Filed under Interviews

Dynamic Programming – Famous coin sum question

Question: Out of given ‘N’ coins, give the minimum number of coins required to sum upto ‘S’

Answer: 

(Assumption: list of coins is sorted)

Loop from 1 to S and check solution for each denomination keeping solution for 0 as 0. DYNAMIC PROGRAMMING !!

For example, if you have N coins as {1, 3, 5} and you have to sum upto 10 then loop from 1 to 10 and for each number check if the number is more than maximum value of denomination present. If yes, than your answer will be (number – maximum denomination)’s answer + 1.

Number — COINS REQUIRED

0 — 0

1 — 1

2 — 2  (i.e. [2-1]’s answer + 1 i.e. [1]’s answer + 1 i.e. 1 + 1 == 2)

3 — 3  (i.e. [3-3]’s answer + 1 i.e. [0]’s answer + 1 i.e. 0 + 1 == 1)

4 — 2

5 — 1

and so on…

10 — 2  (you know why !)

Code:

Image

Leave a comment

Filed under Algorithms