Google | L4 | Interview
- Result
- null
- Location
- null
- Posted
- 13 Aug 2025
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).
How it went
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.
Questions asked (1)
- 01
Find Solid Square in Matrix
Data Structures & Algorithms · Hard
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.