Coding Problem 2

-
                Decode number to string
                                                    asked by facebook

Ques. Given any number you have to find the number of ways to decode the number like if you are given the number 12 then it can be decode as "ab" where a=1 and b=2 and "l" where l=12 so the total number of ways to decoed 12 is 2 as "ab" and "l". 

Solution.
We can map our alphabets to the number from 1 to 26. If we have empty string or a single digit number then we can have only one way to decode it but for two or more than 2 digit numbe we have to check each number plus the pair of numbers. Now here we can simplify it as we can have number from 0 to 9 and we have to check only those pair of numbers which are less than 27 as we have 26 alphabets only. 
Suppose we have input as "4" then we can decode it as "d" i.e. only 1 way. If we have empty string (" ") then also we can decode it as 1 way. Now if we have our input starting from 0 then we can not decode it and return 0 because there is no mapped alphabets to digit 0. 
Now think about larger input like "12345". Now we can decode like - 
1 mapped to "a" so "a"+decode("2345") and we can also decode "l"=12 so "l"+decode(345). So now we can write it as - 
num_ways("12345") = num_ways("2345") + num_ways("345"). So we can peform recursion also. Now we can perform recursion and we have two base conditions. In base conditions we have check the null string and string started from 0.
Now let's see the code and clear everything -

def decode(n, k):
        # checking the length 
        if k == 0:
                return 1

        # take the first number of the input string passed to the function and check if it is zero
        s = len(n) - k
        if n[s] == '0':
                return 0

        # take first digit mapped to the character and call function for remaining input string
        result = decode(n, k-1)

        # checking first two digit and calling function for remaining input
        if k >= 2 and int(n[s:s+2]) <= 26:
                result += helper(n, k-2)
        return result

n = input("enter the number: ")
print("No. of ways to decode are {0} ".format(decode(n, len(n))))

Output:  enter the number: 12
                  No. of ways to decode are 2

                  enter the number: 12345
                  No. of ways to decode are 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