Google Interview Question for Site Reliability Engineers


Country: Irland
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
4
of 4 vote

Union-Find Algorithm

package main

import "fmt"

var sea [3][3]string
var isles [3][3]int
var count int

func initData() {
	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			sea[i][j] = "o"
		}
	}
}

func getRoot(x, y int) (int, int) {
	for true {
		nx := isles[x][y] / 3
		ny := isles[x][y] % 3
		if nx == x && ny == y {
			return x, y
		}
		x = nx
		y = ny
	}
	return 0, 0
}

func mergeIsles(x1, y1, x2, y2 int) {
	rootX1, rootY1 := getRoot(x1, y1)
	rootX2, rootY2 := getRoot(x2, y2)
	if rootX1 != rootX2 || rootY1 != rootY2 {
		count--
		isles[rootX1][rootY1] = isles[rootX2][rootY2]
	}
}

func place(x, y int) int {
	if sea[x][y] == "x" {
		return count
	}
	sea[x][y] = "x"
	count++
	isles[x][y] = x*3 + y
	if x > 0 {
		if sea[x-1][y] == "x" {
			mergeIsles(x-1, y, x, y)
		}
	}
	if x < 2 {
		if sea[x+1][y] == "x" {
			mergeIsles(x+1, y, x, y)
		}
	}

	if y > 0 {
		if sea[x][y-1] == "x" {
			mergeIsles(x, y-1, x, y)
		}
	}
	if y < 2 {
		if sea[x][y+1] == "x" {
			mergeIsles(x, y+1, x, y)
		}
	}
	return count
}

func main() {
	initData()
	fmt.Println(place(1, 2)) // 1
	fmt.Println(place(2, 1)) // 2
	fmt.Println(place(1, 1)) // 1
	fmt.Println(place(0, 0)) // 2
	fmt.Println(place(0, 1)) // 1
}

- dmitry.labutin February 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using another 2 dimensional array that counts for each position the number of adjacent isles.
For example, for the following board:
o x o
x o x
o x x
the extra matrix will look as follows
2 -1 2
-1 4 -1
2 -1 -1
where -1 signals 'x'
when changing 'o' to 'x' we increment all adjacent (horizontal and vertical) counters.
in addition, save a global counter for the number of isles in the board which will be incremented by 1 when changing 'o' to 'x' in a position i,j with corresponding counter equal to zero, and will be decremented by MIN(isles - 1, counters[i][j]-1) and will be returned by the function.

- vesh February 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//This is to find connected components for Graph using DFS/BFS
public class Islands {
	// number of rows n columns
	static final int ROW = 5, COL = 5;

	// A fucntion to check given cell to be included in DFS
	boolean isSafe(int M[][], int row, int col, boolean visited[][]) {
		// row number is in range, column number is in range
		// and value is 1 and not yet visited
		return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row][col] == 1 && !visited[row][col]);
	}

	// A utility function to do DFS for a 2D boolean matrix.
	// It only considers the 8 neighbors as adjacent vertices
	void DFS(int M[][], int row, int col, boolean visited[][]) {

		// if you want to check neighbours of i, j, do following iteration,
		// initialized in rowNbr n colNbr
		/*
		 * [i-1,j-1][i-1,j ][i-1,j+1] [i ,j-1][i ,j ][i ,j+1] [i+1,j-1][i+1,j
		 * ][i+1,j+1]
		 */
		int rowNbr[] = new int[] { -1, -1, -1, 0, 0, 1, 1, 1 };
		int colNbr[] = new int[] { -1, 0, 1, -1, 1, -1, 0, 1 };

		// Mark this cell as visited
		visited[row][col] = true;

		// Recur for all connected neighbours
		for (int k = 0; k < 8; ++k)
			if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))
				DFS(M, row + rowNbr[k], col + colNbr[k], visited);
	}

	// The main function that returns count of islands in a given
	// boolean 2D matrix
	int countIslands(int M[][]) {
		// Make a bool array to mark visited cells.
		// Initially all cells are unvisited
		boolean visited[][] = new boolean[ROW][COL];

		// Initialize count as 0 and traverse through the all cells
		// of given matrix
		int count = 0;
		for (int i = 0; i < ROW; ++i)
			for (int j = 0; j < COL; ++j)
				if (M[i][j] == 1 && !visited[i][j]) // If a cell with
				{ // value 1 is not
					// visited yet, then new island found, Visit all
					// cells in this island and increment island count
					DFS(M, i, j, visited);
					++count;
				}

		return count;
	}

	public static void main(String[] args) {

		int M[][] = new int[][] { { 0, 0, 0, 0, 0 }, 
								  { 0, 0, 0, 0, 0 }, 
								  { 0, 0, 0, 0, 0 }, 
								  { 0, 0, 0, 1, 1 },
								  { 0, 0, 0, 1, 0 } };
		Islands I = new Islands();
		System.out.println("Number of islands is: " + I.countIslands(M));
	}

}

- swamy February 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The DFS approach, but using queue instead of recursion

