Google Backend Developer Interview Preparation Guide (Entry Level)
Google's backend developer interview process for entry-level candidates consists of an initial recruiter screening, followed by 1-2 technical phone screens focusing on coding and algorithms, and an onsite loop of 4-5 rounds that assess coding proficiency, foundational system design thinking, and cultural fit. The entire process evaluates your ability to solve problems under time pressure, write clean production-quality code, understand basic architectural concepts, and demonstrate Google's core values of intellectual curiosity and collaboration.
Interview Rounds
Recruiter Screening
What to Expect
Your initial conversation with a Google recruiter to assess your background, experience, motivation for joining Google, and overall fit. This round also includes a follow-up call after your technical assessments to discuss results and next steps. The recruiter will verify your education, work history, and visa sponsorship needs if applicable. They'll explain the interview process, answer your questions about the role and team, and gauge your genuine interest in backend development at Google.
Tips & Advice
Be genuine and enthusiastic about backend development and Google's mission. Research Google's products and infrastructure (e.g., Google Cloud Platform, Bigtable, Spanner) to show you understand what Google builds. Clearly articulate why you're interested in backend development specifically. Have thoughtful questions about the team, technology stack, and growth opportunities. For entry-level candidates, the recruiter focuses on potential and learning ability rather than years of experience. Mention any relevant coursework, personal projects, or internships that demonstrate backend skills.
Focus Topics
Understanding the Role and Interview Process
Learn what backend developers do at Google, the technologies they use, and what the interview process entails. Ask clarifying questions about the role, team structure, and expectations.
Practice Interview
Study Questions
Communication and Professionalism
Speak clearly, maintain a professional tone, make eye contact (if video), and listen actively to the recruiter's questions.
Practice Interview
Study Questions
Motivation for Backend Development and Google
Articulate genuine reasons for pursuing backend development and specifically why Google appeals to you. Research Google's infrastructure, services, and engineering culture.
Practice Interview
Study Questions
Background and Experience Overview
Prepare a clear 2-3 minute summary of your education, internships, and any relevant projects. Highlight backend-focused work even if limited.
Practice Interview
Study Questions
Technical Phone Screen 1: Coding and Algorithms
What to Expect
A live coding assessment typically conducted on a shared Google Doc or dedicated coding platform. You'll be given 1-2 algorithmic problems to solve in 45-60 minutes. The interviewer will observe your problem-solving approach, code quality, and ability to explain your logic. For entry-level candidates, expect medium-difficulty problems involving arrays, strings, linked lists, or basic graph traversal—nothing requiring advanced algorithms. The focus is on correctness, clean code, and your communication during the process.
Tips & Advice
Start by asking clarifying questions about the problem constraints and edge cases—this shows thoroughness. Think out loud and explain your approach before coding; don't jump into implementation. Write clean, readable code with meaningful variable names. Test your solution mentally with sample inputs. If you get stuck, communicate what you're thinking and ask for hints if needed; partial solutions are better than no solution. Avoid common mistakes like off-by-one errors, not handling null/empty inputs, or forgetting to return results. After writing code, walk the interviewer through your solution and discuss time/space complexity. Optimize if time permits, but a correct brute-force solution is better than an optimized incorrect one.
Focus Topics
Basic Recursion and Backtracking
Solve simple recursive problems, understand base cases and recursive relations. Practice problems like factorial, fibonacci, and basic tree traversals.
Practice Interview
Study Questions
Complexity Analysis (Time and Space)
Identify and articulate the Big O time and space complexity of your solutions. Understand why complexity matters in production systems.
Practice Interview
Study Questions
Code Quality and Communication
Write clean code with descriptive variable names, proper error handling, and comments where necessary. Explain your thought process as you code.
Practice Interview
Study Questions
Linked Lists
Implement and manipulate singly and doubly linked lists. Practice reverse, merge, cycle detection, and nth element problems.
Practice Interview
Study Questions
Hash Maps and Sets
Use hash tables for fast lookups and frequency counting. Understand collisions, load factors, and when to prefer sets over lists.
Practice Interview
Study Questions
Arrays and Strings Manipulation
Master common operations: searching, sorting, reversing, subarray problems, two-pointer techniques, sliding window. Understand time/space trade-offs.
Practice Interview
Study Questions
Technical Phone Screen 2: Coding and Problem Solving
What to Expect
Similar format to Phone Screen 1 but may involve a different problem category or variant. You could face another pure algorithmic problem, or a problem with a slight backend-flavored twist such as parsing data, designing a simple data structure, or implementing a rate limiter algorithm. The goal is to further assess your problem-solving consistency, adaptability, and coding skills under time pressure.
Tips & Advice
Apply the same strategies as Phone Screen 1: clarify requirements, think aloud, code cleanly, test mentally, optimize if time allows. If this problem has a backend angle (e.g., implementing a cache or queue), focus on the data structure choices and explain why you're using specific approaches. If you solved a similar problem in your preparation, avoid copy-pasting your solution—adapt and think through it fresh. The interviewer is assessing whether you can solve different types of problems, not whether you've memorized solutions. Handle mistakes gracefully; if your first approach doesn't work, pivot clearly and try a new strategy.
Focus Topics
Sorting and Searching
Implement or use efficient sorting (mergesort, quicksort) and searching (binary search). Understand stability and in-place sorting.
Practice Interview
Study Questions
Basic Graph Problems
Implement DFS and BFS. Solve simple problems like finding connected components, detecting cycles, and topological sorting (basic).
Practice Interview
Study Questions
Handling Edge Cases and Error Conditions
Identify and handle edge cases: empty inputs, single elements, large inputs, negative numbers, duplicates. Think about error handling in your code.
Practice Interview
Study Questions
Problem-Solving Consistency and Adaptability
Demonstrate consistent approach to different problem types: understand → plan → implement → test → optimize. Adapt your strategy if the first approach doesn't work.
Practice Interview
Study Questions
Stacks and Queues
Implement and use stacks for LIFO and queues for FIFO scenarios. Understand use cases like parsing (balanced parentheses), LRU caches, and task scheduling.
Practice Interview
Study Questions
Trees and Binary Search Trees
Understand tree properties, traversals (in-order, pre-order, post-order), and basic BST operations. Practice level-order traversal and lowest common ancestor problems.
Practice Interview
Study Questions
Onsite Technical Interview 1: Advanced Coding
What to Expect
Part of the onsite loop, this round is another coding assessment focused on slightly more complex problems or requiring multiple passes (e.g., optimize a brute-force solution). You may need to implement a more complete solution or face a problem with multiple parts. The interviewer evaluates coding quality, problem-solving depth, and your ability to think about multiple approaches. For entry-level candidates, this is still fundamentals-focused but expects polished, production-ready code.
Tips & Advice
On-site rounds tend to be slightly more rigorous than phone screens because you're in person and Google is getting closer to a decision. Focus on code quality even more—readable variable names, proper spacing, comments where helpful. If asked to optimize, don't settle for the first working solution; think about improvements. The interviewer may interrupt with follow-up questions or constraint changes; adapt smoothly. If you're unsure about edge cases, ask the interviewer—this shows thoughtfulness. Maintain a steady pace; don't rush coding but also don't get stuck. If you reach an impasse, ask for a hint or pivot to a different approach.
Focus Topics
String Processing and Parsing
Work with string matching, substring problems, parsing structured text, and regex basics. Understand algorithms like KMP (can mention but not required to implement).
Practice Interview
Study Questions
Designing Simple Data Structures
Implement or design simple data structures like LRU Cache, LFU Cache, or a simple LinkedHashMap. Understand trade-offs between operations.
Practice Interview
Study Questions
Dynamic Programming Fundamentals
Understand the concept of overlapping subproblems and optimal substructure. Solve basic DP problems like Fibonacci, coin change, and simple knapsack.
Practice Interview
Study Questions
Code Optimization and Refactoring
Take a working brute-force solution and improve it. Reduce time/space complexity, improve readability, consider practical constraints.
Practice Interview
Study Questions
Testing and Edge Case Validation
Mentally test your code with various inputs: normal cases, edge cases (empty, single item, large), boundary conditions. Walk through test cases.
Practice Interview
Study Questions
Onsite Technical Interview 2: System Design Fundamentals
What to Expect
An introductory system design round tailored for entry-level candidates. Rather than designing a complex distributed system, you'll be asked to think about basic architectural decisions for a simplified backend service. For example: 'Design a simple URL shortener' or 'Design a basic notification system.' The focus is on understanding when to use databases vs caches, basic API design, and simple scalability thinking. You're expected to ask clarifying questions, propose a basic architecture, and discuss trade-offs at a high level. This round assesses your ability to think beyond just coding.
Tips & Advice
Start by asking clarifying questions about scale, users, features, and constraints before proposing a design. Don't over-engineer; a simple, correct design is better than a complex one at entry level. Think about: API endpoints, database choice (SQL vs NoSQL), caching strategies, and maybe simple load balancing. Draw boxes and lines on the whiteboard or document—visuals help communication. Discuss trade-offs: why SQL over NoSQL, when to cache, trade-offs between consistency and availability (no need for formal CAP theorem at entry level, just intuition). If asked about scaling, explain basic concepts like database replication or adding more servers without complex distributed consensus. Be honest about limitations: 'I haven't done this in production, but I would consider...' shows maturity. Listen to interviewer hints and adjust your design accordingly.
Focus Topics
Asynchronous Processing and Message Queues
Understand why some tasks should be async (e.g., sending emails, generating reports). Know that message queues (Kafka, RabbitMQ) decouple producers and consumers.
Practice Interview
Study Questions
Basic Load Balancing and Horizontal Scaling
Understand that adding more servers can increase capacity. Know that load balancers distribute traffic. No need for complex algorithms—just concepts.
Practice Interview
Study Questions
Caching Strategies and Cache Invalidation
Understand why caching improves performance. Know about in-memory caches (Redis), browser caches, and basic invalidation strategies (TTL, LRU).
Practice Interview
Study Questions
Communication and Whiteboarding
Clearly explain your design choices. Draw architecture diagrams. Discuss trade-offs thoughtfully. Ask clarifying questions. Listen to feedback.
Practice Interview
Study Questions
Relational vs NoSQL Database Trade-offs
Understand basic differences between SQL (PostgreSQL, MySQL) and NoSQL (MongoDB, DynamoDB). When to use each: SQL for structured data with relationships, NoSQL for flexible schemas and scale.
Practice Interview
Study Questions
REST API Design Fundamentals
Design clean REST APIs with proper resource naming, HTTP methods, status codes. Understand idempotency and stateless design basics.
Practice Interview
Study Questions
Onsite Behavioral Interview: Googleyness and Culture Fit
What to Expect
A behavioral assessment focused on Google's core values and how you work in teams. The interviewer will ask about your past experiences, challenges you've overcome, teamwork, learning from failures, and motivation. Questions like 'Tell me about a time you disagreed with a teammate,' 'Describe a challenging project you worked on,' or 'How do you approach learning new technologies' are typical. For entry-level candidates, interviewers are assessing your ability to grow, collaborate, and embody Google's values of intellectual honesty, ownership, and user-focus.
Tips & Advice
Prepare 3-5 stories from your academic projects, internships, or personal work that demonstrate Google's values. Use the STAR method (Situation, Task, Action, Result) to structure answers. Focus on: learning from mistakes, collaborating effectively, taking initiative, and user-centric thinking. Be specific with details and outcomes; vague stories are unconvincing. For entry-level candidates, frame stories around learning and growth ('I didn't know this initially, but I learned...') rather than heroic solo achievements. Be authentic; Google values genuine passion, not rehearsed corporate speak. Listen carefully to each question and answer what's asked. Ask thoughtful questions about Google's team and culture to show genuine interest. Mention specific Google products or services you use and why you respect them.
Focus Topics
User-Centric Thinking
Discuss projects where you focused on user needs and impact. Show understanding that code serves users, not just technical elegance.
Practice Interview
Study Questions
Ownership and Initiative
Demonstrate taking responsibility for projects or problems, going beyond the basics, and seeing things through to completion. Show proactive problem-solving.
Practice Interview
Study Questions
Learning Agility and Growth Mindset
Describe situations where you learned new technologies, skills, or domains quickly. Show how you approach unfamiliar challenges with curiosity.
Practice Interview
Study Questions
Google's Core Values: Intellectual Honesty and Transparency
Demonstrate ability to share honest opinions, admit mistakes, and give/receive feedback constructively. Prepare a story showing you challenged an idea respectfully or admitted an error.
Practice Interview
Study Questions
Collaboration and Teamwork
Show examples of working effectively in teams, helping teammates, and contributing to collective success. Discuss how you handle conflicts or different opinions.
Practice Interview
Study Questions
Frequently Asked Backend Developer Interview Questions
Evaluate a string arithmetic expression containing non-negative integers and the four basic operators (with correct precedence), without using a language built-in eval. Explain the role a stack plays in deferring lower-precedence operations until you know the full operand.
Sample Answer
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 - 1condition forces one final resolution using whatever operator preceded that last number. - Division truncating toward zero for negative results: using
int(prev / num)rather thanprev // numavoids 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.
Design graceful degradation strategies for an event-driven notification subsystem when downstream push services (APNs/FCM/email API) are rate-limited or unavailable. Include queueing, prioritization, circuit breakers, fallbacks, retry policies, and how to communicate delays to users and product teams.
Sample Answer
Direct answer
When downstream push providers, the Apple Push Notification service (APNs), Firebase Cloud Messaging (FCM), or an email API, are rate-limited or down, the notification subsystem should queue rather than drop, prioritize what gets sent first, trip a circuit breaker so a struggling provider is not hammered by continued retries, fall back to an alternate channel where one exists, and communicate the delay honestly to both the end user and the team that will get paged about it.
Structured elaboration
| Provider signal | Mechanism | Behavior |
|---|---|---|
| Rate-limited (429 or a backoff header) | Retry with capped exponential backoff and jitter | Requeue with a delay; do not hammer a provider that is telling you to slow down. |
| Sustained failures (a run of consecutive failures) | Circuit breaker opens | Stop sending to that provider for a cooldown window; redirect new sends to queue-and-wait or a fallback channel. |
| Provider fully unavailable | Queue with priority lanes | Critical notifications (security alerts, payment failures) are preserved and retried first once the provider recovers; low-priority notifications (marketing) are shed or deferred longest. |
| Breaker cooldown elapsed (half-open) | Canary a small fraction of traffic | Confirm real recovery before resuming full volume; avoids re-tripping immediately. |
Queueing and prioritization. Tier notifications at publish time (critical/transactional versus informational/marketing), and give the critical tier its own queue or a priority field so degradation sheds the low-priority tier first when the backlog needs to be bounded, the same principle as general backpressure design, tuned here to notification-specific business tiers rather than message size or type.
Circuit breakers. Track failure rate per downstream provider independently, APNs failing does not mean FCM is failing, open the breaker on a sustained failure rate over a short window, and use a half-open state that only lets a small canary volume through before fully reopening the gate. This avoids an immediate re-trip the instant a provider blips back to life.
Fallbacks. Define a real fallback path, not just "retry harder." If push fails and the notification matters, fall back to email (or SMS for the most critical class); if the fallback channel is also degraded, the message stays queued for the original channel with a bounded retry window rather than looping forever.
Retry policy. Capped exponential backoff with jitter, so retries spread out over time instead of synchronizing into a new burst against a provider that is already struggling, and a maximum retry count or time window after which the message moves to a dead-letter queue for manual or delayed reprocessing.
Communicating delays. To end users, this typically means an honest, generic in-app state ("notifications may be delayed") rather than silence, especially for anything the user is actively waiting on. To the product team, it means a dashboard and an alert channel showing current breaker state, queue depth by priority tier, and the estimated time to drain the backlog, so a rate-limit incident is visible as a known, bounded event rather than something someone has to reconstruct from logs afterward.
Worked example
backoff schedule (s):1,2,4,8,16,30capWith a circuit breaker configured to open after 5 consecutive failures within a 60-second window, and a 60-second cooldown before moving to half-open: a sustained APNs outage produces at most 5 failed attempts against the provider, roughly 1+2+4+8+16 = 31 seconds of retry spacing, before the breaker opens and sending stops. From that point, the queue simply holds critical-tier messages for retry once the breaker's half-open canary confirms recovery, rather than continuing to retry against a provider that has already signaled it is down.
Trade-offs and pitfalls
- Retrying without backoff or a circuit breaker turns a provider rate-limit into a self-inflicted denial-of-service against your own outbound traffic, and can get an account or IP range throttled or blocked further.
- Treating all notifications as equally important during degradation means low-value marketing pushes consume the same retry budget as a security alert. Tiering has to exist before the incident, not be improvised during it.
- A fallback channel with no cap of its own can silently overload email, or SMS, which usually carries a real per-message cost, the moment push degrades. Size and rate-limit the fallback too.
- Silence to the user reads as though the notification never happened. Even a generic delay indicator is better than nothing, but overpromising a specific recovery timeline the system cannot guarantee just moves the trust problem downstream.
Evaluate a Reverse Polish Notation expression given as a list of tokens, supporting integers and + - * /. For example ['2','1','+','3','*'] gives 9. Specify how division should truncate and how you handle malformed input.
Sample Answer
The idea in plain words
Reverse Polish Notation (RPN), also called postfix, writes the operator after its two operands: 2 1 + means 2 + 1. Its advantage is that it needs no parentheses and no precedence rules, because the order of the tokens already says what to compute first. A stack (last-in, first-out) evaluates it in one left-to-right pass: a number is pushed; an operator pops the two newest values, computes, and pushes the result back. When the tokens run out, the stack holds exactly one value, the answer.
The detail interviewers watch is operand order. The value popped first is the right operand and the one popped second is the left one. For - and / this matters: 5 2 - is 3, not -3.
The decisions the question asks you to state
- Division truncates toward zero.
-7 / 2is-3. This matches C, C++ and Java integer division (the Java run below confirms it). Python's//is different: it floors (rounds toward minus infinity), so-7 // 2is-4. The code therefore divides absolute values and fixes the sign. - Do not use
int(a / b)for this./produces a float, and floats carry only 53 bits of integer precision (see the explanation below), so large values are silently wrong; the output shows2**53 + 1coming back as...992. - Division by zero is reported as an error rather than crashing with an obscure message.
- Malformed input is reported with a clear error: an operator when fewer than two values are on the stack (
+alone), a token that is neither an integer nor an operator (x), and a finished expression that leaves anything other than exactly one value (1 2, or the empty list). - Negative numbers.
'-7'is a number and'-'is the operator. Testing "is the token in the operator set" first and parsing everything else withintdistinguishes them; testingtoken[0] == '-'would not.
The code
import random
from fractions import Fraction
from math import trunc
OPERATORS = {"+", "-", "*", "/"}
def divide_truncating(a, b):
"""Integer division that rounds toward zero (like C, C++ and Java), not toward minus infinity."""
if b == 0:
raise ZeroDivisionError("division by zero")
quotient = abs(a) // abs(b)
return quotient if (a < 0) == (b < 0) else -quotient
def eval_rpn(tokens, trace=False):
stack = []
for token in tokens:
if token in OPERATORS:
if len(stack) < 2:
raise ValueError(f"operator {token!r} needs two operands, stack has {len(stack)}")
right = stack.pop() # the operand that was pushed last is on the right
left = stack.pop()
if token == "+":
stack.append(left + right)
elif token == "-":
stack.append(left - right)
elif token == "*":
stack.append(left * right)
else:
stack.append(divide_truncating(left, right))
else:
try:
stack.append(int(token)) # accepts '-3' as a number, '-' alone is the operator
except ValueError:
raise ValueError(f"bad token {token!r}") from None
if trace:
print(f" token {token!r:>6}: stack={stack}")
if len(stack) != 1:
raise ValueError(f"expression left {len(stack)} values on the stack")
return stack[0]
def demo():
for tokens in (["2", "1", "+", "3", "*"], ["4", "13", "5", "/", "+"], ["-7", "2", "/"]):
print(tokens)
print(" ->", eval_rpn(tokens, trace=True))
print("floor vs truncate for -7 / 2:", -7 // 2, "vs", divide_truncating(-7, 2))
print("int(a / b) with a = 2**53 + 1, b = 1:", int((2**53 + 1) / 1), "vs", divide_truncating(2**53 + 1, 1))
for bad in (["+"], ["1", "2"], ["1", "0", "/"], ["1", "x", "+"], []):
try:
eval_rpn(bad)
except (ValueError, ZeroDivisionError) as error:
print(f"{bad!r:<16} -> {type(error).__name__}: {error}")
def random_expression(rng, depth):
"""Return (tokens, value) built from a random expression tree, using exact Fractions."""
if depth == 0 or rng.random() < 0.3:
n = rng.randint(-9, 9)
return [str(n)], n
lt, lv = random_expression(rng, depth - 1)
rt, rv = random_expression(rng, depth - 1)
op = rng.choice("+-*/")
if lv is None or rv is None:
v = None # a division by zero inside a subtree poisons the whole expression
elif op == "+":
v = lv + rv
elif op == "-":
v = lv - rv
elif op == "*":
v = lv * rv
else:
v = None if rv == 0 else trunc(Fraction(lv, rv))
return lt + rt + [op], v
def random_check():
rng = random.Random(5)
ok = errors = 0
for _ in range(3000):
tokens, expected = random_expression(rng, 4)
if expected is None:
try:
eval_rpn(tokens)
except ZeroDivisionError:
errors += 1
continue
assert eval_rpn(tokens) == expected
ok += 1
print(f"{ok} valid expressions match an exact-Fraction reference; {errors} zero-division cases raised")
if __name__ == "__main__":
demo()
random_check()
Run, it prints:
['2', '1', '+', '3', '*']
token '2': stack=[2]
token '1': stack=[2, 1]
token '+': stack=[3]
token '3': stack=[3, 3]
token '*': stack=[9]
-> 9
['4', '13', '5', '/', '+']
token '4': stack=[4]
token '13': stack=[4, 13]
token '5': stack=[4, 13, 5]
token '/': stack=[4, 2]
token '+': stack=[6]
-> 6
['-7', '2', '/']
token '-7': stack=[-7]
token '2': stack=[-7, 2]
token '/': stack=[-3]
-> -3
floor vs truncate for -7 / 2: -4 vs -3
int(a / b) with a = 2**53 + 1, b = 1: 9007199254740992 vs 9007199254740993
['+'] -> ValueError: operator '+' needs two operands, stack has 0
['1', '2'] -> ValueError: expression left 2 values on the stack
['1', '0', '/'] -> ZeroDivisionError: division by zero
['1', 'x', '+'] -> ValueError: bad token 'x'
[] -> ValueError: expression left 0 values on the stack
2652 valid expressions match an exact-Fraction reference; 348 zero-division cases raised
Worked trace
For ['2', '1', '+', '3', '*'], which is (2 + 1) * 3:
2and1are pushed: stack[2, 1].+pops 1 (right) and 2 (left), pushes 3: stack[3].3is pushed: stack[3, 3].*pops 3 and 3, pushes 9: stack[9]. One value is left, so the answer is 9.
For ['4', '13', '5', '/', '+'], the / pops 5 (right) and 13 (left), computes 13 / 5 = 2 (truncated), pushes it, and + gives 4 + 2 = 6. For ['-7', '2', '/'] the result is -3, where Python's // would give -4.
The same rule in Java
Java's / on integers truncates toward zero and Math.floorDiv floors, so a Java version uses / directly.
public class TruncDemo {
public static void main(String[] args) {
System.out.println("-7 / 2 = " + (-7 / 2));
System.out.println("-7 % 2 = " + (-7 % 2));
System.out.println("Math.floorDiv(-7, 2) = " + Math.floorDiv(-7, 2));
}
}
Compiled and run on OpenJDK 21 (the Docker image eclipse-temurin:21-jdk), it prints:
-7 / 2 = -3
-7 % 2 = -1
Math.floorDiv(-7, 2) = -4
The % result -1 follows the same truncating rule: (-7 / 2) * 2 + (-7 % 2) is -6 + -1 = -7.
Why floats and fixed-width integers break
Three of the decisions above rest on number facts, and the program below prints each one.
# 1. A float stores 53 significant binary digits, so integers above 2**53 get gaps.
limit = 2**53
print("2**53 =", limit)
for n in (limit + 1, limit + 2, limit + 3):
print(f"int(float({n})) = {int(float(n))}")
print("every integer from 2**53 - 5 up to 2**53 survives the round trip:",
all(int(float(n)) == n for n in range(limit - 5, limit + 1)))
# 2. Floor and truncate are two ways to keep a == q * b + r. They differ in the sign of r.
a, b = -7, 2
q_floor, r_floor = divmod(a, b)
q_trunc = int(a / b)
r_trunc = a - q_trunc * b
print(f"floor: {a} = {q_floor} * {b} + {r_floor}")
print(f"truncate: {a} = {q_trunc} * {b} + {r_trunc}")
# 3. A signed 32-bit integer holds -2**31 .. 2**31 - 1, so -2**31 / -1 does not fit.
lowest, highest = -2**31, 2**31 - 1
result = lowest // -1
print(f"32-bit range: {lowest} to {highest}")
print(f"{lowest} / -1 = {result}, fits in 32 bits: {lowest <= result <= highest}")
2**53 = 9007199254740992
int(float(9007199254740993)) = 9007199254740992
int(float(9007199254740994)) = 9007199254740994
int(float(9007199254740995)) = 9007199254740996
every integer from 2**53 - 5 up to 2**53 survives the round trip: True
floor: -7 = -4 * 2 + 1
truncate: -7 = -3 * 2 + -1
32-bit range: -2147483648 to 2147483647
-2147483648 / -1 = 2147483648, fits in 32 bits: False
- 53 bits. A 64-bit float keeps 53 binary digits of precision for the number itself. Up to
2**53every integer fits exactly. Above it the spacing between storable numbers becomes 2, so2**53 + 1has no slot of its own and rounds to2**53, and2**53 + 3rounds to...996. That is whyint(a / b)returns a wrong integer for big operands even though it looks fine on small ones. - Floor versus truncate. Both rules satisfy
a == q * b + r, so a language must pick one. Truncating toward zero (C, C++, Java) gives-7 = -3 * 2 + -1, so the remainder takes the sign of the dividend. Flooring (Python's//anddivmod) gives-7 = -4 * 2 + 1, so the remainder takes the sign of the divisor. The question asks you to state which one you implement, and the code above implements truncation. - 32-bit overflow. A signed 32-bit integer holds
-2147483648to2147483647, one more negative value than positive ones. Dividing the lowest value by-1should give2147483648, which is one past the top of the range, so the result cannot be stored. Python integers grow as needed and never hit this; in Java or C the result must be handled on purpose.
Complexity
Time O(n) for n tokens: each token is handled once, with O(1) stack work and one int parse. Space O(n) in the worst case, when all the numbers come before any operator, as in 1 2 3 4 + + +, where the stack peaks at 4 values. Python integers have arbitrary precision, so there is no overflow; in Java or C a 32-bit result needs an explicit overflow decision (for example -2147483648 / -1 overflows int).
Edge cases and common mistakes
- Swapping the operand order for
-and/. - Using floor division for negative results (
-4instead of-3). - Parsing with
floatorint(a / b)and losing precision on large values. - Treating the token
'-'as the start of a negative number, or'-3'as an operator. - Not checking that exactly one value remains.
1 2finishes without any error from the loop, but it is not a valid expression. - Letting
ZeroDivisionErroror anIndexErrorfrom an emptypopescape without a message.
Running the code
python rpn.py # Python 3.12
python number_limits.py # the float, floor and 32-bit facts
javac TruncDemo.java && java TruncDemo # JDK 21, file saved as TruncDemo.java
Standard library only.
Provide two analogies you could use to explain the CAP theorem to a product manager who is not a software engineer. For each analogy, say which part of CAP it captures well and where it breaks down.
Sample Answer
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.
How do you stay informed about what a function you regularly work with actually cares about and is measured on, even when you're not in the room for their planning?
Sample Answer
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
| Channel | Typical cadence | What it surfaces |
|---|---|---|
| Their goals or planning document (OKRs, roadmap) | Once per planning cycle | What they are formally accountable for this period |
| Dashboards or metrics they report on | Check periodically | What "good" looks like for them, in their own numbers |
| Retro notes, release notes, postmortems | As published | What is currently painful or top of mind for them |
| Recurring 1:1 with one counterpart | Biweekly or monthly | Informal context, upcoming priorities, translation of jargon |
| Occasional silent sit-in on their planning | A couple of times a year | Calibrates your read of the artifacts against how they actually talk about trade-offs |
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.
Implement is_subsequence(short: str, long: str) -> bool in Python that checks whether 'short' is a subsequence of 'long' (characters in order but not necessarily contiguous). This is used in approximate matching and fuzzy token mapping. Your solution should be O(n) time where n is length of 'long'. Provide an example and handle edge cases.
Sample Answer
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')returningTrue) is easy to get backwards if the loop logic is written slightly differently; the explicitif not short: return Trueguard 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
longstring with many differentshortcandidates, 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 samelongstring 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.
You have a worker pool consuming messages from RabbitMQ. Design a queue-length driven scaling formula that computes desired replicas based on queue depth, current consumer processing rate, and per-consumer throughput. Provide the formula and an example calculation: queue depth 10,000 messages, average processing rate 50 msg/s per consumer, desired latency under 60 seconds.
Sample Answer
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.
What are the constraints that make an API architecture RESTful, and why does each one matter in practice? Cover client-server separation, statelessness, cacheability, a uniform interface, a layered system, and the optional code-on-demand constraint. For each one, give a concrete implication for a production JSON API (for example, how statelessness affects load balancing, or how cacheability changes what you put in a response) rather than just naming it.
Sample Answer
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.
You must sort a large array of expensive-to-copy objects in a memory-constrained backend process where allocating many temporary objects is costly. Propose a practical, stable approach to sort them with limited additional memory (e.g., using indirection array of indices or pointers, external sort, or stable block-sort). Discuss trade-offs in CPU, memory, and cache behavior.
Sample Answer
Direct answer
Do not sort the objects. Sort a small array of indices by the objects' keys with a stable sort, then rearrange the objects once, in place, by following the cycles of that permutation. The objects move at most n times in total (each at most once) and the only extra object alive at any moment is a single temporary; the extra memory is about n small integers (plus whatever the stable sort uses internally). Stability comes from the sort of indices: equal keys keep their input order. The trade-off is that comparisons go through an indirection (look up the key by index), which is less friendly to the CPU cache than comparing values stored side by side, and the in-place permutation pass jumps around memory.
The idea in plain words
Sorting objects directly with a merge sort copies each object about 2 log2 n times (once into the buffer and once back, per level) and needs a buffer as large as the data. If an object is expensive to copy, that is both a time cost and a memory cost, and they are different quantities: the total copying work is the sum over the whole run (2 n log2 n object writes here, shown on 4 objects in the output below), while the peak extra memory is the most that is alive at once (a buffer of n objects here). Indirection attacks both: sort cheap indices, so the heavy objects are not touched until the final order is known, and then move each object once.
Terms: indirection means reaching the object through a small stand-in (here its position number) instead of holding the object itself. Argsort is a sort that returns the positions of the items in sorted order instead of the sorted items. Cache is the small, fast memory next to the CPU: it loads a block of neighbouring memory at once, so reading elements that sit next to each other is fast, while jumping around memory (a cache miss, when the needed bytes are not in the cache yet) is slow. A permutation is a rearrangement of positions; it splits into disjoint cycles (slot 0 wants the item from slot 1, slot 1 wants the item from slot 3, slot 3 wants the item from slot 0, so the three items rotate among those slots). Stable means equal keys keep input order. Fixed point is a slot already holding the right object.
Approach
- Extract the keys into a list
keys(one cheap value per object; use the object field directly if comparison is cheap). order = sorted(range(n), key=keys.__getitem__). Python's sort is stable, soorder[i]is the old position of the object that belongs in slot i, and objects with equal keys appear in input order.- For each slot
startnot yet finished: holdstore[start]in one temporary, then repeatedly dostore[j] = store[order[j]]along the cycle, mark each finished slot (order[j] = j, which makes the pass need no separate visited array), and finally put the held object into the last slot. The loop body is two separate statements,nxt = order[j](remember where the cycle goes next) andorder[j] = j(mark this slot finished), so the order is explicit: read first, then overwrite. - Fixed points cost nothing. The number of object writes is n minus the number of fixed points.
- If the caller only needs to iterate in sorted order, skip step 3 and read
store[order[i]]directly: zero object moves.
Code
Store is a list that counts slot assignments, so the write counts below are tallied by the same functions that do the work. merge_sort_objects is the comparison baseline: a stable merge sort that moves the objects themselves with one buffer, using index ranges instead of slices.
import random
class Store(list):
"""A list that counts slot assignments, standing in for 'moving an expensive object'."""
writes = 0
def __setitem__(self, i, value):
Store.writes += 1
super().__setitem__(i, value)
def sorted_order(keys):
"""Stable argsort: positions of the items in sorted order. Equal keys keep their input order."""
return sorted(range(len(keys)), key=keys.__getitem__)
def apply_order_in_place(store, order, trace=False):
"""Rearrange store so that new[i] = old[order[i]], following permutation cycles.
Holds one object in a temporary at a time. Consumes `order` (marks finished slots with order[j] = j).
"""
for start in range(len(store)):
if order[start] == start:
continue
held = store[start] # the only extra object alive
j = start
while order[j] != start:
store[j] = store[order[j]]
nxt = order[j] # where the next slot in this cycle is
order[j] = j # mark slot j finished
j = nxt
store[j] = held
order[j] = j
if trace:
print(f" cycle from slot {start}: {[o[0] + o[1] for o in store]}")
def merge_sort_objects(store, key, trace=False):
"""Stable top-down merge sort that moves the objects themselves, using one buffer of len(store)."""
n = len(store)
buf = Store([None] * n)
def sort(lo, hi):
if hi - lo < 2:
return
mid = (lo + hi) // 2
sort(lo, mid)
sort(mid, hi)
i, j = lo, mid
for k in range(lo, hi):
if j >= hi or (i < mid and key(store[i]) <= key(store[j])): # <= keeps ties in input order
buf[k] = store[i]; i += 1
else:
buf[k] = store[j]; j += 1
for k in range(lo, hi):
store[k] = buf[k]
if trace:
print(f" merge slots {lo}..{hi - 1}: total object writes so far {Store.writes}")
sort(0, n)
def make_records(n, rng, distinct):
return Store((f"k{rng.randrange(distinct):03d}", f"#{i}") for i in range(n)) # (key, tag)
if __name__ == "__main__":
rng = random.Random(3)
print("trace: 6 records as key+tag, sorted by key")
recs = Store([("b", "1"), ("a", "2"), ("b", "3"), ("a", "4"), ("c", "5"), ("a", "6")])
keys = [r[0] for r in recs]
order = sorted_order(keys)
print(" before:", [r[0] + r[1] for r in recs])
print(" order (old position of each sorted slot):", order)
Store.writes = 0
apply_order_in_place(recs, list(order), trace=True)
print(" after: ", [r[0] + r[1] for r in recs], " object writes:", Store.writes)
print("\nmerge sort on 4 objects, object writes after each merge (each merge writes its slots twice: into the buffer, then back)")
four = Store([("d", "0"), ("c", "1"), ("b", "2"), ("a", "3")])
Store.writes = 0
merge_sort_objects(four, key=lambda r: r[0], trace=True)
print(" 2 * n * log2(n) for n = 4:", 2 * 4 * 2)
print("\nedge cases (object writes)")
for name, rows in (("empty", []), ("one", [("a", "0")]), ("all equal", [("a", str(i)) for i in range(5)]),
("already sorted", [(c, "0") for c in "abcde"]), ("reversed", [(c, "0") for c in "edcba"])):
s = Store(rows); Store.writes = 0
apply_order_in_place(s, sorted_order([r[0] for r in s]))
print(f" {name:15} writes={Store.writes:2d} result={[r[0] + r[1] for r in s]}")
print("\nobject writes for n records (keys from 50 distinct values)")
print(" n merge sort on objects index sort + cycles 2 n log2 n")
for n in (8, 64, 1024):
base = make_records(n, rng, 50)
a, b = Store(base), Store(base)
Store.writes = 0; merge_sort_objects(a, key=lambda r: r[0]); w_merge = Store.writes
Store.writes = 0; apply_order_in_place(b, sorted_order([r[0] for r in b])); w_idx = Store.writes
assert list(a) == list(b) == sorted(base, key=lambda r: r[0])
lg = n.bit_length() - 1
print(f" {n:5d} {w_merge:19d} {w_idx:19d} {2 * n * lg:10d}")
print("\nrandom check: 300 inputs of up to 40 records with many ties, vs sorted(key=...)")
for _ in range(300):
rows = make_records(rng.randrange(0, 41), rng, 4)
want = sorted(rows, key=lambda r: r[0])
got = Store(rows)
apply_order_in_place(got, sorted_order([r[0] for r in got]))
assert list(got) == want
print(" all match, ties in input order")
Run with Python 3.12, it prints:
trace: 6 records as key+tag, sorted by key
before: ['b1', 'a2', 'b3', 'a4', 'c5', 'a6']
order (old position of each sorted slot): [1, 3, 5, 0, 2, 4]
cycle from slot 0: ['a2', 'a4', 'b3', 'b1', 'c5', 'a6']
cycle from slot 2: ['a2', 'a4', 'a6', 'b1', 'b3', 'c5']
after: ['a2', 'a4', 'a6', 'b1', 'b3', 'c5'] object writes: 6
merge sort on 4 objects, object writes after each merge (each merge writes its slots twice: into the buffer, then back)
merge slots 0..1: total object writes so far 4
merge slots 2..3: total object writes so far 8
merge slots 0..3: total object writes so far 16
2 * n * log2(n) for n = 4: 16
edge cases (object writes)
empty writes= 0 result=[]
one writes= 0 result=['a0']
all equal writes= 0 result=['a0', 'a1', 'a2', 'a3', 'a4']
already sorted writes= 0 result=['a0', 'b0', 'c0', 'd0', 'e0']
reversed writes= 4 result=['a0', 'b0', 'c0', 'd0', 'e0']
object writes for n records (keys from 50 distinct values)
n merge sort on objects index sort + cycles 2 n log2 n
8 48 7 48
64 768 64 768
1024 20480 1023 20480
random check: 300 inputs of up to 40 records with many ties, vs sorted(key=...)
all match, ties in input order
Reading the trace
On 4 objects in reverse key order, the merge sort writes 4 object slots in the first merge of two slots (2 into the buffer, 2 back), 8 after the second, and 16 after the last merge, which equals 2 * n * log2 n = 16: every level of merging writes all n slots twice, and there are log2 n levels.
The six records sort by key to a2 a4 a6 b1 b3 c5 (b1 means key b, tag 1). order = [1, 3, 5, 0, 2, 4] says slot 0 wants the object now at position 1, slot 1 wants position 3, and so on.
- Cycle from slot 0: hold
b1; slot 0 takesa2, slot 1 takesa4, and slot 3's value comes from the heldb1. Array:a2 a4 b3 b1 c5 a6. Three writes. - Cycle from slot 2: hold
b3; slot 2 takesa6, slot 5 takesc5, slot 4 gets the heldb3. Three writes.
Total 6 writes for 6 objects, and the equal keys a2 a4 a6 and b1 b3 kept their input order. The edge-case rows show 0 writes for empty, one-element, all-equal and already sorted input (every slot is a fixed point), and 4 writes for the reversed 5-item input (two swaps).
Complexity, with the reason
- Time: O(n log n) key comparisons for the argsort, plus O(n) for the cycle pass. Object writes: at most n (the table shows 7, 64 and 1023 against 48, 768 and 20480 for merge sort on the objects; 20480 is exactly 2 n log2 n for n = 1024).
- Peak extra memory: the
orderlist (n index entries), one temporary object, and the working memory of the sort itself. CPython's list sort may need a temporary array of up to N//2 pointers during merges (from the implementation notes in CPython'slistsort.txt), and a key-function sort also keeps its computed keys; all of those are pointer-sized, not object-sized. Direct merge sort on objects needs a buffer of n objects. - Cache behaviour:
keys[i]lookups and the cycle walk are random accesses, so each is likely to miss the cache on large n; sorting contiguous(key, index)pairs trades 2x key memory for sequential access during comparison. This is a qualitative trade-off; the run counts moves, not time.
If even the index array is too large, or the data exceeds memory
In an interview, the index sort followed by the cycle pass is the expected answer, and mentioning an external sort for data beyond memory is usual; in-place stable block sorts are specialist material that comes up when the interviewer pushes on O(1) extra memory.
- Stable in-place sorts exist (block merge sorts: they merge in small fixed-size blocks inside the array itself, and WikiSort and GrailSort are two published implementations) that use O(1) extra memory with O(n log n) time (the Wikipedia article on block sort gives O(1) auxiliary space in its stated model), but they are intricate and have larger constants; use a tested library implementation rather than writing one.
- C++
std::stable_sorttries to allocate a temporary buffer the size of the data; if that allocation fails, the implementation falls back to a slower algorithm, documented as O(N log^2 N) comparisons instead of O(N log N) (cppreference), that is N times the square of log N, a factor of log N more than the normal bound. In a memory-constrained process that fallback can be what actually runs, so sorting indices is the safer plan. - External sort: if the data does not fit in memory, sort memory-sized runs of
(key, record id), write them to disk, and merge the runs with a k-way merge (repeatedly take the smallest front item among k sorted runs); the permutation is then applied by reading records in sorted order.
Edge cases and common mistakes
- Empty and one-element inputs run without error; all-equal input moves nothing.
- Using an unstable sort of indices (or a comparator that treats ties as unordered) loses stability; the argsort here is stable, and the random check with only four distinct keys confirms equal keys keep input order.
- Applying the permutation the wrong way round (
new[order[i]] = old[i]instead ofnew[i] = old[order[i]]) gives the inverse permutation, which is a different, wrong arrangement; the tests compare againstsorted(..., key=...). - Forgetting to mark finished slots makes the cycle loop revisit them and corrupt the data.
- The cycle pass destroys
order; copy it first (the driver passeslist(order)) if it is needed afterwards.
Design a comprehensive test matrix for an HTTP JSON API endpoint. Include boundary and edge cases such as: very long strings, missing fields, additional unknown fields, deeply nested arrays, binary attachments represented as base64, malformed JSON, Unicode surrogate pairs, SQL/command injection payloads, and permission-denied scenarios. Show how you would represent rows/columns of the matrix and select combinations to automate with limited resources.
Sample Answer
Direct answer
Represent the test matrix as rows of concrete input variants (very long strings, missing fields, extra unknown fields, deeply nested arrays, base64 attachments, malformed JSON, unicode surrogate pairs, injection payloads, permission-denied) crossed against columns of the request DIMENSIONS that can independently vary (which field the variant applies to, HTTP method, auth state, and expected status code), then select which cells to automate first based on risk and blast radius rather than trying to automate the full cross-product.
Structured elaboration: the matrix shape
| Edge-case variant | Applies to which field(s) | Expected status | Automate first? |
|---|---|---|---|
| Very long string (100k+ chars) | name, description | 400 or 413 (defined, not a crash/timeout) | Yes: cheap, high defect-yield |
| Missing required field | id, email | 400 with a field-specific error | Yes: core contract test |
| Additional unknown field | any | 200, extra field ignored (or 400 if strict schema) | Yes: contract-strictness decision |
| Deeply nested array (1000+ levels) | any array field | 400, not a stack overflow | Yes: DoS-adjacent, high severity |
| Base64 attachment, oversized | file field | 413 with a size-limit message | Medium priority |
| Base64 attachment, invalid encoding | file field | 400, not a decode crash | Medium priority |
| Malformed JSON (truncated, trailing comma) | whole body | 400 with a parse-error message, not a 500 | Yes: extremely common real-world input |
| Unicode surrogate pairs (lone/unpaired surrogate) | text fields | 400 or safely sanitized, not a crash | Medium, language/runtime-dependent |
| SQL/command injection payload | text fields | Treated as literal data (200/201), never executed | Yes: security-critical |
| Permission-denied scenario | any endpoint, wrong role/token | 401 (no auth) or 403 (wrong permissions), distinguished correctly | Yes: security-critical |
Worked example: selecting combinations under limited resources
Crossing every variant against every field is exactly the combinatorial-explosion problem pairwise (all-pairs) testing exists to solve. Dimensions multiply rather than add: this matrix's own three independent dimensions (10 variants x 8 fields x 3 auth states) already reach the 240-cell full cross-product cited above, and a fourth independent dimension (say, 5 HTTP methods) would push that to 1,200 cells for the same 10 variants and 8 fields, not a modest increase. Pairwise testing is the standard answer: instead of requiring every value of every dimension to appear together with every value of every other dimension simultaneously, which is what full cross-product coverage guarantees, it only requires that every pair of values, drawn from any two dimensions, appears together in at least one test row. That is enough to catch the large majority of real defects, because combinatorial-testing research has repeatedly found that most software faults are triggered by an interaction between at most two parameters, not by needing every parameter to combine at once. Run for real against this matrix's own three dimensions (10 variants x 8 fields x 3 auth states, 134 required pairs), a standard greedy pairwise-covering algorithm needs only 80 test rows to cover every one of those 134 pairs (verified directly: all 134 covered by the 80 generated rows), a 3x reduction from the 240-cell full cross-product. The 80 is not arbitrary: the two largest dimensions here (10 variants x 8 fields) set a hard lower bound, since covering every variant against every field at least once already requires 10 x 8 = 80 rows on its own, and a well-constructed pairwise set gets the third dimension (3 auth states) covered essentially for free by choosing which auth state accompanies each of those 80 rows rather than adding new rows for it.
Rather than crossing every variant against every field, select automation targets by two criteria applied in order: (1) severity if the case is missed (a crash, a 500, a security bypass, or data corruption ranks above a merely unhelpful 400 message), and (2) how CHEAPLY the case is exercised once the request-building harness exists (once you can post arbitrary JSON to the endpoint, a very-long-string variant costs almost nothing extra to add, so it is nearly free even at low individual risk). This produces the "Yes" column above: malformed JSON, missing required fields, injection payloads, and permission checks are automated first because they combine high severity with low marginal cost; base64/attachment-specific and unicode-specific cases are deferred to a second wave because they are lower-frequency in practice and more expensive to construct realistic payloads for.
Additional cases: typed field and null/missing-field validation
For a concrete POST /users-shaped endpoint with an integer id field, add explicit rows for a STRING value where an integer is expected ("id": "abc"), a float where an integer is expected ("id": 1.5), and id entirely absent versus id: null (these are two different states a strict validator should distinguish: absent means "not provided," null means "explicitly provided as empty," and a schema can legitimately treat them differently, e.g. "absent uses a default, null is rejected").
Trade-offs & pitfalls
The biggest pitfall in building this kind of matrix is treating every cell as equally worth automating; a matrix with 10 variants x 8 fields x 3 auth states is 240 theoretical cells, and attempting to automate all of them produces a slow, brittle suite with diminishing returns. The severity-times-cost prioritization above is the practical answer, but it must be revisited whenever a production incident reveals that a previously deprioritized cell (e.g. a specific unicode edge case) was actually high-severity for this particular system, since the initial prioritization is a judgment call, not a fixed formula.
Want to create your own tailored preparation guide using our deep research?
Get Started for FreeInterview-Ready Courses
Visual-first, interactive, structured learning paths
Browse Backend Developer jobs
AI-enriched listings across hundreds of company career pages
Explore Jobs