Facebook | Find repeating shape in a matrix

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
111

I 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)

Comments (3)