Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

#include <iostream>
#include <queue>

struct Coordinates{
    int X;
    int Y;
    Coordinates(int x , int y) : X(x),Y(y){}
};

const int X = 10;
const int Y = 10;

char grid[X][Y] = {
    {'.','.','X','.','.','.','.','.','.','.'},
    {'.','.','X','.','.','.','.','.','.','.'},
    {'.','.','X','.','.','.','.','.','.','.'},
    {'.','.','X','.','.','.','.','.','.','.'},
    {'X','X','X','.','.','.','.','.','.','.'},
    {'.','.','.','.','.','.','.','X','X','X'},
    {'.','.','.','.','.','.','.','X','.','.'},
    {'.','.','.','.','.','.','.','X','.','.'},
    {'.','.','.','.','.','.','.','X','.','.'},
    {'.','.','.','.','.','.','.','X','.','.'},
};

int shifts[4][2] = {
    { -1 , 0 },
    { 1 , 0 },
    { 0, -1 },
    { 0 , 1 }
};

void draw(){
    for (int x = 0; x < X; ++x){
        for(int y = 0; y < Y; ++y){
            std::cout<<grid[x][y];
        }
        std::cout<<std::endl;
    }
}

bool inBounds(int x , int y){
    return x >= 0 && x <X && y>=0 && y<Y;
}

void fill(int x , int y){
    std::queue<Coordinates> cells;
    cells.push(Coordinates(x,y));
    while(!cells.empty()){
        if (grid[cells.front().X][cells.front().Y] == 'X'){
            cells.pop();
            continue;
        }
        for (int i = 0 ; i < 4 ; ++i ){
            Coordinates current = cells.front();
            current.X += shifts[i][0];
            current.Y += shifts[i][1];
            if (inBounds(current.X , current.Y) && grid[current.X][current.Y] == '.')
               cells.push(current); 
        }
        grid[cells.front().X][cells.front().Y] = 'X';
        cells.pop();
    }
}

int main(){
    draw();
    fill(3,0);
    draw();
}

- GK September 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 vote

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);
            }
        }
    }
}

- iKrumping September 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
};

- ninhnnsoc September 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

you should terminate the call if the pixel is already black rather than expanding through to the black pixel's neighbors.

- zortlord September 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@zortlord: my second if statement would do so, isn't it?

Actually, this code missed boundary cases.

- ninhnnsoc September 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Hemant September 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}
}

- Felipe Cerqueira October 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- naren.meeting October 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anonymous September 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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 });
        }
    }

- zortlord September 29, 2014 | 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