The original article is reprinted from liu Yue’s Technology blog v3u.cn/a_id_168

Now many Internet enterprises learn smart, know that candidates have a purpose to brush the original Leetcode, used to cope with algorithm questions interview, so began to “magic change” these questions, such as this question on an e-commerce platform in Beijing:

There is a square island, which is represented by a two-dimensional square matrix. There is a drunk on the island who can move one space in one of four directions with each step. If he moves beyond the range of the matrix, he will die.

For example: input matrix size 2*2, starting point (0,0), random step n = 1, output 0.5 is a half chance of being alive. For example: input matrix size 3*3, starting point (1,1), random step n = 1, output 1 is 100% aliveCopy the code

At first glance a little meng, but the extraction of key words: two-dimensional matrix, up and down four directions, matrix range, N steps, have you felt very familiar? Those of you who have scanned Leetcode must have been reminded of Leetcode 576: the number of paths out of bounds. The difficulty level is medium.

Given an m by n grid and a sphere. The ball starts at coordinates (I,j), and you can move the ball into adjacent cells, or up, down, left, or right to cross the grid boundary. But, you can move it N times at most. Find the number of paths you can take to move the ball out of the boundary. The answer can be very large and return the value mod 109+ 7.

And the redesign of the topic, the so-called “dead” drunkard, is actually out of the border, and there will be four possible at every step, so the so-called “survival”, that is, when we calculate the number of path out of boundary, divided by the direction of the base 4, you can calculate the “survival”, on the contrary can also be calculated “mortality”, at the end of the day, Magic revision problem or calculate the number of paths to move out of the boundary, not the last question asked the “survival rate”, this problem is just a not very particular about the camouflage, it is likely that the e-commerce platform boss let his research and development of a new algorithm to recruit people, and the research and development has been confused by the demand, I just copied it from Leetcode and changed it.

As for the solution, the subconsciously thought and very easy to understand solution is to use BFS(Breadth First Search), because the drunk can only move N times at most, we just need BFS traversal in turn, if it is found out of bounds, it represents death, and accumulate 1. When the depth of BFS is greater than N, the break ends. In theory there is no problem.

import collections  
def how_likely_alive(m,n,N,i,j):  
    mod = 10**9 + 7  
    Q = collections.deque([(i,j,0)])  
    res = 0  
    while Q:  
        x,y,step = Q.popleft()  
        if step > N: break  
        if 0<=x<m and 0<=y<n:  
            Q.append((x+1,y,step+1))  
            Q.append((x-1,y,step+1))  
            Q.append((x,y+1,step+1))  
            Q.append((x,y-1,step+1))  
        else:  
            res += 1  
    num = res % mod  
    if num == 0:  
        return 1  
    else:  
        return num / 4  
  
  
print(how_likely_alive,2,1,0,0 (2))Copy the code

Normally, if the job isn’t technically demanding, you’ll probably get by with BFS, but if the interviewer wants to do a stress interview to see what your limits are, they’ll ask you to use a more efficient algorithm. If the interviewer doesn’t know the answer to the question, it’s just because the interviewer doesn’t know the answer to the question.

We think back to the topic, the magic change topic there is no definition of the scope of the drunken random walk steps N assuming N values range reached 50, we coordinate point to any one traversal of BFS has four direction at the same time to consider the possibility of back, then the complexity reached four times the size of N, the efficiency obviously not satisfactory, Therefore, when N is relatively small, such as only one step, BFS is the optimal solution, while dp needs to be considered when the range is too large.

Dp (Dynamic Programming) algorithm is a well-known Dynamic Programming algorithm in the industry. Its core idea is to split a complex problem into several sub-problems and solve the big problem step by step by solving the sub-problems. Is it similar to divide-and-conquer? Divide-and-conquer algorithms refer to this article: When we talk about algorithms we are talking about divide-and-conquer algorithms that came to mind from nucleic acid detection in epidemics. However, unlike divide-and-conquer, there is a premise for using dynamic programming: Dynamic programming can only be used if and only if each subproblem is discrete (that is, each subproblem does not depend on other subproblems).

Again, assuming that the drunk has a path dp[N][mi][nj] when he gets to (mi, nj) at step N, we can assume how the current state is derived from the previous move. It’s going up, down, left, and right, and the number of steps is N minus 1.

def how_likely_alive(m, n, N, i, j):  
  
    tmp=[[[0 for i in range(n)] for j in range(m)] for k in range(N+1)]  
    for k in range(1,N+1):  
        for p in range(m):  
            for q in range(n):  
                if 0==p:  
                    up=1  
                else:  
                    up=tmp[k-1][p-1][q]  
                if m-1==p:  
                    down=1  
                else:  
                    down=tmp[k-1][p+1][q]  
                if 0==q:  
                    left=1  
                else:  
                    left=tmp[k-1][p][q-1]  
                if n-1==q:  
                    right=1  
                else:  
                    right=tmp[k-1][p][q+1]  
                tmp[k][p][q]=(up+down+left+right)%1000000007  
  
    num = tmp[N][i][j]  
    if num == 0:  
        return 1  
    else:  
        return num / 4  
    return num

print(how_likely_alive,2,1,0,0 (2))Copy the code

Conclusion: Leetcode algorithm is vast, want to every question, personal feel difficult, but from the point of this two-dimensional matrix of drunk, enterprise if want to change the “magic”, is also a plus ca change, more or less have a track record, so we in the process of brush problem, should be based on the principle of nothing more, real control algorithm core idea, Only then can we draw inferences from one example and win a hundred battles without danger of defeat.

The original article is reprinted from liu Yue’s Technology blog v3u.cn/a_id_168