This page offers several corrected exercises on algorithms, more specifically understanding the difference between the Divide & Conquer paradigm (Divide and rule) and the dynamic programming. The specifics of the path search (shortest path), problem of planning, maximum flow problem and more generally the graph theory is treated separately.
Exercise 1
The brute force algorithm is trivial: a loop.
At each level l, the complete binary tree is composed of 2^(l-1) leaves. So the total of the vertices is 2^l -1. Let l be the level of the tree, so l=sup(log_2 (n)).
Exercise 2
Suppose your input array is called A. What you need to do is form another array, say B, each i value of which is calculated using the recursive formula, max(A[i], B[i- 1]+A[i ])
What you actually do is choose to expand the previous window or start a new one. You can do this since you are only supposed to select continuous elements as part of your subsets.
5, -6, 7, 12, -3, 0, -11, -6
The answer would be 19 (from sub-array {7,12} )
Exercise 3
Use the longest common substring for: BDCABA and ABCBDAB. The algorithm is described as follows:
Exercise 4
Match the longest common substring to the longest common subsequence: BDCABA and ABCBDAB. The longest common subsequence (LCS) problem is to find the longest common subsequence of all sequences in a set of sequences (often only two sequences).
This differs from common substring search problems: unlike substrings, subsequences are not required to occupy consecutive positions in the original sequences.
Exercise 5
Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character modifications (i.e., insertions, deletions, or substitutions) needed to change one word into the other. Propose a dynamic program to solve this problem. Trial with MEILENSTEIN and LEVENSHTEIN.
Exercise 6
Alice and Bob take turns playing a game, with Alice starting first.
Initially, there is a number n on the board. On each player's turn, that player makes a move consisting of:
Choose any x with 0 < x < n and n % x == 0.
Replace the number n on the board with n – x.
Also, if a player cannot move, they lose the game.
Return true if and only if Alice wins the game, assuming both players are playing optimally.
Example 1:
Input: n = 2
Output: true
Explanation: Alice chooses 1 and Bob has no more moves.
Example 2:
Input: n = 3
Output: false
Explanation: Alice chooses 1, Bob chooses 1 and Alice has no more moves.
To answer this problem, we will build a solution table. dp[i] indicates the result of the game for the given number i and for the player who started the game. Alice will try all the factors and choose the one that gives her opponent a losing value.
It is also possible to solve this problem in a more classic recursive way, called Top-Down.
And for a more practical side we are going to add a memosization.
Exercise 7
You are given a cost array of integers where cost[i] is the cost of the ith step of a stair. Once you've paid the cost, you can climb one or two steps.
You can either start from step with index 0 or from step with index 1.
Return the minimum cost to reach the top of the floor.
Example 1:
Entry: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
– Pay 15 and climb two steps to reach the top.
The total cost is 15.
Example 2:
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
– Pay 1 and go up two steps to reach clue 2.
– Pay 1 and go up two steps to reach clue 4.
– Pay 1 and go up two steps to reach clue 6.
– Pay 1 and go up one step to reach clue 7.
– Pay 1 and go up two steps to reach clue 9.
– Pay 1 and climb a step to reach the top.
The total cost is 6.
For a first draft, we will solve this problem by recursive. For this we keep in mind the smallest cost by considering that we go back one step and two steps. And so on until you have the cost of the first or second step.
mincost(0) = cost[0]mincost(1) = cost[1]
mincost(i) = cost[i]+min(mincost(i-1), mincost(i-2))
Which gives the following code:
In a second step, we will stay in a top-down approach and add a memoization system. Thus, a minCost already found will not be recalculated later.
Finally, we will take the problem bottom-up to do dynamic programming;
Exercise 8
Alice and Bob are playing a game with piles of rocks. There are an even number of stacks arranged in a row, and each stack has a positive integer number of stone stacks[i].
The object of the game is to finish with the most stones. The total number of stones on all stacks is odd, so there is no tie.
Alice and Bob take turns, with Alice starting first. Each turn, a player takes the whole stack of stones either from the start or from the end of the row. This continues until there are no more stacks, at which point the person with the most stones wins.
Assuming Alice and Bob are playing optimally, return true if Alice wins the game, or false if Bob wins.
Input: stones = [5,3,4,5]
Output: true
Alice starts first and can only take the first 5 or the last 5.
Let's say she takes the first 5, so the line becomes [3, 4, 5].
If Bob takes 3, then the board is [4, 5], and Alice takes 5 to win with 10 points.
If Bob takes the last 5, then the board is [3, 4], and Alice takes 4 to win with 9 points.
This demonstrated that taking the top 5 was a winning move for Alice, so we return true.
Let's start with a top-down approach with memoization.
- Please note that both players play optimally, so we play optimally no matter who is Alice, who is Bob.
- Let dp(left, right) return [firstScore, secondScore] where firstScore is the maximum score when player1 plays first, secondScore is the maximum score when player2 plays second, he picks up stones in piles[left]…piles[ right ].
- For stones in piles[left]…piles[right], there are 2 choices for player1 to choose:
- Pick left: pickLeft = dp(left + 1, right).
- Player1's score = stacks[left] + pickLeft's second choice score, so firstScore = stacks[left] + pickLeft[1]
- Player2's score = pickLeft's first choice score, so secondScore = pickLeft[0]
- Pick right: pickRight = dp(left, right – 1).
- Player1's score = stacks[right] + pickRight's second score, so firstScore = stacks[right] + pickRight[1]
- Player2's score = pickRight's first choice score, so secondScore = pickRight[0].
- Pick left: pickLeft = dp(left + 1, right).
- We need to get the maximum score when player 1 plays first among more than 2 choices.
- Finally, dp(0, len(stacks) – 1) return [firstScore, secondScore], where alexScore = firstScore since Alice plays first, leeScore = secondScore since Bob plays second.
Now we are going to make a bottom-up algorithm while keeping memoization. Thus the algorithm will be in dynamic programming.
Exercise 9
There are soldiers standing in line. Each soldier is assigned a unique rank value.
You must form a team of 3 soldiers among them according to the following rules:
Choose 3 soldiers with index (i,j,k) with rating (rating[i],rating[j],rating[k]).
A team is valid if: (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < not).
Return the number of teams you can form given the conditions. (soldiers can be part of several teams).
Example 1:
Input: score = [2,5,3,4,1]
Output: 3
Explanation: Three teams can be formed depending on the conditions. (2,3,4), (5,4,1), (5,3,1).
Example 2:
Input: score = [2,1,3]
Output: 0
Explanation: We cannot form any team given the conditions.
It's easy to make a greedy algorithm. The latter is in O(n^3) so we will try to improve the complexity with dynamic programming.
Here is the main idea in the dynamic programming version:
First, we compute this case score[i] > score[j] > score[k] given that i > j > k. Next, compute the case score[i] < score[j] < score[k].
Set dp[i]: how many elements in the notation from 0 to i-1 are less than the notation[i].
For each time we found note[i] > note[j], we accumulate dp[j]. Here, dp[j] means how many notes[k] exist from 0 to j-1. That is, how many cases satisfy grade[i] > grade[j] > grade[k].
Exercise 10
You are given a price chart where price[i] is the price of a given stock on the ith day, and an integer fee representing transaction fees.
Find the maximum profit you can make. You can make as many transactions as you want, but you must pay transaction fees for each transaction.
Note: You cannot engage in multiple trades simultaneously (i.e. you must sell the stock before buying again).
Entry: price = [1,3,2,8,4,9], fee = 2
Output: 8
Explanation: Maximum profit can be achieved by:
– Buy at prices [0] = 1
– Sell at prices[3] = 8
– Buy at prices [4] = 4
– Sell at prices[5] = 9
The total profit is ((8 – 1) – 2) + ((9 – 4) – 2) = 8.
Let's start first with the top-down approach.
- Let dp(i, canBuy) be the maximum profit we can get from price[i..n-1] with canBuy flag == True means we can buy on the ith day.
- For the ith day we have 2 options:
- Ignore it: profit = dp(i+1)
- Buy it or sell it
- If buy: profit = dp(i+1) – price[i]
- If sale: profit = dp(i+1) + price[i] – commission
We will convert to a bottom-up approach to do more traditional dynamic programming.
Let dp[i][j] be the maximum profit we can make from price[i..n-1] with flag j == 1 means we can buy on the ith day.
Since our dp only accesses 2 states: the current dp state dp, the previous dp state dpPrev. We can optimize to O(1) in space complexity.
Exercise 11
You planned a train trip a year in advance. The days of the year on which you will travel are given as an integer number of days. Each day is an integer between 1 and 365.
Train tickets are sold in three different ways:
a 1 day pass is sold at the price of [0] dollars,
a 7-day pass is sold for costs [1] dollars, and
a 30-day pass is sold for costs [2] dollars.
Passes allow for as many consecutive travel days.
For example, if we get a 7 day pass on day 2, we can travel for 7 days: 2, 3, 4, 5, 6, 7 and 8.
Return the minimum number of dollars you need to travel each day in the given list of days.
Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Exit: 11
For example, here is a way to buy passes that allow you to travel according to your travel plan:
On day 1, you purchased a 1-day pass for cost[0] = 2 $, which covered day 1.
On day 3, you bought a 7-day pass for cost[1] = 7 $, which covered days 3, 4, …, 9.
On day 20, you purchased a day pass for cost[0] = 2 $, which covered day 20.
In total, you have spent 11 $ and covered all the days of your trip.
We will see here the bottom-up approach because the reasoning is very similar to the problem of backpack (knapsack) in building the solution.
dp[i] means until the th day the minimum cost of tickets. The size of the dp array depends on the last travel day, so we don't need an array length of 365.
We need a boolean array to mark the travel days, the reason is that if it's not a travel day, we don't need a ticket. However, if it is a travel day, we consider three scenarios (with three types of tickects):
If a 1-day ticket on day i, dp[i] = dp[i – 1] + cost[0]
If a 7-day ticket ends on day i, dp[i] = min(dp[i – 7], dp[i – 6] … dp[i – 1]) + cost[1]
If a 30-day ticket ends on day i, dp[i] = min(dp[i – 30], dp[i – 29] … dp[i – 1]) + cost[2]
But since the value of dp array increases, so:
For a 7-day ticket ending on day i, dp[i] = dp[i – 7] + cost[1]
For a 30-day ticket ending on day i, dp[i] = dp[i – 30] + cost[2]
Exercise 12
You are given an array of integer values where values[i] represents the value of the ith tourist site. Two tourist sites i and j have a distance j – i between them.
The score of a pair (i < j) of tourist sites is values[i] + values[j] + i – j: the sum of the values of the tourist sites, minus the distance between them.
Returns the maximum score of a pair of sights.
Input: values = [8,1,5,2,6]
Exit: 11
We have i = 0, j = 2, values[i] + values[j] + i – j = 8 + 5 + 0 – 2 = 11
Suppose we choose the site [i,…j]. The score can be broken down into 2 parts.
The first part is the startGain that you earn by starting at a certain point i. Note that startGain[i] = a[i] + i.
The second part is the endGain which is the amount you earn by finishing at a certain point j. Note that endGain[i] = a[j] – j.
Note that endGain can be negative.
The overall gain for [i,…j] is nothing but startGain[i] + endGain[j]. (This can be easily verified by the definitions).
We must maximize the overall gain.
What are the possible positions to start the journey? It is clear that we can start everything except the last element. Thus, the optimal journey must begin at one of these elements.
Suppose we are only allowed to start a journey at i. What is the maximum amount we can win in this case? Well, since the startGain is fixed, we need to maximize the endGain. We can do this by stopping at an element that has the maximum endGain provided it appears to the right of i.
As shown above, for each i we need to find the maximum endGain to its right.
maxEndRight[i] = max(maxEndRight[i+1], endGain[i+1]) = max(maxEndRight[i+1], a[i+1] – (i+1))
maxEndRight[i] represents the highest endGain you can get by stopping at any point strictly to the right of i. Since by definition we already know endGain[i+1] (the highest possible gain when ending at any point to the right of i+1), we only have to check the possibility of knowing if s stopping at i+1 would be beneficial or not. Hence the definition of DP.
For each valid i, overallGain[i] = startGain[i] + maxEndRight[i] = a[i] + i + maxEndRight[i]
Note that maxEndRight[i] only depends on maxEndRight[i+1]. Therefore, we can use 2 variables to track previous values.
Since we need the value of maxEndRight[i+1] to calculate the value of maxEndRight[i], so we start the iterations from the back.
As stated, trips cannot start at the last element, so the for loop starts at i=n-2. For this value, maxEndingRight is initialized to endGain[lastIndex] because that is the only possible way to end the trip.
EN 
FR 
ES