Coding Problem 1

-
      Number of Ways to Climb the Stairs 
                                                      asked by Amazon

Ques. There is a Staircase with N steps, and you can climb only certain number of steps at a time given in the list. Write the function which can return the total number of unique ways to climb the staircase using only given number of steps. 

For example - If N = 4, and X = [1, 2] then there are 5 ways to climb the stair.
                        1st way = 1, 1, 1, 1
                        2nd way = 2, 1, 1
                        3rd way = 1, 2, 1
                        4th way = 1, 1, 2
                        5th way = 2, 2
In the above example you have 4 stairs and you can climb only 1 or 2 steps at a time given in list X. Take N and X as a input.
Lets code it!

Solution.  
We can solve it using recursion. We take one step at a time and then repeat the same procedure for the remaining number of steps. Lets solve it for the given example first -

n = 4
def staircase(n):
      if n<=1:
           return 1
      return staircase(n-1) + staircase(n-2)

So what we are doing here is first we reduce the 1 and 2 steps from the original number of steps and call the same procedure for remaining steps simultaneously. Now if we reached only 1 remaining step or less then we can have only one option to climb it and return 1. Thats our base condition.
Now we can generalize this method for any number of given steps. Suppose in X we have multiple values then we can subtract each value from the total number of stairs simultaneously and call the same procedure for the remaining number of stairs. We will take X in the form of list. We will enter the number using space then split it and add them to the list.

N = int(input("Enter the total number of stairs: "))
X = [int(i) for i in input("enter the number of steps at a time: ").split()]
print("X is: ", X)

def staircase(N, X):
        if N < 0:
            return 0
        elif N == 0:
            return 1
        else:
            return sum(staircase(N-x, X) for x in X)   # here we are taking each value from X and reducing them from total number of stairs and calling same procedure for remaining number of stairs

print("Total number of ways are: {0}".format(staircase(N, X)))

Output : Enter total number of stairs: 4
                   enter the number of steps at a time: 1 3 5
                   X is: [1, 3, 5]
                   Total number of ways are: 3

Explanation - Ways are = [1, 1, 1, 1], [1, 3], [3, 1]. There will be no use of 5 because it exceeds the total number of stairs given and similarly for [3, 3].

Comments

Post a Comment

Popular posts from this blog

Coding Problem 10

-
Image
                                Minimum Cost Required                                                        asked by Facebook Ques. A builder is looking to build a row of N houses that can be of K different colors. He has a goal of minimizing cost while ensuring that no two neighbouring houses are of same color. Given an N by K matrix where the nth row and kth column represents the cost to build the nth house with kth color return the minimum cost which achieves this goal. Solution.   Suppose we have cost matrix like this - [ [2, 1, 1],   [1, 10, 3],   [1, 2, 100]  ] Each row represents the house and each column represents the color so the values are the cost of painting the color for a house. Since we know that indexes starts from 0 so cost of pain...
Read more

Coding Problem 3

-
             Sum of Numbers in List                                                      asked by Google Ques. Given a list of numbers and a integer K return whether any two numbers from the list will add upto K or not. For example - Given list is [10, 15, 3, 7] and K = 17, then return True because 10 + 7 = 17. Solution.   So basically we have to find the two numbers that are present in the list and sum of both is equal to K. So we can simply run two loops on the list and check each pair of number if they are equal to K or not. This method is Brute-force and complexity is O(n^2). What we can do here is run the loop over the list and then subtract that number from the target and check whether the remaining number is present in the list or not. Lets see the code  def find_numbers(inp_list, K):    ...
Read more

Coding Problem 9

-
                                    Maximum in Subarray                                                          asked by Google Ques. Given an array of integers and a number k, where 1<= k <= length of array, compute the maximum values of each subarray of length k. For example - given array = [10, 5, 2, 7, 8, 7] and k = 3, we should get [10, 7, 8, 8], since  10 = max(10, 5, 2) 7 = max(5, 2, 7) 8 = max(2, 7, 8) 8 = max(7, 8, 7) Solution. This question has a simple solution. In array we will create a window which consist of number of elements equal to k and can find the maximum among them and append that in output list. But while traversing the array we have to keep something very important in mind. We will not traverse from index 0 to nth index...
Read more