## Amazon Interview Question

• 1
of 1 vote

Team: Machine learning
Country: India
Interview Type: Phone Interview

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

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.:

``````1 0 1 0
0 0 0 1
0 1 0 0``````

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:

``````0 1 1 0
0 0 0 1
1 1 1 0``````

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:

``int[][] genBoard(int i, int j)``

to generate a Matrix of 0's and 1's with size i, j, and:

``void printBoard(int[][] board)``

to print that matrix;
the method

``int countClusters(int[][] board)``

retrieves the number of clusters of 1's in the input matrix,
then the method:

``void exploreCluster(int i,int j, int[][] board, int[][] visited)``

performs the Breadth First Search starting from a specific position, and finally the method

``List<Position> possMoves(Position pos, int[][] board, int[][] visited)``

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:

``````import java.util.ArrayList;
import java.util.List;
import java.util.Random;

class Position {
int i;
int j;
public Position(int i, int j) {
this.i=i;
this.j=j;
}
}
public class CountClusters {
public static int countClusters(int[][] board) {
int clusters = 0;
if(board==null || board.length==0) {
return clusters;
}
int[][] visited = new int[board.length][board.length];
for(int i=0;i<board.length;i++) {
for(int j=0;j<board[i].length;j++) {
if(visited[i][j]!=1 && board[i][j]==1) {
clusters++;
exploreCluster(i,j,board,visited);
}
}
}
return clusters;
}
public static void exploreCluster(int i,int j, int[][] board, int[][] visited) {
if(board==null || visited==null || i<0 || j<0 || i>board.length-1 || j>board[i].length-1) {
return;
}
List<Position> tovisit = new ArrayList<Position>();
Position start = new Position(i,j);
Position visiting;
while(tovisit.size()>0) {
visiting = tovisit.remove(0);
visited[visiting.i][visiting.j]=1;
List<Position> moves = possMoves(visiting,board,visited);
for(Position p: moves) {
}
}
}
public static List<Position> possMoves(Position pos, int[][] board, int[][] visited) {
if(board==null || visited==null || pos.i<0 || pos.j<0 || pos.i>board.length-1 || pos.j>board[pos.i].length-1) {
return moves;
}
int[] dx = {-1,0,1,-1,0,1,-1,0,1};
int[] dy = {-1,-1,-1,0,0,0,1,1,1};
int new_i, new_j;
for(int k=0;k<dx.length;k++) {
new_i=pos.i+dy[k];
new_j=pos.j+dx[k];
if(new_i>=0 && new_i<board.length && new_j>=0 && new_j<board[new_i].length) {
if(board[new_i][new_j]==1 && visited[new_i][new_j]!=1) {
}
}
}
return moves;
}
public static int[][] genBoard(int i, int j) {
if(i<=0 || j<=0) {
System.out.println("Error Generating Board, non positive input size.");
return null;
}
int[][] board = new int[i][j];
Random r = new Random();
for(int x=0;x<i;x++) {
for(int y=0;y<j;y++) {
board[x][y]=r.nextInt(2);
}
}
return board;
}
public static void printBoard(int[][] board) {
if(board==null || board.length==0 || board.length==0) {
System.out.println("Error Printing Board, null or non positive input size.");
return;
}
for(int i=0;i<board.length;i++) {
for(int j=0;j<board[i].length;j++) {
System.out.print(board[i][j]+" ");
}
System.out.println();
}
}
public static void main(String[] args) {
int[][] board = genBoard(3,4);
printBoard(board);
System.out.println("Number of clusters in Matrix: "+countClusters(board));
}
}``````

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

``````public static int numClusters(int[][] board){
if(board == null){
throw new NullPointerException();
}
if(board.length == 0 || board.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.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[]>();
while(!positions.isEmpty()){
int[] position = positions.pop();
this.visited[position][position] = true;
}
}

ArrayList<int[]> getMoves(int[] position){
int xMin = position > 0 ? position -1: position;
int xMax = position < this.xDim -1 ? position + 1 : position;
int yMin = position[y] > 0 ? position - 1 : position;
int yMax = position < this.yDim - 1 ? position + 1 : position;
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){
}
}
}
return results;
}
}``````

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

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.

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

Will this work ?
- Use BFS to find Connected Components

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

(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.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;
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);
}
}``````

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.

### 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.