Learn the basics of memoization and dynamic programming. This video is a part of HackerRank's Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell. www.hackerrank....
You say “the reason is THAT...” instead of the more common and painful “the reason is BECAUSE...” 😍😍😍 Thank you!!!! That alone makes this video awesome!
Thank you very much for the explanation. I was solving the unique paths problem couple of days ago and I was getting exponential time while submitting the answer. Never realized that we could memorize the repetition of work.
Thank you so much this is a magnificent explanation. Super clear I was able to write the code and ut works perfectly. I don't mind the typos it is clear to understand despite those. Thanks!!
Thanks to this lady, the entire interview process is in the gutter! Congratulations on single-handedly destroying the creative interviewing process and turning it into a graded exam!
1:44 Notice how the frequency of each item other than 0 forms the Fibonacci sequence. fib(6): 1 occurrence fib(5): 1 occurrence fib(4): 2 occurrences fib(3): 3 occurences fib(2): 5 occurences fib(1): 8 occurences
Notice that her underlined if statement (at 7:21) can still unnecessarily call the countPaths function multiple times because the zero value it is checking for could have come from either the INITIAL zero value (originally stored in the paths matrix), or a CALCULATED zero value returned from countPaths. Simple initializing all the values in the paths matrix to -1 at the beginning and then checking for a -1 (instead of zero) in that same if statement will fix that.
Though it's a really helpful tutorial of DP (Thanks to Gayle), I think the memoization solution of maze problem misses a parameter in the recursive call. The correct code should be: int countPaths(boolean[][] grid, int row, int col, int[][] paths) { if (!isValidSquare(grid, row, col)) return 0; if (isAtEnd(grid, row, col)) return 1; if (paths[row][col] == 0) { paths[row][col] = countPaths(grid, row + 1, col, paths) + countPaths(grid, row, col + 1, paths); } return paths[row][col]; } In this case, the function will be able to check the paths 2-D array to retrieve the result already calculated. Looking forward to your feedback!
at 2:14 the memoization code for Fibonacci is incorrect. This would be the fix (pink line of code)- else if (!memo[n]) { memo[n] = fib(n-1, memo) + fib(n-2, memo); } In Python: def fib(n, memo): if n==0: memo[n] = 0 return 0 elif n==1: memo[n] = 1 return 1 elif not n in memo: print(n) memo[n] = fib(n-1, memo) + fib(n-2, memo) return memo[n] print( fib(5, {}))
8:26 Actually that cell is unreachable from the green guys current position, because he can't go left or up. Same with the 5 cells (7, 4, 1, 1,1) in the bottom left corner. But I assume you mean that each number represents all available paths IF the guy would have stood in that specific cell?
Yes those cells are unreachable, but it doesn't affect the correctness of the algorithm. The cell at 8:26 is prevented from summing into the final no. of paths because of the blocks to the top and left. A cell which is unreachable to the green guy is always a cell with blocks to the top and left. So by this logic you can convince yourself the algorithm won't sum up paths through unreachable cells.
else if (memo[n]) Isnt this condition saying if array memo of index n is filled? but shouldn't it be !memo[n] cause we are trying to fill up the array?
@@FreakinKatGaming what kind of bullshit answer is this. Plain and simple this code will return null if the value haven't been computed. @Foolish Music you are correct when it comes to the code that they showed.
@@basicnamenothingtoseehere 🤣 wow you a took that seriously. Bless your little heart . Omg you made my day, ain't you just the cutest little Dickens!!!! Man my day was NULL until I read this man variables are awesome. 😅😋 Nahh but why not apt moo - around
In the Fibonacci example why do you do “if else memo[n]” rather than “if else !(memo[n])”? Aren’t you checking if there is a value and if there isn’t (ie it is NULL) then calculate it?
This was honestly one of the most helpful tips I have ever received. When I started out programming, trying to use x and y, I wasted hours working around grid coordinates in my head.
or just use x & y and think in Cartesian its not actually that hard to convert beetween rows&columns to Cartesian x&y and the other way and by making it cartesian you can do x,y instead of y,x because in cartesian x is usually defined before y or to go trought use r & c instead of row & col
Great explanation! In the last example, the space complexity can be reduced to O(n) because we only need two rows or two columns of values if we sweep the matrix row by row.
If you count the presence of the original grid, the space complexity with be O(n^2) regardless. If you don't count the grid, you can define the grid in a way to modify it in place and the space would be O(1).
I once stumbled onto the misconseption you mentioned when using y as rows and x as columns and now I just figured it out why it happened then 😅. When we use the grid representation it would be good to indicate that arrows pointing the directions mean that its the way where row numbers are increasing and not neccessarily the way that rows are aligned I’m kind of dumb but if anyone else had this problem that might be the answer
How'd she calculate the "(simple) Recursive" runtime of O(2^{n^2})? (7:25) I think because there are n^2 possible cells (assuming the problem is run on an n by n grid), and at each cell there are a maximum of two possible moves that would add to a path: go down, or go right. By the basic principle of counting (generalized), there are 2^{n^2} possible outcomes/paths to check for existence, thus the running time is O(2^{n^2}).
Nah it should be O(2^n) because we’re using Manhattan distance here. So every path from start to end is n grids, and at every grid you choose to go right or down, hence 2^n
@@baiyuli97 I got the same answer. I drew out the call tree for N=4, and there are only 7 levels. This means there are 2N - 1 levels, and each node has 2 child nodes. So, it's O(2^n) because the constants go away. Another way to think about it is to draw out the grid and count the steps. Regardless of the order in which you traverse the tree, ultimately you will need to move N - 1 to the right and N - 1 down. If you count the start node as a step, that's 2N - 1. So, any given path will be 2N - 1 deep. I might be wrong, but I can't figure out how she got O(2^(n^2)).
So I wasn’t sure about that. The way she coded it up, you would never hit the square with 7 paths, but that is a valid path which leads me to believe that the algorithm was slightly incomplete, no? I mean, that _should_ be a valid path, but if we have checking left and right in the same recursion then we would never leave the loop. How would one handle that scenario?
How can we call a 2 parameter function with one? Shouldnt the code be more like else if (memo[n]) return memo[n]; ? Then another else for putting the calculation in the memo?
that code is not accurate, the concept is right, but the implementation is not accurate in my opinion. You could refer to www.geeksforgeeks.org/program-for-nth-fibonacci-number/ for the correct implementation
Actually she was right, it just a bit difficult to understand without seeing the full implementation. You guys can follow her full implementation here: github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2008.%20Recursion%20and%20Dynamic%20Programming/Q8_01_Triple_Step/QuestionB.java public static int countWays(int n) { int[] map = new int[n + 1]; Arrays.fill(map, -1); return countWays(n, map); } public static int countWays(int n, int[] memo) { if (n < 0) { return 0; } else if (n == 0) { return 1; } else if (memo[n] > -1) { return memo[n]; } else { memo[n] = countWays(n - 1, memo) + countWays(n - 2, memo) + countWays(n - 3, memo); return memo[n]; } }
I like the methodology for figuring out a solution, but your path traversal breaks down if you're bottlenecked by a zigzag pattern of unavailable spaces where the only way to get to the end is to go right, down, and then left before you can resume going down and to the right
What is the purpose of your if test for memo[n]. You left out the == 0 .Don’t you only want to compute it if it’s not cached and return the one you have cached.
The idea of the second one is correct, but I think it is more obvious if we start from the top left. the number in each position stands for how many paths can lead the little green guy to there. First fill matrix[0][i] (i.e. row0) and matrix[j][0] (i.e. col0) with 1 if there is no barricade, if there is, fill them with 0; since the little green guy can only move to the right or down at each step, so the value of the inner matrix, should be the sum of the matrix[i-1][j] + matrix[i][j-1] 1 1 1 1 1 1 1 1 1 2 X 1 2 3 X 1 1 3 3 4 X 3 3 4 X 3 X 4 4 X 3 7 0 3 X 4 8 8 11 18 0 3 3 X X 8 X 18 0 X 3 3 3 X 0 18 0 0 3 6 9 9 9 27
Nice algorithm, I didn't hear about the requirement that could only move to the right or down so now it makes sense to me. Without that requirement, how do you think the algorithm would be?
Awesome tutorials but I think the example for DP might be improved a bit. From the given example of dynamic programming for the Fibonacci numbers is not obvious what should be the memo[] length. I think the more simpler for understanding example is to use a HashMap. static HashMap memo = new HashMap(); static int fibonachiDp(int n) { if (n == 1 || n == 2) { return 1; } if (memo.containsKey(n)) { return memo.get(n); } else { memo.put(n, fibonachiDp(n - 1) + fibonachiDp(n - 2)); return memo.get(n); } }
Memo length is n. Your code is elegant but unless you can guarantee that your hash table operations work in constant time, her implementation is faster. Note: hash can be guaranteed to be work on constant time with load factor and uniform distribution of keys but the constant is usually large.
8:18 Why just one path? There are three blank cells in the second-to-last row which create more paths. I think the rule is: can't go up or left. I think you didn't mention that rule. Aslo, i think you didn't mention why diags are disallowed. I assume the rule is you can only increment row or column for a step, not both.
If you can only move right and down, then the path on the left most starting at 7 [4][0] to [7][0] downward including that 1 [7][1] is impossible. Same with the 2 [6][6] right at the end. You just cannot get to those squares.
Yes, also having a matrix that looks like this (where 0 means empty space, X means blocked, S start and E end) would be impossible, when there is clearly a path: S X 0 0 0 0 X 0 X 0 0 0 0 X E
In the dynamic programming approach, I think we can have only O(n) space complexity, since we only need to store the values in the current row in the grid and the one below it.
at 8:33 that cell should have zero paths... since the block above and to the left are both blocked off, there is no way for the little man to ever stand on that square?!
Is this code correct? I do not happen to know what language or pseudo language is intended. Written in video .... if (memo[n]). Should that be corrected to ... if (memo[n] < 0) ? .. It seems you would update the value if it does not have a value > 0. The default value is not specified. Should the video be annotated?
I always get confused on logic that increments multiple parameters in counter functions in such cases as she just showed at 06:00 she returns the sum of CountPaths(grid, row+1, col) and countPaths(grid, row, col+1); My bad habit of thinking is I have the tendency is to want to write return CountPaths(grid, row+1, col+1). Even after learning thats not correct.. for some damn reason my mind keeps thinking thats how it should be done. Such a bad habit I have. As if code was that simple.. hehe
at 10:24... the first column to the left after the pink square all have 0 paths; because you can only go to the right and down only so you can't go left .
That problem is fairly similar to the fibonacci problem, and you can model it in the same way as a binary tree. It's binary because we call the function recursively twice in each iteration. Since you have to traverse the entire tree, then we have O(2^(time complexity for one cell)). The algorithm to compute the number of paths from any cell to the destination for the simple, brute-force algorithm is O(n^2), since it has to traverse the whole grid and sum up paths as it goes. Remember, this is with no memoization, so it does the same work over and over again. Therefore, the final time complexity is O(2^(n^2)). It's a good example of how much better the memoized version is. It only has to traverse the grid once. The rest is just constant time lookups.
First case, with recursion, we run two parallel paths to find the distance. Move Right, Move Down (total 2 counts) times all the boxes. Hence two times N^2. In second approach, If there is a 10x10 maze, we have to run the loop 100 times to fill the boxes in the matrix and find the answer. Hence it is just N^2. If we can memoize, which is to store the paths in a map, then it will save some time cost and bring it down to N^2 for the recursion approach itself.
I dunno, for the case of non-memonization: I believe it is 2^(2n) calls to the function. If you draw the recursion tree, at every level the number of nodes doubles. Now we need to find the depth of the tree. When we go down the tree either the x coordinate or y coordinate increases. Both these numbers can only increase up to n, so in 2n calls we will be at the destination. 2n depth means number of calls is \sum_{i=1 to 2n} 2^i = 2^(2n)
7:56 how did you figure out what the recursion approach does? Like i can't even wrap my head around the recursive tree especially at the end .. please reply
You need to recalculate after every fib() call. It's a recursive function. Also, fib(4) means that 4th fibonacci number, and that's 3. 0 1 1 2 3(It's start from 0 - fib(0) = 0)
Hi, I did a small program to test what she said. Here it is: class Fib{ public static void main(String args[]){ long start = System.nanoTime(); System.out.println(fib(6)); long end = System.nanoTime(); System.out.println(end-start); start = System.nanoTime(); System.out.println(fib1(6)); end = System.nanoTime(); System.out.println(end-start); } public static int fib(int n){ return fib(n, new int[n+1]); } public static int fib(int n, int[] mem){ if(n==0) return 0; else if(n==1) return 1; else if (mem[n]==0) mem[n]=fib(n-1) + fib(n-2); return mem[n]; } public static int fib1(int n){ if(n==0) return 0; else if(n==1) return 1; else return fib1(n-1) + fib1(n-2); } } I get this result: // Recursive Solution 8 295978 // Recursive Solution with memoization 8 37240 The memoization solution is almost 8 times faster.
For purposes of conceptual symmetry when partitioning space I too use y as column and x as row. Which order x and y appear in as an index for a matrix is arbitrary (column or row major order). Preserving the idea of x as the horizon is orienting for me. Are you using some kind of projection logic to resolve the inconsistency or do you just accept the x as column without question as a best practice? Also, this is a great video. Thank you.
is runtime Big O of N squared - as you describe it? or is it Big O of 2 to the Power of N Squared - as displayed on the screen? As I understand its the former.
I think you could specify more clearly that you are only moving to the right or down at the outset with that matrix problem, as there are several situations when you could move up and then down and still get to the bottom, for example with that "zero" path square.
And the two that is diagonally above the ending point. I noticed that, too. My instinct would have been to run an a* program to check if a given cell could be reached 1) from the start position and 2) could reach the end position. Just return 1 if it ever reaches the end, for each node having at most 2 connected nodes. Her way seems smarter
The whole concept is dynamic programming. Storing the result of a sub problem to a problem and reusing that answer to solve other sub problems . A problem needs to have overlapping sub problems to be a dynamic programming problem. Memozation is just a way to do a DP problem. There is also tabuoation.
For the path problem, dp solution's space complexity is actually 2(n^2) but it is admissible as (n^2) And we don't fully get rid of call stack since the method is still recursive. But since we store the values, our call stack grows up to a certain degree that is negligible. Does that what she mean at the end of the video ?
when I do return countPaths(grid, row + 1, col) + countPaths(grid, row, col + 1); I get index out of bound how / why do you not account for this? what am I missing? Thanks!
With a memoization solution, the goal is to eliminate the need to repeat calculations that have already been calculated. Initially, the solution could be broken down from path(start, end) = path(A, end) + path (B, end). These separate ones can be broken down (recursively) even further: path(A, end) = path(D, end) + path (C, end) and path(B, end) = path(C, end) + path (E, end). See here, path(C, end) is already repeated. So passing in an additional array, in this case paths[][] can store the values that have been calculated. The condition is thus necessary to check before further calculating. If paths[row][col] already has a value, then just return the value. If paths[row][col] is 0, then then value has not been calculated yet, so calculate it.
Sorry, but if you are writing in Java, why don't you use class property instead of passing the same additional parameter for every function you use. It's a proxy pattern. Also, your painting reminded me with the old days of 'minesweeper game on windows 2000', thanks *_*
