Amazon Interview Question
Team: Machine learning
Country: India
Interview Type: Phone Interview
public static int numClusters(int[][] board){
if(board == null){
throw new NullPointerException();
}
if(board.length == 0 || board[0].length == 0){
throw new IllegalArgumentException();
}
Worker worker = new Worker(board);
return worker.execute();
}
static class Worker{
int[][] board;
boolean[][] visited;
int xDim;
int yDim;
Worker(int[][] board){
this.board = board;
this.xDim = board.length;
this.yDim = board[0].length;
this.visited = new boolean[this.yDim][this.xDim];
}
int execute(){
int count = 0;
for(int y = 0; y < this.yDim; y++){
for(int x = 0; x < this.xDim; x++){
if(!this.visited[y][x] && this.board[y][x] == 1){
count++;
this.visitCluster(x, y);
}
}
}
return count;
}
void visitCluster(int x, int y){
Stack<int[]> positions = new Stack<int[]>();
positions.add(new int[]{y, x});
while(!positions.isEmpty()){
int[] position = positions.pop();
this.visited[position[0]][position[1]] = true;
positions.addAll(generateMoves(position));
}
}
ArrayList<int[]> getMoves(int[] position){
int xMin = position[1] > 0 ? position[1] -1: position[0];
int xMax = position[1] < this.xDim -1 ? position[1] + 1 : position[1];
int yMin = position[y] > 0 ? position[0] - 1 : position[0];
int yMax = position[0] < this.yDim - 1 ? position[0] + 1 : position[0];
ArrayList<int[]> results = new ArrayList<int[]>();
for(int i = yMin; i < yMax; i++){
for(int j = xMin; j < xMax; j++){
if(!this.visited[i][j] && this.board[i][j] == 1){
results.add(new int[]{i, j});
}
}
}
return results;
}
}
One good trick here is to mark already clustered cells with clusterId >=2.
With this approach one can iterate through the matrix and "visit" cells with 1 only (not visited yet). Visit method will mark visited node with clusterId and recursively visit all direct neighbours with value=1 to construct the whole cluster. Number of clusters is clusterId - 2.
The code is in Scala but in imperative 'Java like' way
def findNumClusersAsTree(m: Array[Array[Int]]): Int = {
// this function has side effects
def visitNode(row: Int, col: Int, clusterId: Int): Unit = {
if (m(row)(col) == 1) {
m(row)(col) = clusterId // mark as visited
for{
dr <- -1 to 1 // top and down
if row+dr > 0
if row+dr < m.length
dc <- -1 to 1 // left and right
if col+dc > 0
if col+dc < m(row).length
if m(row+dr)(col+dc) == 1 // visit only not visited (with 1)
} visitNode(row+dr, col+dc, clusterId)
}
}
var clusterId = 2
for {
row <- 0 to m.length-1
col <- 0 to m(row).length-1
if m(row)(col) == 1
} { visitNode(row, col, clusterId); clusterId += 1 }
clusterId - 2
}
Time complexity of this solution is O(n) because we visit each node at most once.
(i) run DFS in order to find connected components
(ii) count number of DFS calls (not including recursive calls)
(iii) return this number
public class Board {
private boolean[][] board;
private int M,N, cnt;
private int[][] labels;
public int clusters(boolean[][] board) {
this.M = board.length;
this.N = board[0].length;
this.cnt = 0;
this.labels = new int[M][N];
for (int k=0; k<M*N; k++) // init labels to 0's
labels[k/M][k%n] = 0;
for (int k=0; k<M*N; k++) { // search for all cluster by DFS
int i=k/M, j=k%N;
if (boadr[i][j] && labels[i][j]==0) {
cnt++;
dfs(i,j);
}
}
return cnt;
}
public void dfs(int i, int j) {
labels[i][j] = cnt;
for (int p=i-1; p<=i+1; p++) // check 8 neighbours
for (int q=j-1; q<=j+1; q++)
if (p>=0 && q>=00 && p<M && q<N && labels[p][q]==0)
dfs(p, q);
}
}
We have to find the number of Clusters composed by elements of the input Matrix with value of 1. I understand that two elements with value of 1 belong to the same cluster if they are adjacent, in horizontal, vertical, or diagonal. E.g.:
Has 3 clusters of 1's, the first Cluster is composed by the single element at Position(0,0), the second cluster by two elements at Position(0,2) and Position(1,3), and the third cluster by the single element at Position(2,1);
Another example:
In this case the Matrix has just 1 cluster, because the two 1's in the first line and the three 1's in the third line are joined (in diagonal) by the 1 at the end of the second line.
To solve this problem I would iterate through the elements of the input Matrix, and every time I find an element with value of 1 in the matrix that has not already been visited, I increment the value of clusters found by 1, and I perform a Breadth First Search in the input Matrix from this element, moving through elements with value of 1 adjacent and marking them as visited.
In the following code you can use:
to generate a Matrix of 0's and 1's with size i, j, and:
to print that matrix;
the method
retrieves the number of clusters of 1's in the input matrix,
then the method:
performs the Breadth First Search starting from a specific position, and finally the method
computes the possible moves from a given position in the Matrix to find adjacent 1's in the cluster; I use a class Position to hold the coordinates of a single position in the Matrix.
Complexity is O(n^2) as we need to visit each element of the Matrix to count how many clusters there are in the matrix.
Here is the complete code for this solution:
- gigi84 December 22, 2014