Created
September 6, 2019 02:57
-
-
Save adrienshen/c10f2b3b171559600c9259e4d203449f to your computer and use it in GitHub Desktop.
Amazon islands interview problem, 1 solution and demo of stack overflow
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
''' | |
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. | |
Example 1: | |
11110 | |
11010 | |
11000 | |
00000 | |
Output: 1 | |
Example 2: | |
11000 | |
11000 | |
00100 | |
00011 | |
Output: 3 | |
Observations: | |
- Diagonals are not considered connected islands for this version of the question | |
- If grid is all zeros, than islands equals 0 | |
- If grid is all ones, than islands equals 1 | |
- The structure of a 2d grid of 1s and 0s is similar to that of a graph data structure, where nodes of an island are connected to 1 or more other nodes of the same island | |
- For graphs, we can use Breath-First-Search algorithm to locate all the nodes in an island | |
- We need an way to keep track of already visited nodes | |
- Initially looks like 0(n) looks like best case scenerio since at least every node in the 2d matrix has to be visited once | |
''' | |
import random | |
# input_matrix = [[0,0,1,1,0], | |
# [1,0,0,0,1], | |
# [1,1,1,1,1], | |
# [0,0,0,0,0]] # 1 | |
def generate_matrix(size=5): | |
# make sure there's a higher porpotion of ones to test call stack limitations | |
return [[random.choice([1,0,1,0,1]) for x in range(size)] for y in range(size)] | |
def pretty_print(matrix): | |
print('\n'.join(['\t'.join([str(cell) for cell in row]) for row in matrix])) | |
# Attempt #1 | |
def locate_islands(input_matrix): | |
row, col, islands = 0, 0, 0 | |
# pretty_print(input_matrix) | |
for ir, row in enumerate(input_matrix): | |
for ic, node in enumerate(row): | |
if (node is 1): | |
islands = islands + 1 | |
# print("starting node for BFS: {},{} is {}".format(ir, ic, node)) | |
bfs(ir, ic) | |
print("output: ", islands) | |
def bfs(ir, ic): | |
# search to right, bottom, top, left of node | |
if (input_matrix[ir][ic] is not 1): | |
return 0 | |
input_matrix[ir][ic] = 2 # mark already visited with 2 | |
# print("Searching...", ic, ir) | |
if (ir+1 < len(input_matrix)) and (input_matrix[ir+1][ic] is 1): | |
bfs(ir+1, ic) | |
if (ic+1 < len(input_matrix[ir])) and (input_matrix[ir][ic+1] is 1): | |
bfs(ir, ic+1) | |
if (ic-1 > 0) and (input_matrix[ir][ic-1] is 1): | |
bfs(ir, ic-1) | |
if (ir-1 > 0) and (input_matrix[ir-1][ic] is 1): | |
bfs(ir-1, ic) | |
return 0 | |
input_matrix = generate_matrix(size=5) | |
locate_islands(input_matrix) | |
# increase the size of grid | |
input_matrix = generate_matrix(size=2000) | |
# RecursionError: maximum recursion depth exceeded while calling a Python object | |
print(len(input_matrix)) # stackoverflow error! | |
locate_islands(input_matrix) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment