a very popular interview question in fb and others with many variations
given a set of denominations (infinite supply) and total amount in cents
1.is it possible to make change
2. number of ways to make change
3. minimum number of coins to make change
4. ways to make change order does not matter
5. ways to make change order matters
repeat above where supply for each denomination is provided.
extension is to do memoization
is there one skeleton that is optimal for one or more of these, any that should be avoided? while I know how to solve each of them I end up choosing the not optimal/suitable approach at times and especially when I get to memoization for 4 and 5..
popular skeletons
1. sort denominations descending and use 0/1 coin per recursion ( no loop in method)
2. sort descending use 1 to as many you can of denomination per recursion (loop in method)
3. recursion returns solution for sub problem ( create a new set of results by cloning sub result and add the current level selection)
4 solution Witten out to passed in object at end of recursion (leaf node).. can you even do memoization here?
5 don't sort
what if given actual pieces of coins, do you convert to denominations and quantities or deal with dups later?
FML...
Want to see the real deal?
More inside scoop? View in App
More inside scoop? View in App
blind
SUPPORT
FOLLOW US
DOWNLOAD THE APP:
FOLLOWING
Industries
Job Groups
- Software Engineering
- Product Management
- Information Technology
- Data Science & Analytics
- Management Consulting
- Hardware Engineering
- Design
- Sales
- Security
- Investment Banking & Sell Side
- Marketing
- Private Equity & Buy Side
- Corporate Finance
- Supply Chain
- Business Development
- Human Resources
- Operations
- Legal
- Admin
- Customer Service
- Communications
Return to Office
Work From Home
COVID-19
Layoffs
Investments & Money
Work Visa
Housing
Referrals
Job Openings
Startups
Office Life
Mental Health
HR Issues
Blockchain & Crypto
Fitness & Nutrition
Travel
Health Care & Insurance
Tax
Hobbies & Entertainment
Working Parents
Food & Dining
IPO
Side Jobs
Show more
SUPPORT
FOLLOW US
DOWNLOAD THE APP:
1.is - Veflausnir
comments