Google L4 | Phone Screen | Reject
Summary
I had a phone screen interview for an L4 role at Google where I was asked to merge two screenshots. I initially misunderstood the problem and later struggled to optimize my brute-force solution, ultimately leading to a rejection.
Full Experience
The interviewer joined and directly jumped into the question. He verbally told me the problem statement, which you see in the first two lines of the question. No input/output was given. Just:
Given two screenshots of a single web page. Return single long screenshot merging both given screenshots with no overlapping content.
I misunderstood the question, thinking of two arrays instead of two 2D matrices. Later, the interviewer wrote the example input and output. I wasted 10 minutes here due to the open-ended problem statement. Yes, a screenshot is a 2D grid with pixels, but it didn't strike me at that moment.
Then I explained my solution (brute force):
The idea is: if the bottom rows of screen1 match the top rows of screen2 (in the same order), remove those overlapping rows from screen2 only before merging.
He agreed and asked me to write the time complexity. I wrote it as O(h * h * w), and he mentioned it was correct. This discussion went on for 15 minutes. I thought I could start coding now. But he stopped me and asked me to optimize it.
I fumbled a lot here. I was thinking about whether I could optimize it to avoid any recalculations. I was going completely in the wrong direction, and I felt the interviewer didn't help me much here. I wasn't getting any other ideas and told him I would write the brute-force solution first and then see if I could optimize it, as I might get some ideas while looking at the code. He initially didn’t agree, but since only 10–13 minutes were left, he agreed. I understood I had already lost the opportunity, but I didn’t give up. I quickly started writing the code, hoping to find some optimization, but I ran out of time.
After the interview, I asked ChatGPT the same question. It also gave the same solution (brute force) with the same time complexity. Then I asked it to optimize, and it gave a slightly optimized solution using precomputed hashes for each row, reducing the time complexity to O(h * w + h * h). You can see the code & conversation here with ChatGPT. This is not a huge deal, but it was still my fault for not even mentioning the precomputed hash optimization. I genuinely don't know if the interviewer was expecting this or some other optimization. What do you think?
Interview Questions (1)
QUESTION: Merge Two Screenshots Given two screenshots of a single web page. Return single long screenshot merging both given screenshots with no overlapping content.
A single screenshot refers to a h*w grid/matrix, where h is the height of the screen and w is the width of screen. When scrolling a web page assume may or may not some screen content can overlap.
Example Input:
Screen 1:
[1 2 3]
[4 4 5]
[6 7 8]
[9 10 11]
Screen 2:
[6 7 8]
[9 10 11]
[13 14 15]
[16 17 19]
Output:
[1 2 3]
[4 4 5]
[6 7 8]
[9 10 11]
[13 14 15]
[16 17 19]
Here
h = 4, w = 3
Preparation Tips
UPDATE: Thanks all for you inputs in comments. Seems KMP is the correct solution to this problem. Feeling this template now. Covered most of the data structures and alogrithms for google but skipped this KMP algo and it costed me and I paid the price. To everyone who is preparing for Google, BE PREPARED IN EVERY TOPIC.