## Google Interview Question

Software Engineer / Developers**Country:**Berling

**Interview Type:**Phone Interview

from collections import deque

def get_dist_to_bin(M: list[list[int]]) -> D list[list[int]]:

r, c = len(M), len(M[0]) # row, cols

bins = deque()

for i in range(r):

for j in range(c):

if M[i][j]:

continue

if i and M[i-1][j]: dq.append( (i,j) )

elif j and M[i][j-1]: dq.append( (i,j) )

elif i<r-1 and M[i+1][j]: dq.append( (i,j) )

elif j<c-1 and M[i][j+1]: dq.append( (i,j) )

D = [[0]*c for _ in range(r)] #initialize output

curr_dist = 0

curr_cnt = len(bins)

while bins:

i, j = dq.popleft()

D[i, j] = curr_dist

curr_cnt -= 1

if i and not D[i-1][j]: dq.append( (i-1,j) )

elif j and not D[i][j-1]: dq.append( (i,j-1) )

elif i<r-1 and not D[i+1][j]: dq.append( (i+1,j) )

elif j<c-1 and not D[i][j+1]: dq.append( (i,j+1) )

if not curr_cnt: #finishes layer

curr_dist += 1

curr_cnt = len(bins)

return D

```py

import numpy as np

import pandas as pd

def is_bin_cell(x, y, matrix):

try:

up = matrix[x-1][y] if x > 0 else 0

except:

up = 0

try:

down = matrix[x+1][y] if x < len(matrix) else 0

except:

down = 0

try:

matrix[x][y-1] if y > 0 else 0

except:

down = 0

try:

left = matrix[x][y-1] if y > 0 else 0

except:

left = 0

try:

right = matrix[x][y+1] if y < len(matrix[0]) else 0

except:

right = 0

if (matrix[x][y] == 0) and (1 in [up, down, right, left]):

return True

return False

def get_bin_cells(matrix):

bindexes = []

for i, row in enumerate(matrix):

for j, _ in enumerate(row):

if is_bin_cell(i, j, matrix):

bindexes.append((i, j))

return bindexes

def euclidean(i, j, matrix):

p1, p2 = i

d1, d2 = j

return (((matrix[p1][0] - matrix[d1][0])**2) + ((matrix[p2][1] - matrix[d2][1])**2)) ** .5

def get_distances(matrix):

bin_cells = get_bin_cells(matrix)

distances = {}

for i, row in enumerate(matrix):

for j, _ in enumerate(row):

distances[f'({i}, {j})'] = [euclidean((i, j), t, matrix) for t in bin_cells]

return distances

# driver code

data = get_distances(matrix)

index = [str(i) for i in data]

rows = [[coord] + i for coord, i in zip(index, data.values())]

pd.DataFrame(rows, columns=['Coord']+get_bin_cells(matrix))

```

The idea is to first find all the bin cells, and add then to a queue. You can then do a flood fill for every iteration through the queue where you add the neighbours of each cell to said queue as you go. See Python implementation below (assumes by 'distance' you meant manhattan distance):

- Anonymous December 03, 2021