Amazon Interview Question
Software Engineer / DevelopersCode :
public void flood(int x, int y){
if(obr[x][y] == 0 ){
obr[x][y] = 2;
flood(x+1,y);
flood(x,y+1);
flood(x-1,y);
flood(x,y-1);
}
}
You obviously missed the question. It explicitly says no recursion. If no recursion then even children can code this.
Almost the same, but without recursion
Queue Q = {node n}
while(Q is not empty)
Node N = Q.deque()
If the color of node N is not equal to target-color,
continue
If the color of node is equal to replacement-color,
continue
Set the color of node to replacement-color.
Q.enque(one step to the east of node)
Q.enque(one step to the west of node)
Q.enque(one step to the north of node)
Q.enque(one step to the south of node)
Return.
Flood-fill (node, target-color, replacement-color):
- pavan September 09, 20091. If the color of node is not equal to target-color, return.
2. If the color of node is equal to replacement-color, return.
3. Set the color of node to replacement-color.
4. Perform Flood-fill (one step to the west of node, target-color, replacement-color).
Perform Flood-fill (one step to the east of node, target-color, replacement-color).
Perform Flood-fill (one step to the north of node, target-color, replacement-color).
Perform Flood-fill (one step to the south of node, target-color, replacement-color).
5. Return.