Google L4 Interview Questions (2026): What They Actually Ask

BFS with a queue. Initialize the queue with the root. At each level, process all nodes currently in the queue, adding their children for the next level. Collect node values into a list per level. Edge case: empty tree.

Often a warm-up question or embedded within a harder problem. The variant Google interviewers reach for most frequently: "return nodes in zigzag order," alternating left-to-right and right-to-left by level. That extension requires a direction flag and either reversing every other level's list or using a deque.

from collections import deque

def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

Conflict resolution stories should include the specific nature of the disagreement (not "we had different opinions" but "they wanted to rewrite the entire service; I thought we should isolate the broken module"), how you surfaced it constructively, and whether the resolution actually stuck. "We talked it out and agreed" is not a complete answer. What changed after the conversation, and how do you know the change held?

Reported from a 2025 Googleyness round where the candidate said the interviewer asked specifically about the aftermath, not just the resolution moment. Google cares about durable outcomes, not one-off conversations.

This maps to the "putting users first" and "doing the right thing" Googleyness traits. The strongest answers involve spotting a pain point (slow CI pipeline, flaky test suite, manual deployment step) that others had accepted as normal, quantifying its cost (2 hours per engineer per week), and shipping a fix that persisted after you moved on. The "without being asked" element matters: Google wants engineers who identify problems, not just execute on assigned tickets.

One specific pattern that scores well here: the candidate noticed the problem through user or teammate feedback, not because it affected them directly. That signals user-first orientation.

Generic answers about scale, impact, or "working on products used by billions" do not land well at Google. They hear that in every interview. What works: specificity about the team's actual work, a product or infrastructure challenge that connects to your background, or a technical direction at Google that you've thought about and have an informed opinion on.

Do homework on what the specific team ships. If it is a Search infrastructure role, that's the 2024 Search quality updates and the indexing pipeline changes. If it is a YouTube team, that's the live streaming latency work. If you cannot get specifics from the recruiter, ask directly: "What is the team's top priority in 2026?" That question itself is a signal.

Maps to "put the user first." The strongest stories describe noticing a user-facing problem that wasn't on your team's roadmap and either fixing it directly or escalating it loudly enough that someone did, with a concrete before-and-after: fewer support tickets, lower error rate, a specific latency number.

Candidates who reach for an actual customer or end user in the example score better than ones who substitute a teammate for "user." The trait is specifically about people outside your immediate team, and interviewers reportedly notice when a candidate quietly swaps in an easier internal example.

Not as a standard round. System design is formally part of the L5 and above evaluation at Google. Multiple candidate reports from 2024 and 2025 confirm that L4 onsites typically include two to three coding rounds plus one Googleyness round. That said, a few teams include a lighter design conversation within the hiring manager call, and some candidates are simultaneously evaluated against the L5 bar, in which case a design round may appear. Ask your recruiter directly for your specific loop format.

Most candidates report six to ten weeks from initial application to verbal offer. The phone screen typically happens one to two weeks after the GHA. Onsites are scheduled one to three weeks after the phone screen clears. Hiring committee review after the onsite adds another one to two weeks. Referrals and recruiter-sourced candidates often move faster, sometimes four to five weeks total. The hiring committee review is the step with the most variance in timing.

Python is the most commonly used language in reported Google interviews and is generally preferred for its readability in a shared Google Doc. Java and C++ are also accepted. The shared Doc format means there is no syntax highlighting or autocomplete, so using a language with clean, readable syntax matters more than usual. Whatever you choose, know the standard library cold: Python's collections module, heapq, and itertools come up constantly, and fumbling with syntax in a Doc with no autocomplete wastes time.

Phone screen: medium difficulty, sometimes on the easier end of medium. Onsite coding rounds: medium to hard, with follow-up constraints that often push a medium problem into hard territory. The "Count Range Sum" problem (hard) has been specifically reported at L4 onsites. A practical benchmark from candidate reports: if you can solve 70% of LeetCode mediums and 30% of hards in 30 minutes with a clean explanation, you are roughly at the bar. Speed matters less than correctness and communication.

The GHA is a 30 to 45 minute personality-and-culture screen with about 50 Likert-scale questions. It is not a coding test. Google does use it as a filter before the recruiter call in some pipelines, so candidates who rush through it or answer inconsistently can get screened out before their resume reaches a human reviewer. Answer honestly and consistently. There are no objectively correct answers, but large inconsistencies between related questions flag the screener.

Both, and increasingly a hybrid. As of 2025, Google has been requiring at least one in-person round for candidates within commuting distance of a Google office, partly in response to AI-assisted cheating concerns during virtual coding sessions. For candidates geographically remote from a Google office, fully virtual loops are still available. The format for your specific loop will be communicated by your recruiter. The coding environment is identical either way: a shared Google Doc with no editor tooling.

Each interviewer submits a written packet, not just a numeric score, describing what they observed in detail. A hiring committee made up of engineers and managers who never interviewed you then reviews the full set of packets and makes the call without meeting you in person. If approved, most L4 candidates move into a separate Team Match process to be paired with a specific team, and Google's final leveling can occasionally shift up or down slightly during that stage based on team fit.

Reported: this two-stage structure surprises a lot of candidates who assume the interview loop itself makes the final decision. Multiple 2025 write-ups describe waiting two to three weeks between hiring committee approval and being matched to an actual team, which is separate time from the interview process itself.

Yes, but Google enforces a cooldown before you can interview again. The most commonly reported window is 12 months after a full-loop rejection, sometimes shorter for candidates rejected earlier in the process, such as at the recruiter screen or phone screen stage. The exact window isn't published anywhere official, and recruiters give different numbers depending on the specific req and how the rejection was recorded internally.

Reported: candidates who reapply after addressing one specifically named weakness from their prior loop describe better outcomes than those who just say they "practiced more" in general. Vague, undirected re-preparation reportedly gets flagged in a similar way to the first attempt.

A stack is last-in-first-out. The last element you push is the first one you pop. A queue is first-in-first-out. The first element you enqueue is the first one you dequeue. Both support O(1) insert and remove when implemented correctly, the difference is purely about which end you're allowed to touch.

Stacks show up in call frames (the actual function call stack), undo/redo history, parsing balanced parentheses, and depth-first traversal, since you naturally want to explore the most recently discovered node first. Queues show up in breadth-first traversal, task scheduling, and any producer-consumer setup where fairness matters, like a print queue or a request buffer, because you want to process things in the order they arrived rather than the order you most recently saw them.

One gotcha interviewers like to probe: implementing a queue with two stacks. You push everything onto an "in" stack, and when you need to dequeue, you pop everything from "in" into an "out" stack (reversing the order) and pop from "out". Each element moves at most twice across its lifetime, so the amortized cost per operation is still O(1) even though a single dequeue can occasionally be O(n).

Big O describes how the running time or memory use of an algorithm grows as the input size n grows, ignoring constant factors and lower-order terms. O(n) means the work scales linearly with input size, O(n log n) is what you get from good sorting algorithms and divide-and-conquer approaches, O(n squared) usually means nested loops over the same collection, and O(log n) means you're cutting the problem in half at each step, like binary search.

Interviewers care about it because it's the fastest way to tell whether a candidate's solution will actually work at scale, not just on the small example in front of them. A brute force O(n squared) solution that checks every pair might pass on an input of 10 elements and time out on an input of 10 million, which is exactly the kind of thing that breaks in production. Asking for the complexity forces you to reason about your own solution instead of pattern-matching to a memorized answer.

It's also worth knowing the difference between average case and worst case, and being able to state both. A hash map lookup is O(1) on average but O(n) in the worst case if every key collides into the same bucket. Google interviewers will sometimes push on this specifically, asking what happens if your hash function is bad or your input is adversarial, so having an answer ready for the worst case, not just the happy path, shows you actually understand the data structure rather than just having used it.

