Articles

Blogs

MCQ

SQL

Q&A

Tools

Tags

Jobs

News

Community

LogIn

Email

Password

Show Password

Forget Password

I don't have account.Sign Up!

Login

‹ ›

‹ ›

‹ ›

‹ ›

Sponsored -53%

Zebronics #1 Best Seller

ZEBRONICS Blanc Slim Wireless Mouse — Rechargeable, BT + 2.4GHz (Black)

Up to 1600 DPI · Silent clicks · 63g · Multicolor LED

★★★★★★★★★★ 4.0 (9,512) 5K+ bought last month

₹376 M.R.P. ₹799Save ₹423

Buy Now →

Adℹ

✕

I Got Rejected by Google After 5 Rounds : Here's Everything I Learned (L4 Backend Engineer)

Gagan Bansal

Last Updated : 31 August 2026

307 Views

#google

#dsa

#interview-experience

#hr-interview

#experienced-candidate-interview

#interview-questions

#backend-interview-experience

Adℹ

I still remember opening the rejection email. Three and a half weeks of prep, five rounds and one line that said "we've decided not to move forward at this time." No specifics, no feedback, just silence wrapped in polite corporate language.

If you're reading this because you have a Google interview coming up, I want this to feel different from the usual "here are the questions I was asked" post. I want to walk you through how I actually thought through each problem brute force, the moment it clicked and the mistakes I made along the way. This was a Backend Developer role, L4 level, referral-based, fully remote. Five rounds, spread across three to four weeks.

Round 1: The Square Made of Ones

Duration: 60 min | Difficulty: Hard

The interviewer opened with almost no small talk. He shared a matrix of 0s and 1s and told me somewhere inside it, there might be exactly one square sub-matrix made entirely of 1s I had to find its size and the top-left corner.

My thought process:

• First instinct was brute force check every possible square, every size, every position. That's close to O(n⁴) and saying that number out loud made it obvious it wasn't good enough.
• The real question was: what am I recomputing again and again? Every time I check a square of size k ending at (i, j), I'm re-checking cells I already checked for smaller squares. That's the signal for dynamic programming.
• The idea: define dp[i][j] as the size of the largest square of 1s ending (bottom-right corner) at (i, j). If matrix[i][j] is 0, dp[i][j] is 0. If it's 1, the square can only grow as far as its weakest neighbor the minimum of the cell above, the cell to the left and the cell diagonally above-left plus one.

public class LargestSquareSubmatrix {

    // Returns {size, topRow, topCol}. If no square of 1s exists, size = 0.
    public static int[] findLargestSquare(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new int[]{0, -1, -1};
        }

        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] dp = new int[rows][cols];

        int maxSize = 0;
        int bottomRightRow = -1;
        int bottomRightCol = -1;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 1) {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1; // first row/column, square can only be size 1
                    } else {
                        dp[i][j] = Math.min(dp[i - 1][j],
                                    Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                    }
                    if (dp[i][j] > maxSize) {
                        maxSize = dp[i][j];
                        bottomRightRow = i;
                        bottomRightCol = j;
                    }
                }
            }
        }

        if (maxSize == 0) return new int[]{0, -1, -1};
        int topRow = bottomRightRow - maxSize + 1;
        int topCol = bottomRightCol - maxSize + 1;
        return new int[]{maxSize, topRow, topCol};
    }
}

Why it's optimal:

• Time: O(rows × cols) every cell is visited exactly once.
• Space: O(rows × cols) for the DP table, but can be reduced to O(cols) since each cell only needs the row above and the value to its left. I mentioned this without being asked, which is what turned it into a real technical conversation instead of just a pass/fail check.

My mistake: I almost started coding before fully stating the DP recurrence out loud. The interviewer gently stopped me "walk me through the relationship first." That pause probably saved me from messing up the boundary conditions for row 0 and column 0.

Follow-up he asked: What if multiple squares share the same maximum size how do you return all of them? My answer: Track a list instead of a single position and append whenever dp[i][j] equals the current maxSize, not just when it's strictly greater.

