I recently gave a test on HackerRank, and submitted my answer for the following question. I passed all the test cases but company told me that the answer is not efficient, and they are not moving forward with my candidacy. I don't have a screenshot of the question, so I will explain as much as possible.Question:We have to create phone number of length 7 by the movement of knight and bishop on a keypad. The properties of the phone number:The phone number cannot start from 1 or 0.The phone number should not contain special characters.The length of the phone number should be 7.The movement of Knight and Bishop is same as on Chess. See the figure below:Your program will take input as 'knight' or 'bishop', and print out the total number of phone numbers the if knight and bishop will move on the keypad.My approach:__author__ = 'rakesh'#My approach is to convert the whole keypad into graph with nodes representing number and edges represent there is a path#exists between two nodes. This graph is an undirected graph which means it is bidirectional#Now I am going to define a dictionary with key repserenting the node(Number on Keypad) and values representing direct connection to node.#What you see below is the movement of knight represented by key value pair#It is extremely important to avoid loop in the graph otherwise it will go into infinte recursion.knight = {'1': ['6', '8'],  #movement of knight          '2': ['7', '9'],  #this is how the graph will look like for Knight with key representing the starting point and where they can go from there          '3': ['4', '8'],          '4': ['3', '9', '0'],          '6': ['1', '7', '0'],          '7': ['2', '6'],          '8': ['1', '3'],          '9': ['4', '2'],          '0': ['4', '6']         }#removed the path which will go into special characters since phone number cannot contain thatbishop = {'1': ['5', '9'],  #movement of bishop in the keypad          '2': ['4', '6'],          '3': ['5', '7'],          '4': ['2', '8'],          '5': ['1', '3', '7', '9'],  #path leading to #, * are ignored          '6': ['2', '8'],          '7': ['5', '0', '3'],          '8': ['4', '6'],          '9': ['5', '0', '1'],          '0': ['7', '9']         }def knightFindPhoneNumbers(knight, start, path=[]):  #here path basically is your phone number.    '''    :param graph:  The movement of knight    :param start: You can start from anywhere except 0 and 1    :param path:    :return: list containing all the valid numbers    '''    path = path + [start]    if len(path) == 7:  #if the total number of length of path is 7 return the path. It means we found a valid phone number        return [path] #we found one valid phone number    if not knight.has_key(start):        return []    paths = []    for node in knight[start]:        if node:            newpaths = knightFindPhoneNumbers(knight, node, path)            for newpath in newpaths:                paths.append(newpath)    return pathsdef bishopFindPhoneNumbers(bishop, start, path=[]):    '''    :param bishop:  The movement of bishop    :param start: You can start from anywhere except 0, 1. Phone numbers cannot contain these digits    :param path: capture the phone number    :return: list of all phone numbers starting from some digit    '''    path = path + [start]    if len(path) == 7:  #if the total number of lenght of digits is 7 return the path        return [path]    if not bishop.has_key(start):        return []    paths = []    for node in bishop[start]:        if node:            newpaths = bishopFindPhoneNumbers(bishop, node, path)            for newpath in newpaths:                paths.append(newpath)    return pathschessPlayer = raw_input()   #take the input from the usercount = 0if chessPlayer.strip() == 'knight':    for i in ['2', '3', '4', '5', '6', '7', '8', '9']:  #the phone number can start from 2, 3, 4, 5, 6, 7, 8, 9        for k in knightFindPhoneNumbers(knight, i):            count += 1  #print out the phone numbers    print countelif chessPlayer.strip() == 'bishop':    for i in ['2', '3', '4', '5', '6', '7', '8', '9']:   #the phone number can start from 2, 3, 4, 5, 6, 7, 8, 9        for k in bishopFindPhoneNumbers(bishop, i):  #find phone numbers start from 2, 3, 4, 5, 6, 7, 8, 9            count += 1    print countThe recruiter told me the solution is inefficient, and I am wondering if anyone could suggest improvements to my answer or a better solution.
Find total number of phone numbers formed by the movement of Knight and Bishop on keypad
python;performance;programming challenge
Counting and enumerating are two different problems.  Sometimes there is no better way to count than actually enumerating all the possible values, but that is often not the case, and this is one of those cases.To build an efficient algorithm, we are going to use dynamic programming.  We will build a 7 rows by 10 columns array.  Using zero-based indexing, the item in row r and column c is the number of phone numbers of r + 1 digits that have c as the last digit.It should be obvious that the first row of that array will befirst_row = [0, 0, 1, 1, 1, 1, 1, 1, 1, 1]and that subsequent rows can be filled out by initializing them to all zeros, and then use the adjacency graph to add the values at a given column of the previous row, to all the columns that are successors of that one in the graph.Once the array is fully filled out, the sum of the last row is the total number of numbers that can be created.  Because we only care about the sum of this last row, and each row only depends on the previous one, we only need to keep two rows of the array in memory at a time.  Putting it all together into code:def count_paths(graph, length):    this_row = [0] * 2 + [1] * 8    for row in range(1, length):        prev_row = this_row        this_row = [0] * 10        for prev, nexts in graph.items():            for next_ in nexts:                this_row[next_] += prev_row[prev]    return sum(this_row)Converting your string dictionary into its int equivalent:knight = {0: [4, 6], 1: [6, 8], 2: [7, 9], 3: [4, 8], 4: [3, 9, 0],          6: [1, 7, 0], 7: [2, 6], 8: [1, 3], 9: [4, 2]}you can now run the following:>>> count_paths(knight, 7)952which of course returns the same result as your code, but uses a more efficient algorithm.  How much more efficient?  Well, if \$n\$ is the length of the phone number, and \$m\$ is the maximum number of possible next digits for any digit, your algorithm will have exponential behavior, \$O(m^n)\$, while the DP approach brings that down to \$O(m n)\$.That is, by the way, a huge improvement.  Try e.g. to run your code to calculate the number of 100 digit-long phone numbers, and I bet you will run out of memory before it finishes, while the DP approach spits the result in a blink of the eye:>>> count_paths(knight, 100)2657396588204099682921354979006480384L