Sliding window with two pointers and a hash set. The left pointer advances whenever a duplicate is found, removing the leftmost character from the set. Track the maximum window size seen. Time complexity O(n), space O(min(n, alphabet size)).

Reported from a 2025 phone screen. The follow-up almost always extends to: "What if the string contains Unicode characters instead of ASCII?" The answer changes the space complexity bound, since the character set is no longer bounded by 128. The interviewer is checking whether you understand why you chose the data structure, not just that you did.

def length_of_longest_substring(s: str) -> int:
    char_set = set()
    left = 0
    max_len = 0
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
    return max_len

Sort by start time. Iterate through the list; if the current interval's start is less than or equal to the previous merged interval's end, extend the end. Otherwise append a new interval. Common edge cases to discuss: single interval, all intervals overlapping, intervals that touch exactly (e.g., [1,3] and [3,5], most Google interviewers want these merged).

Reported from multiple L4 onsites and at least two phone screens. Shows up with different framings: meeting rooms, calendar events, time blocks. The underlying structure is always the same. One candidate's 2024 write-up described four follow-up questions after the base solution, ending with "what if intervals can be added dynamically and you need to query the merged state after each insertion?"

def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Bottom-up DP. Boolean array dp where dp[i] is true if s[0:i] can be segmented. For each index i, check all j from 0 to i: if dp[j] is true and s[j:i] is in the word set, set dp[i] to true. Time O(n^2 * m) where m is average word length for the substring check; use a hash set for O(1) word lookups.

Reported from a phone screen and an onsite in 2024. Follow-up: "Return all valid segmentations, not just whether one exists." That shifts the problem from DP to backtracking with memoization, and the state space is much larger. Interviewers want to hear you articulate the shift in approach before implementing.

Build a hash map where the key is a canonical form of each word (either the sorted character string, or a fixed-length count vector of the 26 lowercase letters) and the value is the list of original words that share that key. One pass through the input, one hash map. Time is O(n * k log k) with sorting as the key, or O(n * k) with a count vector, where k is average word length.

Reported from several 2024-2025 phone screens as a warm-up before a harder string problem. The follow-up worth having ready: "the sorted-string key is O(k log k) per word, can you do better?" The count-vector key answers that directly, and most candidates don't reach for it until prompted, which is exactly why interviewers ask.

Two passes. First pass builds a prefix-product array where each index holds the product of every element to its left. Second pass walks right to left, multiplying a running suffix product into the prefix array as it goes. No division anywhere, so a zero anywhere in the input never causes a divide-by-zero edge case to handle separately.

Reported from multiple 2024 phone screens. The instinctive first answer (divide the total product by each element) gets rejected immediately once you say it out loud, since division isn't allowed and zeros in the input break it anyway. Interviewers want to see you reach for prefix and suffix products without being told division is banned.

def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [1] * n
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    return result

Bottom-up 1D DP. dp[amount] holds the fewest coins needed to make that amount, initialized to infinity except dp[0] = 0. For each amount from 1 up to the target, try every coin denomination and take dp[amount - coin] + 1 if that's smaller than the current value. If dp[target] is still infinity at the end, the amount can't be made with the given coins.

Reported from a phone screen in late 2024. The follow-up that shows up almost every time: "now return one valid combination of coins, not just the count." That requires tracking which coin was used at each dp index and walking backward from the target once the table is filled, which is a different kind of bookkeeping than the count-only version.

DFS or BFS from each unvisited land cell. Mark visited cells in-place (change '1' to '0' or a separate visited array). Each DFS call from a new '1' increments the island count. Time O(m*n), space O(m*n) for the recursion stack in the worst case (grid entirely land).

Reported from multiple 2025 onsite rounds. Follow-ups go fast here: "What if the grid is too large to fit in memory?" (stream rows, track boundary cells). "What if cells connect diagonally?" (add 4 more neighbor directions). "What is the area of the largest island?" (track size during DFS). Having these extensions ready to discuss matters.

