Question

Microsoft | OA Coding Questions and Solutions | Set - 49 | 2022

Answer 1

First question is exactly same as https://leetcode.com/problems/maximal-network-rank/
Second one is similar to https://leetcode.com/problems/unique-paths-iii/

 

Got 70 min to solve these

Answer 2

Q2 Solution

 

class Solution {
    public int uniquePathsIII(int[][] maze) {
        int sr=0,sc=0,obs=0;
        
        for (int i = 0; i < maze.length; i++) {
            for (int j = i; j < maze[i].length; j++) {
                if (maze[i][j]==1) {
                    sr = i;
                    sc = j;
                }
                if(maze[i][j]==-1){
                    obs +=1;
                }
            }
        }
        
        return pathAll2("",maze,sr,sc,obs);
    }
    
    public static int pathAll2(String p, int[][] maze, int r, int c,int obs){
        //if(r==maze.length-1&& c==maze[0].length-1){
        if(maze[r][c]==2){
            if(p.length()==(maze.length*maze[0].length)-1-obs){
            //System.out.println(p);
            //System.out.println();
            return 1;
            }
            return 0;
        }
        if(maze[r][c]==-1){
            return 0;
        }
        int count =0;
        maze[r][c]=-1;       
        if(r<maze.length-1){
            count += pathAll2(p+'D', maze, r+1, c,obs);
        }
        if(c<maze[0].length-1){
            count += pathAll2(p+'R', maze, r, c+1,obs);
        }
        if(r>0){
            count += pathAll2(p+'U', maze, r-1, c,obs);
        }
        if(c>0){
            count += pathAll2(p+'L', maze, r, c-1,obs);
        }
        maze[r][c]=0;
        return count;
    }
}