Round 2: Numbers, Order and a Slightly Cold Room

Duration: 60 min | Difficulty: Medium

This round felt different from the first minute pleasant interviewer, but a flatness in his energy that made it hard to read whether I was doing well or badly. If you've had an interview where the other person just doesn't react, you know how unsettling that silence can be.

The problem: Given three numbers in a fixed order and a target, find an expression using only +, * and () that evaluates to the target, keeping the numbers in order. Example: 3, 2, 4 with target 20 → (3 + 2) * 4 = 20.

My thought process:

• He asked first: how many combinations are even possible? I said "four," thinking only about the two operator slots (+ or *) 2 × 2 = 4. Wrong and I sat in that silence for a second before catching it.
• Parentheses change grouping, not just which operator goes where. (a + b) * c and a + (b * c) can give completely different results with the same operators.
• Real approach: try every way to split the numbers into a left group and a right group, recursively find every value each group could produce, then combine those two sets with every operator to check if the target appears.

import java.util.*;

public class ExpressionTargetFinder {

    // Returns true if numbers (in given order) can be combined with +, *, ()
    // to reach the target.
    public static boolean canReachTarget(int[] nums, long target) {
        Map<String, Set<Long>> memo = new HashMap<>();
        Set<Long> allPossibleValues = solve(nums, 0, nums.length - 1, memo);
        return allPossibleValues.contains(target);
    }

    private static Set<Long> solve(int[] nums, int left, int right,
                                     Map<String, Set<Long>> memo) {
        String key = left + "-" + right;
        if (memo.containsKey(key)) return memo.get(key);
        Set<Long> results = new HashSet<>();
        if (left == right) {
            results.add((long) nums[left]);
            memo.put(key, results);
            return results;
        }
        // every split point = every possible place for the "outermost" parentheses
        for (int split = left; split < right; split++) {
            Set<Long> leftValues = solve(nums, left, split, memo);
            Set<Long> rightValues = solve(nums, split + 1, right, memo);
            for (long l : leftValues) {
                for (long r : rightValues) {
                    results.add(l + r);
                    results.add(l * r);
                }
            }
        }
        memo.put(key, results);
        return results;
    }
}

Why this generalizes: it doesn't just handle three numbers for any n numbers, it's "split into a left half and right half, solve each recursively, combine." Same divide-and-conquer shape as evaluating all results of an expression with different parenthesizations. Memoization barely matters at n = 3, but leaving it out looks like you only solved the specific case in front of you, not the pattern.

My mistake: my first version had no memoization. When he asked "what if there were six numbers instead of three?", I had to admit it would recompute the same sub-ranges repeatedly. I added the memo map live.

Follow-up he asked: Can you return the actual expression string, not just whether it's possible? My answer: Store pairs of (value, expressionString) in the memo instead of just values, so you can reconstruct exactly which grouping produced the target.

Takeaway from this round: don't assume a flat, unreadable interviewer means you're failing. Stay steady and keep thinking clearly anyway.

Round 3: Painting a Fence, One Stroke at a Time

Duration: 60 min | Difficulty: Medium

A relief after the last round this interviewer was actually present, asking questions because he was curious, not just to check boxes.

The problem: A fence made of boards with different heights. A brush 1m wide can paint one board vertically (full height, one stroke) or paint horizontally across adjacent boards at the same height level, as long as all of them reach that height. Find the minimum strokes to paint the whole fence. Example: [1, 2, 2, 1, 2] → 3.

My thought process:

• Baseline: paint every board vertically always valid, always costs exactly n strokes.
• A horizontal stroke only helps when it covers more than one board at once.
• Key idea: look at the shortest board in the current range. You can paint min_height horizontal strokes across the entire range, since every board is at least that tall. What's left above that line is a smaller version of the same problem, split into segments wherever a board's leftover height hits zero solve each segment recursively.

public class FencePainting {

    public static int minStrokes(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        return solve(heights, 0, heights.length - 1);
    }

