hey everyone today I have a coding
interview question and it's a question
that's being asked by Amazon among other
companies and in this problem you're
given a staircase with n steps so if the
given n is for your staircase will have
four steps and that means that you can
go from the bottom to the top in four
steps so that's one two three and four
steps and suppose that you can only take
one or two steps at a time so if you
start at the bottom you can only go from
the bottom to here or here and if you
decide to go here you can only go from
here to here or to here and the problem
here is writing a function called num
ways which takes the positive integer n
and returns the number of ways you can
go from the bottom to the top so if the
given n is 2 instead of 4 there's only 2
ways of going from the bottom to the top
the first way would be taking one step
at a time and the second way would be
taking two steps from the bottom to the
top so your function num ways should
return to if the given n is 2 and once
you're done with this problem
think about this variation what if in
addition to n you're also given X which
is a set of positive integers and this
is going to be the set of numbers of
steps you're allowed to take instead of
just one or two steps so in this
particular case you can go from the
bottom to over here by taking one step
at a time
or you can go from the bottom to over
here by taking one to three steps but
you're not allowed to take two steps
here because two is not in the set and
you're not allowed to take five steps
either here because we don't have enough
steps for five steps so maybe pause the
video right here if you want to practice
and try solving the first problem as
well as this variation of the problem
okay here's how I would think about it
I'm gonna go a little bit slowly here so
I'm gonna put an outline of this video
with some timestamps in the description
so you don't have to watch
whole thing if you don't want to now I
would first think about some simple
cases for example when n is 2 or 1 like
we saw earlier when n is 2 there are
only two ways to get to the top from
bottom
the first way was taking one step at a
time and the second way was taking two
steps and if you label each of those
steps you'll be able to write down each
of those paths so you might label the
first step the bottom zero and then this
step one and then the top two then
you'll have these two paths going from 0
to 1 to 2 or going from 0 to 2 and I'm
just going to write down 2 here to show
that we have two paths here or two ways
of going from the bottom to the top and
we can do the same thing for when n is
equal to 1 and the only way here for us
to go from the bottom to the top is just
by taking one step or going from zero
let's say this step right here to one so
that's this path right here 0 to 1 and
then I'm going to write down here 1 as
well to show that we have only one path
and let's do the same thing for when N
equals 3 first of all let's label these
stairs as 0 1 2 & 3 the first path we
can immediately find is this 1 0 1 2 and
then 3 let me write it down here that's
the one right here
and then the next one might be 0 1 and
then 3 that's the one right here and
then we also have 0 2 2 2 3 and that's
the one right here so here we have 3
paths so that's what your function
should return if you're given n is 3 and
you can do the same thing for when n is
equal to 4 as well I'm just gonna skip
over this just the same time but you'll
find that there are 5 paths here ok so
the question here is can you find any
pattern for what we've found so far it's
actually kind of hard if you're not used
to this kind of thing but
the easiest way to find a good pattern
here is by visually so let's go back to
when n is equal to 3 in that case you
ask yourself how can we go from step 0
to step 3 and to answer that question
you need to ask yourself should I go
over just one step or two steps from the
bottom and if we decided to take just
one step from the bottom then you needed
to ask yourself how can we go from step
one to step three but if you look at
only this part up here that's actually
just a staircase with two steps so when
you ask yourself how can we go from step
one to step three that's actually a
problem that we've already solved when n
is equal to two because in this case two
we ask ourselves how can we go from step
zero to step two or go over a staircase
of two steps and I think this pattern is
gonna be more clear once we relabeled
these steps so let's label these steps
not from the bottom but from the top
instead so the top step is gonna be 0
here and then this step is gonna be 1 2
and this last step the bottom step is
gonna be called 3 and once we real able
all the other steps as well these steps
is gonna look like this so with this
relabeling the top step 4 when n is
equal to 1 becomes 0 and the bottom step
is going to be 1 and the same thing for
when n is equal to 2 and with that
labeling scheme these are the paths that
we have so instead of 0 1 for 1 and is
equal to 1 we have 1 0 because we go
from 1 to 0 and we can do the same thing
for 1 n is equal to 3 as well the first
path we can find is 3 2 1 0 and then the
next one is 3 2 0 and so on ok now let's
go back to what we did earlier going
back to you know when we were on the
ground when n is equal to 3 then you
need to ask yourself should I
take just one step or two steps right
and if we decide to take one step then
you have three two as the first part of
this path and from there of course you
need to ask yourself how can we go from
Step two to step zero and that's exactly
the same question that we've already
answered when n is equal to two going
from step two to step zero so if you
examine the rest of the paths you know
this path to one zero and to zero
they're exactly the same as the paths we
saw when n is equal to two and you can
do a similar analysis if you decide to
go from three to one as well in that
case we have three one as the first part
of the path and from there you need to
ask yourself how can we go from step one
to zero and that's exactly the same
question all right this is kind of silly
but it's exactly the same as what we
asked earlier when n is equal to one and
in that case the rest of the path is
just one there and that's of course
exactly the same as the path we had for
when and is equal to one so basically
what we found here is that for when n is
equal to three these first two paths is
the same as the path we had for when n
is equal to 2 and the last path is the
same as the path we had for when n is
equal to 1 and based on that we can
write that numbers of 3 or the number of
ways of climbing over a staircase of 3
steps is equal to num ways of 2 + num
ways of 1 and actually in general this
should be num ways of n is equal to num
ways of n minus 1 plus 9 ways of n minus
2 so you can check that for example for
when n is equal to 4 num ways of 4 as
you can see is 5 here and that's num
ways of 3 which is 3 + num ways of 2
which is 2 so 2 plus 3 which is 5 here
you might say what about when n is equal
to 0
I would actually argue that in that case
numbers of zero should be one and here's
how I think about it it's sort of like
asking yourself how many ways are there
to climb over a staircase of zero steps
or how can we get from step they're
right here to step zero which is also
the top well let's say you're standing
on step zero at the bottom and then boom
you're at the top step zero so this is
kind of silly but the only way to get
from step zero to step zero is just zero
this path right here so we only have one
and that's why num ways of zero should
be one anyway let's now think about how
we can use this recursive relationship
to write some code ok so this is the
recursive relationship that we found
earlier and to find a recursive function
with that we need to find base cases one
choice would be to choose one and two
but I would argue that the simpler
choice is these two zero and one and
with that we'll have these base cases
none ways of zero and none ways of one
being equal to one and based on that we
can write our recursive function we're
gonna call it num ways of course it's
gonna take and a positive integer and
then let's first take care of the base
case
that's one N is equal to zero or one
we're just gonna return one and if
that's not the case or else we're gonna
return the sum of numbers n minus 1 and
num ways and minus 2 now examining this
function you probably see that this is
just like the Fibonacci sequence and you
might also see that this is not the most
efficient way to find num ways to see
why let's just quickly examine when n is
equal to 4 or when you call n wo 4 or
num ways of 4 to find and return value
of n w4 you need to first find the
return values for n w3 + NW of 2 and to
compute NW of 3 or num ways of 3 you
need to first compute and W 2 and n W 1
and so on and just looking at this tree
you see that n W of 2
is repeated twice and that's wasteful
and it's wasteful because we need to
repeat the same computation twice to
find the value of NW of two and this
problem gets worse and worse as n
becomes larger and larger so let's see
how we can fix that we can fix it with
dynamic programming and one way to
implement it would be with a bottom-up
approach so let me just quickly explain
the idea here for the bottom-up approach
we're gonna use this table of N and num
ways of N and at the beginning we don't
have the values for num ways of N and
let's say as an example we're trying to
find the value of num ways of 4 so n is
equal to 4 in that case we'll first
construct an array of length 5 or length
n plus 1 and then we'll know right away
that the first two elements of that
array should be 1 because that's the
base case that we have here and after
that we'll find a value for each element
by adding up the two previous elements
so 1 plus 1 equals 2 and then 1 plus 2
equals 3 and so on and once we find the
value that we were looking for which is
5 in this case we'll just return it from
our function and that approach is going
to look like this in code we're gonna
call this function num ways bottom up
and it's gonna take a positive integer n
and first of all we're gonna take care
of the base cases when n is equal to 0
or 1
we're gonna return 1 and otherwise or if
we haven't returned yet we're gonna
initialize an array an integer array of
length n plus 1 and then we're going to
assign it to a variable called num and
then we're gonna set the first two
numbers of this array num 0 and nums 1
to 1 and after that we're gonna run a
for loop for i from two that's two right
here up to n that's for example 4 and
for each of those i Nam's i or the
current element that we're examining
should be the sum of the
previous two elements noms I minus one
and noms I minus two and after we find
the last number of this array or noms of
n we're just gonna return that now this
function works just fine but if you want
to make it more efficient or if you want
to save more space there's a way to do
that so when you're running this for
loop when I is equal to for example 3
right here to find num ways of 3 right
here you don't need all the elements in
the array
all you need is the two previous
elements so basically you only need to
store only two elements at a time as you
go through this for loop so you can
store these two elements and then these
two elements and these two elements and
so and that way you can save some space
so anyway this is my solution to the
first problem let's take a look at the
variation I told you about as I
explained earlier in this variation of
the problem you're given n as well as X
which is a set of numbers of steps you
can take at a time and let's solve this
problem recursively as well and we're
gonna base our recursive solution to
this problem on the recursive solution
that we saw earlier to the previous
problem so we have the function we saw
earlier num ways the only difference
from what we saw earlier is the fact
that we don't have an else statement and
with the same kind of argument that I
used earlier you should be able to find
this recursive relationship num ways of
n is the sum of numbers of n minus 1 and
numbers of animals 3 and num ways of n
minus 5 if the given X is this one 1 3 &
5 so based on this function and based on
this recursive relationship your
intuition might say that your function
let's call it num ways X should look
like this again I'm assuming that X is 1
3 5 4 now and this says the base case
when n is equal to 0 we should return 1
and otherwise we should return the sum
of numbers of n minus 1 and minus 3 and
n minus 5 but
this function is not gonna work so when
n is for example two num ways of n minus
3 would be num ways of minus 1 and none
ways of minus 1 isn't defined well so
let's see how we can fix it I would fix
it by only adding num ways of n minus 3
to the total that we're gonna return
only when n minus 3 is greater than or
equal to 0 because only when n minus 3
is greater than or equal to 0 num ways
of n minus 3 is well-defined and we're
gonna do the same thing for num ways of
n minus 5 as well and let's see how that
might look like in code here I'm gonna
call this new function num ways X as
well of course it's going to take a
positive integer n and returns the
number of ways you can climb over a
staircase of n steps will first take
care of the base case when n is equal to
0 we're going to return 1 and then we're
gonna define a new variable called total
we're going to assign 0 to it and after
that we're gonna run a for loop for each
I in this set 1 3 5 for example and only
when n minus I is greater than or equal
to 0 we're gonna add num ways X of n
minus I to total and at the end of this
function we'll just return total okay so
this function works but just like we saw
earlier this is not the most efficient
way to do it so let's see how we can fix
it with a bottom-up approach again let's
call our bottom-up function num ways X
bottom-up and in this function first of
all we're gonna take care of the base
case
if n is equal to 0 we should return 1
and then just like the bottom-up
approach we saw earlier for the previous
problem we're gonna define an integer
array whose length is n plus 1 and then
we're going to assign it to nums
and we're gonna set the first element of
this array to 1 after that we're gonna
run a full loop for i from 1 up to n and
in this for loop we're gonna do pretty
much
exactly the same thing as what we did
earlier in this portion of the code so
this is just the recursive solution that
we've developed earlier so in this for
loop first of all we're gonna define a
variable called total to zero and then
we're gonna run another for loop inside
this for loop and that's gonna say for
each J in this set for example 1 3 & 5
only if I minus J is greater than or
equal to zero we're gonna add nums of I
minus J to total and nums of I minus J
here corresponds to nan weighs X of I
minus J so that's the number of ways we
can climb over a staircase of I minus J
steps and after this inner for loop for
each J we find the value of total we're
going to assign that to noms of I and
numbers of I here is the number of ways
you can climb over staircase of I steps
and then do the same thing from 1 up to
N and once we find the value of num of n
that's the answer that we're looking for
so we're just gonna return that and if
you want to modify this function so that
it works with any X any set of numbers
not just this particular set of numbers
then you just need to replace this with
X and then have this function take X as
an extra argument okay now this problem
actually came from this website called
daily coding problem it's a website
where you can get a daily coding problem
just like this one and if we want more
problems like this one I'd actually
highly recommend it it's actually a
website that's made by a friend of mine
who I used to work with at Google too
and if you use my referral link CS dojo
dot io / daily it'll let them know that
you came from here and with that link
you can get a 10% discount on their
premium subscription as well but
personally I would say that even their
free option and there are blog articles
on the site have a lot of value - anyway
thanks a lot for watching this video as
always and I'll see you in the next one