Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
You get into infinite recursion here if oldColor ==
newColor. I would add a quick explicit check for that condition.
use a linefill approach much faster..
start with (x,y) extend to [L,R] where L & R are left and right extreme on the monochromatic extensions.
then construct lines top and bottom of this line which are monochromatic extensions
this one will fill as lines and will beat the above algorithm in complexity as you are visiting every point 8 times
ashish, I don't see how that is faster. In order to find L and R, you need to scan the image one pixel at a time in both directions to see if there's an interruption. (Unless there's a better way I'm not seeing?) But if you do this, you might as well color each pixel as you go, which is essentially the same thing as this algorithm is doing.
@above
Hello,
please have a look in this way
i am at (x,y) i will check (x-1,y) ,(x,y-1),(x+1,y) ,(x,y+1) and not necessarily in this order.. but all of these will be checked
i sure have made (x,y) as new color but when i am at(x-1,y) i am still going to check (x,y),(x-1,y-1),(x-1,y+1),(x-2,y) because still the if statement needs to run so this is redundant check.. but if i know from [1,15] all are newcolor at given y-coordinate .. i dont need to check those coordinate again rather i will be looking at (y-1) coordinate points [1,15] and then left and right extend to get the new Line[L,R] at y-1 coordinate and same way the y + 1 direction.
#include <iostream>
#include <cstdlib>
using namespace std;
class BucketFill
{
const int m_XLen;
const int m_YLen;
int* m_bitmap;
int m_oldColor;
int m_newColor;
int& Color(int x, int y)
{
return m_bitmap[x * m_YLen + y];
}
typedef int Direction; // N = 0, NE = 1, E = 2, SE = 3, S = 4, SW = 5, W = 6, NW = 7, NOWHERE = 8
static const int NOWHERE = 8;
Direction Opposite(Direction d)
{
if (d >= 0 && d < NOWHERE)
return (d + 4) % 8;
else
return NOWHERE;
}
Direction FindNext(int x, int y)
{
for (Direction d = 0; d <= 7; ++d)
{
int xx = x;
int yy = y;
if (Move(xx, yy, d) && Color(xx, yy) == m_oldColor)
return d;
}
return NOWHERE;
}
bool Move(int& x, int& y, Direction d)
{
int xx = x;
int yy = y;
switch (d)
{
case 0: --yy; break; // N
case 1: ++xx; --yy; break; // NE
case 2: ++xx; break; // E
case 3: ++xx; ++yy; break; // SE
case 4: ++yy; break; // S
case 5: --xx; ++yy; break; // SW
case 6: --xx; break; // W
case 7: --xx; --yy; break; // NW
default: break; // NOWHERE
}
if (xx >= 0 && xx < m_XLen && yy >= 0 && yy < m_YLen)
{
x = xx;
y = yy;
return true;
}
return false;
}
int Base()
{
return ~m_oldColor & 0xFF;
}
void SetPrevDirection(int x, int y, Direction d)
{
Color(x, y) = Base() + d;
}
Direction GetPrevDirection(int x, int y)
{
return Color(x, y) - Base();
}
bool FillSome(int& x, int& y)
{
Direction d = FindNext(x, y);
if (d != NOWHERE)
{
Move(x, y, d);
SetPrevDirection(x, y, Opposite(d));
}
else
{
const Direction d = GetPrevDirection(x, y);
Color(x, y) = m_newColor;
if (d == NOWHERE)
return false;
Move(x, y, d);
}
return true;
}
public:
BucketFill(int* bitmap, int XLen, int YLen)
: m_bitmap(bitmap)
, m_XLen(XLen)
, m_YLen(YLen)
{}
void Fill(int newColor, int x0, int y0)
{
m_newColor = newColor;
m_oldColor = Color(x0, y0);
SetPrevDirection(x0, y0, NOWHERE);
while (FillSome(x0, y0))
;
}
};
void Print(int* bitmap, int XLen, int YLen, const char* msg)
{
cout << msg << endl;
for (int y = 0; y < YLen; ++y)
{
for (int x = 0; x < XLen; ++x)
{
cout << (char)(bitmap[x * YLen + y] & 0xFF);
}
cout << endl;
}
cout << endl;
}
int main()
{
const int oldColor = 'X';
const int newColor = '+';
const int otherColor = ' ';
const int x0 = 0;
const int y0 = 0;
const int XLen = 40;
const int YLen = 20;
int bitmap[XLen][YLen] = {0};
for (int x = 0; x < XLen; ++x)
for (int y = 0; y < YLen; ++y)
{
const bool isOld = rand() < RAND_MAX / 2;
bitmap[x][y] = isOld ? oldColor : otherColor;
}
Print(&bitmap[0][0], XLen, YLen, "before:");
BucketFill bf(&bitmap[0][0], XLen, YLen);
bf.Fill(newColor, x0, y0);
Print(&bitmap[0][0], XLen, YLen, "after:");
return 0;
}
public void changeColor(int[][] a, int newcolor, int oldcolor, int x, int y){
int row = a.length;
int col = a[0].length;
if(x-1>=0 && a[x-1][y] == oldcolor){
a[x-1][y] = newcolor;
changeColor(a, newcolor, oldcolor,x-1,y);
}
if(y+1<col && a[x][y+1] == oldcolor){
a[x][y+1] = newcolor;
changeColor(a, newcolor, oldcolor,x,y+1);
}
if(x+1<row && a[x+1][y] == oldcolor){
a[x+1][y] = newcolor;
changeColor(a, newcolor, oldcolor,x+1,y);
}
if(y-1>=0 && a[x][y-1] == oldcolor){
a[x][y-1] = newcolor;
changeColor(a, newcolor, oldcolor,x,y-1);
}
return;
}
struct Point{
int x;
int y;
};
void bucketfill(int newcolor, int x, int y, vector<vector<int> >& bitmap) {
Point direction[4] = {(-1 , 0), (0, -1), (0, 1), (1, 0)};
vector<Point> list;
Point s;
s.x = x;
s.y = y;
list.push_back(s);
int c = 0, color = bitmap[x][y];
bitmap[x][y] = newcolor;
while(c < list.size()){
for(int i = 0; i < 4; i++){
Point newp;
newp.x = list[c].x + direction[i].x;
newp.y = list[c].y + direction[i].y;
if(newp.x >=0 && newp.x < bitmap.size() && newp.y >= 0 && newp.y < bitmap[newp.x].size() && bitmap[newp.x][newp.y] == color){
list.push_back(newp);
bitmap[newp.x][newp.y] = newcolor;
}
}
c++;
}
}
- skeptical.scientist January 05, 2013def bucketfill(image,newcolor,x,y): width=len(image) height=len(image[0]) oldcolor=image[x][y] if oldcolor==newcolor: return #added because of eugene's reply image[x][y]=newcolor if x>0: if image[x-1][y]==oldcolor: bucketfill(image,newcolor,x-1,y) if y>0: if image[x][y-1]==oldcolor: bucketfill(image,newcolor,x,y-1) if x<width-1: if image[x+1][y]==oldcolor: bucketfill(image,newcolor,x+1,y) if y<height-1: if image[x][y+1]==oldcolor: bucketfill(image,newcolor,x,y+1) return