Leetcode discuss: 935. Knight Dialer

Here is the link.

C# Need to move fast

July 18, 2020 10:36 PM

Introduction

I am preparing for Facebook phone screen on July 20, 2020. One thing I have to work on is to move fast. I will be measured how fast I can solve the problem.

I am working on this marathon on Leetcode phone mock interview, the idea is to push myself to move fast, solve as many algorithms as possible.

First I need to get myself under this drill, work on algorithm problem solving non-stoppable for 10 hours at least.

I came cross this algorithm as the second one, I remembered that I solved the problem before.

How to analyze?
It took me over 20 minutes and then I knew that it can be solved using DFS or BFS algorithm for N step. And I thought about there is no need for each path. All we need is the total count.

Another thing is that intermediate steps are also only 10 digits. The array is good enough for me to build recurrence formula. I need to count number for each digit for each step.

DFS/BFS -> 10 digits each step -> Simple recurrence
It should take me less than five minutes to spot the pattern. But it did take me 20 minutes or so.

When to code?
After over 40 minutes, I started to code the solution; First I define the hashset array, and then map digit 0 - 9 to next step, cross 1x2 or 2x1, eight directions.

Performance
It is hard for me to push myself. It is interesting to learn that I gained some confidence after two hour solving a problem this afternoon. Here is the discuss post I shared. It was tough for me to be patient to solve it after failing so many times.

Facebook phone screen advice
I like to share those four things to work on when I practice through mock interviews:
As a reminder, please keep these 4 criteria in mind during your technical interview:

1. Communication: Ask clarifying questions around the problem before solving
2. Speed: One of our values here is moving fast
3. Verification and testing: bug free as possible, talking through edge cases
4. Problem-solving: Finding a working solution

public class Solution {
    public int KnightDialer(int N) {
        // DFS -> only 10 digits each step - using array to represent 
        // 
        if( N <= 0 || N > 5000)
            return -1; 
        
        var map = new HashSet<int>[10];
        for(int i = 0; i < 10; i++)
        {
            map[i] = new HashSet<int>(); 
        }
        
        map[0] = new HashSet<int>(new int[]{4, 6});
        map[1] = new HashSet<int>(new int[]{6, 8});
        map[2] = new HashSet<int>(new int[]{7, 9});
        map[3] = new HashSet<int>(new int[]{4, 8});
        map[4] = new HashSet<int>(new int[]{0, 3, 9}); 
        //map[5] = new HashSet<int>(new int[]{});
        map[6] = new HashSet<int>(new int[]{0, 1, 7});
        map[7] = new HashSet<int>(new int[]{2, 6});
        map[8] = new HashSet<int>(new int[]{1, 3}); 
        map[9] = new HashSet<int>(new int[]{2, 4}); 
        
        var previous = new long[10];
        var current = new long[10];
        
        var number = 1000 * 1000 * 1000 +7;
        
        for(int i = 0; i < N; i++)
        {            
            if(i == 0)
            {
                for(int j = 0; j < 10; j++)
                {
                    current[j] = 1; 
                }                              
            }
            else 
            {
                for(int j = 0; j < 10; j++)
                {
                    var set = map[j];
                    foreach(var item in set)
                    {
                        current[item] = (long)(current[item] + previous[j]) % number;
                    }
                }
            }                 
            
            // reset current array
            for(int j = 0; j < 10; j++)
            {
                previous[j] = current[j];
                current[j] = 0; 
            }
        }
        
        return (int)(previous.Sum() % number); 
    }
}