    private static int solve(int[] heights, int low, int high) {
        if (low > high) return 0;

        int minHeight = Integer.MAX_VALUE;
        for (int i = low; i <= high; i++) {
            minHeight = Math.min(minHeight, heights[i]);
        }
        int horizontalCost = minHeight;
        int i = low;
        while (i <= high) {
            if (heights[i] == minHeight) {
                i++;
                continue; // nothing left above the min line for this board
            }
            int start = i;
            while (i <= high && heights[i] != minHeight) i++;
            int[] leftover = new int[i - start];
            for (int k = 0; k < leftover.length; k++) {
                leftover[k] = heights[start + k] - minHeight;
            }
            horizontalCost += solve(leftover, 0, leftover.length - 1);
        }
        int verticalCost = high - low + 1;
        return Math.min(horizontalCost, verticalCost);
    }
}

Tracing the example [1, 2, 2, 1, 2]:

• Min height across all 5 = 1 → one horizontal stroke covers all of them.
• Leftover after subtracting: [0, 1, 1, 0, 1] → splits into segments [1, 1] and [1].
• [1, 1] costs min(1, 2) = 1. [1] costs min(1, 1) = 1.
• Total: 1 + 1 + 1 = 3, versus 5 if painted vertically. Minimum is 3 matches the expected output.

Why it's optimal: each recursive call only scans its own range and ranges shrink every call nowhere close to trying every possible combination of strokes, which would blow up exponentially.

Mistake: none major this time I'd seen a similarly shaped "painting" problem in prep, so the recursion felt familiar rather than something I was inventing live.

Follow-up he asked: What if the brush could also paint diagonally? My answer: Honestly said I'd need time to think, since diagonal strokes break the clean row/column split this recursion depends on.

Round 4: The Round That Quietly Broke Me a Little

Duration: 60 min | Difficulty: Hard

This is the round I keep replaying and the one I suspect the rejection came from.

The problem: Design a small messaging system with two operations:

• registerEvent(user1, user2, content) records that user1 messaged user2 with some content.
• getFrequent() returns any user who has received messages from the most unique senders (repeated messages from the same sender count once).

My thought process:

• First instinct: a map from receiver to a message count. Caught my own mistake before he pointed it out a plain counter would count repeated messages from the same sender multiple times, which the problem explicitly rules out.
• Fix: map receiver to a set of senders instead of a count. A set naturally ignores duplicates.

import java.util.*;

public class MessagingFrequencyTracker {

    // receiver -> set of unique senders who have messaged them
    private final Map<String, Set<String>> receiverToSenders = new HashMap<>();
    private int maxUniqueSenders = 0;

    public void registerEvent(String sender, String receiver, String content) {
        receiverToSenders
            .computeIfAbsent(receiver, k -> new HashSet<>())
            .add(sender);
        int currentCount = receiverToSenders.get(receiver).size();
        if (currentCount > maxUniqueSenders) {
            maxUniqueSenders = currentCount;
        }
    }

    // Returns any one user who has received messages from the most
    // unique senders. Returns null if no events registered.
    public String getFrequent() {
        for (Map.Entry<String, Set<String>> entry : receiverToSenders.entrySet()) {
            if (entry.getValue().size() == maxUniqueSenders) {
                return entry.getKey();
            }
        }
        return null;
    }
}

• registerEvent: O(1) average one HashSet insert, one HashMap lookup.
• getFrequent: O(1) because maxUniqueSenders is tracked incrementally instead of recalculated on every call.

Two things I only got to because he pushed me, not because I saw them myself:

• He asked: "What if getFrequent() is called far more often than registerEvent() does your approach handle that well?" My first version scanned all receivers inside getFrequent() O(number of receivers) every call. Moving the max-tracking into the write path fixed it, but only after his nudge.
• I never asked out loud what the content field was for. I quietly assumed it was irrelevant and moved on. A stronger candidate asks: "does content matter here or is it just for completeness?" it costs ten seconds and shows you read the whole problem.

Follow-up he asked: How would this change if you needed the top 3 most-messaged users, not just one? My answer: Talked through a small sorted structure a TreeMap keyed by count or a min-heap of size 3 instead of a single integer. Got there, but slower than I liked.