Build a trie where each node stores the character and a list (or priority queue) of the top-k most frequent completions seen at that prefix. On insert, walk down the trie updating frequency counts and propagating the top-k candidates up the prefix chain. On search, return the stored candidates at the prefix node in O(prefix length) time.

Reported from a 2025 L4 onsite. This is a real product-flavored question: "Implement search autocomplete." Interviewers care about the trade-off discussion as much as the code. Storing top-k at every node is O(n * k) space but gives O(1) query time per prefix character. Alternatives: walk the subtrie on every query (less space, slower queries). Having a position on the trade-off before coding is expected.

DFS with two sets: a visited set and a recursion stack. If DFS encounters a node that's already in the recursion stack, a cycle exists. After fully exploring a node's neighbors, remove it from the stack. The standard visited set alone is not enough for directed graphs; a node can be visited from two different paths without implying a cycle.

Reported from a phone screen in late 2024. The most common follow-up: "How does this change for an undirected graph?" The undirected version only needs a visited set and parent tracking, since an edge back to the parent is not a cycle. Expect the follow-up to lead into topological sort, which builds directly on cycle detection in directed graphs.

def has_cycle(graph: dict) -> bool:
    visited = set()
    rec_stack = set()

    def dfs(node):
        visited.add(node)
        rec_stack.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in rec_stack:
                return True
        rec_stack.remove(node)
        return False

    return any(dfs(node) for node in graph if node not in visited)

Greedy interval scheduling. Sort meetings by end time (not start time, this is where candidates go wrong). Greedily select each meeting that starts at or after the end of the last selected meeting. This produces the maximum count. Proof: choosing the meeting that ends earliest always leaves the most room for future meetings.

Reported from an L4 onsite in 2025 in a slightly different form: "You have a list of meetings with start and end times. What is the maximum number of meetings one person can attend?" Interviewers push on why you sort by end time rather than start time. The answer is not just correct but needs a clear justification.

Recursive DFS. If the current node is null or matches either target node, return it. Otherwise recurse into both the left and right subtrees. If both recursive calls return a non-null result, the current node is the split point and therefore the answer. If only one side returns non-null, pass that result upward.

Reported as one of the most common warm-up questions across both phone screens and onsites, often given before a harder graph problem in the same round. Two follow-ups show up repeatedly: "what changes if the tree is a binary search tree" (you can skip one branch entirely using the BST ordering property, giving O(log n) instead of O(n)), and "what if nodes have a parent pointer instead" (the problem collapses into finding the intersection point of two linked lists).

def lowest_common_ancestor(root, p, q):
    if root is None or root == p or root == q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        return root
    return left if left else right

Model courses as nodes and prerequisites as directed edges, then run Kahn's algorithm: compute the in-degree of every node, push all zero-in-degree nodes into a queue, and repeatedly pop a node, "complete" it, and decrement the in-degree of its neighbors, pushing any that hit zero. If the total number of processed nodes equals the total number of courses, every course is finishable; if fewer, a cycle exists somewhere in the graph and finishing is impossible.

Reported as the direct continuation of the directed-cycle-detection question earlier in this page, and candidate write-ups describe interviewers presenting it in the exact same interview session as a natural next step: the DFS-with-recursion-stack cycle check above tells you a cycle exists, this problem asks you to also produce a valid ordering when one doesn't.

DFS or BFS from the given starting node, using a hash map from original node to its cloned counterpart. Before recursing into a neighbor, check whether it's already in the map; if so, use the existing clone instead of creating a new one and recursing again, which is what prevents infinite loops when the graph contains cycles.

Reported from several 2024-2025 phone screens, usually presented with a small diagram of 4-6 nodes. Almost every candidate who fails this gets stuck re-cloning the same node repeatedly in a cycle; the hash-map-before-you-recurse ordering is the entire trick, and it's easy to get backward under time pressure.

Modified binary search. At each step, check which half of the current range (left-to-mid or mid-to-right) is properly sorted, then check whether the target falls inside that sorted half's value range. If it does, search that half; if it doesn't, the target must be in the other half, even though that half isn't sorted on its own.

