Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Simple recursive solution in Java
public class Main {
public static void main(String[] args) {
char[][] arrayToFill = {
{'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
{'.', 'X', 'X', 'X', '.', '.', 'X', 'X', 'X', '.'},
{'.', 'X', '.', 'X', 'X', 'X', 'X', '.', 'X', '.'},
{'.', 'X', '.', '.', '.', '.', '.', '.', 'X', '.'},
{'.', 'X', '.', '.', '.', '.', '.', '.', 'X', '.'},
{'.', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', '.'},
{'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'}};
fillArray(arrayToFill, 4, 6);
for(char[] string: arrayToFill) {
for(char symbol: string) {
System.out.print(symbol);
}
System.out.println();
}
}
private static void fillArray(char[][] arrayToFill,int y, int x) {
if(x >= 0 && y >= 0 && arrayToFill.length > y && arrayToFill[0].length > x){
if(arrayToFill[y][x] == '.') {
arrayToFill[y][x] = 'X';
fillArray(arrayToFill, y, x + 1);
fillArray(arrayToFill, y, x - 1);
fillArray(arrayToFill, y + 1, x);
fillArray(arrayToFill, y - 1, x);
}
}
}
}
void floodFill(int x, int y){
Color[x,y] = black; // fill this pixel
for(u = -1; u<=1; u++)
for(v = -1; v<=1; v++)
if (u*v == 0 and u+v != 0) // go to left, right, up, down pixels only
if (Color[x+u,y+v] == white)
floodFill(x+u,y+v);
return;
};
you should terminate the call if the pixel is already black rather than expanding through to the black pixel's neighbors.
#include <iostream>
#include <queue>
using namespace std;
struct Index {
int r;
int c;
Index(int x1, int y1) :r(x1), c(y1)
{
}
};
void FloodFill(char arr[7][10], int row, int col, int currRow, int currCol){
queue<Index> que;
que.push(Index(currRow, currCol));
while (!que.empty())
{
Index curr = que.front();
arr[curr.r][curr.c] = 'X';
que.pop();
if (curr.r - 1 >= 0 && arr[curr.r - 1][curr.c] == '.')
{
arr[curr.r-1][curr.c] = 'X';
que.push(Index(curr.r - 1, curr.c));
}
if (curr.c - 1 >= 0 && arr[curr.r][curr.c - 1] == '.')
{
arr[curr.r][curr.c-1] = 'X';
que.push(Index(curr.r, curr.c-1));
}
if (curr.r + 1 < row && arr[curr.r + 1][curr.c] == '.')
{
arr[curr.r + 1][curr.c] = 'X';
que.push(Index(curr.r + 1, curr.c));
}
if (curr.c + 1 < col && arr[curr.r][curr.c + 1] == '.')
{
arr[curr.r][curr.c+1] = 'X';
que.push(Index(curr.r, curr.c+1));
}
}
}
void FloodFillRec(char arr[7][10], int row, int col, int currRow, int currCol){
arr[currRow][currCol] = 'X';
if (currRow - 1 >= 0 && arr[currRow - 1][currCol] == '.')
{
FloodFillRec(arr, row, col, currRow -1, currCol);
}
if (currCol - 1 >= 0 && arr[currRow][currCol - 1] == '.')
{
FloodFillRec(arr, row, col, currRow, currCol-1);
}
if (currRow + 1 < row && arr[currRow + 1][currCol] == '.')
{
FloodFillRec(arr, row, col, currRow+1, currCol);
}
if (currCol + 1 < col && arr[currRow][currCol + 1] == '.')
{
FloodFillRec(arr, row, col, currRow, currCol+1);
}
}
int main()
{
char in[9][10] = {
{ '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
{ '.', 'X', 'X', 'X', '.', '.', 'X', 'X', 'X', '.' },
{ '.', 'X', '.', 'X', 'X', 'X', 'X', '.', 'X', '.' },
{ '.', 'X', '.', '.', '.', '.', '.', '.', 'X', '.' },
{ '.', 'X', '.', '.', '.', '.', '.', '.', 'X', '.' },
{ '.', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', '.' },
{ '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
{ '.', 'X', '.', '.', '.', '.', '.', '.', 'X', '.' },
{ '.', 'X', '.', '.', '.', '.', '.', '.', 'X', '.' },
};
FloodFillRec(in, 10, 10, 3, 3);
return 0;
}
import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone
{
private char[][] arr;
public Ideone(char[][] in)
{
arr = deepCopy(in);
}
private char[][] deepCopy(char[][] in)
{
char[][] out = new char[in.length][];
for (int i = 0; i < in.length; i++) {
out[i] = Arrays.copyOf(in[i], in[i].length);
}
return out;
}
private void printArr()
{
for (int i = 0; i < arr.length; i++) {
for (int l = 0; l < arr[i].length; l++)
System.out.print(arr[i][l] + " ");
System.out.println();
}
}
private void fill(int x, int y)
{
arr[x][y] = 'X';
printArr();
if (y + 1 < arr[0].length && arr[x][y + 1] == '.')
fill(x, y + 1);
if (x + 1 < arr.length && arr[x + 1][y] == '.')
fill(x + 1, y);
if (x > 0 && arr[x - 1][y] == '.')
fill(x - 1, y);
if (y > 0 && arr[x][y - 1] == '.')
fill(x, y - 1);
return;
}
public static void main (String[] args) throws java.lang.Exception
{
char[][] in={
{'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'},
{'.', 'X', 'X', 'X', '.', '.', 'X', 'X', 'X', '.'},
{'.', 'X', '.', 'X', 'X', 'X', 'X', '.', 'X', '.'},
{'.', 'X', '.', '.', '.', '.', '.', '.', 'X', '.'},
{'.', 'X', '.', '.', '.', '.', '.', '.', 'X', '.'},
{'.', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', '.'},
{'.', '.', '.', '.', '.', '.', '.', '.', '.', '.'}};
Ideone ide = new Ideone(in);
ide.printArr();
ide.fill(2, 2);
}
}
package com.nv;
public class Main {
public static void main(String[] args) {
new Main().run();
}
private int[][] arr = { {0,0,0,0,0,0,0},
{0,1,1,1,1,0,0},
{0,1,0,0,1,0,0},
{0,1,0,0,1,0,0},
{0,1,1,1,1,0,0},
{0,0,0,0,0,0,0},
};
private void run() {
print();
fillAt(2,2);
print();
}
private void print() {
System.out.println("---------------------------------------");
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
System.out.print(" " + arr[i][j]);
}
System.out.println("");
}
System.out.println("---------------------------------------");
}
private void fillAt(int r, int c) {
if(r < 0 || c <0 || r >= arr.length || c >= arr[r].length || arr[r][c] == 1)
return;
arr[r][c] = 1;
fillAt(r+1, c);
fillAt(r-1, c);
fillAt(r, c+1);
fillAt(r, c-1);
}
}
---------------- Out Put -----------------------
---------------------------------------
0 0 0 0 0 0 0
0 1 1 1 1 0 0
0 1 0 0 1 0 0
0 1 0 0 1 0 0
0 1 1 1 1 0 0
0 0 0 0 0 0 0
---------------------------------------
---------------------------------------
0 0 0 0 0 0 0
0 1 1 1 1 0 0
0 1 1 1 1 0 0
0 1 1 1 1 0 0
0 1 1 1 1 0 0
0 0 0 0 0 0 0
---------------------------------------
the easiest method would probably be to create a method which can be recursively called, and keep a global list of visited noted, ie. bfs. You could also identify the borders of the region and then use an algorithm to fill the region inside, but that would be probably too overengineered for most purposes
How about a DFS approach:
private static final char BLACK = 'X';
private static final char WHITE = '.';
public void fill(char[][] pic, int x, int y){
//discard bad inputs
if(pic == null || pic.length == 0 || pic[0].length == 0 || x < 0 || x >= pic.length || y < 0 || y >= pic[0].length || pic[x][y] == BLACK)
return;
//initialize tracking variables
//tracks whether the position has already been added to the stack
boolean[][] added = new boolean[pic.length][pic[0].length];
//tracks the places that should be checked
Stack<int[]> unchecked = new Stack<int[]>();
unchecked.add(new int[]{x, y});
while(!unchecked.isEmpty()){
int[] pos = unchecked.pop();
pic[pos[0]][pos[1]] = BLACK;
for(int[] newPos : getPossiblePos(pic, added, pos)){
added[newPos[0]][newPos[1]] = true;
unchecked.add(newPos);
}
}
}
public ArrayList<int[]> getPossiblePos(char[][] pic, boolean[][] added, int[] pos) {
ArrayList<int[]> results = new ArrayList<int[]>(8);
// if has column to the left
if (pos[0] > -1) {
// if has column to the right
if (pos[0] < pic.length) {
// if it has a top row
if (pos[1] > -1) {
// if it has a bottom row
if (pos[1] < pic[0].length) {
int xLo = pos[0] - 1;
int xHi = pos[0] + 1;
int yLo = pos[1] - 1;
int yHi = pos[1] + 1;
addIfValid(results, xLo, yLo);
addIfValid(results, xLo, pos[1]);
addIfValid(results, xLo, yHi);
addIfValid(results, pos[0], yLo);
addIfValid(results, pos[0], yHi);
addIfValid(results, xHi, yLo);
addIfValid(results, xHi, pos[1]);
addIfValid(results, xHi, yHi);
}
// no bottom row
else {
int xLo = pos[0] - 1;
int xHi = pos[0] + 1;
int yLo = pos[1] - 1;
addIfValid(results, xLo, yLo);
addIfValid(results, xLo, pos[1]);
addIfValid(results, pos[0], yLo);
addIfValid(results, xHi, yLo);
addIfValid(results, xHi, pos[1]);
}
}
// else has not top row but has a bottom row
else if (pos[1] < pic[0].length) {
int xLo = pos[0] - 1;
int xHi = pos[0] + 1;
int yHi = pos[1] + 1;
addIfValid(results, xLo, pos[1]);
addIfValid(results, xLo, yHi);
addIfValid(results, pos[0], yHi);
addIfValid(results, xHi, pos[1]);
addIfValid(results, xHi, yHi);
}
// has no top or bottom row
else {
int xLo = pos[0] - 1;
int xHi = pos[0] + 1;
addIfValid(results, xLo, pos[1]);
addIfValid(results, xHi, pos[1]);
}
}
// no right column
else {
// if it has a top row
if (pos[1] > -1) {
// if it has a bottom row
if (pos[1] < pic[0].length) {
int xLo = pos[0] - 1;
int yLo = pos[1] - 1;
int yHi = pos[1] + 1;
addIfValid(results, xLo, yLo);
addIfValid(results, xLo, pos[1]);
addIfValid(results, xLo, yHi);
addIfValid(results, pos[0], yLo);
addIfValid(results, pos[0], yHi);
}
// no bottom row
else {
int xLo = pos[0] - 1;
int yLo = pos[1] - 1;
addIfValid(results, xLo, yLo);
addIfValid(results, xLo, pos[1]);
addIfValid(results, pos[0], yLo);
}
}
// else has not top row but has a bottom row
else if (pos[1] < pic[0].length) {
int xLo = pos[0] - 1;
int yHi = pos[1] + 1;
addIfValid(results, xLo, pos[1]);
addIfValid(results, xLo, yHi);
addIfValid(results, pos[0], yHi);
}
// has no top or bottom row
else {
int xLo = pos[0] - 1;
addIfValid(results, xLo, pos[1]);
}
}
}
// if has column to the right but none to the left
else if (pos[0] < pic.length) {
// if it has a top row
if (pos[1] > -1) {
// if it has a bottom row
if (pos[1] < pic[0].length) {
int xHi = pos[0] + 1;
int yLo = pos[1] - 1;
int yHi = pos[1] + 1;
addIfValid(results, pos[0], yLo);
addIfValid(results, pos[0], yHi);
addIfValid(results, xHi, yLo);
addIfValid(results, xHi, pos[1]);
addIfValid(results, xHi, yHi);
}
// no bottom row
else {
int xHi = pos[0] + 1;
int yLo = pos[1] - 1;
addIfValid(results, pos[0], yLo);
addIfValid(results, xHi, yLo);
addIfValid(results, xHi, pos[1]);
}
}
// else has not top row but has a bottom row
else if (pos[1] < pic[0].length) {
int xHi = pos[0] + 1;
int yHi = pos[1] + 1;
addIfValid(results, pos[0], yHi);
addIfValid(results, xHi, pos[1]);
addIfValid(results, xHi, yHi);
}
// has no top or bottom row
else {
int xHi = pos[0] + 1;
addIfValid(results, xHi, pos[1]);
}
}
// no right column
else {
// if it has a top row
if (pos[1] > -1) {
// if it has a bottom row
if (pos[1] < pic[0].length) {
int yLo = pos[1] - 1;
int yHi = pos[1] + 1;
addIfValid(results, pos[0], yLo);
addIfValid(results, pos[0], yHi);
}
// no bottom row
else {
int yLo = pos[1] - 1;
addIfValid(results, pos[0], yLo);
}
}
// else has not top row but has a bottom row
else if (pos[1] < pic[0].length) {
int yHi = pos[1] + 1;
addIfValid(results, pos[0], yHi);
}
}
return results;
}
public void addIfValid(ArrayList<int[]> list, char[][] pic, boolean[][] added, int x, int y) {
if (pic[x][y] == WHITE && !added[x][y]) {
list.add(new int[] { x, y });
}
}
- GK September 29, 2014