Round 5: The Human Round

Duration: 45 min | Difficulty: Medium (Behavioral)

By this point I was genuinely tired the kind of tired that's hard to explain unless you've done back-to-back technical rounds spread across separate days over several weeks.

Questions I was asked:

• Walk me through a project you've worked on and your role in it.
• Tell me about a mistake you made and what you learned from it.
• Give an example of working closely with a team.
• Tell me about a time you had a conflict at work and how you resolved it.
• How do you take ownership when something goes wrong?

What worked for me: I talked about a real production incident a mistake I made with a caching layer that served stale data to users for close to twenty minutes before anyone noticed. I walked through:

• How I traced it back to the root cause.
• What I changed to prevent it from happening again.
• What I told my team afterward so they could catch the same class of mistake earlier next time.

Ownership, a real mistake, a real fix, a real lesson that lands far better than a vague, safe answer with no actual stakes in it.

My advice for this round:

• Prepare 3-4 real stories, not invented ones.
• Practice saying them out loud so they don't sound rehearsed.
• Interviewers notice the difference between a story you're remembering and one you're reciting.

What I Think Actually Went Wrong

I don't know for certain Google doesn't give that kind of feedback. But my honest guess is Round 4. Not because the final solution was wrong it worked and it hit O(1) for both operations. It's the two nudges that mattered. At L4, you're expected to:

• Ask the clarifying question about the content field on your own.
• Think about read-heavy versus write-heavy access patterns without being asked.

I got to the right place, but I got there by being pushed, not by getting there myself. That's a real gap, worth sitting with instead of explaining away.

Preparation Tips

• Don't rely on memorized patterns. Every problem in this loop was a twist on something familiar DP, backtracking, divide and conquer but none matched a textbook version word-for-word. Train yourself to recognize the underlying shape of a problem (overlapping subproblems, need to try every grouping, shrinking ranges), not just its surface description.
• Always be ready to explain trade-offs, even after your solution works. In almost every round, the moment I finished a working solution, the next question was about space, scaling or read/write frequency. Google checks whether you'd think to improve your own solution unprompted.
• Ask the clarifying questions you're tempted to skip. My biggest actual mistake across all five rounds was skipping past the content field without asking what it was for. It costs nothing to ask.
• Don't let a flat or disengaged interviewer shake your confidence. It says very little about how you're actually doing and even less about how your remaining rounds will go.
• Say "let me think about that" and actually mean it. Faking an instant answer is less credible than taking a real moment to think.

Closing Thoughts

Getting rejected after five rounds and three to four weeks of back-and-forth stings in a way that's hard to explain unless you've been through a loop this long. But writing this all out the code, the exact moments I hesitated, the questions I should've asked taught me more than the rejection email ever could. If you're prepping for something similar, I hope going through this with you, mistakes and all, makes your own prep a little sharper than mine was.

If you've been through something similar or you're about to be, I'd genuinely like to hear how it went for you too.

Trending Developer Reads

Visa Software Engineer 1 (SDE-1) Interview Experience | CodeSignal OA + Graph-Based Technical Rounds

Zepto SDE-1 Interview Experience (Backend Developer) : Real DSA, LLD, Chess Game Design

Blinkit (Eternal) SDE-1 Interview Experience (June 2026) – Offer Received

Spinny SDE-1 Interview Experience (Selected)

Rippling SDE-2 Interview Experience (4+ Years Experience) | Offer Received | Coding, LLD & System Design

American Express (AMEX) Online Assessment Experience (2026) | 3 Coding Questions

Amazon SDE-2 Interview Experience (3 Years Experience)

My Adobe SDE Interview Experience (Aug 2026) 5 Rounds, Selected

Top 50+ SQL Interview Questions and Answers for Intermediate to Advanced

JioHotstar Staff Software Engineer Interview Experience (Bangalore)

Responses (0)

Write a response

Hide Comments

No Comments yet.

‹ ›

‹ ›

‹ ›

‹ ›

Sponsored -53%

Zebronics #1 Best Seller

