Google Backend Developer Interview Preparation Guide (Entry Level)

Direct answer

Scan the expression once left to right, accumulating the current number and, on hitting an operator (or the string's end), resolving the previous operator against a value stack rather than a running total directly. Addition and subtraction push a signed value onto the stack to be settled later; multiplication and division pop the stack's top, combine it with the current number immediately, and push the result back, because those two operators must bind tighter than whatever addition or subtraction comes before or after them. The stack is what lets the scan defer every addition and subtraction until the very end, once every higher-precedence operation touching a given operand has already been folded in, summing the stack at that point gives the correct, precedence-respecting result.

Structured elaboration

Why a single accumulator is not enough

Evaluating left to right with one running total works for pure addition and subtraction, but multiplication and division must apply to their immediate neighbors before anything else touches those values. A single accumulator has no way to "undo" a value it already folded into the total in order to multiply it by something appearing later.

What the stack defers, specifically

Each time a complete number is read, look at the operator that preceded it:

• +: push the number as-is; it will be added in at the end.
• -: push the number negated; subtraction is addition of a negative.
• * or /: pop the stack's current top, combine with the new number right now, and push the combined result back, this is what "deferring lower-precedence operations" really means in reverse: it is addition and subtraction that get deferred, while multiplication and division are resolved immediately because their operands are already fully known.
  At the very end, summing the whole stack applies every deferred addition and subtraction in one shot, correctly, because every *// touching any of those values has already been folded in before it ever reached the stack.

Handling division sign and formatting

Division must truncate toward zero (not Python's default floor division, which rounds toward negative infinity for negative operands), so int(a / b) rather than a // b is used to match the conventional integer-arithmetic contract.

Worked example

def calculate(s: str) -> int:
    s = s.strip()
    stack = []
    num = 0
    op = '+'
    n = len(s)
    for i, ch in enumerate(s):
        if ch.isdigit():
            num = num * 10 + int(ch)
        if (not ch.isdigit() and ch != ' ') or i == n - 1:
            if op == '+':
                stack.append(num)
            elif op == '-':
                stack.append(-num)
            elif op == '*':
                stack.append(stack.pop() * num)
            elif op == '/':
                prev = stack.pop()
                stack.append(int(prev / num))
            op = ch
            num = 0
    return sum(stack)

print(calculate("3+2*2"))
print(calculate(" 3/2 "))
print(calculate(" 3+5 / 2 "))
print(calculate("14-3/2"))
print(calculate("1*2-3/4+5*6-7*8+9/10"))

This prints:

7
1
5
13
-24

Tracing "3+2*2": read 3, hit +, push 3 (stack [3]), op becomes +. Read 2, hit *, push 2 (stack [3, 2]), op becomes *. Read the final 2 (end of string triggers resolution with op = '*'): pop 2, multiply by the new 2, push 4 (stack [3, 4]). Sum is 7, matching the printed output. "14-3/2" similarly resolves 3/2 to 1 via truncating division before the pending subtraction is ever applied, giving 14 - 1 = 13.

Key points

• The stack holds fully-resolved, precedence-correct terms; the final sum() is the only place addition and subtraction actually happen across terms.
• * and / never get their own stack entries, they immediately combine with whatever the stack's top already holds.
• Multi-digit numbers accumulate via num = num * 10 + int(ch) before any operator triggers resolution.

Complexity

Time: $O(n)$, a single pass over the string. Space: $O(n)$ in the worst case for the stack (an expression that is entirely additions and subtractions of single terms pushes one entry per term), though it can be reduced to $O(1)$ extra space by tracking only the running total and the most recent term instead of a full stack, at the cost of a less direct mapping to "what the stack is doing" pedagogically.

Edge cases

• Leading, trailing, or embedded spaces: skipped by the ch != ' ' check, which does not trigger a resolution and does not get added into the accumulating number.
• Multi-digit numbers: accumulated digit by digit before any operator resolves them.
• Expression ending exactly on a number (no trailing operator): the i == n - 1 condition forces one final resolution using whatever operator preceded that last number.
• Division truncating toward zero for negative results: using int(prev / num) rather than prev // num avoids Python's floor-toward-negative-infinity behavior on mixed-sign division.

Trade-offs & pitfalls

The most common bug is using // for division and getting a different (floored, not truncated) result on negative operands; int(a / b) sidesteps this by truncating through the int() conversion itself. A frequent design question is whether to extend this to full recursive-descent parsing to support parentheses and unary operators (Basic Calculator III-style): the single-pass stack approach generalizes naturally to nested parentheses by recursing into a sub-expression whenever ( is seen and returning the sub-result to the outer scan, whereas true operator-precedence parsing with a formal grammar is a more general (and more code-heavy) solution better suited to expressions with many operator types or user-defined precedence rules.

Approach (brief)
Find the midpoint with fast/slow pointers, reverse the second half in-place, compare nodes pairwise, then restore the reversed half to original order. O(n) time, O(1) extra space, no allocations.

Code

// Definition
struct ListNode {
    char val;
    ListNode* next;
    ListNode(char x): val(x), next(nullptr) {}
};

bool isPalindrome(ListNode* head) {
    if (!head || !head->next) return true;

    // find midpoint (slow at start of second half for even, middle+1 for odd)
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    // for odd length, skip the middle node
    if (fast) slow = slow->next;

    // reverse second half
    ListNode *prev = nullptr, *cur = slow;
    while (cur) {
        ListNode* nxt = cur->next;
        cur->next = prev;
        prev = cur;
        cur = nxt;
    }
    // prev is head of reversed second half
    ListNode *p1 = head, *p2 = prev;
    bool ok = true;
    while (p2) {
        if (p1->val != p2->val) { ok = false; break; }
        p1 = p1->next; p2 = p2->next;
    }

    // restore second half by reversing prev again
    cur = prev; prev = nullptr;
    while (cur) {
        ListNode* nxt = cur->next;
        cur->next = prev;
        prev = cur;
        cur = nxt;
    }
    // reconnect: if fast was null (even) slow started at first node of second half
    // if fast non-null (odd) slow had been advanced one extra, reconnection handled implicitly

    return ok;
}

Explanation & safety

• No allocations or external containers used.
• Handles odd/even lengths: when fast != nullptr after loop, list length is odd and we advanced slow past middle.
• Restoration reverses the modified segment back so original list is preserved.
• Time O(n), space O(1). Edge cases: empty, single node, two nodes, all same chars.

Direct answer

CAP theorem (Consistency, Availability, Partition tolerance) says that when a distributed system's network partitions, some nodes cannot talk to others, you must choose between staying available (keep answering requests) or staying consistent (guarantee every reader sees the latest write); you cannot fully guarantee both during that partition. For a product manager, the useful frame is not the three-letter acronym, it is the trade-off it forces: during a network problem, do we serve possibly-stale data, or do we go silent until we're sure the data is correct? Two analogies below make that concrete, plus where each one starts to mislead.

How to build and stress-test an analogy like this

• Start from something the audience already manages themselves so the coordination problem is intuitive without teaching new vocabulary.
• Map only the DECISION the concept forces (here, what happens when parts can't talk), not every mechanism. If you find yourself trying to represent quorum writes or version numbers in the analogy, you've picked the wrong analogy or gone too deep.
• Stress-test it before using it: ask yourself what a sharp follow-up question would reveal is wrong with it. If it has no honest breaking point, you haven't tested it hard enough, you've only used it once.
• Name the breaking point out loud, before they find it. That's the senior move: it turns a limitation into evidence you understand the real system, instead of a gotcha that undermines the analogy later.
• The same loop, familiar system, one decision, explicit breaking point, works for any concept in this family: explaining algorithmic complexity (Big-O) to a PM, a model's bias/variance trade-off to a stakeholder, why a prediction leans on certain inputs (SHAP values), or why Raft consensus needs a leader election before it can make progress.

Worked example

Analogy 1: bank branches during a network outage. A bank has several branches connected by a private network. A customer withdraws money at Branch A. If the network to Branch B is up, Branch B's ledger updates immediately, every branch shows the correct new balance (Consistency). If a cable gets cut between the branches (a partition), Branch B has two choices: let customers keep withdrawing using its last-known balance (Availability, but the balance might be wrong), or refuse withdrawals until the network is fixed and balances can be confirmed (Consistency, but Branch B is unavailable). What it captures well: the forced, binary choice under a partition, and that it's a business decision, not a bug to fix. Where it breaks: real banks resolve most of this with human reconciliation and legal recourse, an incorrect balance gets corrected by staff, with clear liability rules. Distributed databases usually make this choice automatically, in milliseconds, with no human in the loop, so the "someone will sort it out later" comfort the analogy implies isn't actually available.

Analogy 2: two people, one shared paper shopping list, two different stores. You and a partner keep a shared shopping list at home but each take a photo before heading to a different grocery store. While your phones have signal, any item one of you crosses off can be relayed to the other, so the list stays in sync (Consistency). If both phones lose signal at once (a partition), you each keep shopping off your own photo, you stay productive (Availability), but you risk both buying milk, or neither of you buying it, because neither photo reflects the other's crossed-off items. What it captures well: a partition doesn't stop work, it stops coordination, and the resulting inconsistency is a direct, visible consequence of choosing to stay available. Where it breaks: reconciling two shopping lists is cheap and forgiving, worst case you return the extra milk. Reconciling two halves of a financial ledger or an inventory count is not cheap or forgiving in the same way, so the analogy understates how expensive real clean-up can be.

Trade-offs and pitfalls

Don't let either analogy imply CAP is a permanent, top-level architecture choice; it applies at the moment of a partition, and most systems are both consistent and available the rest of the time. That's the single most common misunderstanding a PM walks away with if you aren't explicit about it. Also resist collapsing CAP into "consistency vs speed," that conflates it with the separate latency/consistency trade-offs many systems make even without a partition. And don't use the analogy to make the decision for the PM, the job here is to make the trade-off legible so they can weigh it against the product's actual tolerance for stale data.

Direct answer. REST is defined by six architectural constraints, and each one is a deliberate trade-off, not a style preference: client-server separation, statelessness, cacheability, a uniform interface, a layered system, and optionally code-on-demand. An API that violates one of these is not automatically wrong, but you should know exactly which constraint you are giving up and why.

What each constraint buys you.

• Client-server separation: the client (mobile app, browser, partner integration) and the server evolve independently as long as the contract holds. You can rewrite your entire backend in a different language and, if the HTTP contract is unchanged, no client needs to know.
• Statelessness: every request carries everything the server needs to process it (auth token, pagination cursor, filters). The server holds no memory of "where the client is" between requests. This is what lets you put ten identical server instances behind a load balancer and route any request to any of them, and what lets you kill an unhealthy instance mid-traffic without special draining logic for in-flight conversations.
• Cacheability: responses declare whether they can be cached (Cache-Control, ETag), so a client, a CDN, or a shared proxy can serve a repeat request without hitting your origin at all. A read-heavy public GET endpoint that never says anything about caching is leaving free capacity on the table.
• Uniform interface: the same small vocabulary (a handful of HTTP methods, resource-shaped URIs, standard status codes) works for every resource in the system. A client that understands GET/POST/PUT/DELETE for one resource already understands them for a resource it has never seen.
• Layered system: a client cannot tell, and should not need to know, whether it is talking directly to your application server or to a gateway, a cache, or a load balancer in front of it. This is what lets you insert a CDN or an API gateway later without changing a single client.
• Code on demand (optional): the server can ship executable logic to the client (classically, JavaScript). Rarely invoked as a REST constraint in practice; most APIs simply do not use it.

Worked example. Say you have a GET /products/{id} endpoint. Statelessness means the request needs the product id and nothing else, no "current product" server-side session. Cacheability means the response can carry Cache-Control: public, max-age=60 and an ETag, so a CDN answers the next thousand identical requests without your database seeing them. Layering means you can put that CDN in front of the origin tomorrow without touching the endpoint's code, because the client was never coupled to the fact that it originally talked directly to your application server.

Trade-offs and pitfalls. The most common mistake is quietly violating statelessness: storing "the user's current search" or "step 2 of a wizard" in a server-side session tied to a sticky connection. It works until you scale horizontally or need to fail an instance over, at which point in-flight state is silently lost. The second common mistake is treating cacheability as an afterthought (an endpoint returns Cache-Control: no-store by default and nobody revisits it), which caps your ceiling on read throughput far below what the constraint would otherwise buy you for free. Code-on-demand is the constraint most real systems simply skip, and that is fine: REST does not require using every constraint, it requires knowing what each one costs you when you drop it.

Direct answer

Build a standing information diet from what the partner function already produces for itself, its goals or planning document, the metrics it is measured on, and its retro or release notes, and pair that with a recurring informal check-in with one counterpart in that function. You are not trying to get invited into their planning meeting; you are trying to read what they optimize for, and occasionally confirm your read against a real person.

Structured elaboration

The habit that ties these together: translate their metric into one sentence you could say back to them and have them agree it is accurate, then test that sentence the next time you talk. If you cannot state their current priority in a sentence they would sign off on, your information diet has a gap.

Worked example

Suppose you regularly partner with a support or customer-success function but are not in their planning. Their quarterly goals page (a document they publish for their own team) states the goal is "reduce median response time." Reading that before proposing a change that would meaningfully increase inbound volume lets you flag the likely trade-off to your counterpart ahead of launch, rather than finding out after the fact that you worked against their stated goal. The artifact told you what they were measured on; the counterpart conversation confirmed it was still current.

Trade-offs & pitfalls

• Relying only on artifacts risks reading a goal that is stale or aspirational and no longer reflects what the team is actually prioritizing day to day.
• Relying only on a single counterpart's opinion risks mistaking one person's take for the function's actual priority, especially if that person is not close to how the team's metrics are reviewed.
• A common miss: reading the dashboard but never validating the interpretation with anyone in that function, which produces confidently wrong assumptions that only surface when a decision already went the wrong way.
• The senior differentiator on an easy-sounding question like this is treating it as a standing habit built before you need it, rather than something you scramble to learn only after a conflict has already surfaced.

Direct answer

Walk through long once with a single pointer, and advance a second pointer into short only when the current character of long matches the character short is currently waiting for. If the pointer into short reaches the end before long runs out, every character of short was found in order, so short is a subsequence of long.

Structured elaboration

Approach

def is_subsequence(short, long):
    i = 0
    if not short:
        return True
    for ch in long:
        if i < len(short) and ch == short[i]:
            i += 1
        if i == len(short):
            return True
    return i == len(short)

Only one pass over long is made, and the pointer into short never moves backward, so the total work is O(n) where n is the length of long, matching the question's explicit complexity requirement. No extra data structure is needed since matching only ever needs to compare the CURRENT position of short against the current character of long.

Application context (the question's explicit ask)

This same one-pass check is the building block behind approximate matching and fuzzy token mapping: for example, checking whether a user's typed abbreviation could plausibly expand to a longer canonical term ("gcm" as a subsequence of "google cloud monitoring"), or filtering a large candidate list down to the ones that could still match a partially typed query, before applying a more expensive scoring step only to that smaller candidate set.

Worked example

Executed with python3 s83.py, five pinned cases including two explicit edge cases (empty short, empty long):

is_subsequence('abc', 'ahbgdc')     = True  expected=True  match=True
is_subsequence('axc', 'ahbgdc')     = False expected=False match=True
is_subsequence('', 'anything')      = True  expected=True  match=True
is_subsequence('abc', '')           = False expected=False match=True
is_subsequence('ace', 'abcde')      = True  expected=True  match=True

'abc' is found in order inside 'ahbgdc' (a, then b, then c, each appearing later than the last), so it returns True. 'axc' fails because after matching 'a', no 'x' appears anywhere later in 'ahbgdc', so the pointer into short never reaches the end.

Trade-offs and pitfalls

• The empty-short-is-always-a-subsequence edge case (is_subsequence('', 'anything') returning True) is easy to get backwards if the loop logic is written slightly differently; the explicit if not short: return True guard above makes this an intentional decision rather than an accident of how the loop happens to terminate.
• If this check needs to run many times against the SAME long string with many different short candidates, a smarter structure (precomputing, for each position and character, the next occurrence of that character) avoids repeating the full O(n) scan per query, at the cost of O(n * alphabet size) preprocessing; that preprocessing trade is only worth it when the number of queries against the same long string is large.
• This only answers yes/no. If the caller also needs the actual matched positions in long (for example, to highlight which characters satisfied the match), track and return the index list as the pointer advances, rather than just the boolean.

Design

The scaling decision needs one formula that converts three inputs, queue depth, per-consumer throughput, and target drain time, into a target replica count, plus a floor and a re-evaluation cadence so it keeps adjusting as those inputs change.

Formula

desired_replicas = ceil( queue_depth / (per_consumer_rate * target_drain_seconds) )

Intuition: per_consumer_rate times target_drain_seconds is how many messages one consumer can clear within the time budget you are willing to allow. Dividing the current backlog by that number gives the number of consumers, working in parallel, needed to clear the whole backlog within that same budget. The ceiling rounds up because a fractional consumer cannot exist.

Worked example

Given queue depth 10,000 messages, average processing rate 50 messages per second per consumer, and desired latency under 60 seconds:

desired_replicas = ceil(10,000 / (50 * 60))
                  = ceil(10,000 / 3,000)
                  = ceil(3.33)
                  = 4

Checking the result: with 4 consumers running in parallel, actual drain time is 10,000 / (4 * 50) = 50 seconds, comfortably under the 60-second target.

Refinements for a real deployment

• Recompute per_consumer_rate from a rolling window of actual completions rather than a fixed assumed constant, since real throughput drifts with message-size mix, downstream latency, and resource contention.
• If the queue is still actively receiving messages during the drain window, add expected arrivals to the numerator: desired_replicas = ceil((queue_depth + expected_arrivals_during_drain) / (per_consumer_rate * target_drain_seconds)), otherwise the formula only accounts for draining the existing backlog and can undershoot.
• Add a minimum-replica floor so the fleet does not scale to zero if the queue can receive a message at any moment, unless scale-to-zero with its cold-start delay is an explicit design goal.
• Re-evaluate on a short interval, 10 to 30 seconds, so replica count tracks a changing backlog quickly, paired with an asymmetric cooldown, faster scale-out and slower scale-in, to avoid flapping.

I’d treat this as both a debugging and a reliability issue.

Debugging

• Confirm the failure mode from logs and crash dumps: stack overflow, recursion depth exceeded, or container OOM.
• Reproduce with a deep left- or right-skewed tree and measure max depth.
• Inspect the traversal path to verify it is purely recursive and not tail-call optimized in Python or the runtime.

Immediate mitigation

• Add a request-level guard: reject trees over a safe depth or node count.
• Roll back or disable the endpoint if needed.
• Hotfix the traversal to an iterative stack-based version to remove recursion risk.

Long-term redesign

• Replace recursive DFS with iterative traversal using an explicit stack.
• Validate inputs at the edge: depth, node count, and cycle checks if the structure is user-provided.
• Add fuzz tests and adversarial cases in CI.
• Instrument metrics for depth distribution, traversal latency, and rejection counts.

For a backend service, I’d also add a circuit breaker around expensive tree operations and document a hard contract for maximum allowed depth. The key lesson is that recursion is fine for trusted, shallow data, but production services need predictable memory usage under worst-case inputs.

Direct answer

A lock-free hash table replaces mutexes with atomic compare-and-swap (CAS) operations on individual pointers or slots, so a thread that loses a race simply retries instead of ever blocking. That freedom brings two hard problems: safely freeing memory a reader might still be traversing, and resizing without a stop-the-world pause, both of which sharded locking sidesteps by simply accepting that one shard's lock holder can occasionally stall everyone else waiting on that same shard.

Structured elaboration

Non-blocking insert and lookup. Represent each bucket as a chain of nodes linked by atomic pointers. Insert performs a CAS on the relevant pointer (the bucket head, or a node's next pointer) to splice in a new node, and if the CAS fails because another thread's concurrent insert won first, the thread simply retries the CAS immediately, it is never suspended waiting on another thread. Lookup only follows pointers and never mutates anything, so it needs no synchronization at all beyond the atomic pointer reads themselves, which is why lookups are truly non-blocking.

Safe memory reclamation. The central hazard is freeing a node another thread is still mid-traversal on. Two standard techniques: hazard pointers, where each thread publishes, in a small shared per-thread slot, which node pointer it is currently about to dereference before it dereferences it; a thread that wants to free a removed node first scans all published hazard pointers and only frees the memory once no other thread has that node marked, otherwise it defers the free onto a retire list and rechecks later. Or epoch-based reclamation, where each thread announces a monotonically increasing global epoch counter value when it begins an operation, and memory removed during epoch E is only actually freed once every thread has advanced past epoch E, meaning nobody can still hold a reference into that stale epoch. Epoch-based reclamation is usually cheaper (an integer read/write versus scanning a hazard array) but reclaims memory less promptly, since one slow or stalled thread delays reclamation for every removed node, not just the ones it happens to touch.

Concurrent resizing. Allocate the new, larger table and migrate buckets from old to new incrementally, using a CAS-based per-bucket migration marker so that any thread, reader, writer, or an idle helper, that touches a not-yet-migrated bucket can help finish moving it (a common lock-free "helping" pattern that avoids any single thread becoming a resize bottleneck). Readers mid-transition either check both tables or follow a forwarding pointer left behind in a migrated bucket, so no key is ever lost or briefly duplicated.

Worked example

Compare the two designs directly:

For a service where even brief lock contention is unacceptable, this table is the actual argument for the added complexity: sharded locking still has a genuine worst-case blocking path (a popular shard, or a preempted lock holder), while the lock-free design guarantees every OTHER thread keeps making progress regardless of what one thread is doing.

Trade-offs and pitfalls

Be precise about the guarantee: lock-free means the system as a whole always makes progress, it does not mean any one specific thread is guaranteed to finish in bounded time (a thread could in principle retry indefinitely while others keep winning the race); that stronger, per-thread guarantee is called wait-free and costs considerably more to implement. The reclamation and resizing logic are also where the real engineering cost lives: hazard-pointer scans add a real per-operation cost, epoch-based schemes can leak memory indefinitely if a single thread stalls inside an old epoch and never advances, and resize-helping code is exactly the kind of rare-interleaving logic that passes ordinary tests and fails only under real production concurrency.

Approach (brief)
Use dynamic programming with a 1D array of length n (columns). dp[j] = number of ways to reach current cell in column j for the current row. If a cell is blocked set dp[j]=0. Initialize dp[0]=1 if start not blocked. This yields O(m*n) time and O(n) space.

Node.js implementation

// grid is array of m rows, each row is array of n booleans: false = free, true = blocked
function uniquePathsWithObstacles(grid) {
  const m = grid.length;
  if (m === 0) return 0;
  const n = grid[0].length;
  const dp = new Array(n).fill(0);
  dp[0] = grid[0][0] ? 0 : 1; // start

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j]) {
        dp[j] = 0; // blocked
      } else if (j > 0) {
        dp[j] += dp[j - 1]; // from left + top (dp[j] still holds top)
      }
    }
  }
  return dp[n - 1];
}

Complexity

• Time: O(m * n)
• Space: O(n)

Handling very large grids with sparse obstacles

• Treat the large dimension as rows or columns; iterate over the smaller dimension.
• Represent obstacles sparsely: map rowIndex -> sorted array/set of blocked columns. For each row, only update dp at columns that are reachable or blocked; use interval propagation: between blocked columns you can compute prefix sums.
• Use a sparse hashmap for dp (col -> ways) when n is huge but few reachable columns per row. Update only keys that change.
• For extremely large empty regions, use combinatorics (binomial coefficients) to jump across obstacle-free rectangles; precompute factorials with big integers/modulo if needed.

Edge cases

• Start or end blocked => 0
• Single row/column handled naturally
• Consider big-integer or modulo if path counts can overflow.