Question

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

Answer 1

Q1: https://leetcode.com/problems/maximum-number-of-balloons
Q2: https://www.chegg.com/homework-help/questions-and-answers/battleships-game-played-rectangular-board-given-representation-board-size-n-height-x-m-wid-q97030738

Answer 2

Question -2
The below code works for every test case given. (#tested)

 

def countnumberofships (b : List[List[int]]) -> List[int]:
    num_rows = len(b)
    num_cols = len(b[0])
    res = []
    def get_neighbour(coord):
        row, col= coord
        delta_row = [-1,0,1,0]
        delta_col = [0,1,0,-1]
        res= []
        for i in range(len(delta_row)):
            row_neighbour = row + delta_row[i]
            col_neighbour = col + delta_col[i]
            if 0 <= row_neighbour < num_rows and 0<= col_neighbour < num_cols:
                res.append((row_neighbour, col_neighbour))
        return res
    def getsize(start):
        queue = deque([start])
        r, c  = start
        b[r][c] = 0
        size = 0
        while len(queue) > 0:
            node = queue.popleft() #when_we are poping we can increase the size to get the size of an island
            size += 1
            for neighbour in get_neighbour(node):
                r, c = neighbour
                if b[r][c] == 0:
                    continue
                queue.append(neighbour)
                b[r][c] = 0
        return size
    res = [0] * 3
    for i in range(num_rows):
        for j in range(num_cols):
            if b[i][j] == 0:
                continue
            size =getsize((i, j))
            if size <= 3:
                res[size -1] += 1
    return res
#replacing_the '.' with '0' and '#' with '1'
#now_it becomes a number of islands problem (but to get the size of island)
b = ['.##.#','#.#..','#...#','#.##.']
for i in range(len(b)):
    b[i] = b[i].replace('.','0').replace('#','1')
    b[i] = [int(x) for x in str(b[i])]
print(countnumberofships(b))

Answer 3

Q2 - BFS

 

public static void main(String[] args) {

    String[] B1 = {".##.#", "#.#..", "#...#", "#.##."};
    Arrays.stream(getCounts(B1)).forEach(e -> System.out.print(e + ","));

    System.out.println();
    String[] B2 = {".#..#", "##..#", "...#."};
    Arrays.stream(getCounts(B2)).forEach(e -> System.out.print(e + ","));

    System.out.println();
    String[] B3 = {"##.", "#.#", ".##"};
    Arrays.stream(getCounts(B3)).forEach(e -> System.out.print(e + ","));

    System.out.println();
    String[] B4 = {"...", "...", "..."};
    Arrays.stream(getCounts(B4)).forEach(e -> System.out.print(e + ","));
}
public static int[] getCounts(String[] B) {

    int[] result = new int[3];  //The key point is having only 3 different ships and the sizes are 1,2,3 regardless of the shape. 


    char[][] map = new char[B.length][B[0].length()];    //create a 2 dimension array like a standard matrix problem
    for (int row = 0; row < B.length; row++) {  //string is like charArray
        for (int col = 0; col < B[row].length(); col++) {
            map[row][col] = B[row].toCharArray()[col]; 
        }
    }

    for (int row = 0; row < map.length; row++) {
        for (int col = 0; col < map[0].length; col++) {
            if (map[row][col] == '#') { //there is a ship
                map[row][col] = '.';   //assign . to make it visited
                int count = getSizeOfShip(map, row, col); // standard BFS logic
                if (count <= 3) 
                    result[count - 1]++;  //since we have 3 different of shapes, we can put each ship in their index   size-1 to index0, size-2 to index1, size-3 to index2
            }
        }
    }
    return result;
}

public static int getSizeOfShip(char[][] map, int row, int col) {

    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[]{row, col});
    int count = 1;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int[] position = queue.remove();
            for (int[] dir : dirs) {
                int x = dir[0] + position[0];
                int y = dir[1] + position[1];
                if (x >= 0 && x < map.length && y >= 0 && y < map[0].length && map[x][y] == '#') {
                    map[x][y] = '.';
                    count++;
                    queue.add(new int[]{x, y});
                }
            }
        }
    }
    return count;
}