ZEBRONICS Blanc Slim Wireless Mouse — Rechargeable, BT + 2.4GHz (Black)

Up to 1600 DPI · Silent clicks · 63g · Multicolor LED

★★★★★★★★★★ 4.0 (9,512) 5K+ bought last month

₹376 M.R.P. ₹799Save ₹423

Buy Now →

‹ ›

‹ ›

‹ ›

‹ ›

Sponsored -34%

iQOO Amazon's Choice

iQOO Z10 Lite 5G — Cyber Green, 4GB RAM, 128GB Storage

Dimensity 6300 · 50MP Sony AI Camera · 6000 mAh · IP64

★★★★★★★★★★ 4.0 (2,052) 500+ bought last month

₹18,997 M.R.P. ₹28,999Save ₹10,002

Buy Now →

\n \n \n \n \n

I still remember opening the rejection email. Three and a half weeks of prep, five rounds and one line that said \"we've decided not to move forward at this time.\" No specifics, no feedback, just silence wrapped in polite corporate language.

If you're reading this because you have a Google interview coming up, I want this to feel different from the usual \"here are the questions I was asked\" post. I want to walk you through how I actually thought through each problem brute force, the moment it clicked and the mistakes I made along the way. This was a Backend Developer role, L4 level, referral-based, fully remote. Five rounds, spread across three to four weeks.

Round 1: The Square Made of Ones

Duration: 60 min | Difficulty: Hard

The interviewer opened with almost no small talk. He shared a matrix of 0s and 1s and told me somewhere inside it, there might be exactly one square sub-matrix made entirely of 1s I had to find its size and the top-left corner.

My thought process:

\n
• First instinct was brute force check every possible square, every size, every position. That's close to O(n⁴) and saying that number out loud made it obvious it wasn't good enough.
\n
• The real question was: what am I recomputing again and again? Every time I check a square of size k ending at (i, j), I'm re-checking cells I already checked for smaller squares. That's the signal for dynamic programming.
\n
• The idea: define dp[i][j] as the size of the largest square of 1s ending (bottom-right corner) at (i, j). If matrix[i][j] is 0, dp[i][j] is 0. If it's 1, the square can only grow as far as its weakest neighbor the minimum of the cell above, the cell to the left and the cell diagonally above-left plus one.
\n

