Google Onsite | L3/L4
1767

Consider MxN Source Grid and Target Grid.
Soure grid consist of 0's and 1's
Target Grid consit of only 0's.
You don't have access to these grids.

You have following two functions as black box(you don't have to implement them)
int getSource(int i, int j, int i1, int j1) -> return1 if the rectangle enclosed by these co-ordinates in the source grid contain all 1's else return -1.
void setTarget(int i, int j, int i1, int j1) -> Assign 1 to all the points present inside the rectangle enclosed by these co-ordinates in the target grid.
Both of these operations are O(1).

Now, Convert the target grid into the source grid by only using these 2 functions.

Ex:
Source:
1 0 1 0 0 0
1 1 1 0 0 0
1 1 1 1 1 1

getSource(0, 0, 0, 5) -> -1
getSource(1, 0, 2, 2) -> 1

Target:
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

setTarget(2, 2, 3, 4) ->
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 1 1 0
0 0 1 1 1 0

Comments (8)