private static final char GROUND = 'x';
  private static final char WATER = 'o';
  private static final char VISITED = 'v';

  public static void main(String[] args) {
    try (Scanner scanner = new Scanner(System.in)) {
      int T = scanner.nextInt();
      for (int t = 0; t < T; t++) {
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        scanner.nextLine();
        char[][] board = new char[n][m];
        for (int j = 0; j < m; j++) {
          int i = 0;
          for (String s : scanner.nextLine().split(" ")) {
            board[i++][j] = s.toLowerCase().charAt(0);
          }
        }
        int x = scanner.nextInt();
        int y = scanner.nextInt();
        System.out.println(getNumberOfIsles(board, n, m, x, y));
      }
    }
  }

  private static int getNumberOfIsles(char[][] board, int n, int m, int x, int y) {
    // update board
    char[][] updatedBoard = deepCopyOfBoard(board);
    updatedBoard[x][y] = GROUND;

    // check number of isles
    int numberOfIsles = 0;

    int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (updatedBoard[i][j] == GROUND) {
          LinkedList<int[]> island = new LinkedList<>();
          island.add(new int[]{i, j});
          while (!island.isEmpty()) {
            int[] currentPoint = island.pollFirst();
            updatedBoard[currentPoint[0]][currentPoint[1]] = VISITED;
            for (int[] direction : directions) {
              int newI = currentPoint[0] + direction[0];
              int newJ = currentPoint[1] + direction[1];
              if (0 <= newI && newI < n && 0 <= newJ && newJ < m && updatedBoard[newI][newJ] == GROUND) {
                island.add(new int[]{newI, newJ});
              }
            }
          }
          numberOfIsles++;
        } else if (updatedBoard[i][j] == WATER) {
          updatedBoard[i][j] = VISITED;
        }
      }
    }

    return numberOfIsles;
  }

  private static char[][] deepCopyOfBoard(char[][] originalBoard) {
    if (originalBoard == null) {
      return null;
    }

    char[][] copiedBoard = new char[originalBoard.length][];
    int i = 0;
    for (char[] originalBoardLine : originalBoard) {
      copiedBoard[i++] = Arrays.copyOf(originalBoardLine, originalBoardLine.length);
    }

    return copiedBoard;
  }

Input:

3
3 3
o o o 
o o o 
o o o
1 2
3 3
o o o 
o x x 
o x o
0 0
7 6
x o o o x o o
o o x o x x o
o x o x o x o
x o x o o x o
x o o o x o o
x x x o o x o
2 2

Output:

1
2
6

- Mike L April 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def mark_land(arr, row, col):
    arr[row][col] = "x"


def get_surrounding_lands(arr, rows, cols, row, col):
    surroundings = []
    for x, y in [(row, col+1), (row, col-1), (row+1, col), (row-1, col)]:
        if x < 0 or y < 0 or x >= rows or y >= cols:
            continue
        if arr[x][y] == "x":
            surroundings.append((x,y))
    return surroundings


def count_isles(arr, rows, cols):
    ''' Counts isles. If there is land surrounding to the current land, it's
    marked and counted as part of one big isle.
    '''
    count = 0
    marked = {}
    for r in range(rows):
        for c in range(cols):
            if arr[r][c] == "o":
                continue
            if marked.get((r,c), False) == True:
                continue
            marked[(r,c)] = True
            count += 1
            surroundings = get_surrounding_lands(arr, rows, cols, r, c)
            for sx, sy in surroundings:
                if marked.get((sx, sy), False) == False:
                    marked[(sx, sy)] = True
    return count


def test():
    # Test case 1
    arr = [
        ["o", "o", "o"],
        ["o", "o", "o"],
        ["o", "o", "o"]
    ]
    mark_land(arr, 0, 2)
    result = count_isles(arr, 3, 3)
    assert result == 1, result

    # Test case 2
    arr = [
        ["o", "o", "o"],
        ["o", "o", "o"],
        ["o", "o", "o"]
    ]
    mark_land(arr, 1, 1)
    mark_land(arr, 1, 2)
    mark_land(arr, 2, 1)
    result = count_isles(arr, 3, 3)
    assert result == 1, result



test()

- Anonymous May 26, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def mark_land(arr, row, col):
    arr[row][col] = "x"


def get_surrounding_lands(arr, rows, cols, row, col):
    surroundings = []
    for x, y in [(row, col+1), (row, col-1), (row+1, col), (row-1, col)]:
        if x < 0 or y < 0 or x >= rows or y >= cols:
            continue
        if arr[x][y] == "x":
            surroundings.append((x,y))
    return surroundings


def count_isles(arr, rows, cols):
    ''' Counts isles. If there is land surrounding to the current land, it's
    marked and counted as part of one big isle.
    '''
    count = 0
    marked = {}
    for r in range(rows):
        for c in range(cols):
            if arr[r][c] == "o":
                continue
            if marked.get((r,c), False) == True:
                continue
            marked[(r,c)] = True
            count += 1
            surroundings = get_surrounding_lands(arr, rows, cols, r, c)
            for sx, sy in surroundings:
                if marked.get((sx, sy), False) == False:
                    marked[(sx, sy)] = True
    return count


def test():
    # Test case 1
    arr = [
        ["o", "o", "o"],
        ["o", "o", "o"],
        ["o", "o", "o"]
    ]
    mark_land(arr, 0, 2)
    result = count_isles(arr, 3, 3)
    assert result == 1, result

    # Test case 2
    arr = [
        ["o", "o", "o"],
        ["o", "o", "o"],
        ["o", "o", "o"]
    ]
    mark_land(arr, 1, 1)
    mark_land(arr, 1, 2)
    mark_land(arr, 2, 1)
    result = count_isles(arr, 3, 3)
    assert result == 1, result



test()

- Jude May 26, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More