Google | L4 | Interview
Summary
Interviewed at Google for a L4 position. The interview focused on a problem where I had to find a solid square of 1s in a matrix, returning its coordinates and size. The expected time complexity was O(m or n).
Full Experience
During my interview at Google for the L4 position, I was presented with a problem involving a matrix representing a video frame. The task was to identify a solid square of 1s, which represented a book tag. If such a square existed, I needed to return its upper-left corner coordinates and the size of the square. If not, the size should be 0. Additionally, the square was guaranteed to be at least sqrt(n) x sqrt(n) in size. The expected solution had to achieve a time complexity of O(m or n), which I found challenging to implement efficiently.
Interview Questions (1)
Write a function that finds a single tag in an image. Your function will be given an m x n matrix, representing one frame of video. The matrix consists of mostly 0s, but somewhere within the matrix there may be a solid square of 1s. This solid square represents the book tag.
If the square of 1s is present, your function should return the coordinates of the upper-left corner of the square of 1s, and the size of the square. If there isn't a square of 1s, return that the size is 0. Additionally, if there is a square of 1s it will be at least sqrt(n) x sqrt(n) in size.