Amazon Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
simple flood fill with DFS
keep a counter and increment it whenever a separate dfs is called
//Given n*m fields of O's and X's, where O=white, X=black, for example
//
//OOOXOOO
//OOXXOXO
//OXOOOXO
//Return the number of black shapes. A black shape consists of one or
// more adjacent X's (diagonals not included).
// In the example, the answer is 3.
using namespace std;
void explore(int arr[][7],int i,int j,int m,int n)
{
if(i < 0 || i > m-1)
{
return;
}
if(j < 0 || j > n-1)
{
return;
}
if(arr[i][j] == 0 || arr[i][j] == -1)
{
return;
}
arr[i][j] = -1;
//Open below to include diagonal also
/*
explore(arr,i-1,j-1,m,n);
explore(arr,i+1,j+1,m,n);
explore(arr,i-1,j+1,m,n);
explore(arr,i+1,j-1,m,n);
*/
explore(arr,i,j-1,m,n);
explore(arr,i,j+1,m,n);
explore(arr,i-1,j,m,n);
explore(arr,i+1,j,m,n);
}
int countbBlackShapes(int arr[3][7],int m,int n)
{
int count = 0;
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
if(arr[i][j] == 1)
{
explore(arr,i,j,m,n);
count++;
}
}
}
//To recovedr the data again place -1 as 1
for(int p = 0; p < m; p++)
{
for(int q = 0; q < n; q++)
{
if(arr[p][q] == -1)
arr[p][q] = 1;
}
}
return count;
}
int main()
{
//OOOXOOO
//OOXXOX
//OXOOOXO
//X =1
//O =0
int M[3][7]= {
{0,0,0,1,0,0,0},
{0,0,1,1,0,1,0},
{0,1,0,0,0,1,0}
};
cout<<"Number of Black Shapes="<<countbBlackShapes(M,3,7);
}
this is my initial appraoch i will improve it for time complexity...
char[][] data = new char[3][];
public void load(){
data[0] = "OOOXOOO".toCharArray();
data[1] = "OOXXOXO".toCharArray();
data[2] = "OXOOOXO".toCharArray();
}
public void parse() {
int count = 0;
for (int i = 0; i < data.length; i++) {
for (int j = 0; j < data[i].length; j++) {
if ((j + 1) < data[i].length) {
if (data[i][j] == 'X') {
if (data[i][j] == data[i][j + 1]) {
// Adjacent columns are equal X
++count;
}
if ((i - 1) >= 0) {
// Check top
if (data[i - 1][j] == data[i][j]) {
++count;
}
}
if ((i + 1) < data.length) {
// Check bottom
if (data[i + 1][j] == data[i][j]) {
++count;
}
}
}
}
}
}
System.out.println("Count: " + count);
}
One of either // Check top or // Check bottom code block must be removed to get expected count.
@Satish Will u try a test case on your code.....
i not know java so i cannot check
int M[5][9] = {
{0,1,1,0,1,0,1,0,0},
{1,1,0,0,1,1,1,0,0},
{0,1,1,1,1,0,0,0,0},
{1,1,0,0,0,0,0,0,0},
{0,1,1,1,0,0,0,0,0}
};
No of black shapes here is 1
1 used as black shape i mean x and 0 used for white shape
Without recursion just count the adjacent elements first row-wise and then column-wise. This can be done without recursion using the loops as:
#include <stdio.h>
#include <conio.h>
int countRows(char a[][7],int n,int m)
{
int j=0,count=0,flag=0;
for(int i=0;i<n;)
{
if(a[i][j]=='X'&&a[i][j+1]=='X'&&j<m-1)
{
j=j+2;
flag=1;
}
if(a[i][j]=='X'&&a[i][j+1]!='X'&&j<m-1)
{
j=j+2;
}
if(a[i][j]=='X'&&j==m-1)
j++;
if(a[i][j]=='O'&&j<m)
{
j++;
if(flag==1)
{
count=count+1;
}
flag=0;
}
if(j==m)
{
i++;
j=0;
}
}
return count;
}
int countCols(char a[][7],int n,int m)
{
int i=0,count=0,flag=0;
for(int j=0;j<m;)
{
if(a[i][j]=='X'&&a[i+1][j]=='X'&&i<n-1)
{
i=i+2;
flag=1;
}
if(a[i][j]=='X'&&a[i+1][j]!='X'&&i<n-1)
i=i+2;
if(a[i][j]=='X'&&i==n-1)
i++;
if(a[i][j]=='O'&&i<n)
{
i++;
if(flag==1)
{
count=count+1;
}
flag=0;
}
if(i==n)
{
j++;
i=0;
}
}
return count;
}
int main()
{
char a[][7]={{'O','O','O','X','O','O','O'},{'O','O','X','X','O','X','O'},
{'O','X','O','O','O','X','O'}};
int n=sizeof(a)/sizeof(a[0]);
int m=sizeof(a[0])/sizeof(a[0][0]),flag=0;
printf("%d",countRows(a,n,m)+countCols(a,n,m));
}
Please can you elaborate that because i have checked it and it is working for all the cases i have checked for. Please provide a case for which it is wrong
{'O','O','O','X','O','O','O'} it will return 0. not mentioning it fails on boundary checking
public class CountXGroups {
/**
* O , O , X , O , X
* O , X , O , X , O
* O , O , O , X , O
* O , X , X , X , O
*/
char[][] grid = { {'O' , 'O' , 'X' , 'O' , 'O'} ,
{'O' , 'X' , 'O' , 'X' , 'O'} ,
{'O' , 'O' , 'O' , 'X' , 'O'} ,
{'X' , 'O' , 'X' , 'O' , 'X'} };
public static void main(String[] args) {
CountXGroups countXGroups = new CountXGroups();
countXGroups.countXGroups();
}
private void countXGroups() {
int counter = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
char value = grid[i][j];
if (value == 'X') {
if (!check(grid, i, j)) {
counter++;
}
update(grid, i, j);
}
}
}
System.out.println(counter);
}
private boolean check(char[][] grid, int i, int j) {
return checkLeft(grid, i, j) || checkUp(grid, i, j) ;
}
private void update(char[][] grid, int i, int j) {
grid[i][j] = 'Y';
if (j > 0) {
char left = grid[i][j - 1];
if (left == 'X') {
update(grid, i, j - 1);
}
}
if (j + 1 < grid[i].length) {
char right = grid[i][j + 1];
if (right == 'X') {
update(grid, i, j + 1);
}
}
if (i + 1 < grid.length) {
char down = grid[i + 1][j];
if (down == 'X') {
update(grid, i + 1, j);
}
}
}
private boolean checkUp(char[][] grid, int i, int j) {
if (i > 0) {
if (grid[i - 1][j] == 'Y') {
return true;
}
}
return false;
}
private boolean checkLeft(char[][] grid, int i, int j) {
if (j > 0) {
if (grid[i][j - 1] == 'Y') {
return true;
}
}
return false;
}
}
public class CountXGroups {
/**
* O , O , X , O , X
* O , X , O , X , O
* O , O , O , X , O
* O , X , X , X , O
*/
char[][] grid = { {'O' , 'O' , 'X' , 'O' , 'O'} ,
{'O' , 'X' , 'O' , 'X' , 'O'} ,
{'O' , 'O' , 'O' , 'X' , 'O'} ,
{'X' , 'O' , 'X' , 'O' , 'X'} };
public static void main(String[] args) {
CountXGroups countXGroups = new CountXGroups();
countXGroups.countXGroups();
}
private void countXGroups() {
int counter = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
char value = grid[i][j];
if (value == 'X') {
if (!check(grid, i, j)) {
counter++;
}
update(grid, i, j);
}
}
}
System.out.println(counter);
}
private boolean check(char[][] grid, int i, int j) {
return checkLeft(grid, i, j) || checkUp(grid, i, j) ;
}
private void update(char[][] grid, int i, int j) {
grid[i][j] = 'Y';
if (j > 0) {
char left = grid[i][j - 1];
if (left == 'X') {
update(grid, i, j - 1);
}
}
if (j + 1 < grid[i].length) {
char right = grid[i][j + 1];
if (right == 'X') {
update(grid, i, j + 1);
}
}
if (i + 1 < grid.length) {
char down = grid[i + 1][j];
if (down == 'X') {
update(grid, i + 1, j);
}
}
}
private boolean checkUp(char[][] grid, int i, int j) {
if (i > 0) {
if (grid[i - 1][j] == 'Y') {
return true;
}
}
return false;
}
private boolean checkLeft(char[][] grid, int i, int j) {
if (j > 0) {
if (grid[i][j - 1] == 'Y') {
return true;
}
}
return false;
}
}
1 represents 'X'
0 represents 'O'
public class FindShapes {
public static int countBlackShapes(int[][] arr, int rows, int cols)
{
if(arr.length == 0)
return 0;
int count = 0;
boolean ind = false;
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < cols - 1; j++)
{
if((arr[i][j] == arr[i][j+1]) && arr[i][j] == 1)
{
ind = true;
}
else{
if(ind == true)
count = count + 1;
ind = false;
}
if((j == cols - 2) && ind == true)
{
count = count + 1;
ind = false;
}
}
}
for(int i = 0; i < cols; i++)
{
for(int j = 0; j < rows - 1; j++)
{
if((arr[j][i] == arr[j+1][i]) && arr[j][i] == 1)
{
ind = true;
}
else{
if(ind == true)
count = count + 1;
ind = false;
}
if((j == rows - 2) && ind == true)
{
count = count + 1;
ind = false;
}
}
}
return count;
}
public static void main(String[] args)
{
int arr[][] = {
{1, 1, 0, 1, 1},
{1, 1, 0, 1, 1},
{0, 0, 1, 0, 0}
};
System.out.println(FindShapes.countBlackShapes(arr, 3, 5));
}
}
Using the simple flood fill with DFS, i was able to code something up.
I found algorithm off top coder, but it just uses DFS, and i just substituted Xs for 1s, and marked a node as visited as -1, if you need to restore the graph, you could keep track of items, then just restore afterwards.
public class testJava {
public static void main(String[] args) {
int[][] worldMap = new int[][] { { 0, 0, 0, 1, 0, 0, 0, },
{ 0, 0, 1, 1, 0, 1, 0 }, { 0, 1, 0, 0, 0, 1, 0 } };
testJava test = new testJava();
test.solveProblem(worldMap);
}
public void solveProblem(int[][] worldMap) {
System.out.println("# of rows " + worldMap.length);
System.out.println("# of cols " + worldMap[0].length);
int result = 0;
int maxResult = 0;
for (int i = 0; i < worldMap.length; i++) {
for (int j = 0; j < worldMap[0].length; j++) {
if (worldMap[i][j] > 0) {
result = doFill(worldMap, j, i);
System.out.println("results: " + result);
if (result > maxResult) {
maxResult = result;
}
}
}
}
System.out.println("max result : " + maxResult);
}
public int doFill(int[][] worldMap, int x, int y) {
System.out.println("do fill called x: " + x + " y: " + y);
if (x == 5 && y == 2)
System.out.println("debug");
// check x bounds
if (x < 0 || x >= worldMap[0].length)
return 0;
if (y < 0 || y >= worldMap.length)
return 0;
if (worldMap[y][x] == 0)
return 0;
if (worldMap[y][x] == -1)
return 0;
// visited node
worldMap[y][x] = -1;
return 1 + doFill(worldMap, x - 1, y) + doFill(worldMap, x + 1, y)
+ doFill(worldMap, x, y + 1) + doFill(worldMap, x, y - 1);
}
C++ code using floodfill algorithm
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <string>
using namespace std;
// flood fill.
inline unsigned getKey(unsigned row, unsigned col, unsigned ncols){
return row * ncols + col;
}
template <size_t T>
void fill(char mat[][T], int i, int j, unsigned nrows, unsigned ncols, const unordered_map<unsigned, unsigned> &hash,
unordered_set<unsigned> &visited, unsigned regionId, bool diag){
if (i <0 || i >= nrows || j<0 || j>= ncols || mat[i][j] != 'x') return;
unsigned key = getKey(i,j,ncols);
if (visited.find(key) != visited.end()) return;
cout << "Visited:" << i<<"," <<j<<"\n";
visited.insert(key);
if(diag) fill(mat, i-1, j-1, nrows, ncols, hash, visited, regionId, diag);
fill(mat, i-1, j, nrows, ncols, hash, visited, regionId, diag);
if(diag) fill(mat, i-1, j+1, nrows, ncols, hash, visited, regionId, diag);
fill(mat, i, j-1, nrows, ncols, hash, visited, regionId, diag);
fill(mat, i, j+1, nrows, ncols, hash, visited, regionId, diag);
if(diag) fill(mat, i+1, j-1, nrows, ncols, hash, visited, regionId, diag);
fill(mat, i+1, j, nrows, ncols, hash, visited, regionId, diag);
if(diag) fill(mat, i+1, j+1, nrows, ncols, hash, visited, regionId, diag);
}
template <size_t T>
unsigned getNumRegions(char mat[][T], unsigned nrows, unsigned ncols, bool diag = false){
unsigned num = 0;
unordered_map<unsigned, unsigned> hash;
unordered_set<unsigned> visited;
for (unsigned i=0; i<nrows; ++i){
for (unsigned j=0; j<ncols; ++j){
unsigned key = getKey(i,j,ncols);
if (mat[i][j] != 'x' || (visited.find(key) != visited.end()) ) continue;
cout << "Fill:" << i<<"," <<j<<"\n";
fill<T>(mat, i, j, nrows, ncols, hash, visited, ++num, diag);
}
}
return num;
}
int main() {
char mat[4][3] = {
{'x','o','o'},
{'o','x','x'},
{'x','o','o'},
{'o','x','x'}
};
cout << getNumRegions<3>(mat,4,3, true) <<"\n";
cout << getNumRegions<3>(mat,4,3) <<"\n";
cout << "Done!\n";
return 0;
}
You loop through every cell and as you detect one black cell then you recurse on it to find the black shape holding that black cell. Of course, as you detect black shapes you make them white shapes to prevent repeating yourself.
import java.util.Scanner;
public class Main {
/*
* Input : Row count, Column count then
* the grid with 1's and 0's
* where 1 means black zero means 0.
*
* ex:
* 2 4
* 0 1 1 0
* 1 0 0 1
*
* */
private int n; //row count
private int m; //column count
private int[][] inputGrid;
public void init(){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
/*Surround the input grid with zeros.
* This makes checking neighbours easier.
*/
inputGrid = new int[n+2][m+2];
for(int j = 0 ; j < m+2; j++){
inputGrid[0][j] = 0;
inputGrid[n+1][j] = 0;
}
for(int i = 1 ; i < n+1; i++){
inputGrid[i][0] = 0;
inputGrid[i][m+1] = 0;
for(int j = 1 ; j < m + 1 ; j ++ ){
inputGrid[i][j] = sc.nextInt();
}
}
}
public void detectBlackShape(int i, int j){
inputGrid[i][j] = 0;
if(inputGrid[i][j-1] == 1) detectBlackShape(i, j-1);
if(inputGrid[i-1][j] == 1) detectBlackShape(i-1,j);
if(inputGrid[i+1][j] == 1) detectBlackShape(i+1, j);
if(inputGrid[i][j+1] == 1) detectBlackShape(i, j+1);
}
public int process(){
int count = 0;
for(int i = 1 ; i < n+1 ; i++){
for(int j = 1 ; j < m+1 ; j++){
if(inputGrid[i][j] == 1){
count++;
detectBlackShape(i,j);
}
}
}
return count;
}
public void print(int result){
System.out.println(result);
for(int i = 1 ; i < n+1;i++){
for(int j = 1 ; j < m+1;j++){
System.out.print(inputGrid[i][j] + " ");
}
System.out.println();
}
}
public void run(){
init();
int result = process();
// print(result);
System.out.println(result);
}
public static void main(String[] args) {
new Main().run();
}
}
and
public class CountTheShapes {
public static void main(String[] args) {
char[][] matrix = new char[][]
{"OOOXOOO".toCharArray(),
"OOXXOXO".toCharArray(),
"OXOOOXO".toCharArray()};
boolean visited[][] = new boolean[matrix.length][matrix[0].length];
int count = 0;
for(int row=0;row<matrix.length;row++){
for(int col=0;col<matrix[row].length;col++){
if(!visited[row][col] && matrix[row][col] == 'X'){
searchShape(matrix,row,col,visited);
count++;
}
}
}
System.out.println(count);
}
private static void searchShape(char[][] matrix, int row, int col, boolean[][] visited) {
if(row<0 || row >= matrix.length || col<0 || col >=matrix[row].length){
return;
}
if(visited[row][col] || matrix[row][col] == 'O'){
return;
}
visited[row][col] = true;
searchShape(matrix, row+1, col, visited);
searchShape(matrix, row-1, col, visited);
searchShape(matrix, row, col+1, visited);
searchShape(matrix, row, col-1, visited);
}
}
and
I was asked a variant of this question recently the question was to ind out all the unique objects from these matrix. Consider for example:
- shawn June 19, 20140 1 1 1 0
0 0 1 0 0
1 1 0 1 0
1 1 0 1 1
0 0 0 1 0
so for example the above matrix contains two kinds of shapes one is
1 1 1
1
and the other is
1 1
1 1
Note that the third shape which is
1
1 1
1
is actually the first shape rotated by 90 degrees anticlockwise.
The problem was to find out the unique shapes and a rather more easy part would be how do you store the individual objects. I gave them a solution where each object will be stored as binary string where the corresponding 0's and 1's are being the representation of number of 0's and 1's in all the four directions so for example the object in the following matrix:
0 1 1 1 0
0 0 1 0 0
can be encoded as follows:
Consider the conventions as left->right->top->bottom for counting the adjacent 1s for a position, so the encoded string becomes:
0101#1101#1000#0010
and similarly we can represent other objects by using the following format and then sorting the adjacent substrings separated by #.
We can uniquely represent different objects by using the following conventions, and then rotate the matrix to find out the uniqueness of the object for example the following object:
1
1 1 1will become 1 1 when rotated by 90 degrees anticlockwise and have the same
1 1
representation. This can be used to identify the unique objects in the matrix.