Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Problem Challenge 1 (easy)

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

[1,1,1,1,1,1,1,1,1,1],

[1,0,0,0,0,0,0,0,0,1],

[1,0,1,1,1,1,1,1,0,1],

[1,0,1,0,0,0,0,1,0,1],

[1,0,1,0,1,1,0,1,0,1],

[1,0,1,0,1,1,0,1,0,1],

[1,0,1,0,0,0,0,1,0,1],

[1,0,1,1,1,1,1,1,0,1],

[1,0,0,0,0,0,0,0,0,1],

[1,1,1,1,1,1,1,1,1,1]]

Every water in a island is a lake. Additionally we have several islands. They aren't mentioned in description. What should I do with them? Count or not?

A

Anonymous

· 2 years ago

class Solution:
  
  def get_neighbors(self, matrix, i, j):
    neighbors = []
    rows = [-1, 0, 1, 0]
    cols = [0, 1, 0, -1]
    for k in range(len(rows)):
      x = rows[k] + i
      y = cols[k] + j
      if x >= 0 and x < len(matrix) and y >= 0 and y < len(matrix[0]):
        neighbors.append((x, y))
    return neighbors
  
  def cacl_perimeter(self, matrix, i, j):
    perimeter = 0
    # top perimeter
    if  i == 0 or (i - 1 >= 0 and matrix[i - 1][j] == 0):
      perimeter += 1
    # bottom perimeter  
    if  i == len(matrix) - 1 or (i + 1 < len(matrix) and matrix[i + 1][j] == 0):
      perimeter += 1
    # left perimeter
    if  j == 0 or (j - 1 >= 0 and matrix[i][j - 1] == 0):
      perimeter += 1
    # right perimeter  
    if  j == len(matrix[0]) - 1 or (j + 1 <
A

Anonymous

· 3 years ago

# the total should be returned not just the edge of a single island
# correct implementation is below

def findIslandPerimeter(matrix):
    rows = len(matrix)
    cols = len(matrix[0])
    visited = [[False for i in range(cols)] for j in range(rows)]
    total = 0 # added
    for i in range(rows):
        for j in range(cols):
            if (matrix[i][j] == 1 and not visited[i][j]):
                total += islandPerimeterDFS(matrix, visited, i, j) # updated

    return total # updated
Show 1 reply
A

Anonymous

· 3 years ago

https://www.google.com/search?q=lake&oq=lake - A lake is a body of water that is surrounded by land.

I think the description has a typo: lakes are allowed. Designgurus has even a test case:

[

[0,0,0,0,0],

[0,1,1,1,0],

[0,1,0,1,0],

[0,1,1,1,0],

[0,0,0,0,0]

]

Show 1 reply
A

Anonymous

· 3 years ago

The description states:

"An island is a connected set of 1s (land) and is surrounded by either an edge or 0s (water). Each cell is considered connected to other cells horizontally or vertically (not diagonally)."

Based on this definition, an island of [[1]] should not be an island, since it's not a set of connected 1s.

Ignoring that and pretending a single 1 is an island, the below test case has multiple singular islands, which violates the following:

"The given matrix has only one island, write a function to find the perimeter of that island."

[[0,1,0,1,0,1,0,1,0],[1,0,1,0,1,0,1,0,1],[0,1,0,1,0,1,0,1,0]]

So what's actually the expected behaviour here??

Show 2 replies
A

Anonymous

· 3 years ago

I don't understand why the perimeter of this island [[1,1,1,1,0,1,1,1,1]] is 10 in the test case, shouldn't it be 20?

Show 1 reply
A

Anonymous

· 4 years ago

Could be missing edge cases, but it seems like the solution would be the number of land cells in the island * 2 + 2?

Show 1 reply
A

Anonymous

· 4 years ago

One small way to improve the answer provided in this challenge is doing away with the memory array to tell where you've been before. There's no need for it. Just mark the node as something other than 0 or 1 to mark that you've been there.

So for example mark the nodes you've visited with a value of 2 and then do a check grid[x][y] == 2 and if that's true you can return 0 in the recursive call. Saves a little time and memory.

Show 1 reply
A

Anonymous

· 4 years ago

Is this a typo? Shouldn't it be Island Perimeter instead of Parameter?

Show 4 replies

Reading Progress

0%

Vote for new content