Reported as a frequent phone screen filter question. It's treated less as a hard problem and more as a "did you actually get the boundary conditions right" check: the difference between <= and <, and how duplicate values break the "which half is sorted" logic, are exactly the kind of off-by-one mistakes that a shared Google Doc with no compiler won't catch for you.

Maintain a min-heap of size k. For each new number, push it onto the heap, and if the heap grows past size k, pop the smallest element off. The root of the heap is always the kth largest value seen so far. Each insertion is O(log k).

The static-array version of this question (find the kth largest element in a fixed array) can be solved faster on average with quickselect, but Google interviewers reportedly prefer rephrasing it as a stream specifically because quickselect doesn't work incrementally. That reframing is a deliberate way to force the heap-based answer rather than the average-case-faster one.

Google wants end-to-end ownership. The story should cover how you identified the problem, how you mobilized resources or people without formal authority, what blocked you, and what the concrete outcome was (shipped by date X, reduced latency by Y ms, removed Z lines of tech debt). The phrase "without being asked to" is in the question for a reason: they want proactive behavior, not task completion.

Reported from a 2025 Googleyness round. The follow-up after this question is almost always "what would you have done differently?" Have a specific answer, not a generic "I'd communicate earlier." Generics signal you haven't actually processed the experience.

This tests the "challenging the status quo" trait and collaborative mindset together. The answer should describe a specific disagreement or inertia you encountered, the data or reasoning you used to make your case, and how you got others to move without being their manager. "I made a spreadsheet comparing the two approaches and shared it in the team channel" is more credible than "I scheduled a meeting to align everyone."

Reported in multiple 2024-2025 behavioral write-ups. Interviewers specifically want to see that influence came from substance, not social pressure. Candidates who describe "building consensus" without describing the content of their argument tend to get a weak signal here.

Google specifically does not want polished-failure stories where everything turned out fine. They want to see intellectual honesty: something that actually went wrong, your role in it, and a concrete change you made as a result. "We shipped a race condition to prod that caused 2 hours of downtime. I had reviewed the code but missed the concurrency assumption. After that I added a specific concurrency checklist to our PR review template" is the kind of specificity that scores well.

Interviewers follow up by asking whether the structural change you made actually worked. If you don't know, say so. "I don't have data on whether the checklist prevented similar bugs after I left the team" is a better answer than claiming impact you can't verify.

The answer structure that works: name the specific technical disagreement (not "an architectural decision" but "whether to use a message queue or direct RPC calls for inter-service communication"), describe what evidence you brought to the conversation, state what the outcome was, and reflect on whether the decision was correct in hindsight. Candidates who defer entirely to seniority signal low agency. Candidates who claim they always win disagreements signal low self-awareness.

One candidate who went through a 2025 Google L4 loop described spending 20 minutes on this single question. The interviewer kept asking "and then what?" until they'd reconstructed the entire technical debate, not just the surface conflict. Prepare the technical substance, not just the interpersonal resolution.

Google values bias toward action and comfort with ambiguity. The answer should show that you identified what you did and didn't know, took the smallest action that would reduce your uncertainty (an experiment, a quick prototype, a user research session with three people), and committed to a path with an explicit trigger to revisit. Answers that describe endless data gathering before any decision signal analysis paralysis.

The follow-up is usually "how did the decision turn out?" Have the honest answer. If it turned out badly, explain what signal you got and how quickly you caught it. Speed of feedback loops is part of what Google is evaluating here.

This maps directly to the "valuing feedback" trait. The strongest answers name the feedback close to verbatim ("my tech lead told me my code reviews were blocking the team because I was too slow"), describe the actual internal reaction honestly, including if it stung at first, and then describe one specific behavior that changed afterward, with some way to check whether it stuck.

Interviewers push on whether you actually changed, not whether you nodded along in the moment. "I agreed with the feedback and thanked them" without a described change afterward reads, in the words of one 2025 candidate account, "like you're describing a conversation, not an outcome."

This is a distinct comfort-with-ambiguity prompt from the incomplete-information question above; it's specifically about a plan shifting mid-flight rather than starting from a blank slate. Strong answers quantify how much rework the change actually cost, whether any earlier design decision happened to absorb part of the change for free, and what you'd design differently next time to make future pivots cheaper.

Reported from a 2025 Googleyness round transcript shared on Blind. The candidate noted a pointed follow-up: "was the requirement change avoidable?" Sometimes it wasn't. Saying so, instead of forcing a lesson-learned narrative onto something genuinely out of your control, is a fine answer.

Distinct from disagreeing with a senior engineer's technical call, this one tests whether you can say no upward without becoming obstinate or simply complying. Strong answers describe the specific reasoning you brought, what alternative you offered instead of a flat no, and the actual outcome, including cases where you pushed and still lost the argument.

Reported from 2025 candidate accounts describing this as one of the harder Googleyness questions to answer honestly. Interviewers reportedly rate "I raised the concern, was overruled, and executed anyway without carrying resentment into the work" as a legitimate and even preferred outcome. Compliance without ever raising the concern in the first place is the answer that scores lowest here, worse than pushing back and losing.

Two-pointer approach: maintain a left and right pointer starting at each end, along with the current max height seen from each side. At each step, move the pointer with the smaller max height inward, adding the difference between that pointer's height and the current max to the trapped water total. O(n) time, O(1) space.

Reported from onsite rounds in 2024 and 2025. The brute-force approach (precompute left-max and right-max arrays) is correct but interviewers expect you to optimize to O(1) space. One candidate reported being asked "what if the input is a 2D elevation map instead of a 1D array?" after solving the 1D version, which requires a BFS/priority-queue approach.

