July 10, 2021
Here is the link.
Hard level algorithm | DP solution warmup | States definition | Top down
July 9, 2021
Introduction
It is risky business to invest time to work on hard level algorithms. I am not sure what is the best way to spend time to learn a hard level algorithm. I came back to warm up the algorithm, since I have a phone interview from a California startup with an office in Vancouver on July 12, 2021. Make a hard level algorithm simple. Write a story and one a time.
States | DP problem definition | How to make it clear and easy to understand?
Dynamic programming algorithm can be such a hard problem. So it is important for me to learn how to define states, three states for this algorithm, and also put together some simple questions to help myself to think top down, and how to design by coping the idea first, and then explain thinking process.
'A': Absent.
'L': Late.
'P': Present.
Rules to follow:
- The student was absent ('A') for strictly fewer than 2 days total.
- The student was never late ('L') for 3 or more consecutive days.
Case study | n = 2 | Answer: 8 cases:
Input: n = 2
Output: 8
Explanation: There are 8 records with length 2 that are eligible for an award:
"PP", "AP", "PA", "LP", "PL", "AL", "LA", "LL"
Only "AA" is not eligible because there are 2 absences (there need to be fewer than 2).
How to think about top down, and then define three states:
state 1: length of sequence
state 2: total A in the sequence
state 3: count of continuous 'L'
Top down or bottom up? | Choose top down here | Memoization
Actually think more precisely, top down, suffix not prefix of string, I should write down more precisely:
state 1: length of sequence
state 2: total A in the sequence, suffix of sequence
state 3: count of continuous 'L', suffix of sequence
Last char can have three cases: 'P', 'A', 'L'
"?P", so top down, the existing sequence "P", no 'A', 0 of consecutive 'L'
"?A", so top down, the existing sequence "A", 1 'A', 0 of consecutive 'L'
'?L", so top down, the existing sequence "A", 1 'A', 1 of consecutive 'L'
I just work on simple analysis, so the answer of n = 2 should be "??", so top down, the existing sequence "", no 'A', 0 of consecutive 'L'.
Another two tips to help warmup rules:
- Consecutive 'L' may be reset, for example, "PPLLPLL", top down, 1 to 2 consecutive 'L', and then P is the third char, reset to 0 of consecutive 'L'
- Total count of 'A' always increases, valid possible count of 'A' are 0 or 1, for example, valid sequence "PPAP", starting from rightmost, from 0 to 1, and stay as 1 until first char 'P' is visited.
So first define the function:
private int helper(int n, int chosenA, int continuousL, int[, ,] cache)
n = 2,
"??", top down, the suffix string is empty, so there is no 'A', 0 is the length of continuous 'L'.
return helper(n, 0, 0, cache);
If I can understand the above statement and reasoning behind. Continue to read the following analysis.
Last char can have three choices, 'A', 'L', 'P'.
If suffix string already has 'A', then there is no option for 'A', otherwise 'A' can be taken. So it is easy for me to read the following statements in the function:
if (chosenA == 0)
{
// add 'A', reset continuousL = 0
// n -> n - 1
result += helper(n - 1, chosenA + 1, 0, cache); // Choose 'A'
result %= mod;
}
If I can understand the above statements, then I think that I can work independently and write a working solution. Otherwise go back to problem statement, and then read again.
Actionable Items
Change variable name chosenA to suffixA, variable name continuousL to suffixContinuousL.
Stay tuned. I will add more detail in short future.
public class Solution {
/// <summary>
/// July 9, 2021
/// How to solve this problem using three dimension dynamic programming?
/// 1. First, define states, three states, length of sequence, number of days absent, and maximum continuous 'L';
/// 2. Second, try to build recurrence formula.
/// Not allowed:
/// 1. Two days absent
/// 3. Three day continuous late
/// Still confused, review the discussion post here:
/// To save time, only work on length = 2, make sure that total found is 8.
/// "PP", "AP", "PA", "LP", "PL", "AL", "LA", "LL"
/// if n = 0, then "" is only option, empty string.
/// if n = 2, then cache's state - length of sequence should be 3, allow 0, 1, 2 three options.
/// Argue that return should be help(2, 0, 0, cache), chosenA = 0, continuousL = 0 as well.
///
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public int CheckRecord(int n)
{
var cache = new int[n + 1, 2, 3];
for (int row = 0; row < n + 1; row++)
{
for (int col = 0; col < 2; col++)
{
for (int L = 0; L < 3; L++)
{
cache[row, col, L] = -1;
}
}
}
return helper(n, 0, 0, cache);
}
/// <summary>
/// Returns the number of ways to create a string of
/// length n with characters 'A', 'L', 'P'
/// while having <= 1 total 'A's and <= 2 consecutive 'L's.
/// n = 0, return 1, ''
/// n = 1, return 3 'A' or 'P' or 'L'
/// n = 2, last option can have three choices, 'A' or 'P' or 'L'
/// Think about top down
/// return helper(n, 0, 0, cache), length of sequence is n, and no 'A' is used, no 'L' is used.
/// ?'A' -> subprobem -> total A used should be chosenA + 1
/// ?'L' -> subproblem -> if it is allowed - check first, and then update count
/// ?'P' -> subproblem -> always ok, reset continuousL, chosenA - no change
/// </summary>
/// <param name="n"></param>
/// <param name="chosenA"></param>
/// <param name="continuousL"></param>
/// <param name="cache"></param>
/// <returns></returns>
private int helper(int n, int chosenA, int continuousL, int[, ,] cache)
{
int mod = 1000 * 1000 * 1000 + 7;
// base case - 1,
if (n == 0)
{
return 1;
}
if (cache[n, chosenA, continuousL] != -1)
{
return cache[n, chosenA, continuousL];
}
int result = 0;
if (chosenA == 0)
{
// add 'A', reset continuousL = 0
// n -> n - 1
result += helper(n - 1, chosenA + 1, 0, cache); // Choose 'A'
result %= mod;
}
if (continuousL < 2)
{
// add 'L', continuousL++
// chosenA - no change
result += helper(n - 1, chosenA, continuousL + 1, cache); // Choose 'L'
result %= mod;
}
// add 'P'
// reset continuousL = 0
// chosenA - no change
result += helper(n - 1, chosenA, 0, cache); // Choose 'P'
result %= mod;
// memoization - save to cache
cache[n, chosenA, continuousL] = result;
return result;
}
}
