Hi Everyone,
Yesterday I had an interview, and got a question like this
0001000
0011100
0000011
0100000
1110000
given a matrix of 0's and 1's return the maximum repeating shape in in the matrix. A shape is denoted by a grouping of 1s from above, under, left, and right.
in this secnario the answer would be 2, and the maximum repeating shape is
1
111I know that I saw that question once but I can't find it anywhere. Can someone point me to it? Also does anyone know how to solve it?
m = [
[0, 0, 1, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0],
[0, 0, 1, 1, 0],
[0, 1, 0, 0, 0],
[1, 1, 1, 0, 0],
]
def find_shapes(m):
def get_shape(row, col, offr, offc, co, vis):
co.append((offr, offc))
vis.add((row, col))
for r, c in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
rowr, colc = row + r, col + c
if 0 <= rowr < len(m) and 0 <= colc < len(m[0]) \
and m[rowr][colc] == 1 and (rowr, colc) not in vis:
get_shape(rowr, colc, offr + r, offc + c, co, vis)
return tuple(co)
counts = {}
visited = set()
for i in range(len(m)):
for j in range(len(m[0])):
if m[i][j] == 1 and (i, j) not in visited:
shape = get_shape(i, j, 0, 0, [], visited)
if shape not in counts:
counts[shape] = 0
counts[shape] += 1
return counts
((0, 0), (1, 0), (1, -1), (1, 1)) 2
((0, 0), (0, 1)) 1
This is my solution. O(V + E)