public class LargestSquareSubmatrix {\n\n    // Returns {size, topRow, topCol}. If no square of 1s exists, size = 0.\n    public static int[] findLargestSquare(int[][] matrix) {\n        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {\n            return new int[]{0, -1, -1};\n        }\n\n        int rows = matrix.length;\n        int cols = matrix[0].length;\n        int[][] dp = new int[rows][cols];\n\n        int maxSize = 0;\n        int bottomRightRow = -1;\n        int bottomRightCol = -1;\n\n        for (int i = 0; i < rows; i++) {\n            for (int j = 0; j < cols; j++) {\n                if (matrix[i][j] == 1) {\n                    if (i == 0 || j == 0) {\n                        dp[i][j] = 1; // first row/column, square can only be size 1\n                    } else {\n                        dp[i][j] = Math.min(dp[i - 1][j],\n                                    Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;\n                    }\n                    if (dp[i][j] > maxSize) {\n                        maxSize = dp[i][j];\n                        bottomRightRow = i;\n                        bottomRightCol = j;\n                    }\n                }\n            }\n        }\n\n        if (maxSize == 0) return new int[]{0, -1, -1};\n        int topRow = bottomRightRow - maxSize + 1;\n        int topCol = bottomRightCol - maxSize + 1;\n        return new int[]{maxSize, topRow, topCol};\n    }\n}\n

Why it's optimal:

\n
• Time: O(rows × cols) every cell is visited exactly once.
\n
• Space: O(rows × cols) for the DP table, but can be reduced to O(cols) since each cell only needs the row above and the value to its left. I mentioned this without being asked, which is what turned it into a real technical conversation instead of just a pass/fail check.
\n

My mistake: I almost started coding before fully stating the DP recurrence out loud. The interviewer gently stopped me \"walk me through the relationship first.\" That pause probably saved me from messing up the boundary conditions for row 0 and column 0.

Follow-up he asked: What if multiple squares share the same maximum size how do you return all of them?\nMy answer: Track a list instead of a single position and append whenever dp[i][j] equals the current maxSize, not just when it's strictly greater.

Round 2: Numbers, Order and a Slightly Cold Room

Duration: 60 min | Difficulty: Medium

This round felt different from the first minute pleasant interviewer, but a flatness in his energy that made it hard to read whether I was doing well or badly. If you've had an interview where the other person just doesn't react, you know how unsettling that silence can be.

The problem: Given three numbers in a fixed order and a target, find an expression using only +, * and () that evaluates to the target, keeping the numbers in order. Example: 3, 2, 4 with target 20 → (3 + 2) * 4 = 20.

My thought process:

\n
• He asked first: how many combinations are even possible? I said \"four,\" thinking only about the two operator slots (+ or *) 2 × 2 = 4. Wrong and I sat in that silence for a second before catching it.
\n
• Parentheses change grouping, not just which operator goes where. (a + b) * c and a + (b * c) can give completely different results with the same operators.
\n
• Real approach: try every way to split the numbers into a left group and a right group, recursively find every value each group could produce, then combine those two sets with every operator to check if the target appears.
\n

import java.util.*;\n\npublic class ExpressionTargetFinder {\n\n    // Returns true if numbers (in given order) can be combined with +, *, ()\n    // to reach the target.\n    public static boolean canReachTarget(int[] nums, long target) {\n        Map<String, Set<Long>> memo = new HashMap<>();\n        Set<Long> allPossibleValues = solve(nums, 0, nums.length - 1, memo);\n        return allPossibleValues.contains(target);\n    }\n\n    private static Set<Long> solve(int[] nums, int left, int right,\n                                     Map<String, Set<Long>> memo) {\n        String key = left + \"-\" + right;\n        if (memo.containsKey(key)) return memo.get(key);\n        Set<Long> results = new HashSet<>();\n        if (left == right) {\n            results.add((long) nums[left]);\n            memo.put(key, results);\n            return results;\n        }\n        // every split point = every possible place for the \"outermost\" parentheses\n        for (int split = left; split < right; split++) {\n            Set<Long> leftValues = solve(nums, left, split, memo);\n            Set<Long> rightValues = solve(nums, split + 1, right, memo);\n            for (long l : leftValues) {\n                for (long r : rightValues) {\n                    results.add(l + r);\n                    results.add(l * r);\n                }\n            }\n        }\n        memo.put(key, results);\n        return results;\n    }\n}\n

Why this generalizes: it doesn't just handle three numbers for any n numbers, it's \"split into a left half and right half, solve each recursively, combine.\" Same divide-and-conquer shape as evaluating all results of an expression with different parenthesizations. Memoization barely matters at n = 3, but leaving it out looks like you only solved the specific case in front of you, not the pattern.

My mistake: my first version had no memoization. When he asked \"what if there were six numbers instead of three?\", I had to admit it would recompute the same sub-ranges repeatedly. I added the memo map live.

Follow-up he asked: Can you return the actual expression string, not just whether it's possible?\nMy answer: Store pairs of (value, expressionString) in the memo instead of just values, so you can reconstruct exactly which grouping produced the target.

Takeaway from this round: don't assume a flat, unreadable interviewer means you're failing. Stay steady and keep thinking clearly anyway.

Round 3: Painting a Fence, One Stroke at a Time

Duration: 60 min | Difficulty: Medium

A relief after the last round this interviewer was actually present, asking questions because he was curious, not just to check boxes.

The problem: A fence made of boards with different heights. A brush 1m wide can paint one board vertically (full height, one stroke) or paint horizontally across adjacent boards at the same height level, as long as all of them reach that height. Find the minimum strokes to paint the whole fence. Example: [1, 2, 2, 1, 2] → 3.

My thought process:

\n
• Baseline: paint every board vertically always valid, always costs exactly n strokes.
\n
• A horizontal stroke only helps when it covers more than one board at once.
\n
• Key idea: look at the shortest board in the current range. You can paint min_height horizontal strokes across the entire range, since every board is at least that tall. What's left above that line is a smaller version of the same problem, split into segments wherever a board's leftover height hits zero solve each segment recursively.
\n

public class FencePainting {\n\n    public static int minStrokes(int[] heights) {\n        if (heights == null || heights.length == 0) return 0;\n        return solve(heights, 0, heights.length - 1);\n    }\n\n    private static int solve(int[] heights, int low, int high) {\n        if (low > high) return 0;\n\n        int minHeight = Integer.MAX_VALUE;\n        for (int i = low; i <= high; i++) {\n            minHeight = Math.min(minHeight, heights[i]);\n        }\n        int horizontalCost = minHeight;\n        int i = low;\n        while (i <= high) {\n            if (heights[i] == minHeight) {\n                i++;\n                continue; // nothing left above the min line for this board\n            }\n            int start = i;\n            while (i <= high && heights[i] != minHeight) i++;\n            int[] leftover = new int[i - start];\n            for (int k = 0; k < leftover.length; k++) {\n                leftover[k] = heights[start + k] - minHeight;\n            }\n            horizontalCost += solve(leftover, 0, leftover.length - 1);\n        }\n        int verticalCost = high - low + 1;\n        return Math.min(horizontalCost, verticalCost);\n    }\n}\n

Tracing the example [1, 2, 2, 1, 2]:

\n
• Min height across all 5 = 1 → one horizontal stroke covers all of them.
\n
• Leftover after subtracting: [0, 1, 1, 0, 1] → splits into segments [1, 1] and [1].
\n
• [1, 1] costs min(1, 2) = 1. [1] costs min(1, 1) = 1.
\n
• Total: 1 + 1 + 1 = 3, versus 5 if painted vertically. Minimum is 3 matches the expected output.
\n

Why it's optimal: each recursive call only scans its own range and ranges shrink every call nowhere close to trying every possible combination of strokes, which would blow up exponentially.

Mistake: none major this time I'd seen a similarly shaped \"painting\" problem in prep, so the recursion felt familiar rather than something I was inventing live.

Follow-up he asked: What if the brush could also paint diagonally?\nMy answer: Honestly said I'd need time to think, since diagonal strokes break the clean row/column split this recursion depends on.

Round 4: The Round That Quietly Broke Me a Little

Duration: 60 min | Difficulty: Hard

This is the round I keep replaying and the one I suspect the rejection came from.

The problem: Design a small messaging system with two operations:

\n
• registerEvent(user1, user2, content) records that user1 messaged user2 with some content.
\n
• getFrequent() returns any user who has received messages from the most unique senders (repeated messages from the same sender count once).
\n

My thought process:

\n
• First instinct: a map from receiver to a message count. Caught my own mistake before he pointed it out a plain counter would count repeated messages from the same sender multiple times, which the problem explicitly rules out.
\n
• Fix: map receiver to a set of senders instead of a count. A set naturally ignores duplicates.
\n

import java.util.*;\n\npublic class MessagingFrequencyTracker {\n\n    // receiver -> set of unique senders who have messaged them\n    private final Map<String, Set<String>> receiverToSenders = new HashMap<>();\n    private int maxUniqueSenders = 0;\n\n    public void registerEvent(String sender, String receiver, String content) {\n        receiverToSenders\n            .computeIfAbsent(receiver, k -> new HashSet<>())\n            .add(sender);\n        int currentCount = receiverToSenders.get(receiver).size();\n        if (currentCount > maxUniqueSenders) {\n            maxUniqueSenders = currentCount;\n        }\n    }\n\n    // Returns any one user who has received messages from the most\n    // unique senders. Returns null if no events registered.\n    public String getFrequent() {\n        for (Map.Entry<String, Set<String>> entry : receiverToSenders.entrySet()) {\n            if (entry.getValue().size() == maxUniqueSenders) {\n                return entry.getKey();\n            }\n        }\n        return null;\n    }\n}\n

\n
• registerEvent: O(1) average one HashSet insert, one HashMap lookup.
\n
• getFrequent: O(1) because maxUniqueSenders is tracked incrementally instead of recalculated on every call.
\n

Two things I only got to because he pushed me, not because I saw them myself:

\n
• He asked: \"What if getFrequent() is called far more often than registerEvent() does your approach handle that well?\" My first version scanned all receivers inside getFrequent() O(number of receivers) every call. Moving the max-tracking into the write path fixed it, but only after his nudge.
\n
• I never asked out loud what the content field was for. I quietly assumed it was irrelevant and moved on. A stronger candidate asks: \"does content matter here or is it just for completeness?\" it costs ten seconds and shows you read the whole problem.
\n

Follow-up he asked: How would this change if you needed the top 3 most-messaged users, not just one?\nMy answer: Talked through a small sorted structure a TreeMap keyed by count or a min-heap of size 3 instead of a single integer. Got there, but slower than I liked.

Round 5: The Human Round

Duration: 45 min | Difficulty: Medium (Behavioral)

By this point I was genuinely tired the kind of tired that's hard to explain unless you've done back-to-back technical rounds spread across separate days over several weeks.

Questions I was asked:

\n
• Walk me through a project you've worked on and your role in it.
\n
• Tell me about a mistake you made and what you learned from it.
\n
• Give an example of working closely with a team.
\n
• Tell me about a time you had a conflict at work and how you resolved it.
\n
• How do you take ownership when something goes wrong?
\n

What worked for me: I talked about a real production incident a mistake I made with a caching layer that served stale data to users for close to twenty minutes before anyone noticed. I walked through:

\n
• How I traced it back to the root cause.
\n
• What I changed to prevent it from happening again.
\n
• What I told my team afterward so they could catch the same class of mistake earlier next time.
\n

Ownership, a real mistake, a real fix, a real lesson that lands far better than a vague, safe answer with no actual stakes in it.

My advice for this round:

\n
• Prepare 3-4 real stories, not invented ones.
\n
• Practice saying them out loud so they don't sound rehearsed.
\n
• Interviewers notice the difference between a story you're remembering and one you're reciting.
\n

What I Think Actually Went Wrong

I don't know for certain Google doesn't give that kind of feedback. But my honest guess is Round 4. Not because the final solution was wrong it worked and it hit O(1) for both operations. It's the two nudges that mattered. At L4, you're expected to:

\n
• Ask the clarifying question about the content field on your own.
\n
• Think about read-heavy versus write-heavy access patterns without being asked.
\n

I got to the right place, but I got there by being pushed, not by getting there myself. That's a real gap, worth sitting with instead of explaining away.

Preparation Tips

\n
• Don't rely on memorized patterns. Every problem in this loop was a twist on something familiar DP, backtracking, divide and conquer but none matched a textbook version word-for-word. Train yourself to recognize the underlying shape of a problem (overlapping subproblems, need to try every grouping, shrinking ranges), not just its surface description.
\n
• Always be ready to explain trade-offs, even after your solution works. In almost every round, the moment I finished a working solution, the next question was about space, scaling or read/write frequency. Google checks whether you'd think to improve your own solution unprompted.
\n
• Ask the clarifying questions you're tempted to skip. My biggest actual mistake across all five rounds was skipping past the content field without asking what it was for. It costs nothing to ask.
\n
• Don't let a flat or disengaged interviewer shake your confidence. It says very little about how you're actually doing and even less about how your remaining rounds will go.
\n
• Say \"let me think about that\" and actually mean it. Faking an instant answer is less credible than taking a real moment to think.
\n

Closing Thoughts

Getting rejected after five rounds and three to four weeks of back-and-forth stings in a way that's hard to explain unless you've been through a loop this long. But writing this all out the code, the exact moments I hesitated, the questions I should've asked taught me more than the rejection email ever could. If you're prepping for something similar, I hope going through this with you, mistakes and all, makes your own prep a little sharper than mine was.

If you've been through something similar or you're about to be, I'd genuinely like to hear how it went for you too.