...
Let's pretend we're working on a computer vision project. In this project,
librarians sent us videos of their bookshelves. Based on frames from these videos,
we want to quickly and efficiently find the spine tags on the library books.
For the purposes of the interview, we'll be simplifying this to the following problem.
input matrix - m x n = m ~ n = all 0s
spine tag - square of 1s
000000000000
000000000000
000000000000
000000000000
000001111000
000001111000
000001111000
000001111000
000000000000
000000000000
This Google interview problem simplifies a computer vision task: given a frame represented as an m×n matrix of 0s and 1s, where a spine tag corresponds to a square submatrix of 1s, determine how to detect that square quickly and efficiently. The challenge typically lies in finding the top-left coordinate and size of the square of 1s, ideally in linear or near-linear time, rather than checking every possible square with brute force.
END
