## Amazon Interview Question for Software Engineer in Tests

• 0

Country: India
Interview Type: Written Test

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

Pseudocode for fill color.

void fill_color(int x,int y,int fillcolor,int bordercolor)
{ int currcolor;

currcolor=findcolor(x,y);

if((currcolor!=bordercolor)&(currcolor!=fillcolor))
{
setpixel(x,y,currcolor);
fill_color(x+1,y,fillcolor,bordercolor);//right
fill_color(x-1,y,fillcolor,bordercolor);//left
fill_color(x,y+1,fillcolor,bordercolor);//up
fill_color(x,y-1,fillcolor,bordercolor);//down
}

}

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

setpixel(x,y,fillcolor); //Not currcolor

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

setpixel(x,y,fillcolor); //Not currcolor

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

What's the time and space complexity of this solution? I think it is O(n*m) the time and O(n+m) memory where n is the width and m the height of the grid, but not sure :S

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

This logic is same as above.

``````void fill_color_impl(int** pixmap, int width, int height, int x, int y, int fillColor, int currentColor, int currentColorUndefined) {
if (x < 0 || x >= width ||
y < 0 || y >= height)
return;

if (currentColorUndefined) {
currentColor = pixmap[y][x];
currentColorUndefined = 0;
}

if (currentColor != pixmap[y][x])
return;

pixmap[y][x] = fillColor;
fill_color_impl(pixmap, width, height, x-1, y, fillColor, currentColor, currentColorUndefined);
fill_color_impl(pixmap, width, height, x, y-1, fillColor, currentColor, currentColorUndefined);
fill_color_impl(pixmap, width, height, x+1, y, fillColor, currentColor, currentColorUndefined);
fill_color_impl(pixmap, width, height, x, y+1, fillColor, currentColor, currentColorUndefined);
}

void fill_color(int** pixmap, int width, int height, int x, int y, int fillColor) {
fill_color_impl(pixmap, width, height, x, y, fillColor, 0, 1);
}``````

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

This logic is same as above.

``````void fill_color_impl(int** pixmap, int width, int height, int x, int y, int fillColor, int currentColor, int currentColorUndefined) {
if (x < 0 || x >= width ||
y < 0 || y >= height)
return;

if (currentColorUndefined) {
currentColor = pixmap[y][x];
currentColorUndefined = 0;
}

if (currentColor != pixmap[y][x])
return;

pixmap[y][x] = fillColor;
fill_color_impl(pixmap, width, height, x-1, y, fillColor, currentColor, currentColorUndefined);
fill_color_impl(pixmap, width, height, x, y-1, fillColor, currentColor, currentColorUndefined);
fill_color_impl(pixmap, width, height, x+1, y, fillColor, currentColor, currentColorUndefined);
fill_color_impl(pixmap, width, height, x, y+1, fillColor, currentColor, currentColorUndefined);
}

void fill_color(int** pixmap, int width, int height, int x, int y, int fillColor) {
fill_color_impl(pixmap, width, height, x, y, fillColor, 0, 1);
}``````

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

This logic is same as above.

``````void fill_color_impl(int** pixmap, int width, int height, int x, int y, int fillColor, int currentColor, int currentColorUndefined) {
if (x < 0 || x >= width ||
y < 0 || y >= height)
return;

if (currentColorUndefined) {
currentColor = pixmap[y][x];
currentColorUndefined = 0;
}

if (currentColor != pixmap[y][x])
return;

pixmap[y][x] = fillColor;
fill_color_impl(pixmap, width, height, x-1, y, fillColor, currentColor, currentColorUndefined);
fill_color_impl(pixmap, width, height, x, y-1, fillColor, currentColor, currentColorUndefined);
fill_color_impl(pixmap, width, height, x+1, y, fillColor, currentColor, currentColorUndefined);
fill_color_impl(pixmap, width, height, x, y+1, fillColor, currentColor, currentColorUndefined);
}

void fill_color(int** pixmap, int width, int height, int x, int y, int fillColor) {
fill_color_impl(pixmap, width, height, x, y, fillColor, 0, 1);
}``````

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

Stack overflow will occur as there will be too many recursive calls. Refer to wikipedia "Flood fill " for a more elegant solution using Queues

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

it will quickly overflow for large screen if using DFS. A BFS implementation though a little bit complex.

{{
enum Color {
BLACK, WHITE, RED, YELLOW, GREEN
}

public void paintfill(Color[][] screen, int x, int y, Color ocolor,
Color ncolor) {

while (!queue.isEmpty()) {
Position p = queue.remove();
if (fill(screen, p.x - 1, p.y, ocolor, ncolor))
if (fill(screen, p.x + 1, p.y, ocolor, ncolor))
if (fill(screen, p.x, p.y - 1, ocolor, ncolor))
if (fill(screen, p.x, p.y + 1, ocolor, ncolor))
}

}

public boolean fill(Color[][] screen, int x, int y, Color ocolor,
Color ncolor) {
if (x < 0 || y < 0 || x >= screen[0].length || y >= screen.length)
return false;

if (screen[y][x] == ocolor) {
screen[y][x] = ncolor;
return true;
} else
return false;
}

public static class Position {
public int x;
public int y;

public Position(int x, int y) {
this.x = x;
this.y = y;
}

}}}

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.