google logo
Google· SDE II

Google | L4 | Interview

Result
null
Location
null
Posted
13 Aug 2025
371 reads

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)

  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.

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Google recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!