Amazon Interview Question


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.LinkedList;
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[0].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) {
			System.out.println("Bad Input in explore Cluster");
			return;
		}
		List<Position> tovisit = new ArrayList<Position>();
		Position start = new Position(i,j);
		tovisit.add(start);
		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) {
				tovisit.add(p);
			}
		}
	}
	public static List<Position> possMoves(Position pos, int[][] board, int[][] visited) {
		List<Position> moves = new LinkedList<Position>();
		if(board==null || visited==null || pos.i<0 || pos.j<0 || pos.i>board.length-1 || pos.j>board[pos.i].length-1) {
			System.out.println("Bad Input in explore Cluster");
			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) {
					moves.add(new Position(new_i,new_j));
				}
			}
		}
		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[0].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));
	}
}

- gigi84 December 22, 2014 | Flag Reply
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[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;
	}
}

- zortlord December 22, 2014 | Flag Reply
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.

- tomasz.lasica December 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Will this work ?
- Convert Adjacency Matrix into Adjacency List
- Use BFS to find Connected Components

- abettikk December 23, 2014 | Flag Reply
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[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);
    }
}

- autoboli January 06, 2015 | 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