Question

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

Answer 1

 

I am expecting answer in java 8.

 

// you can also use imports, for example:
 import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int[][] vectorToMatrix(int[] A) {
        int dim = (int) sqrt(A.length);
        
        int[][] result = new int[dim][dim];
        
        for (int i = 0; i < A.length; i++) {
           result[i / dim][i % dim] = A[i];
        }

        return result;
    }
    
    public int solution(int[] A) {
        int [][] matrix = vectorToMatrix(A); 
        //..
    }
}

Answer 2

int[][] grid;
int m,n;
public int biggestTerriority(int[][] grid) {
 this.grid = grid;
 m = grid.length;
 n = grid[0].length;
 int ans = 0;
 for(int r=0; r<m; r++) {
  for(int c=0; c<n; c++) {
   if(grid[r][c]!=’*’) ans = Math.max(backtrack(r,c,grid[r][c]), ans);  
  }
 }
 return ans;
}

private int backtrack(int r, int c, int group) {
 if(r<0 || r>=m || c<0 || c>=n || grid[r][c]==’*’ || grid[r][c]!=group) return 0;
 grid[r][c]=’*’;
 int size = 1+backtrack(r+1,c, group) + backtrack(r-1,c, group) + backtrack(r,c+1,group) +backtrack(r,c-1,group);
 return size;
}

Answer 3

The question is similar to Number of Islands problem https://leetcode.com/problems/number-of-islands/

 

public int solution(int[] A) {
        int[][] matrix = vectorToMatrix(A);

        int rowSize = matrix.length;
        int colSize = matrix[0].length;

        int territory_value; // number representing a territory e.g 4
        int size = 0; // size of the biggest territory

        // For every territory value, count all the neighbours you can reach from it
        for (int x = 0; x < rowSize; x++) {
            for (int y = 0; y < colSize; y++) {
                if (matrix[x][y] != -1) {
                    territory_value = matrix[x][y];
                    size = max(size, dfs(matrix, territory_value, x, y, 0));
                }
            }
        }
        return size;
    }


private int dfs(int[][] matrix, int territory_value, int x, int y, int territory_size) {

        int rowSize = matrix.length;
        int colSize = matrix[0].length;

        if (x < 0 || y < 0 || x >= rowSize || y >= colSize || matrix[x][y] != territory_value) {
            return territory_size;
        }

        matrix[x][y] = -1; // mark territory position as seen
        ++territory_size;

        // Visit all neighbours
        territory_size = dfs(matrix, territory_value, x + 1, y, territory_size);
        territory_size = dfs(matrix, territory_value, x - 1, y, territory_size);
        territory_size = dfs(matrix, territory_value, x, y + 1, territory_size);
        territory_size = dfs(matrix, territory_value, x, y - 1, territory_size);

        return territory_size;

    }