def trap(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    return water

Two pointers over s, plus a frequency count of the characters needed from t. Expand the right pointer, decrementing a "still needed" counter each time a required character is seen enough times. Once every character requirement is satisfied, shrink the left pointer as far as possible while the window stays valid, recording the smallest valid window found. O(n + m) time.

Reported from a 2025 onsite as the direct escalation after the longest-substring-without-repeating-characters warm-up earlier in this page, candidates who treat it as an unrelated new problem lose time re-deriving the sliding window mechanics from scratch instead of adapting what they already built. Google interviewers reportedly watch for that specific transition.

from collections import Counter

def min_window(s: str, t: str) -> str:
    if not t or not s:
        return ""
    need = Counter(t)
    missing = len(t)
    left = start = end = 0
    for right, char in enumerate(s, 1):
        if need[char] > 0:
            missing -= 1
        need[char] -= 1
        if missing == 0:
            while left < right and need[s[left]] < 0:
                need[s[left]] += 1
                left += 1
            if end == 0 or right - left < end - start:
                start, end = left, right
    return s[start:end]

The O(n^2) version is straightforward: dp[i] holds the longest increasing subsequence ending at index i, computed by checking every earlier index j where nums[j] < nums[i]. The O(n log n) version Google wants as a follow-up maintains a separate array of the smallest possible tail value for each subsequence length seen so far, and uses binary search to find where each new number belongs in that array.

Reported from a 2025 L4 onsite. One candidate's write-up described the interviewer accepting the O(n^2) solution, then asking, without any other prompt, "can you do this in O(n log n)?" The binary-search-on-tails trick isn't something most engineers derive live under pressure; it's worth having memorized cold rather than reasoned out from first principles in the room.

from bisect import bisect_left

def length_of_lis(nums: list[int]) -> int:
    tails = []
    for num in nums:
        i = bisect_left(tails, num)
        if i == len(tails):
            tails.append(num)
        else:
            tails[i] = num
    return len(tails)

2D DP table where dp[i][j] is the minimum number of insertions, deletions, or substitutions needed to turn the first i characters of word1 into the first j characters of word2. If the current characters match, dp[i][j] = dp[i-1][j-1]. If they don't, dp[i][j] = 1 + min of the insert, delete, and substitute cases.

Reported from a 2024 L4 onsite and flagged in candidate prep guides as a genuine hard problem rather than a medium with escalating constraints. The standard follow-up: reduce the space from O(m*n) to O(min(m,n)) by only keeping two rows of the table in memory at once, since each row only depends on the row directly above it.

def min_distance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    return dp[m][n]

Binary search on the smaller array to find the correct partition. For each candidate partition, check if the max of the left side of both arrays is less than or equal to the min of the right side of both arrays. Adjust the partition left or right based on which condition is violated. Handles odd and even combined lengths differently.

Reported from a 2024 L4 onsite and listed in multiple candidate prep guides as a "classic Google hard." The key insight to articulate: you're not searching for a value, you're searching for a partition point. Interviewers at Google want the O(log n) solution specifically; the O(n) merge approach is accepted as a starting point only.

def find_median_sorted_arrays(nums1: list[int], nums2: list[int]) -> float:
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    m, n = len(nums1), len(nums2)
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2
        j = (m + n + 1) // 2 - i
        max_left1 = float('-inf') if i == 0 else nums1[i - 1]
        min_right1 = float('inf') if i == m else nums1[i]
        max_left2 = float('-inf') if j == 0 else nums2[j - 1]
        min_right2 = float('inf') if j == n else nums2[j]
        if max_left1 <= min_right2 and max_left2 <= min_right1:
            if (m + n) % 2 == 1:
                return float(max(max_left1, max_left2))
            return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2.0
        elif max_left1 > min_right2:
            hi = i - 1
        else:
            lo = i + 1
    return 0.0

Use prefix sums and a modified merge sort. During the merge step, for each element in the right half, count how many prefix sums in the left half fall within [prefix[j] - upper, prefix[j] - lower] using two pointers. This gives O(n log n) total. Brute force is O(n^2) and explicitly rejected at Google.

Reported from a 2024 L4 onsite. This is a legitimate hard problem, not just a medium with a follow-up. Interviewers use it specifically because it requires a non-obvious connection between prefix sums and merge sort. Candidates who recognize the pattern from prior exposure do significantly better than those who derive it fresh.

Preorder DFS for serialization, writing each node's value and using an explicit marker (commonly "#" or "null") for missing children, joined with a delimiter. Deserialization reads the same token stream in order and rebuilds the tree recursively, consuming one token per call and trusting that the preorder-with-null-markers format is unambiguous by construction.

Reported from a 2025 onsite as one of the harder tree problems in current rotation. What makes it a real hard rather than a dressed-up medium: the interviewer is evaluating whether you pick a traversal order that's actually reversible before you start typing, not just whether you can write a tree traversal. Candidates who start coding before deciding how null children get represented tend to rewrite half their solution partway through.

BFS over an implicit graph where each word is a node, and two words are connected if they differ by exactly one letter. Starting from the source word, at every position in the current word try all 26 possible letter substitutions, check whether the result is in the word set, and if so mark it visited and add it to the next BFS layer. The first time the target word is reached, the current BFS depth is the answer.

Reported in at least two 2025 onsite write-ups as, in one candidate's words, "Google's favorite disguised BFS problem." The graph is never handed to you, you have to recognize that a shortest-path problem is hiding inside a string transformation and construct the adjacency on the fly. That recognition step, more than the BFS mechanics itself, is what the interviewer is grading.

from collections import deque
import string

def ladder_length(begin_word: str, end_word: str, word_list: list[str]) -> int:
    words = set(word_list)
    if end_word not in words:
        return 0
    queue = deque([(begin_word, 1)])
    while queue:
        word, steps = queue.popleft()
        if word == end_word:
            return steps
        for i in range(len(word)):
            for c in string.ascii_lowercase:
                candidate = word[:i] + c + word[i + 1:]
                if candidate in words:
                    words.remove(candidate)
                    queue.append((candidate, steps + 1))
    return 0

Min-heap holding the current head node from each of the k lists, keyed by node value. Pop the smallest, append it to the result list, and if that node has a next node, push it onto the heap. Continue until the heap is empty. Total time is O(N log k), where N is the combined number of nodes across all lists.

Reported from a 2024 L4 onsite and named alongside count range sum earlier on this page as one of the two problems candidates specifically described as "actually hard, not a medium with follow-ups." The naive approaches, merging lists two at a time or dumping every node into one list and sorting, both get pushed on immediately since neither reaches O(N log k).

import heapq

def merge_k_lists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    dummy = tail = ListNode()
    while heap:
        val, i, node = heapq.heappop(heap)
        tail.next = node
        tail = tail.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

Two sub-problems: offline aggregation of query frequencies (MapReduce over search logs, updated every hour or day), and online serving of top-k completions for a prefix. For serving, a trie with top-k completions cached at each node works but doesn't scale to billions of queries. In practice, the prefix is hashed to a serving shard that holds a compact prefix tree. Discuss staleness tolerance (hourly vs. daily updates), personalization (user history re-ranks suggestions), and the different latency requirements for each character typed (under 100ms to feel instant).

This problem comes up at both L4 and L5 levels. At L4, interviewers are mostly evaluating data structure selection and trade-off reasoning. At L5, they push on the distributed sharding strategy and consistency model. Reported from a 2025 onsite where the candidate described it as "a trie question dressed up as a system design."

Key components: a hash function to generate short codes (base62 encoding of an auto-incremented ID works better than pure hashing for collision avoidance), a key-value store for the mapping (Redis for hot paths, a relational DB for durability), and a redirect service. Discuss read vs. write ratio (reads dominate heavily), TTL for expiring links, custom alias support, and analytics (what to count, where to store counts without making the redirect path slow).

One of the most consistently reported design problems at Google L4 and L5. Google interviewers want the trade-off discussion, not just the architecture diagram. "Why base62 over MD5?" and "how do you handle hash collisions?" are expected follow-ups. Reported from multiple candidate write-ups covering 2024-2025 onsites.

Token bucket and sliding window log are the two algorithms worth knowing cold. Token bucket is simpler and works well for bursty traffic; sliding window log is more accurate but higher memory cost. For a distributed rate limiter, the counter must live in a shared store (Redis with atomic increment and TTL). Discuss consistency trade-offs: a local in-process counter is fastest but allows rate-limit bypass across instances; centralized Redis is accurate but adds a network round-trip to every request.

Reported from L4 onsites in 2025 and confirmed as a standard Google system design problem across multiple preparation guides. The interviewer specifically wants to hear you discuss the distributed case, not just the single-server version.

Model the domain with classes: a ParkingLot containing multiple Levels, each Level containing Spots sized for different vehicle types, a Vehicle hierarchy, and a Ticket issued on entry that gets reconciled against a pricing rule on exit. A strategy pattern for spot assignment (nearest available spot, or size-matched spot) keeps the allocation rule swappable without touching the rest of the system.

Reported from a handful of 2024-2025 phone screens as an alternative to a pure algorithm question, more common on teams building internal tooling rather than consumer-facing products. Interviewers care about where state lives and how the classes talk to each other, not the diagram itself, one candidate reported being asked "what happens if two cars arrive at the exact same instant for the last spot?" specifically to see how far the class boundaries had been thought through.

Consistent hashing is the core decision: it shards keys across nodes so that adding or removing a single node only reshuffles a small fraction of the total keys, instead of remapping everything the way a naive modulo-based hash would. Beyond that, discuss per-node LRU eviction, a replication factor for availability when a node fails, and whether writes go through the cache synchronously (write-through) or get flushed later (write-behind), depending on how much staleness the system can tolerate.

Reported from L4-adjacent design conversations in 2025. Interviewers reportedly treat "consistent hashing" as a named concept you either bring up unprompted or don't; candidates who describe the same idea in vaguer terms ("we spread the keys across servers evenly") get a noticeably weaker signal for the same underlying answer.