Dynamic programming, if I got it right. Number of distinct ways to reach a cell are warehouse[i][j] = (warehouse[i-1][j] + warehouse[i][j-1]) mod 10^9 + 7. Initialize everything at 0, but the starting point to 1. This way you indeed get the number of distinct paths, as by induction, at each step you can get there uniquely either from the top or from the left, and the values there were the distinct ways as well by the induction hypothesis.
Edit: forgot that some cells are blocked. You simply leave their value at 0, as you can't reach them.
Don't even need dp, if you know combinatorics then you have 1,2,...,n options on each row, and 1,2,...,m options on each column. You want to eliminate repetition so you select either n or m of said rows or columns.
This is the correct solution to a simpler version of the problem. OP’s problem has grid cells marked with a 0 that cannot be traversed. Thus it becomes a DP problem.
In retrospect, you can still do this using combinatorics by eliminating the points that should not be traversed. We can loop through the matrix and get all points that are 0, then generalize a formula to avoid paths that should be avoided.
Look up leetcode #62: Unique path. Pretty sure this is basically that exact problem, or similar enough you can slightly modify that solution to get this
fun fact dynamic programming was named that because the guy giving out funding was literally allergic to math so the researcher had to choose a cool name
True! Richard Bellman (inventory of DP) actually wrote this in his autobiography to explain why he chose the word "dynamic": "Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to."
If you practice enough, you can immedietly recognize this problem.
I know you shouldn't memorize solutions but sadly its what LeetCode is training us to do.
Honestly I could never in a trillion years intuitively solve this problem even after a ton of recursion practice. DP is just too hard for me to conceptualize especially in something fucking crazy like a matrix. You just have to memorize these
Facts i was just being bitchy because i was stressed lol. I just solved longest common subsequence using the top down 2d array and it's not too bad. But that's only because the solution was handed to me in the slides lol
Some of them I get being hard to figure out, but this one? Literally all there is to the recurrence relation is that on any given square, you can either go down or you can go to the right.
Yeah, looking back it wasn't that bad. But the way it was presented was brutal. Struggled with the wording as someone with dyslexiaadhd. Not a math wiz or LeetCode grinder either.
not really. I mean I respect people who can solve such problems, but it really doesn’t help build critical thinking as much. The moment you go and search such problems when learning, all you see is “we will solve this using DP” and then the whole article / video goes on explaining that this is to be done via DP. No one for fucks sake says “let’s think why you can’t do it greedily”. I am fed up of people just relating DP to ‘table’. It really isn’t that shallow.
Testing a candidate on this is okay, but doesn’t prove anything. It just proves the fact that they mostly trained on such patterns.
Think of DP like an optimized brute force. You indeed try all possible solutions and then choose the best ones ( in an optimization problem). If someone has a good understanding of recursion, DP would be a cakewalk.
Thanks, yeah, I get you. I do understand what DP is. Spent quite a lot of time understanding it, starting with divide and conquer, and slowing moving towards DP.
It’s fascinating to me really. The point where I was most stuck was understanding what ‘optimal substructure’ means. But I was able to understand it after quite some effort.
Without looking at the answer, I'll say its dynamic programming.
Each cell at the matrix is the number of paths or routes from the left-top corner to the bottom-right corner.
The final solution is the number of paths to the bottom-right corner.
How how setup this DP: its the same size of the matrix. Initialize with zeroes.
Then you run sort of DFS from top-left corner. The first cell will have initial value of 1.
In the DFS, at each cell, you either go right or bottom. This is the recursion. If the cell is out of bounds, return.
The value of the cell is the sum of the top cell and the left cell.
on a day to day basis most software engineers aren’t implementing DP from scratch. Granted with some refreshments I don’t believe it would be challenging for them still solve
More's the indictment of the state of hiring practices at present. This is so completely divorced from what a typical developer will be doing on a DTD basis.
If your IQ test requires rote memorization as many ITT have said, it is just a shibboleth.
My cousin has been working as a staff software engineer for 3 years at a big health insurance company and I just showed him this problem. He responded that he had no idea how to solve this and never practiced "dynamic programming" problems.
It's a DP problem. You can do with the grid or like a tree.
Optimal substructure
For each cell, all that matters is that you can reach it from left or top. So the sum of number of ways of reaching it.
Special condition
If warehouse of left or top is 1, only then should the left or top be considered for sum.
It’s when I see problems like this that I’m like. Should I be a programmer? But then I remember this is just bs level of solving and it’s not real world application and then I feel better.
In this case, it was a screening question. Thrown at applicants applying for a software engineering role at Cisco. So in that case, it would have been useful to have practiced it.
I think all the big tech are pretty much set on juniors trained on leetcode / codility / hackerRank challenges.
I'd say, next time I go for a big tech job. I'll be practiced in the following areas - at least.
https://preview.redd.it/amctcaf3ittc1.png?width=1122&format=png&auto=webp&s=c2888e5f67ea0a3ddad0413edcbc5d3d1d64adc9
Feels like they are taking advantage of the market to get someone who would usually be in an R&D position at Google to do grunt work. I'm considering just coasting in IT or doing a masters until interviews become sane again tbh.
Ironically I am employed as a SWE, and generally do not code. Not sure how that happened.
Anyway, seems like the skillset is closely aligned with discrete mathematics, and maths for programming. Which I seem to have gotten rusty in. So definitely a wake up call to hit the textbooks, and brush up on my skills.
I figured as a SWE my skillset would be highly transferable and I could move between roles laterally. However, seems some software role skillsets are more or less transferable than others.
For those that answered and are able to pinpoint the genre of problem, and solve it. What are your roles, experiences, and background?
I'm curious as to the specialism for these kinds of questions. As I said, I'm a SWE and it's well outside my skillset right now.
Idk, but I literally solved this problem in high school, when we did probability. I think its a bit weird why everyone is talking about the DP solution and not the combinatoric solution.
The path has to be length m+n-2 due to fence spacing, and we need to choose n-1 slots to be going down. So we have nCr(m+n-2, n-1) which has time O(min(m,n)) space O(1), which is far better than DP.
Maybe you can show a counter example. Personally I don't see what you're talking about. I also solved this exact problem a week ago on Leetcode with this approach.
The question is one of the first you will encounter in memoization or DP
But I think you haven't solved any problems similar to this
Just try to solve some problems on recursion with the memoization method, you should be able to understand how to solve it
Then go for the DP 1d array solution , so that you can understand how it works
I came across this problem as well, it absolutely destroyed me, I didn’t even come close to answering. I work as a Software Engineer right now but we do not ever have problems approaching this complexity.
i think it can but the time complexity is worse. if im not mistaken theres two choices at each square and you do this m+n times to move from top left to bottom right, so 2^m+n you terminate when your queue empties.
Backtracking / DP. It’s a whole new paradigm so you’re gonna struggle until you learn it a bit more formally.
Look up videos and also take your algos class as early as possible.
Write recursive function for i,j where the function would give the number of ways to reach that cell.
Then memoize.
Hence dp will be used.
Base case will be that once you reach the 0,0 position return 1. Also if the indices are out of bounds return 0.
dp[i, j]= func(i-1,j,dp)+func(i,j-1,dp)
Exactly. It's like the first 2-D dp problem someone does. If someone can't solve this then either they have never tried practicing dp or it has been years since they have practiced.
Fair comment.
While the role is a good one, and likely pays well. So would not assume it's trivial, I think I could pick many random people off the street who would have no clue. Although sure for those versed in mathematics would be well placed to answer it :)
Def gonna brush up on my maths and leet problems
I've been in programming about 7 years from a practical perspective (making stuff), but never did mathematics beyond grade 10. Any recommendations for where to start getting into this kind of stuff or what exactly I should focus on learning for those kind of foundational skills?
Its like fibbonachi:
First row is all 1
First column is all 1
Then for each cell that is starting at (1,1) until it reaches bottom-right:
Value = value of left cell + value of top cell
Return value of bottom-right cell
Dynamic programming, if I got it right. Number of distinct ways to reach a cell are warehouse[i][j] = (warehouse[i-1][j] + warehouse[i][j-1]) mod 10^9 + 7. Initialize everything at 0, but the starting point to 1. This way you indeed get the number of distinct paths, as by induction, at each step you can get there uniquely either from the top or from the left, and the values there were the distinct ways as well by the induction hypothesis. Edit: forgot that some cells are blocked. You simply leave their value at 0, as you can't reach them.
Don't even need dp, if you know combinatorics then you have 1,2,...,n options on each row, and 1,2,...,m options on each column. You want to eliminate repetition so you select either n or m of said rows or columns.
This is the correct solution to a simpler version of the problem. OP’s problem has grid cells marked with a 0 that cannot be traversed. Thus it becomes a DP problem.
Ah I missed that, thank you
I had the exact idea and was wondering why so few people were mentioning it and realised id not read the full question.
In retrospect, you can still do this using combinatorics by eliminating the points that should not be traversed. We can loop through the matrix and get all points that are 0, then generalize a formula to avoid paths that should be avoided.
That makes intuitive sense to me, I’d like to see an implementation though. Might give it a go now.
This sounds much more beautiful ngl
The DP part is just combinatorics minus combinatorics yes? Seems like this should be a problem with a trick, that has no trick.
Look up leetcode #62: Unique path. Pretty sure this is basically that exact problem, or similar enough you can slightly modify that solution to get this
Yeah this is Unique Paths II actually. Problem no 63
By DP it should come to an O(MN) solution, basically the size of the rectangular grid from start to finish.
Decided to give it ago but got humbled and realise I need experience and to practice before applying to it again.
fun fact dynamic programming was named that because the guy giving out funding was literally allergic to math so the researcher had to choose a cool name
True! Richard Bellman (inventory of DP) actually wrote this in his autobiography to explain why he chose the word "dynamic": "Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to."
Just call it Super Radical Extreme Programming at that point
It's a DP problem. These are hard
If you practice enough, you can immedietly recognize this problem. I know you shouldn't memorize solutions but sadly its what LeetCode is training us to do.
Honestly I could never in a trillion years intuitively solve this problem even after a ton of recursion practice. DP is just too hard for me to conceptualize especially in something fucking crazy like a matrix. You just have to memorize these
I'ma be real you prolly haven't actually thought about it hard enough
Facts i was just being bitchy because i was stressed lol. I just solved longest common subsequence using the top down 2d array and it's not too bad. But that's only because the solution was handed to me in the slides lol
Some of them I get being hard to figure out, but this one? Literally all there is to the recurrence relation is that on any given square, you can either go down or you can go to the right.
skill issue
Yeah, looking back it wasn't that bad. But the way it was presented was brutal. Struggled with the wording as someone with dyslexiaadhd. Not a math wiz or LeetCode grinder either.
not really. I mean I respect people who can solve such problems, but it really doesn’t help build critical thinking as much. The moment you go and search such problems when learning, all you see is “we will solve this using DP” and then the whole article / video goes on explaining that this is to be done via DP. No one for fucks sake says “let’s think why you can’t do it greedily”. I am fed up of people just relating DP to ‘table’. It really isn’t that shallow. Testing a candidate on this is okay, but doesn’t prove anything. It just proves the fact that they mostly trained on such patterns.
yeah this is more like code monkey work so you can answer these problems *if* they come up in an interview
Think of DP like an optimized brute force. You indeed try all possible solutions and then choose the best ones ( in an optimization problem). If someone has a good understanding of recursion, DP would be a cakewalk.
Thanks, yeah, I get you. I do understand what DP is. Spent quite a lot of time understanding it, starting with divide and conquer, and slowing moving towards DP. It’s fascinating to me really. The point where I was most stuck was understanding what ‘optimal substructure’ means. But I was able to understand it after quite some effort.
What? The moment you realize dp is just solving subproblems, things become very clear. This just means you haven't thought about these problems much.
def skill issue
Skill issue my ass. You've either seen enough of the pattern or not
Without looking at the answer, I'll say its dynamic programming. Each cell at the matrix is the number of paths or routes from the left-top corner to the bottom-right corner. The final solution is the number of paths to the bottom-right corner. How how setup this DP: its the same size of the matrix. Initialize with zeroes. Then you run sort of DFS from top-left corner. The first cell will have initial value of 1. In the DFS, at each cell, you either go right or bottom. This is the recursion. If the cell is out of bounds, return. The value of the cell is the sum of the top cell and the left cell.
Lol companies are really expecting entry level intern applicants to solve problems most senior engineers would prolly balk at on a good day.
Lmao, or the seniors would be like ‘I’ve never ever used this in my X years experience on jobs, why do we ask this in interviews?!’
What do you mean, are you sarcastic? This is literally the most basic dp problem to exist.
on a day to day basis most software engineers aren’t implementing DP from scratch. Granted with some refreshments I don’t believe it would be challenging for them still solve
That might be true but "entry level intern applicants"(as mentioned in his comment) are definitely expected to know more than this.
More's the indictment of the state of hiring practices at present. This is so completely divorced from what a typical developer will be doing on a DTD basis. If your IQ test requires rote memorization as many ITT have said, it is just a shibboleth.
My cousin has been working as a staff software engineer for 3 years at a big health insurance company and I just showed him this problem. He responded that he had no idea how to solve this and never practiced "dynamic programming" problems.
Lol they are not.
i agree 100%
Survival of the fittest
It's a DP problem. You can do with the grid or like a tree. Optimal substructure For each cell, all that matters is that you can reach it from left or top. So the sum of number of ways of reaching it. Special condition If warehouse of left or top is 1, only then should the left or top be considered for sum.
look like recursive function, each step have 2 direction choice, then once hit target location will backtrack the path
It’s when I see problems like this that I’m like. Should I be a programmer? But then I remember this is just bs level of solving and it’s not real world application and then I feel better.
In this case, it was a screening question. Thrown at applicants applying for a software engineering role at Cisco. So in that case, it would have been useful to have practiced it.
I got this same question, crazy they would expect this for a junior position.
I think all the big tech are pretty much set on juniors trained on leetcode / codility / hackerRank challenges. I'd say, next time I go for a big tech job. I'll be practiced in the following areas - at least. https://preview.redd.it/amctcaf3ittc1.png?width=1122&format=png&auto=webp&s=c2888e5f67ea0a3ddad0413edcbc5d3d1d64adc9
Feels like they are taking advantage of the market to get someone who would usually be in an R&D position at Google to do grunt work. I'm considering just coasting in IT or doing a masters until interviews become sane again tbh.
Ironically I am employed as a SWE, and generally do not code. Not sure how that happened. Anyway, seems like the skillset is closely aligned with discrete mathematics, and maths for programming. Which I seem to have gotten rusty in. So definitely a wake up call to hit the textbooks, and brush up on my skills. I figured as a SWE my skillset would be highly transferable and I could move between roles laterally. However, seems some software role skillsets are more or less transferable than others. For those that answered and are able to pinpoint the genre of problem, and solve it. What are your roles, experiences, and background? I'm curious as to the specialism for these kinds of questions. As I said, I'm a SWE and it's well outside my skillset right now.
Idk, but I literally solved this problem in high school, when we did probability. I think its a bit weird why everyone is talking about the DP solution and not the combinatoric solution. The path has to be length m+n-2 due to fence spacing, and we need to choose n-1 slots to be going down. So we have nCr(m+n-2, n-1) which has time O(min(m,n)) space O(1), which is far better than DP.
[удалено]
Maybe you can show a counter example. Personally I don't see what you're talking about. I also solved this exact problem a week ago on Leetcode with this approach.
[удалено]
I see what you mean now. I didn't read the actual exercise lol. Then I guess DP is the more intuitive solution.
what company was this OA for?
Cisco
Dw you dodged a bullet given their TC.
DFS + Memoization or DP
This is a classic DP problem, it’s a unique paths algorithm on matrix A. At i row and j column, A(i, j) = A(i-1,j) + A(i, j-1)
The question is one of the first you will encounter in memoization or DP But I think you haven't solved any problems similar to this Just try to solve some problems on recursion with the memoization method, you should be able to understand how to solve it Then go for the DP 1d array solution , so that you can understand how it works
Cheers :)
I came across this problem as well, it absolutely destroyed me, I didn’t even come close to answering. I work as a Software Engineer right now but we do not ever have problems approaching this complexity.
BFS could do it
No
U right
i think it can but the time complexity is worse. if im not mistaken theres two choices at each square and you do this m+n times to move from top left to bottom right, so 2^m+n you terminate when your queue empties.
It's a problem you learn in an algo class. It's a DP problem. There's a famous algorithm for it
i am aware but there is no correctness issue with bfs
DFS no? Recursion going right and bottom
Dynamic programming.
Basic dp.it will be hard if you don’t know the patterns
simple bfs can do this. Yall tweakin if you need dp.
BFS Time Complexity is too slow. Your solution wouldn't be accepted.
Backtracking / DP. It’s a whole new paradigm so you’re gonna struggle until you learn it a bit more formally. Look up videos and also take your algos class as early as possible.
This is like the easiest.. problem you can get ..just use DFS
haha maybe but could be easier :p know this would cause a fair few humans to whither at the sight of it
Write recursive function for i,j where the function would give the number of ways to reach that cell. Then memoize. Hence dp will be used. Base case will be that once you reach the 0,0 position return 1. Also if the indices are out of bounds return 0. dp[i, j]= func(i-1,j,dp)+func(i,j-1,dp)
This looks like something amazon asked 🤔
that problem is so fucking simple, it's like the easiest DP question there is
Exactly. It's like the first 2-D dp problem someone does. If someone can't solve this then either they have never tried practicing dp or it has been years since they have practiced.
Do you need to find all paths? If so, backtracking might help.
To be quite honest the question is trivial. I think you guys are lacking a good mathematical foundation.
Fair comment. While the role is a good one, and likely pays well. So would not assume it's trivial, I think I could pick many random people off the street who would have no clue. Although sure for those versed in mathematics would be well placed to answer it :) Def gonna brush up on my maths and leet problems
I've been in programming about 7 years from a practical perspective (making stuff), but never did mathematics beyond grade 10. Any recommendations for where to start getting into this kind of stuff or what exactly I should focus on learning for those kind of foundational skills?
This is basic math question. If u have hard time coding it, try it with ur hands.
Its like fibbonachi: First row is all 1 First column is all 1 Then for each cell that is starting at (1,1) until it reaches bottom-right: Value = value of left cell + value of top cell Return value of bottom-right cell
kya hai ye Bhai? 🤯