For each iteration of the inner loop, we get the solution with denoms[j]
and store it in x
. We also get the solution without denoms[j]
and store it in y
. By doing this, we’re able to reference earlier solutions to avoid duplicate computations.
For each coin in the denomination, there can only be two possibilities: to include it or exclude it. We know that if the coin, denom[j]
, is larger than amount
, then x
is set to 0 since including it into consideration is impossible.
The time complexity is O(amount×denomsLength), which is the number of for loop iterations.
Note: Each of these three methods includes time complexity, meaning that time complexity is an important concept to understand to succeed at the coin change problem.
Dining philosophers problem#
The dining philosophers problem is commonly used in concurrent algorithm design to demonstrate issues with synchronization and the techniques to solve them. The problem states that there are five philosophers sitting around a circular table. The philosophers must alternatively think and eat.
Each philosopher has a bowl of food in front of them, and they require a fork in each hand to eat. However, there are only five forks available. You need to design a solution where each philosopher can eat their food without causing a deadlock.
With this problem, it’s common for developers to overlook the idea that it’s not really asking about a real-world scenario, but rather illustrating the kinds of problems you could run into in threaded program executions and/or negligent handling of locks. The idea is to get you to think about limitations and proper ordering to accomplish this task in the most efficient way.
To prepare for this question, you should dive deeper into synchronization, concurrency control, and semaphores.
Here are two possible ways to solve this problem:
- Limiting the philosophers that are about to eat
- Reordering the fork pick-up
Let’s look at the reordering the fork pick-up solution in Java: