CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Facebook Interview Question


Country: United States



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

Working Java code. Could probably be made a little bit more efficient but I verified that it works. Idea is to try dropping water on every square and let it flow to the square's neighbors (if they have a height that is less than or equal to the current square's height), and then update information about the current square.

import java.util.ArrayList;

public class ContinentalDivide {

    public static class Square {
        public boolean canReachPacific;
        public boolean canReachAtlantic;
        public boolean visited;

        public Square() {
            canReachPacific = false;
            canReachAtlantic = false;
            visited = false;
        }
    }

    private static class Position {
        public int row, col;

        public Position(int row, int col) {
            this.row = row;
            this.col = col;
        }

        public String toString() {
            return "(" + row + ", " + col + ")";
        }
    }

    public static ArrayList<Position> getContinentalDivide(int[][] height) {
        int nrows = height.length;
        int ncols = height[0].length;
        Square[][] grid = new Square[nrows][ncols];

        // create Square objects
        for (int row = 0; row < nrows; row++) {
            for (int col = 0; col < ncols; col++) {
                grid[row][col] = new Square();
            }
        }

        // mark .canReachPacific and .canReachAtlantic as true for edges
        for (int row = 0; row < nrows; row++) {
            grid[row][0].canReachPacific = true;
            grid[row][ncols-1].canReachAtlantic = true;
        }
        for (int col = 0; col < ncols; col++) {
            grid[0][col].canReachPacific = true;
            grid[nrows-1][col].canReachAtlantic = true;
        }

        // visit every square and drop water on it
        for (int row = 0; row < nrows; row++) {
            for (int col = 0; col < ncols; col++) {
                if (!grid[row][col].visited)
                    dropWater(row, col, grid, height);
            }
        }

        ArrayList<Position> divide = new ArrayList<Position>();
        for (int row = 0; row < nrows; row++) {
            for (int col = 0; col < ncols; col++) {
                if (grid[row][col].canReachPacific && grid[row][col].canReachAtlantic)
                    divide.add(new Position(row, col));
            }
        }

        return divide;
    }

    // drop water on a square, let it flow to surrounding squares if possible,
    // and then update the current square's .canReachPacific and .canReachAtlantic
    // instance variables
    public static void dropWater(int row, int col, Square[][] grid, int[][] height) {
        int nrows = height.length;
        int ncols = height[0].length;

        grid[row][col].visited = true;

        // up
        if (row != 0 && height[row][col] >= height[row-1][col]) {
            if (!grid[row-1][col].visited)
                dropWater(row-1, col, grid, height);
            grid[row][col].canReachPacific |= grid[row-1][col].canReachPacific;
            grid[row][col].canReachAtlantic |= grid[row-1][col].canReachAtlantic;
        }

        // down
        if (row != nrows-1  && height[row][col] >= height[row+1][col]) {
            if (!grid[row+1][col].visited)
                dropWater(row+1, col, grid, height);
            grid[row][col].canReachPacific |= grid[row+1][col].canReachPacific;
            grid[row][col].canReachAtlantic |= grid[row+1][col].canReachAtlantic;
        }

        // left
        if (col != 0 && height[row][col] >= height[row][col-1]) {
            if (!grid[row][col-1].visited)
                dropWater(row, col-1, grid, height);
            grid[row][col].canReachPacific |= grid[row][col-1].canReachPacific;
            grid[row][col].canReachAtlantic |= grid[row][col-1].canReachAtlantic;
        }

        // right
        if (col != ncols-1 && height[row][col] >= height[row][col+1]) {
            if (!grid[row][col+1].visited)
                dropWater(row, col+1, grid, height);
            grid[row][col].canReachPacific |= grid[row][col+1].canReachPacific;
            grid[row][col].canReachAtlantic |= grid[row][col+1].canReachAtlantic;
        }
    }

    public static void main(String[] args) {
        int[][] height = {
            {1, 2, 2, 3, 5},
            {3, 2, 3, 4, 4},
            {2, 4, 5, 3, 1},
            {6, 7, 1, 4, 5},
            {5, 1, 1, 2, 4}
        };

        ArrayList<Position> divide = getContinentalDivide(height);

        for (Position p : divide)
            System.out.println(p);
    }

}

- Sid March 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can keep a secondary 2D array with each element keeping 2 boolean values P and A.
Pass through the perimeter elements of the continent and check to see if these values have direct access to P or A. Then Pass through again checking to see if they have direct access to P or A, again through neighbors with smaller heights.

Now that we have checked the outer perimeter, we will check the first inner perimeter twice again- Check all outward neighbors of elements- if any of these outward elements are smaller in height, OR the current element's A and P boolean values with that of the neighbors.

Continue this until you get to the middle element.

Finally, pass through all of the elements and return those that have both boolean values set to true.

Assuming rectangle with height of m and width of n,

Runtime: 3m*n
Space: m*n

- SK March 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Start with the shoreline. Let the water flow *up* from the shore, and mark the ocean it came from. If land is encountered with marks from both oceans, add it to the results.

enum ocean{NONE, PACIFIC, ATLANTIC};
struct coord{ int x, y; };
struct entry{ int x, y; ocean o; };

std::vector<coord> FindDivides(int* pTerrain, int w, int h)
{
   std::vector<coord> results;
   std::vector<int> oceanMap(w*h, NONE);
   std::stack<entry> todo;

   for (int i = 0; i < w; i++)
   {
      todo.push({ i, 0, PACIFIC });
      todo.push({ i, h - 1, ATLANTIC });
   }
   for (int i = 0; i < h; i++)
   {
      todo.push({ 0, i, PACIFIC });
      todo.push({ w-1, i, ATLANTIC });
   }
   while (todo.size())
   {
      entry e = todo.top();
      todo.pop();
      int idx = e.y*w + e.x;
      if (oceanMap[idx] & e.o)
         continue;
      oceanMap[idx] |= e.o;
      if (oceanMap[idx] == (PACIFIC|ATLANTIC))
         results.push_back({ e.x, e.y });
      coord nextc[4] = { { e.x - 1, e.y }, { e.x + 1, e.y },
                         { e.x, e.y - 1 }, { e.x, e.y + 1 } };
      for (coord c : nextc)
      {
         if ((c.x < 0) || (c.x >= w) || (c.y < 0) || (c.y >= h))
            continue;
         int nextIdx = c.y*w + c.x;
         if ((pTerrain[nextIdx] >= pTerrain[idx]) && !(oceanMap[nextIdx] & e.o))
            todo.push({ c.x, c.y, e.o });
      }
   }
   return results;
}

void main()
{
   int heights[] = {1, 2, 2, 3, 5,
                    3, 2, 3, 4, 4,
                    2, 4, 5, 3, 1,
                    6, 7, 1, 4, 5,
                    5, 1, 1, 2, 4 };
   std::vector<coord> results = FindDivides(heights, 5, 5);
   for (coord c : results)
      printf("(%d, %d), ", c.x, c.y);
   getch();
}

output:

(2, 2), (3, 1), (4, 1), (4, 0), (1, 3), (0, 4), (0, 3),

- tjcbs2 March 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is possible for this solution to add a cell in to a queue more than once? How do you mark 'visited' status?

If you don't deal with the 'visited' status, what is the time complexity for this solution?

- mattsun March 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

There are two checks for visited status:

(oceanMap[idx] & e.o)

If this is non-zero then the "water" of the current ocean (e.o) has already visited this cell. One check is done before adding the new cell to the stack. The other is done after the cell is popped from the stack, before it is processed, because it is possible that the cell was visited after it was added to the stack.

Time complexity is O(w*h). Without handling visited status, it would be O((w*h)^2).

- tjcbs2 March 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If there are several oceans around, will this solution put the cell into the queue every time an ocean connects to this cell?

- mattsun March 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Flow water upwards from Pacific and Atlantic and look for intersection.

import java.util.*;

public class Divide {
    private static class Node {
	public int row;
	public int column;

	public int hashCode() {
	    return row + column;
	}

	public boolean equals(Object obj) {
	    if (obj == this) {
		return true;
	    } else if (obj instanceof Node) {
		Node n = (Node)obj;
		return (n.row == this.row && n.column == this.column);
	    } else {
		return false;
	    }
	}

	public String toString() {
	    StringBuffer buf = new StringBuffer();
	    buf.append(this.row);
	    buf.append(",");
	    buf.append(this.column);
	    return buf.toString();
	}

	public Node() {
	}

	public Node(int row, int column) {
	    this.row = row;
	    this.column = column;
	}
    };

    private int array[][];
    private HashSet<Node> pacific;
    private HashSet<Node> atlantic;
    private HashSet<Node> divide;
    private int rows;
    private int columns;

    private Divide() {
    }
    
    private void divide(int array[][]) {
	this.array = array;
	this.rows = array.length;
	this.columns = array[0].length;

	this.pacific = this.initPacific();
	this.atlantic = this.initAtlantic();
	this.divide = new HashSet<Node>();

	this.findDivide();
	this.dump();
    }

    private void dump() {
	for (Node node : this.divide) {
	    System.out.print("{");
	    System.out.print(node.row);
	    System.out.print(",");
	    System.out.print(node.column);
	    System.out.print("}");
	    System.out.print(",\n");
	}
    }

    private void findDivide() {
	HashSet<Node> newPacific = new HashSet<Node>(this.pacific);
	HashSet<Node> newAtlantic = new HashSet<Node>(this.atlantic);

	while (true) {
	    newPacific = this.findNext(newPacific, 1, 1);
	    newAtlantic = this.findNext(newAtlantic, -1, -1);
	    if (!newPacific.isEmpty() || !newAtlantic.isEmpty()) {
		this.pacific.addAll(newPacific);
		this.atlantic.addAll(newAtlantic);
	    } else {
		HashSet<Node>intersect = new HashSet<Node>(this.pacific);
		intersect.retainAll(this.atlantic);    
		this.divide.addAll(intersect);
		return;
	    }
	}
    }

    private HashSet<Node> findNext(HashSet<Node>set, int rowDir, int columnDir) {
	HashSet<Node> newSet = new HashSet<Node>();
	for (Node node : set) {
	    int otherRow = node.row + rowDir;
	    if (0 <= otherRow && otherRow < this.rows) {
		int n = this.array[otherRow][node.column];
		if (n >= this.array[node.row][node.column]) {
		    Node otherNode = new Node(otherRow, node.column);
		    newSet.add(otherNode);
		}
	    }

	    int otherColumn = node.column + columnDir;
	    if (0 <= otherColumn && otherColumn < this.columns) {
		int n = this.array[node.row][otherColumn];
		if (n >= this.array[node.row][node.column]) {
		    Node otherNode = new Node(node.row, otherColumn);
		    newSet.add(otherNode);
		}
	    }
	}

	return newSet;
    }

    private HashSet<Node>initPacific() {
	HashSet<Node>set = new HashSet<Node>();
	for (int i = 0; i < this.rows; i++) {
	    set.add(new Node(i, 0));
	}
	for (int i = 1; i < this.columns; i++) {
	    set.add(new Node(0, i));
	}
	return set;
    }

    private HashSet<Node>initAtlantic() {
	HashSet<Node> set = new HashSet<Node>();
	for (int i = 0; i < this.rows; i++) {
	    set.add(new Node(i, this.columns-1));
	}
	for (int i = 0; i < this.columns-1; i++) {
	    set.add(new Node(this.rows - 1, i));
	}
	return set;
    }

    public static void main(String args[]) {
	int array[][]= { { 1,2,2,3,5},{3,2,3,4,4},{2,4,5,3,1},{6,7,1,4,5},{5,1,1,2,4}};
	Divide divide = new Divide();
	divide.divide(array);
    }
}

- babesh March 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solution in PHP, water flows in reverse direction from outer oceans to identify intersections, flowing occurs through recursion:

class ContinentalDivide
{
    const PACIFIC = 1;
    const ATLANTIC = 2;

    public static function find(&$cont)
    {
        $results = '';
        $cont_height = count($cont);
        $cont_width = count($cont[0]);

        for ($y = 0; $y < $cont_height; ++$y) {
            $results .= self::flows($y, 0, 0, self::PACIFIC, $cont); // Flow East from Pacific
            $results .= self::flows($y, $cont_width - 1, 0, self::ATLANTIC, $cont); // Flow West from Atlantic
        }

        for ($x = 0; $x < $cont_width; ++$x) {
            $results .= self::flows(0, $x, 0, self::PACIFIC, $cont); // Flow South from Pacific
            $results .= self::flows($cont_height - 1, $x, 0, self::ATLANTIC, $cont); // Flow North from Atlantic
        }
        return ' [' . rtrim($results, ' ,') . ']';
    }

    private static function flows($y, $x, $flow, $ocean, &$cont)
    {
        $results = '';
        if (isset($cont[$y][$x]) && (!($cont[$y][$x][1] & $ocean)) && ($flow <= $cont[$y][$x][0])) {
            $cont[$y][$x][1] |= $ocean;
            if ($cont[$y][$x][1] == (self::PACIFIC | self::ATLANTIC))
                $results .= "($x,$y), ";
            $results .= self::flows($y + 1, $x, $cont[$y][$x][0], $ocean, $cont);
            $results .= self::flows($y - 1, $x, $cont[$y][$x][0], $ocean, $cont);
            $results .= self::flows($y, $x + 1, $cont[$y][$x][0], $ocean, $cont);
            $results .= self::flows($y, $x - 1, $cont[$y][$x][0], $ocean, $cont);
        }
        return $results;
    }
}

$cont = array(
    array(array(1, 0), array(2, 0), array(2, 0), array(3, 0), array(5, 0)),
    array(array(3, 0), array(2, 0), array(3, 0), array(4, 0), array(4, 0)),
    array(array(2, 0), array(4, 0), array(5, 0), array(3, 0), array(1, 0)),
    array(array(6, 0), array(7, 0), array(1, 0), array(4, 0), array(5, 0)),
    array(array(5, 0), array(1, 0), array(1, 0), array(2, 0), array(4, 0))
);

echo ContinentalDivide::find($cont);

- JosephB May 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solution in C++.
I used DFS to search the graph.

Running time will be O(N) for DFS.

#include<iostream>
using namespace std;

#define ATLANTIC 2
#define PACIFIC 1

int x_move[4] = {-1,0,1,0};
int y_move[4] = {-0,-1,0,1};



void dfs(int** map, int** marked, int w, int h, int x, int y, int dir)
{
  for (int m = 0; m < 4; m++)
  {
    int nx = x+x_move[m];
    int ny = y+y_move[m];
    if (nx > 0 && nx <w-1 && ny> 0 && ny <h-1&& ((marked[ny][nx] &dir) == 0) && map[y][x] <= map[ny][nx])
    {
      marked[ny][nx] |= dir;
      dfs(map, marked, w, h, nx, ny, dir);
    }
  }
}

void find_high_ground(int** map, int w, int h)
{
  int x, y;
  int** marked = new int*[h];
  for(y = 0; y < h; y++)
    marked[y] = new int[w];

  //initialize marked array
  for (x= 0; x < w; x++)
  {
    marked[0][x] = PACIFIC;
    marked[h-1][x] = ATLANTIC;
  }
  for (y = 0; y < h; y++)
  {
    if (y == 0)
    {
      marked[y][0] = PACIFIC;
    } else if (y == h-1)
    {
      marked[y][w-1] = ATLANTIC;
    } else {
      marked[y][0] = PACIFIC;
      marked[y][w-1] = ATLANTIC;
    }
  }
  //do dfs from pacific positions
  for (x = 0; x <w; x++)
    dfs(map, marked, w, h, x, 0, PACIFIC);
  for (y = 0; y <h-1; y++)
    dfs(map, marked, w, h, 0, y, PACIFIC);
  for (x = 0; x < w; x++)
    dfs(map, marked, w, h, x, h-1, ATLANTIC);
  for (y = 1; y < h; y++)
    dfs(map, marked, w, h, w-1, y, ATLANTIC);


  //print all cell with 3
  for (y = 0; y<h; y++)
  {
    for (x = 0; x <w; x++)
    { if (marked[y][x] == (PACIFIC|ATLANTIC))
        cout << "("<<map[y][x]<<") ";
      else
        cout << map[y][x] << " ";
    }
    cout<<endl;
  }
  cout<<endl;

  //print all cell with 3
  for (y = 0; y<h; y++)
    for (x = 0; x <w; x++)
      if (marked[y][x] == (PACIFIC|ATLANTIC))
        cout << "("<<x-1<<", "<<y-1<<") ";
  cout<<endl;
}

int main ()
{
  int array[7][7] = {{0,0,0,0,0,0,0}, {0,1,2,2,3,5,0},{0,3,2,3,4,4,0}, {0,2,4,5,3,1,0}, {0,6,7,1,4,5,0}, {0,5,1,1,2,4,0}, {0,0,0,0,0,0,0 }};

  int *input[7];
  for (int y = 0; y< 7; y++)
  {
    input[y] = new int[7];
  }
  for (int j =0; j <7; j++)
    for (int i = 0; i <7; i++)
      input[j][i] = array[j][i];

  find_high_ground(input, 7, 7);
  return 1;
}

- hankm2004 July 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the constraint were "water can flow from A to B if height(A) > height(B)", we'd have a DAG and this simple solution using DFS and memoization would do:

int dfs(currentCell){
    if(currentCell.visited == TRUE){
        return currentCell.canFlow;
    }
    else
    {
        if(isBorderCell(currentCell)):
            currentCell.canFlow = true;
        else
            currentCell.canFlow = false;
        for(cell in currentCell.neighbours):
            if(cell.height < currentCell.height)
                currentCell.canFlow = currentCell.canFlow || dfs(cell);
        return currentCell.canFlow
    }
}

list<cell> continentalDivide;
for(cell in map):
    if(dfs(cell) == TRUE):
        add cell to continentalDivide;

Since the constraint allows water flowing between cells with equal height, we would have cycles between neighbouring cells with the same height, so a DP solution wouldn't work. However, you can preprocess the map to compress neighbouring cells with the same height to a single cell, thus going back to the first situation, making it possible to use the first DP. This preprocessing takes O(numberOfCells), while the DP takes O(numberOfCells + numberOfEdges). Since it's a grid, numberOfEdges = numberOfCells * constant, so the DP also has amortized complexity of O(numberOfCells).

- caio July 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Isnt this question a little too big for a 45 min interview?

- Saad ahmed August 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

And the python version:

A = 1
P = 2

def divide(arr):
	height = len(arr)
	width = len(arr[0])
	res = []

	visited = [[False] * width for i in range(height)]
	map = [[0] * width for i in range(height)]

	for row in range(height):
		for col in range(width):
			drop(arr, row, col, height, width, visited, map)
			if map[row][col] == (A | P):
				res.append((row, col))

	return res

def drop(arr, r, c, height, width, visited, map):

	if visited[r][c] == True:
		return map[r][c]

	visited[r][c] = True

	if r > 0:
		if arr[r][c] >= arr[r-1][c]:
			drop(arr, r-1, c, height, width, visited, map)
			map[r][c] = map[r][c] | map[r-1][c]
	else:
		map[r][c] = map[r][c] | A

	if r < height-1:
		if arr[r][c] >= arr[r+1][c]:
			drop(arr, r+1, c, height, width, visited, map)
			map[r][c] = map[r][c] | map[r+1][c]
	else:
		map[r][c] = map[r][c] | P


	if c > 0:
		if arr[r][c] >= arr[r][c-1]:
			drop(arr, r, c-1, height, width, visited, map)
			map[r][c] = map[r][c] | map[r][c-1]
	else:
		map[r][c] = map[r][c] | A

	if c < width-1:
		if arr[r][c] >= arr[r][c+1]:
			drop(arr, r, c+1, height, width, visited, map)
			map[r][c] = map[r][c] | map[r][c+1]
	else:
		map[r][c] = map[r][c] | P

	return 


land = [[1, 2, 2, 3, 5],
	[3, 2, 3, 4, 4],
	[2, 4, 5, 3, 1],
	[6, 7, 1, 4, 5],
	[5, 1, 1, 2, 4] 
	];

print(divide(land))

- Dmitry September 19, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A = 1
P = 2

def divide(arr):
	height = len(arr)
	width = len(arr[0])
	res = []

	visited = [[False] * width for i in range(height)]
	map = [[0] * width for i in range(height)]

	for row in range(height):
		for col in range(width):
			drop(arr, row, col, height, width, visited, map)
			if map[row][col] == (A | P):
				res.append((row, col))

	return res

def drop(arr, r, c, height, width, visited, map):

	if visited[r][c] == True:
		return map[r][c]

	visited[r][c] = True

	if r > 0:
		if arr[r][c] >= arr[r-1][c]:
			drop(arr, r-1, c, height, width, visited, map)
			map[r][c] = map[r][c] | map[r-1][c]
	else:
		map[r][c] = map[r][c] | A

	if r < height-1:
		if arr[r][c] >= arr[r+1][c]:
			drop(arr, r+1, c, height, width, visited, map)
			map[r][c] = map[r][c] | map[r+1][c]
	else:
		map[r][c] = map[r][c] | P


	if c > 0:
		if arr[r][c] >= arr[r][c-1]:
			drop(arr, r, c-1, height, width, visited, map)
			map[r][c] = map[r][c] | map[r][c-1]
	else:
		map[r][c] = map[r][c] | A

	if c < width-1:
		if arr[r][c] >= arr[r][c+1]:
			drop(arr, r, c+1, height, width, visited, map)
			map[r][c] = map[r][c] | map[r][c+1]
	else:
		map[r][c] = map[r][c] | P

	return 


land = [[1, 2, 2, 3, 5],
	[3, 2, 3, 4, 4],
	[2, 4, 5, 3, 1],
	[6, 7, 1, 4, 5],
	[5, 1, 1, 2, 4] 
	];

print(divide(land))

- Dmitry September 19, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A = 1
P = 2

def divide(arr):
height = len(arr)
width = len(arr[0])
res = []

visited = [[False] * width for i in range(height)]
map = [[0] * width for i in range(height)]

for row in range(height):
for col in range(width):
drop(arr, row, col, height, width, visited, map)
if map[row][col] == (A | P):
res.append((row, col))

return res

def drop(arr, r, c, height, width, visited, map):

if visited[r][c] == True:
return map[r][c]

visited[r][c] = True

if r > 0:
if arr[r][c] >= arr[r-1][c]:
drop(arr, r-1, c, height, width, visited, map)
map[r][c] = map[r][c] | map[r-1][c]
else:
map[r][c] = map[r][c] | P

if r < height-1:
if arr[r][c] >= arr[r+1][c]:
drop(arr, r+1, c, height, width, visited, map)
map[r][c] = map[r][c] | map[r+1][c]
else:
map[r][c] = map[r][c] | A


if c > 0:
if arr[r][c] >= arr[r][c-1]:
drop(arr, r, c-1, height, width, visited, map)
map[r][c] = map[r][c] | map[r][c-1]
else:
map[r][c] = map[r][c] | P

if c < width-1:
if arr[r][c] >= arr[r][c+1]:
drop(arr, r, c+1, height, width, visited, map)
map[r][c] = map[r][c] | map[r][c+1]
else:
map[r][c] = map[r][c] | A

return


land = [[1, 2, 2, 3, 5],
[3, 2, 3, 4, 4],
[2, 4, 5, 3, 1],
[6, 7, 1, 4, 5],
[5, 1, 1, 2, 4]
];

print(divide(land))

- Dmitry September 19, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A = 1
P = 2

def divide(arr):
	height = len(arr)
	width = len(arr[0])
	res = []

	visited = [[False] * width for i in range(height)]
	map = [[0] * width for i in range(height)]

	for row in range(height):
		for col in range(width):
			drop(arr, row, col, height, width, visited, map)
			if map[row][col] == (A | P):
				res.append((row, col))

	return res

def drop(arr, r, c, height, width, visited, map):

	if visited[r][c] == True:
		return map[r][c]

	visited[r][c] = True

	if r > 0:
		if arr[r][c] >= arr[r-1][c]:
			drop(arr, r-1, c, height, width, visited, map)
			map[r][c] = map[r][c] | map[r-1][c]
	else:
		map[r][c] = map[r][c] | P

	if r < height-1:
		if arr[r][c] >= arr[r+1][c]:
			drop(arr, r+1, c, height, width, visited, map)
			map[r][c] = map[r][c] | map[r+1][c]
	else:
		map[r][c] = map[r][c] | A


	if c > 0:
		if arr[r][c] >= arr[r][c-1]:
			drop(arr, r, c-1, height, width, visited, map)
			map[r][c] = map[r][c] | map[r][c-1]
	else:
		map[r][c] = map[r][c] | P

	if c < width-1:
		if arr[r][c] >= arr[r][c+1]:
			drop(arr, r, c+1, height, width, visited, map)
			map[r][c] = map[r][c] | map[r][c+1]
	else:
		map[r][c] = map[r][c] | A

	return 


land = [[1, 2, 2, 3, 5],
	[3, 2, 3, 4, 4],
	[2, 4, 5, 3, 1],
	[6, 7, 1, 4, 5],
	[5, 1, 1, 2, 4] 
	];

print(divide(land))

- Dmitry September 19, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
using namespace std;

bool isOceanReachable(int N, int A[][5], int i, int j, int C[][5], int comp)
{
	if (C[i][j] == -1)
		return false;

	if (C[i][j] == 0)
	{
		C[i][j] = -1;
		bool result = (i == comp || j == comp);

		if (!result && (i - 1 >= 0 && A[i][j] >= A[i - 1][j]))
			result = isOceanReachable(N, A, i - 1, j, C, comp);
		if (!result && (i + 1 < N && A[i][j] >= A[i + 1][j]))
			result = isOceanReachable(N, A, i + 1, j, C, comp);
		if (!result && (j - 1 >= 0 && A[i][j] >= A[i][j - 1]))
			result = isOceanReachable(N, A, i, j - 1, C, comp);
		if (!result && (j + 1 < N && A[i][j] >= A[i][j + 1]))
			result = isOceanReachable(N, A, i, j + 1, C, comp);

		C[i][j] = result ? 1 : -1;
	}

	return C[i][j] == 1;
}

int main()
{
	int N = 5;
	int A[5][5] = {
		{1,2,1,2,3},
		{1,1,2,3,2},
		{1,3,4,4,1},
		{2,5,3,3,2},
		{2,1,5,3,1}
	};

	int C_A[5][5] = { {0} };
	int C_B[5][5] = { {0} };

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (isOceanReachable(N, A, i, j, C_A, 0) && isOceanReachable(N, A, i, j, C_B, N - 1))
				cout << "{" << i << ", " << j << "}=" << A[i][j] << " ";
		}
	}

	return 0;
}

- Anonymous December 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
using namespace std;

bool isOceanReachable(int N, int A[][5], int i, int j, int C[][5], int comp)
{
	if (C[i][j] == -1)
		return false;

	if (C[i][j] == 0)
	{
		C[i][j] = -1;
		bool result = (i == comp || j == comp);

		if (!result && (i - 1 >= 0 && A[i][j] >= A[i - 1][j]))
			result = isOceanReachable(N, A, i - 1, j, C, comp);
		if (!result && (i + 1 < N && A[i][j] >= A[i + 1][j]))
			result = isOceanReachable(N, A, i + 1, j, C, comp);
		if (!result && (j - 1 >= 0 && A[i][j] >= A[i][j - 1]))
			result = isOceanReachable(N, A, i, j - 1, C, comp);
		if (!result && (j + 1 < N && A[i][j] >= A[i][j + 1]))
			result = isOceanReachable(N, A, i, j + 1, C, comp);

		C[i][j] = result ? 1 : -1;
	}

	return C[i][j] == 1;
}

int main()
{
	int N = 5;
	int A[5][5] = {
		{1,2,1,2,3},
		{1,1,2,3,2},
		{1,3,4,4,1},
		{2,5,3,3,2},
		{2,1,5,3,1}
	};

	int C_A[5][5] = { {0} };
	int C_B[5][5] = { {0} };

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (isOceanReachable(N, A, i, j, C_A, 0) && isOceanReachable(N, A, i, j, C_B, N - 1))
				cout << "{" << i << ", " << j << "}=" << A[i][j] << " ";
		}
	}

	return 0;
}

- Saurabh Agrawal December 12, 2018 | 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