Google Senior Backend Developer Interview Preparation Guide
Google's senior backend engineer interview process is a multi-stage evaluation designed to assess algorithmic problem-solving, system design expertise, scalability thinking, and cultural fit. The process typically consists of an initial recruiter screening, two technical phone screens focusing on coding and system design, followed by 4-5 onsite interview rounds that test coding proficiency, advanced system design capabilities, architecture thinking, and behavioral alignment with Google's values. For senior-level candidates, system design and complex infrastructure challenges are weighted heavily.
Interview Rounds
Recruiter Screening
What to Expect
Initial 30-minute call with a Google recruiter to discuss your background, career goals, and fit for the senior backend engineer role. The recruiter will verify your experience level, discuss compensation expectations, and assess your motivation for joining Google. They may ask brief technical questions to ensure you meet minimum qualifications for the role (e.g., confirmation of your backend development experience with mentioned technologies). This round is primarily evaluative from a career-fit perspective and to ensure you understand the role and level.
Tips & Advice
Be genuine about your motivation for Google beyond salary and brand. Prepare a concise 2-3 minute summary of your career progression and why you're seeking a senior-level role. Research Google's products and mention specific projects or technologies you're excited about. Ask informed questions about the team, projects, and growth opportunities. Be honest about compensation expectations. Show enthusiasm for backend infrastructure challenges. Have your resume and LinkedIn profile updated and consistent.
Focus Topics
Motivation for Google
Express specific, genuine reasons for wanting to join Google beyond compensation. Reference particular projects, engineering challenges, or Google's infrastructure approach.
Practice Interview
Study Questions
Understanding of the Senior Backend Role
Demonstrate understanding of what a senior backend engineer at Google does: designing scalable APIs, leading architecture decisions, mentoring junior engineers, and owning end-to-end system reliability.
Practice Interview
Study Questions
Career Progression and Experience Validation
Clearly communicate your 5+ years of backend development experience, progression through different roles, and key technical achievements. Validate your familiarity with required technologies (Node.js, Python, Java, PostgreSQL, MongoDB, AWS/Azure).
Practice Interview
Study Questions
Technical Phone Screen 1: Algorithms and Coding
What to Expect
45-60 minute live coding interview focusing on algorithmic problem-solving. You'll solve 1-2 medium-to-hard problems on a shared document (typically Google Doc or CoderPad). The interviewer will ask clarifying questions, observe your problem-solving approach, and evaluate code quality, time/space complexity analysis, and communication. For senior-level candidates, expectations include not just correct solutions but also optimized code with proper error handling, edge case consideration, and production-ready practices.
Tips & Advice
Start by asking clarifying questions about input constraints, edge cases, and performance requirements. Think out loud throughout the problem. Discuss your approach before coding. After coding, explain your time and space complexity and discuss potential optimizations. For senior candidates, add defensive programming: null checks, input validation, and error handling. Write clean, readable code with meaningful variable names. If you get stuck, explain your thought process and ask for hints. Test your code mentally with examples. Practice on LeetCode Medium-Hard problems, focusing on graph algorithms, dynamic programming, and data structure manipulation. Most importantly, demonstrate clean coding practices that would be acceptable in production code.
Focus Topics
String and Array Manipulation
Substring problems, array partitioning, two-pointer techniques, sliding windows. Practical for data parsing and processing in backend applications.
Practice Interview
Study Questions
Time and Space Complexity Analysis
Big-O notation, identifying bottlenecks, analyzing trade-offs between different approaches. Be able to articulate why your solution is optimal or suggest better alternatives.
Practice Interview
Study Questions
Dynamic Programming and Optimization
Memoization, tabulation, optimal substructure identification. Focus on problems involving sequences, combinations, and optimization with constraints.
Practice Interview
Study Questions
Hash Tables and Set Operations
Using hash maps and sets for efficient lookups, frequency counting, and deduplication. Core data structures for backend engineering.
Practice Interview
Study Questions
Graph and Tree Traversal Algorithms
DFS, BFS, topological sorting, cycle detection, shortest path algorithms. These are foundational for backend problems like dependency resolution and distributed systems modeling.
Practice Interview
Study Questions
Production-Quality Code Practices
Error handling, input validation, null checks, meaningful variable naming, code organization. Senior-level expectation: write code as if it will be deployed to production.
Practice Interview
Study Questions
Technical Phone Screen 2: System Design
What to Expect
45-60 minute system design interview where you'll design a backend system for a realistic scenario. Examples include designing a URL shortener, rate limiter, notification service, or distributed caching system. You'll gather requirements, propose a high-level architecture, design API schemas and database schemas, discuss scaling strategies, identify bottlenecks, and explain trade-offs in your design choices. The interviewer will probe deeper into specific components and ask follow-up questions to assess your thinking on reliability, consistency, performance, and security.
Tips & Advice
Start by clarifying requirements and constraints with the interviewer (scale, latency requirements, consistency needs, geographic distribution). Propose a simple solution first, then incrementally improve it. Draw diagrams clearly identifying components, data flow, and communication patterns. Discuss trade-offs explicitly: consistency vs. availability, latency vs. throughput, cost vs. performance. For senior-level, be familiar with Google's infrastructure (Google Cloud Platform services like Spanner, Bigtable, Datastore, Pub/Sub, Cloud Load Balancing). Discuss monitoring, logging, and alerting as integral parts of your design. Consider failure scenarios and how your system handles them. Know when to use SQL vs. NoSQL, synchronous vs. asynchronous processing, and caching strategies. Use the RESHADED framework: Requirements, Estimation, Schema, High-level architecture, Algorithms, Deep dive, Evaluation.
Focus Topics
Scalability Techniques (Read/Write Optimization)
Database sharding, read replicas, write-ahead logging, eventual consistency models. How to identify and eliminate bottlenecks as system load grows.
Practice Interview
Study Questions
API Design and Versioning
RESTful API design principles, status codes, error handling, pagination, rate limiting, versioning strategies (URL vs. header), and idempotency for mutations.
Practice Interview
Study Questions
Reliability and Failure Handling
Redundancy, failover mechanisms, circuit breakers, retry logic, dead letter queues, and monitoring. How systems handle failures gracefully without cascading failures.
Practice Interview
Study Questions
Caching Strategies and Redis
In-memory caching patterns (cache-aside, write-through, write-behind), TTL management, cache invalidation, and distributed caching. Redis as a caching and data structure store.
Practice Interview
Study Questions
Distributed System Architecture Fundamentals
Understanding of microservices, load balancing, horizontal scaling, service discovery, and API gateway patterns. How components communicate and coordinate.
Practice Interview
Study Questions
Database Design and Trade-offs (SQL vs. NoSQL)
When to use relational databases (PostgreSQL) vs. document stores (MongoDB) vs. columnar stores. Understanding schemas, indexing strategies, query optimization, and replication topologies.
Practice Interview
Study Questions
Onsite Round 1: Advanced Coding and Data Structures
What to Expect
45-minute in-person or video interview focused on solving 1-2 medium-to-hard algorithmic problems with emphasis on backend-relevant scenarios. Problems may involve concurrent data structures, efficient data processing, or API implementation. The interviewer evaluates correctness, code quality, problem-solving approach, and your ability to think about scalability and production concerns even in algorithmic problems. This round differs from phone screen 1 by potentially having more complex edge cases or requiring discussion of distributed aspects.
Tips & Advice
Treat this as a continuation of phone screen 1 with potentially higher difficulty or complexity. Practice backend-specific problems: implementing LRU cache, designing rate limiter, processing data streams, or handling concurrent requests. Think about thread safety and concurrency issues. For senior candidates, also think about how the solution would scale in a distributed system. Discuss monitoring and observability even for algorithmic problems. Ask questions about requirements and constraints. Communicate your thought process clearly. Use clear variable names and well-structured code. After solving, discuss edge cases, potential optimizations, and production considerations.
Focus Topics
Data Processing and Stream Handling
Processing large datasets efficiently, streaming data, batch processing, and handling backpressure. Relevant for backend services processing continuous data flows.
Practice Interview
Study Questions
API Implementation and Request Handling
Implementing API endpoints, handling different HTTP methods, status codes, error responses, request validation, and middleware patterns.
Practice Interview
Study Questions
Backend-Specific Problem Patterns (LRU Cache, Rate Limiter, etc.)
Commonly asked backend problems: implementing LRU cache, designing rate limiters (token bucket vs. sliding window), designing URL shorteners, implementing pub/sub systems. These directly apply to production backend systems.
Practice Interview
Study Questions
Concurrent and Thread-Safe Data Structures
Understanding of concurrency issues (race conditions, deadlocks), thread-safe collections, locks, and atomic operations. How to design data structures for multi-threaded backend applications.
Practice Interview
Study Questions
Onsite Round 2: System Design - Infrastructure and Scalability
What to Expect
45-60 minute interview focused on designing a complex distributed backend system. This differs from phone screen 2 by potentially being more complex or asking you to design internal infrastructure rather than customer-facing services. Examples might include designing a logging system, monitoring infrastructure, distributed cache layer, or message queue system. You'll need to discuss not just functionality but also operational concerns: deployment, monitoring, debugging, and maintaining the system at scale. Interviewers probe your understanding of real production challenges and how you'd architect systems for reliability and observability.
Tips & Advice
For infrastructure system design, emphasize operational aspects from the start. Discuss how the system will be monitored, debugged, and operated in production. Be familiar with Google Cloud Platform services (Cloud Pub/Sub, Cloud Spanner, Bigtable, Cloud Dataflow, Stackdriver Monitoring). Design with failure scenarios in mind and explain how the system detects and recovers from failures. Discuss data consistency models (strong consistency vs. eventual consistency) and when each is appropriate. Draw clear diagrams showing data flow, component interaction, and scaling mechanisms. For senior candidates, discuss not just 'what' but 'why' - why this architecture over alternatives, what trade-offs were made, and what would you change at 10x scale. Discuss cost implications and operational overhead. Ask clarifying questions about SLOs, blast radius requirements, and how failures in one component should affect others.
Focus Topics
Fault Tolerance and Disaster Recovery
Designing systems to withstand failures (redundancy, replication, failover), disaster recovery procedures, backup strategies, and RTO/RPO considerations.
Practice Interview
Study Questions
Deployment and Infrastructure as Code
Deployment strategies (canary, blue-green), infrastructure automation, containerization (Docker/Kubernetes), configuration management, and change management in production.
Practice Interview
Study Questions
Data Consistency and Consensus Algorithms
CAP theorem, strong vs. eventual consistency, ACID properties, consensus algorithms (Paxos, Raft). When to use each model and trade-offs.
Practice Interview
Study Questions
Message Queues and Event-Driven Architecture
Understanding of pub/sub systems, message brokers (like Apache Kafka, Google Cloud Pub/Sub), event sourcing, and event-driven architecture. How to decouple components using asynchronous messaging.
Practice Interview
Study Questions
Distributed Tracing and Observability
Monitoring, logging, tracing, metrics collection, and debugging distributed systems. Understanding tools for observability and how to instrument systems for operational visibility.
Practice Interview
Study Questions
Onsite Round 3: System Design - Real-World Problem Solving
What to Expect
45-60 minute interview where you design a solution to a specific Google-relevant or complex real-world backend challenge. This may be inspired by actual Google infrastructure problems or common backend challenges at scale. Examples include designing backend for collaborative real-time editing (like Google Docs), designing a complex payment processing system, or architecting a search index update system. This round emphasizes practical thinking about engineering trade-offs, understanding of Google's technology choices, and ability to make sound architectural decisions under constraints.
Tips & Advice
Research Google's publicly known technical challenges and solutions (Google Docs real-time collaboration, Google Search infrastructure patterns, Spanner distributed database design). When given a problem, don't rush to architecture - spend time understanding requirements, constraints, and success metrics. Propose a simple solution first, then discuss how it would fail at scale and how to improve it. Reference Google-specific infrastructure where applicable (Bigtable for wide tables, Spanner for consistency, Pub/Sub for events). Discuss trade-offs explicitly and defend your choices. For senior candidates, show you can make pragmatic decisions balancing perfect design with time-to-market constraints. Discuss how you'd phase the rollout and what metrics you'd track. Consider edge cases and failure modes specific to the problem. Ask about acceptable latency, consistency requirements, and scale expectations.
Focus Topics
Version History and Audit Trails
Designing systems that maintain complete history of changes, enable time travel, and provide audit trails. Event sourcing and immutable data patterns.
Practice Interview
Study Questions
Handling Large-Scale Data Processing
Batch processing, stream processing, MapReduce patterns, handling data skew, and scalable data transformation. How to process terabytes of data efficiently.
Practice Interview
Study Questions
Real-Time Synchronization and Collaboration
Techniques for real-time data synchronization across multiple clients (Operational Transformation, CRDTs). How systems like Google Docs handle concurrent edits and conflict resolution. WebSocket and long-polling communication patterns.
Practice Interview
Study Questions
Google Cloud Platform Services and Architecture
Practical knowledge of GCP services: Google Cloud Spanner (distributed relational database), Bigtable (wide-column store), Cloud Pub/Sub (messaging), Cloud Dataflow (data processing), Load Balancers, and how to use them together.
Practice Interview
Study Questions
Onsite Round 4: Behavioral and Cultural Fit (Googleyness)
What to Expect
45-minute interview focused on assessing cultural fit, leadership potential, and alignment with Google's values. The interviewer will ask about your past experiences, how you've handled conflicts, examples of collaboration, learning from failures, and your approach to problem-solving and teamwork. They'll assess your potential to thrive in Google's culture, contribute to team dynamics, and grow as a senior engineer. This round also evaluates humility, ownership, and ability to drive projects to completion while supporting others.
Tips & Advice
Prepare stories using the STAR method (Situation, Task, Action, Result) that demonstrate Google's values: innovation, ownership, collaboration, and impact. Focus on stories where you led without authority, influenced team decisions, mentored junior engineers, or drove architectural improvements. Be honest about failures and emphasize what you learned. Discuss how you handle disagreements and make decisions when there's no clear right answer. Show genuine passion for technology and learning. Share examples of how you've improved team processes or code quality. For senior roles, emphasize your ability to mentor others and raise the bar for your team. Ask thoughtful questions about team culture, how success is measured, and what the biggest challenges are. Be authentic - Google wants people who genuinely fit their culture, not those pretending to.
Focus Topics
Learning Agility and Adaptability
Examples of quickly learning new technologies or domains, adapting to changing requirements, and growing from setbacks. How you stay current with technology trends.
Practice Interview
Study Questions
Impact and Results Orientation
Focus on concrete examples of projects you've completed, metrics you've improved, and business impact you've driven. How you prioritize and make trade-off decisions.
Practice Interview
Study Questions
Collaboration and Communication
Examples of working effectively with cross-functional teams (frontend engineers, data engineers, product managers), handling disagreements constructively, and supporting teammates. Communication of complex technical ideas to non-technical audiences.
Practice Interview
Study Questions
Ownership and Initiative
Show examples of taking ownership of problems, driving projects to completion, and being accountable for outcomes. Discuss how you identify technical debt and drive improvements.
Practice Interview
Study Questions
Leadership and Influence Without Authority
Demonstrate ability to lead projects, influence team decisions, and drive technical direction as a senior individual contributor. Examples of mentoring, code review impact, and raising engineering standards.
Practice Interview
Study Questions
Frequently Asked Backend Developer Interview Questions
System design: Design the key storage and lookup component for a URL shortener service that must handle 100M stored URLs and 1B redirects per day. Explain how you would generate unique short IDs (hash vs counter vs randomness), avoid collisions, shard storage, handle hot keys, and support analytics.
Sample Answer
Direct answer
Generating short IDs for a URL shortener has three realistic options: hash the long URL and truncate
(risking collisions you must detect and handle), use a monotonically increasing counter encoded in a
compact base (e.g. base62, guaranteed collision-free but requires coordinating the counter across
shards), or generate a random ID and check for collision before committing (simple, but needs a
uniqueness check on every write). Most production designs land on a sharded counter or a
collision-checked random ID, not a raw hash truncation, specifically because hash truncation's
collision rate becomes a real operational problem at scale.
Structured elaboration
Why "just hash the URL and truncate" is the tempting but weaker option. A hash function
distributes long URLs into IDs, but a SHORT id (say 7 base62 characters, about 3.5 * 10^12 possible
values) truncated from a longer hash inherits the birthday-paradox collision behavior of that space,
at meaningful scale (billions of URLs), the odds of two different URLs truncating to the same short
ID stop being negligible, and now every WRITE needs a re-check-and-extend-on-collision path anyway,
undermining the "just hash it" simplicity that made this option appealing in the first place.
Counter-based generation avoids collisions structurally. If short IDs come from an always-
increasing counter (encoded in base62 for compactness: 7 base62 characters already cover over
3.5 trillion values), collisions are structurally impossible, no two counter values are ever equal.
The real engineering problem this creates is COORDINATING that counter across many write-serving
shards without it becoming a single bottleneck or a contention point, standard answers include
pre-allocating counter RANGES to each shard (so each shard hands out IDs from its own reserved block
without talking to a central counter on every write) or using a distributed ID generator (e.g. a
Snowflake-style scheme combining a timestamp, a shard ID, and a local sequence number into one
globally-unique value).
Sharding storage and handling hot keys. Once you have a short ID, routing "look up this ID's
target URL" to the right storage shard is itself a hashing/sharding decision, and consistent hashing is the standard mechanism, letting you add storage
capacity without re-shuffling nearly every existing mapping. A small number of extremely popular
short links (a "hot key", e.g. a viral URL getting a disproportionate share of the 1B/day redirect
traffic) benefit from an additional caching layer in front of the sharded storage, since the
consistent-hashing layer alone routes a hot key's reads to one shard/replica set, it doesn't by
itself absorb that shard's disproportionate read volume.
Supporting analytics. Redirects (1B/day, roughly 11,600/sec on average) are the hot read path,
so recording a click/redirect event can't sit synchronously in front of that response: incrementing
a counter in the same hash-based store on every redirect would turn the read-hot-key problem above
into a WRITE-hot-key problem on the exact same keys. The standard fix is to decouple: the redirect
handler emits a small, asynchronous event (short ID, timestamp, minimal request metadata) onto a
log or stream and returns the redirect immediately, without waiting on that write. A separate
downstream consumer aggregates those events (batched or streaming) into a store optimized for
analytics rollups (per-short-ID counts, referrer/geo breakdowns, time-bucketed series) that
dashboards read, not the redirect path itself. This keeps the redirect's hot path doing exactly one
thing (look up and redirect), and lets the analytics side scale, or even drop an occasional event
under overload, without ever affecting redirect latency or correctness.
Worked example
At 100M stored URLs and 1B redirects/day (about 11,600 redirects/sec on average, ignoring peak
skew), a counter-based scheme needs only about log62(100,000,000), roughly 5 base62 characters, to
uniquely represent every stored URL with room to grow, comfortably under the 6-7 character short
codes seen in practice, which typically budget headroom for years of future growth rather than
sizing exactly to the current count. The read path (1B/day, heavily read-dominated versus the
write/creation path) is where caching hot redirects in front of the sharded lookup store earns its
keep, since redirect lookups vastly outnumber new-URL creations.
Trade-offs and pitfalls
The pitfall worth naming explicitly: presenting hash-and-truncate as if it were collision-free "often
enough" without ever quantifying the actual birthday-paradox math at the scale the question specifies,
this is exactly the kind of claim that should come with a rough number (as above) rather than a bare
assertion. A second pitfall is treating the SHARDING/consistent-hashing layer as if it alone solved
hot-key read pressure, it solves balanced OWNERSHIP of the keyspace, not necessarily balanced READ
LOAD when a small number of keys receive a wildly disproportionate share of traffic, that needs an
explicit caching or replica-fan-out answer on top.
You have the filled table dp where dp[i][j] is the maximum path sum from the top-left to cell (i, j) in a grid with moves right and down. Show how to recover one path that achieves dp[m-1][n-1], and say what you do on ties.
Sample Answer
The idea
Every cell of the table was filled as dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1]). So the cell that an optimal path used just before (i, j) is the neighbour with the larger dp value. To recover the path, start at the bottom-right cell, repeatedly step to that larger neighbour, and stop at (0, 0); then reverse the list, because you collected the cells from the end. The grid itself is not needed: the table already contains the answer to "which neighbour won".
The choice has to compare dp values, not raw grid values. A neighbour with a big cell value can still be a bad place to come from if the best sum reaching it is small.
The rules, step by step
- Start at
(m-1, n-1)and record the cell. - In the first row, the only possible predecessor is the left neighbour; in the first column, the only one is the upper neighbour. Handle these before comparing: a negative index in Python wraps to the last row instead of failing at once, so the walk would read the wrong cells.
- Otherwise compare
dp[i-1][j]withdp[i][j-1]and step to the larger. - On a tie both neighbours lead to a path with the same optimal sum, so either is correct. Pick a fixed rule (here: prefer the cell above, with
prefer="left"as the alternative) so the same table always produces the same path. Which tie rule you choose changes the path, never the sum. - When the cell is
(0, 0), stop and reverse.
Code
The program fills the table, recovers the path with both tie rules, shows a table with a tie in the last cell, runs the common bug (comparing grid values) next to the correct walk-back, and checks everything against exhaustive enumeration of all paths.
import random
def fill(grid):
"""dp[i][j] = max sum of a right/down path from (0, 0) to (i, j)."""
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
dp[i][j] = grid[i][j]
else:
up = dp[i - 1][j] if i > 0 else None
left = dp[i][j - 1] if j > 0 else None
dp[i][j] = grid[i][j] + max(v for v in (up, left) if v is not None)
return dp
def recover(dp, prefer="up"):
"""Walk back from the bottom-right cell using only the filled table.
The cell we came from is the neighbour with the larger dp value; on a tie, `prefer` decides."""
i, j = len(dp) - 1, len(dp[0]) - 1
cells = [(i, j)]
while (i, j) != (0, 0):
if i == 0:
j -= 1 # first row: only the left neighbour exists
elif j == 0:
i -= 1 # first column: only the upper neighbour exists
elif dp[i - 1][j] > dp[i][j - 1]:
i -= 1
elif dp[i - 1][j] < dp[i][j - 1]:
j -= 1
elif prefer == "up":
i -= 1
else:
j -= 1
cells.append((i, j))
cells.reverse()
return cells
def all_optimal_paths(grid):
"""Every right/down path whose sum equals the maximum (exhaustive, for checking)."""
m, n = len(grid), len(grid[0])
found = []
def go(i, j, path, total):
path.append((i, j))
total += grid[i][j]
if (i, j) == (m - 1, n - 1):
found.append((total, tuple(path)))
else:
if i + 1 < m:
go(i + 1, j, path, total)
if j + 1 < n:
go(i, j + 1, path, total)
path.pop()
go(0, 0, [], 0)
best = max(t for t, _ in found)
return [p for t, p in found if t == best], best
def wrong_recover(grid):
"""The common bug: walk back comparing raw grid values instead of dp values."""
i, j = len(grid) - 1, len(grid[0]) - 1
cells = [(i, j)]
while (i, j) != (0, 0):
if i == 0:
j -= 1
elif j == 0:
i -= 1
elif grid[i - 1][j] >= grid[i][j - 1]:
i -= 1
else:
j -= 1
cells.append((i, j))
return cells[::-1]
def total(grid, cells):
return sum(grid[i][j] for i, j in cells)
grid = [[1, 3, 1],
[1, 5, 1],
[4, 2, 1]]
dp = fill(grid)
print("dp:")
for row in dp:
print(" ", row)
for rule in ("up", "left"):
p = recover(dp, rule)
print(f"tie rule {rule}: {p} sum {total(grid, p)}")
tied = [[0, 2, 1], [2, 0, 3], [1, 3, 0]]
dpt = fill(tied)
print("tie grid dp:", dpt)
print("tie grid, up :", recover(dpt, "up"))
print("tie grid, left:", recover(dpt, "left"))
paths, best = all_optimal_paths(tied)
print("optimal paths on the tie grid:", len(paths), "with sum", best)
trap = [[0, 0, 0],
[0, 0, 5],
[9, 1, 0]]
dpw = fill(trap)
pw = wrong_recover(trap)
print("grid-value walk-back on", trap, "gives", pw, "sum", total(trap, pw), "but dp says", dpw[-1][-1])
print("dp walk-back gives", recover(dpw), "sum", total(trap, recover(dpw)))
random.seed(36)
cases = bad = tie_cases = differ = 0
for _ in range(500):
m, n = random.randint(1, 5), random.randint(1, 5)
g = [[random.randint(-3, 3) for _ in range(n)] for _ in range(m)]
d = fill(g)
opt, best = all_optimal_paths(g)
pu, pl = recover(d, "up"), recover(d, "left")
cases += 1
bad += not (tuple(pu) in opt and tuple(pl) in opt and best == d[-1][-1] == total(g, pu) == total(g, pl))
tie_cases += len(opt) > 1
differ += pu != pl
print("seeded cases:", cases, "mismatches:", bad, "| cases with several optimal paths:", tie_cases, "| cases where the two tie rules differ:", differ)
print("1x1 grid:", recover(fill([[-4]])), " single row:", recover(fill([[2, -1, 3]])), " single column:", recover(fill([[2], [-1], [3]])))
Output:
dp:
[1, 4, 5]
[2, 9, 10]
[6, 11, 12]
tie rule up: [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2)] sum 12
tie rule left: [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2)] sum 12
tie grid dp: [[0, 2, 3], [2, 2, 6], [3, 6, 6]]
tie grid, up : [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]
tie grid, left: [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]
optimal paths on the tie grid: 2 with sum 6
grid-value walk-back on [[0, 0, 0], [0, 0, 5], [9, 1, 0]] gives [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)] sum 5 but dp says 10
dp walk-back gives [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)] sum 10
seeded cases: 500 mismatches: 0 | cases with several optimal paths: 76 | cases where the two tie rules differ: 76
1x1 grid: [(0, 0)] single row: [(0, 0), (0, 1), (0, 2)] single column: [(0, 0), (1, 0), (2, 0)]
Reading the output
- On the 3 x 3 grid the path is
(0,0), (0,1), (1,1), (2,1), (2,2)with sum 1 + 3 + 5 + 2 + 1 = 12, equal todp[2][2]. Both tie rules give the same path here because no tie is met on the way back. - On the tie grid (
[[0, 2, 1], [2, 0, 3], [1, 3, 0]]) the cell(2,2)hasdp[1][2] = dp[2][1] = 6. Preferring the cell above gives the route along the top and right edge; preferring the left gives the route down the left edge and along the bottom. Exhaustive enumeration finds exactly 2 optimal paths, and each rule produces one of them. - The bug demonstration: on
[[0, 0, 0], [0, 0, 5], [9, 1, 0]]the cell above the end holds 5 and the cell to its left holds 1, so comparing raw grid values steps up, but the best sum reaching the cell above is only 5 while the best sum reaching the left cell is 10 (through the 9). The raw-value walk-back ends with sum 5, whiledpsays 10, and the correct walk-back finds the path through the 9. - The random check uses 500 seeded grids from 1 x 1 to 5 x 5 with values from -3 to 3 (negatives and zeros included): both tie rules always return a legal optimal path, and in 76 of those cases there are several optimal paths and the two rules return different ones, so the tie handling is exercised, not just present.
Complexity
- Time
O(m + n)for the walk-back: every step moves up or left by one, so at mostm + n - 2steps. For a 1 x 1 grid there are 0 steps and the path is just(0, 0). - Space
O(m + n)for the returned list; no extra table, no recursion. - Filling the table itself is
O(mn).
Common mistakes
- Comparing grid values instead of
dpvalues (the bug shown above). - Forgetting the first row and first column and indexing with -1.
- Forgetting to reverse the collected cells.
- Returning the sum of the path computed from the grid and trusting it without comparing with
dp[m-1][n-1]in a test.
Running the code
docker run --rm -v "$PWD":/w -w /w python:3.12 python grid_path_recovery.py
Save the listing as grid_path_recovery.py; it uses only the standard library.
Your team moved to microservices, but engineering velocity has stalled: releases need cross-team coordination, on-call keeps getting paged for cascading issues, and a schema change in one service quietly breaks two others. Which architectural anti-patterns do you suspect are at play? For each one, give a concrete detection signal you'd look for in monitoring or traces, and one pragmatic, incremental remediation step.
Sample Answer
Direct answer
Those three symptoms point to six suspects, including one that is worth checking even though it does not map cleanly to a single symptom below. Lockstep releases suggest a distributed monolith: services that are packaged and deployed separately, so they look like microservices, but are coupled tightly enough that they still have to change and ship together, the coordination cost of a monolith without the deployment independence a microservice split is supposed to buy. Cascading pages (one service's trouble tripping alerts through several other services it calls, or that call it, in a chain) suggest chatty services and long synchronous call chains, possibly with cyclic dependencies. A god service, one service that has absorbed so many responsibilities that it shows up in almost every trace and almost every incident, is that additional suspect: it can force lockstep releases because every dependent team waits on the team that owns it, and it can make pages cascade because it sits on the path of most requests. A schema change breaking two other services points to shared-database coupling or a leaky abstraction (an interface meant to hide a service's internal details, that lets them show through anyway) that exposes one service's internal schema to others. Confirm each with evidence from traces, deploy history and database access logs before acting, then fix incrementally, starting with the one that causes the most pages. Do not propose a rewrite.
Symptom to anti-pattern, detection signal and first remediation step
| Symptom | Suspected anti-pattern | Detection signal | One incremental remediation |
|---|---|---|---|
| Releases need cross-team coordination | Distributed monolith: independently deployed services that must still ship together | Deploy coupling: share of releases where 2 or more services had to deploy in the same window for one change; co-change in version control (the same ticket touching several repositories) | Make API changes backward compatible (add fields, never rename or remove in one step) and add consumer-driven contract tests (each consumer publishes the requests it relies on; the provider's CI fails if it breaks them), so each service can ship alone |
| On-call paged for cascading issues | Chatty services: many fine-grained calls to render one result | Trace span count per user request and fan-out (how many downstream calls one request triggers); many sequential calls to the same service inside one trace (the N+1 pattern: one call to fetch a list, then one extra call per item in that list, instead of a single batched call) | Replace the loop of per-item calls with one batch endpoint (GET /prices?ids=...), or keep a local read-only copy of slowly changing reference data |
| Same cascade, pages across many teams | Cyclic service dependencies: A calls B, B calls C, C calls A | Build the service call graph from trace data and look for cycles; a single incident paging several teams' services in a loop | Break one edge of the cycle: move the back-call to an event the upstream service publishes, so the dependency points one way |
| One service appears in almost every trace | God service: one service that owns too many responsibilities | High in-degree (a graph term for many incoming edges, here meaning many other services call into it) in the call graph; one repository with commits from many teams; its deploys correlate with others' incidents | Carve out the single most frequently changed responsibility behind its own interface first |
| Schema change in one service breaks two others | Shared-database coupling | Database logs or per-role query statistics (usage broken down by database login/credential, not by job role) showing several services' credentials reading or writing the same tables; incidents in other services following a migration | Give each table exactly one owning service; as a first step, publish a read-only database view or an API as the stable contract and move readers onto it |
| Same, via the API or events | Leaky abstraction exposing internal schema | API responses or events whose field names mirror table columns; change-data-capture streams (a feed of every row-level insert, update and delete, read straight off the database) of raw tables consumed directly by other teams | Introduce an explicit, versioned public model and map the internal schema to it, so internal columns can change freely |
Span: one timed operation in a distributed trace, such as one HTTP call. Trace: the tree of spans produced by one user request.
Worked example: putting numbers on the cascade
A checkout trace shows one user request producing 23 spans (a span is one timed operation in the trace, such as one HTTP call; 23 means some services are called more than once) across 7 services, with 6 of the calls made one after another, which is what makes the request slow. Separately from that latency picture, checkout's correctness depends on all 7 services succeeding, whether a given call sits on the sequential chain or not: if any one of them fails, the checkout fails. Suppose each of the 7 services is available 99.9% of the time and checkout needs all of them to succeed.
- Chained availability: 0.999 raised to the 7th power (one factor per required service) = 0.99302, about 99.30%. That looks like a small drop from 99.9%, because both numbers are close to 100%.
- Over a 30-day month (43,200 minutes), that is (1 - 0.99302) x 43,200, about 301 minutes of failed checkouts, versus 0.001 x 43,200 = 43.2 minutes for a single 99.9% service. 301 / 43.2 is about 7: it is the expected downtime, not the availability percentage, that scales roughly with the number of required services.
So a design where every request synchronously depends on seven services has about seven times the expected downtime of any one of them (301 minutes a month versus 43.2), before even counting the extra latency the 6 sequential calls add on top, even though the availability percentages themselves look close (99.30% versus 99.9%). The 23-span, 6-sequential-call shape is why the request is also slow; the 7-services-required shape is why it is fragile. That is the architectural reason on-call keeps getting paged: the dependency structure multiplies failure, and no single team's service looks broken.
For deploy coupling, pull the last quarter's release records. If, for example, 31 of 50 releases needed a coordinated deploy, that 62% is the number to drive down, and the co-change data shows which service pairs to fix first.
Sequencing the remediation
The aim is to reduce risk and restore delivery speed without a big-bang rewrite:
- Measure first. Record the baseline: deploy-coupling rate, pages per week by root-cause service, median spans per key request, number of services with write access to each shared table.
- Stop the bleeding on pages. Fix the worst chatty path or break the cycle on the most-paged flow; these are local changes with fast payback.
- Stop new coupling. Add contract tests in CI, and a rule that no new service gets credentials to another service's tables. This keeps the smell from recurring while you pay down the old debt.
- Pay down the shared database table by table, starting with the tables whose migrations caused incidents.
- Report progress in delivery terms: lead time for changes (the time from a commit to it running in production) and change failure rate (the share of production changes that cause an incident), two of the DORA metrics (the software delivery measures from the DevOps Research and Assessment programme), plus the deploy-coupling rate.
Pitfalls
- Armouring instead of fixing. Timeouts and circuit breakers (a guard that stops calling a failing dependency for a while, instead of piling retries onto a call that keeps failing) limit the blast radius (how much of the system one failure can drag down) of a bad dependency but leave the dependency in place; they are not a remediation of the architecture.
- Merging everything back. Sometimes two services that always change together should become one, and that is a legitimate fix, but decide it per pair from co-change evidence, not as a reaction to pain.
- Guessing from symptoms alone. The same "cascading pages" symptom can come from chatty calls or from a cycle; the trace graph tells you which.
- Fixing everything at once. Coordinated remediation across all teams recreates the coordination problem you are trying to remove.
You need accurate p95/p99 latency numbers for a high-throughput service made of many instances. What's the difference between computing that from histograms versus summaries, and what pitfalls come up when you aggregate percentile data across instances?
Sample Answer
Direct answer
Use histograms, not summaries, when p95/p99 needs to be aggregated across many instances, because histogram buckets are additive cumulative counters you can sum across instances before computing a quantile, while a summary's quantile is already computed per-instance and cannot be correctly averaged into a fleet-wide percentile.
Why this is true
Why summaries don't aggregate
A summary computes its quantile locally from that instance's own observations. Averaging five instances' p99s is not the fleet's p99: an instance handling a small, unlucky slice of high-latency traffic gets diluted by four instances with normal traffic, hiding exactly the tail behavior the query was meant to surface.
Why histograms do aggregate
A histogram exposes cumulative bucket counts, how many observations were at or below each boundary. Bucket counts are just counts, so you can sum them across instances first, then compute the quantile once from the merged distribution:
Blefleet=i=1∑nBle(i)then interpolate the quantile from the merged Bfleet. This is mergeable because summation is associative; a pre-computed quantile is not.
The PromQL shape (illustrative, not the point of the question):
histogram_quantile(0.99, sum by (le, job) (rate(http_request_duration_seconds_bucket[5m])))
Pitfalls specific to aggregating this way
- All instances must share identical bucket boundaries, or
sum by (le)is adding counts from buckets that don't actually represent the same ranges. - Accuracy is bounded by bucket granularity (see the bucket-design question): a coarse tail bucket makes the interpolated p99 a rough estimate, not an exact value.
- At low sample counts, a low-traffic service or a short
rate()window, the interpolated quantile can be noisy or misleading. Widen the window or require a minimum sample count before alerting on it.
When per-instance precision genuinely matters more
Summaries still have a place: debugging one specific instance's actual latency distribution, or client environments where a full histogram implementation isn't available. Just don't build fleet-wide SLO dashboards on top of them.
Alternatives when storing every observation isn't affordable
When a fixed-bucket histogram isn't precise enough, or the quantile is being computed outside the metrics pipeline entirely, for example inside application code or a tracing system, two streaming estimators are the common choices:
- Reservoir sampling: keep a fixed-size random sample of everything seen and compute the quantile from the sample at read time. Simple and unbiased, but tail accuracy (p99) degrades because a small sample only has a handful of items above the p99 threshold.
- t-digest or HDR histogram: adaptive structures that allocate more resolution near the tails (t-digest) or guarantee a fixed relative error across the whole range (HDR histogram), and both are mergeable across instances the way a Prometheus histogram is, unlike a plain reservoir sample, which isn't trivially mergeable without keeping the full underlying sample from every instance.
- The trade-off between the two: reservoir sampling is simpler with no accuracy bias but has higher tail variance for a fixed memory budget. t-digest and HDR trade a bit of implementation complexity for much better tail accuracy at the same memory footprint, which is why they're the more common choice in tracing systems where the tail is usually the point of interest.
Worked example
Quantify the reservoir-sampling tail-noise problem concretely. With a reservoir size k=1000 computing p99:
expected observations above p99 in the reservoir=k×(1−0.99)=1000×0.01=10With only about 10 samples informing the estimate above the 99th percentile, the standard error of that estimate is large relative to the value itself, a handful of samples is a small basis for estimating a tail. That's exactly why reservoir sampling is fine for a median but noisy for p99, and why t-digest's tail-biased resolution, allocating proportionally more centroids near the extremes, exists specifically to fix this.
Trade-offs and pitfalls
- Reaching for a summary because the client library makes it one line of code, without realizing it breaks fleet-wide aggregation once the service scales past one instance, is the single most common version of this mistake.
- Mixing bucket boundaries across a service's versions, for example after a library upgrade changes the defaults, silently breaks historical quantile continuity even though nothing errors.
- Reservoir sampling's simplicity is attractive for a quick implementation, but if the actual goal is tail latency, which it almost always is for an SLO, the sample size needed for a stable p99 estimate is much larger than what feels sufficient for a median. Budget memory accordingly or use t-digest instead.
You need to add a column to a production table with hundreds of millions of rows, and you cannot take a long lock or cause a visible outage. Describe a safe approach: what technique would you use to make the change incrementally, how would a dual-write-and-backfill strategy work if you needed one, and how would you monitor and cap the impact on live traffic while it runs, including a way to back out if something goes wrong?
Sample Answer
Direct answer
Adding the column itself should be near-instant: a plain ADD COLUMN with a constant (or
NULL) default is a metadata-only change on modern PostgreSQL and doesn't rewrite the
table. The actual risk is in populating it: run that as an explicit incremental backfill
in small batches with pacing between them, have the application dual-write the new column
on every new or updated row going forward before the backfill starts, and monitor replication lag (how far behind the primary a replica's copy of the data has fallen) and lock wait as hard caps that pause the job automatically.
The plan
The ADD COLUMN step itself. On PostgreSQL 11 and later, ADD COLUMN with a
constant default, including NULL, is metadata-only and does not rewrite existing rows.
That's a genuine change from older versions, and a common misconception is that any ADD COLUMN with a default rewrites the whole table; that's only true for a volatile,
non-constant default, or certain constraint additions. This step takes a brief exclusive
lock, but for milliseconds, a fundamentally different risk than the population step.
If a full backfill is needed (computing a derived value per row, the harder case this
question is really about):
- Incremental technique: iterate in small batches by primary-key range, each batch its
own short transaction, with a brief pause between batches so replication and any read
replicas can keep up, and so row locks don't accumulate into one long-held transaction. - Dual-write: ship the application change that writes the new column on every new or
updated row first, before the batch backfill starts, so the backfill isn't chasing a
moving target. The batch job then only needs to cover rows written before that deploy. - Monitoring and capping impact: watch replication lag (don't let a replica fall far
enough behind that a failover would lose data, or that it starts serving badly stale
reads); watch lock-wait time and set alock_timeoutso a batch that's queued too long
aborts rather than backs up behind unrelated traffic; watch dead-tuple growth (a dead tuple is the old copy of a row that Postgres leaves behind after anUPDATE, since it writes a new row version instead of editing the old one in place); the backfill itself generates a dead row version for every update, a real bloat event, meaning the table fills up with dead tuples faster than they get cleaned out, at this row count that needs its own vacuum planning (VACUUMis the background process that reclaims the space those dead tuples hold so the table doesn't just keep growing); and cap the overall rate (target
rows/sec) rather than running batches back to back as fast as possible. - Backing out: since the column can be added nullable with nothing yet depending on it,
backing out mid-backfill just means stopping the job. The column can sit partially
populated with no correctness impact as long as nothing treats it as authoritative
until the backfill and validation are complete, and the dual-write path can be
feature-flagged off independently of the backfill's progress.
Worked example: backfill timing (pinned inputs)
total_rows = 400_000_000
batch_size_rows = 5_000
sleep_between_batches_ms = 50
exec_time_per_batch_ms = 20 # illustrative per-batch UPDATE execution time
num_batches = total_rows / batch_size_rows
time_per_batch_s = (sleep_between_batches_ms + exec_time_per_batch_ms) / 1000.0
total_time_s = num_batches * time_per_batch_s
print(f"num_batches = {num_batches:,.0f}")
print(f"time_per_batch = {time_per_batch_s*1000:.0f}ms")
print(f"total wall time = {total_time_s:,.0f}s = {total_time_s/3600:.1f} hours")
num_batches = 80,000
time_per_batch = 70ms
total wall time = 5,600s = 1.6 hours
Halving the batch size to 2,500 rows roughly doubles num_batches to 160,000 and, for a
similar per-batch overhead, roughly doubles the wall time to about 3.2 hours, a direct
trade between how gentle each batch is on the live system and how long the whole backfill
takes. That trade is worth sizing explicitly against how much time the migration is
actually allowed to take, not defaulted to "as small as possible."
Trade-offs and pitfalls
- Assuming
ADD COLUMNitself is the risky step; on modern PostgreSQL with a constant
default it usually isn't. The real risk in this scenario is almost always the
subsequent full-table update to populate a derived value; don't spend the caution
budget on the step that doesn't need it. - Smaller batches and longer pauses are safer for the shared system but make the backfill
take proportionally longer, size this trade-off deliberately, not by habit. - Shipping the backfill before the dual-write path is verified working means the backfill is chasing a target that's still drifting from concurrent, uninstrumented writes: rows the backfill already processed keep getting changed by callers the dual-write path never reached, so the column silently falls out of sync with its source again after the batch job has already moved past that row. This is the same kind of drift failure that hits any derived copy of data, a cache, a summary table, a replica, whenever its update logic misses a write instead of catching every one.
- Not planning for the backfill's own bloat: 400 million updates generate 400 million
dead tuples somewhere, a genuinely large vacuum workload competing with the same system
the whole plan is trying not to disrupt.
Implement a binary search tree from scratch with search, insert, and delete, handling the 0-child, 1-child, and 2-child deletion cases. Then explain what can make this tree degrade to O(n) operations, and what a self-balancing variant (AVL or red-black) does differently on insert to prevent it.
Sample Answer
Direct answer
A binary search tree (BST), a tree where every node's left subtree holds smaller keys and its right subtree holds larger keys, supports search, insert, and delete by walking down from the root using key comparisons, giving O(log n) operations only when the tree stays roughly balanced. Deleting a node has three cases depending on how many children it has: a leaf (0 children) is simply removed, a node with exactly 1 child is replaced by that child, and a node with 2 children is replaced by its in-order successor's key (the smallest key in its right subtree), after which that successor is deleted from its original position, where it is now guaranteed to have at most one child.
Structured elaboration
Approach: BST search, insert, delete
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def bst_search(root, key):
node = root
while node is not None:
if key == node.key:
return node
node = node.left if key < node.key else node.right
return None
def bst_insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = bst_insert(root.left, key)
elif key > root.key:
root.right = bst_insert(root.right, key)
return root
def _min_node(root):
node = root
while node.left is not None:
node = node.left
return node
def bst_delete(root, key):
if root is None:
return None
if key < root.key:
root.left = bst_delete(root.left, key)
elif key > root.key:
root.right = bst_delete(root.right, key)
else:
if root.left is None and root.right is None:
return None # 0-child case
if root.left is None:
return root.right # 1-child case (right only)
if root.right is None:
return root.left # 1-child case (left only)
# 2-child case: replace key with in-order successor, then delete it
successor = _min_node(root.right)
root.key = successor.key
root.right = bst_delete(root.right, successor.key)
return root
Approach: why a plain BST can degrade, and what AVL does differently
- A plain BST's height depends entirely on insertion order: inserting already-sorted keys (or reverse-sorted keys) builds a tree that is really a linked list in disguise, one child per node, giving O(n) search, insert, and delete instead of O(log n).
- An AVL tree (a self-balancing BST named for its inventors, Adelson-Velsky and Landis) prevents this by tracking a height at every node and, after every insert, walking back up and checking a balance factor (the height of the right subtree minus the height of the left subtree) at each ancestor. If the balance factor ever reaches +-2, a rotation restructures that subtree back to +-1; this happens on the way back up from the newly inserted node, so no ancestor is ever left unbalanced for more than the single insert that caused it.
- The specific rotation applied depends on where the imbalance shows up: a single rotation fixes a "straight-line" imbalance (left-left or right-right), and a double rotation (rotating the child first, then the node itself) fixes a "zig-zag" imbalance (left-right or right-left).
- A red-black tree solves the same degradation problem with a different, looser invariant, a coloring rule rather than a strict height-balance rule, trading a slightly taller worst-case tree for fewer rotations per insert.
def _h(node):
return node.height if node else 0
def _update_height(node):
node.height = 1 + max(_h(node.left), _h(node.right))
def _balance_factor(node):
return _h(node.right) - _h(node.left)
def _rotate_left(x):
y = x.right
x.right = y.left
y.left = x
_update_height(x)
_update_height(y)
return y
def _rotate_right(y):
x = y.left
y.left = x.right
x.right = y
_update_height(y)
_update_height(x)
return x
def avl_insert(root, key):
if root is None:
node = Node(key)
node.height = 1
return node
if key < root.key:
root.left = avl_insert(root.left, key)
elif key > root.key:
root.right = avl_insert(root.right, key)
else:
return root
_update_height(root)
bf = _balance_factor(root)
if bf > 1: # right-heavy
if _balance_factor(root.right) < 0:
root.right = _rotate_right(root.right) # RL case
return _rotate_left(root)
if bf < -1: # left-heavy
if _balance_factor(root.left) > 0:
root.left = _rotate_left(root.left) # LR case
return _rotate_right(root)
return root
Key points
- Search, insert, and delete on a BST are all O(height), so the entire performance story of a BST reduces to controlling its height.
- The delete case that needs the most care is the 2-child case: the node cannot simply be removed, a replacement key must be found that preserves the ordering invariant, and the in-order successor (or equivalently, the in-order predecessor) is the only choice that doesn't require restructuring more than one path.
- AVL's rebalancing only ever looks at the path from the inserted node back to the root, keeping a single insert's rebalancing cost proportional to the tree's height, not its size.
Worked example
Building a BST from [5, 3, 8, 2, 4, 7, 9] via repeated bst_insert, an in-order traversal prints [2, 3, 4, 5, 7, 8, 9], confirming the BST property. Deleting 2 (a leaf, the 0-child case) leaves [3, 4, 5, 7, 8, 9]. Deleting 3 next (now a 1-child case, since 3's only remaining child is 4) leaves [4, 5, 7, 8, 9]. Deleting 5, the root (a 2-child case), replaces its key with its in-order successor, 7, then removes the original 7 from the right subtree, leaving [4, 7, 8, 9].
To see the degradation: inserting [1, 2, 3, 4, 5, 6, 7] in sorted order into a plain BST via bst_insert produces a tree of height 7 (a straight chain, one child per node, for n = 7 nodes, the O(n) worst case). Running the same 7 keys through avl_insert instead produces a tree of height 3, and an in-order traversal still prints [1, 2, 3, 4, 5, 6, 7], confirming the rebalancing preserved the BST property while keeping the tree flat.
Trade-offs & pitfalls
Complexity
Plain BST: search, insert, and delete are all O(h), where h is the tree's height; h ranges from O(logn) (balanced) to O(n) (degenerate, such as sorted-order insertion).
AVL: search, insert, and delete are all O(logn) worst case, since the height-balance invariant guarantees h=O(logn) regardless of insertion order; each insert does O(logn) work walking back up, plus at most a constant number of rotations.
Space: O(n) for the tree itself; O(h) additional stack space for the recursive implementations shown here.
Edge cases
- Deleting a node with 2 children whose in-order successor is itself a leaf: the recursive
bst_deletecall on the successor correctly falls into the 0-child case. - Deleting the root: handled the same as any other node, since the function returns the (possibly new) subtree root at every level.
- Inserting a duplicate key: the implementation shown ignores duplicates; a production version needs to decide up front whether duplicates are allowed and where they go if so.
- Empty tree: search and delete both return
Nonesafely; insert on an empty tree creates the first node.
A common bug in from-scratch delete implementations is fixing up the tree's shape but forgetting to also update any augmented metadata (heights, subtree sizes, color bits) on every node along the path back to the root; for AVL specifically, forgetting to update height before computing the balance factor at a node makes every rebalancing decision above it wrong. A second pitfall is choosing the in-order predecessor instead of the in-order successor for the 2-child case inconsistently across an implementation; either works, but mixing them without matching invariant logic can subtly break ordering.
Show what a JSON response for an order resource would look like if it included hypermedia links for the actions currently available on it (for example pay, cancel, and view items). Explain what HATEOAS is supposed to buy a client that the links alone would not otherwise know, and give the concrete reason most public REST APIs today skip full hypermedia even though the specification recommends it.
Sample Answer
Direct answer. HATEOAS (Hypermedia As The Engine Of Application State) means a response includes links describing what the client can legitimately do next from this resource's current state, so the client does not need to hard-code which endpoints exist or which transitions are valid; it follows links the server hands it.
Worked example. For an order in the "pending" state:
{
"id": "ord_123",
"status": "pending",
"total": 4200,
"_links": {
"self": { "href": "/orders/ord_123" },
"items": { "href": "/orders/ord_123/items", "method": "GET" },
"pay": { "href": "/orders/ord_123/pay", "method": "POST" },
"cancel": { "href": "/orders/ord_123/cancel", "method": "POST" }
}
}
The items link is a plain GET that stays present regardless of the order's state, since viewing the line items is never a state-dependent action, unlike pay and cancel, which only appear while the order is actually in a state where they are legal.
Once the order is paid, the server's next response for that same order would include a "ship" link and drop "pay" and "cancel" entirely. The client does not need business logic hard-coded like show a pay button only when status is pending; it just renders whatever links are present.
What this actually buys you. The client-server coupling gets looser in one specific way: valid-transition logic lives on the server, not duplicated in every client. If the business rule for when an order can be cancelled changes (say, cancellation is disabled once payment starts processing, not just once it succeeds), you change it in one place on the server, and every client (web, mobile, a partner's integration) picks up the new behavior automatically the next time they fetch the resource, because the cancel link simply stops appearing rather than each client needing an updated copy of the rule.
Why most public APIs skip it anyway. The honest reason is that hypermedia adds real client-side complexity (parsing and following links instead of calling a URL your team already documented and your SDK already hard-codes) for a benefit that mostly matters when you have many independent, evolving clients that cannot easily be updated in lockstep. Most companies' actual API consumers are their own web and mobile apps, deployed together with the backend, so the decoupling benefit is smaller than it sounds, and clients overwhelmingly prefer a documented, predictable URL they can call directly over a discovery protocol they have to implement. Full HATEOAS survives mostly in specs and prep material, not in most production public APIs, precisely because the cost (client complexity, harder caching of what actions exist) is paid up front while the benefit only shows up much later, if ever.
Trade-offs and pitfalls. Treat HATEOAS as a genuine trade-off you can articulate, not a rule you are expected to follow: if your API has one first-party client you control end-to-end, the coupling HATEOAS avoids barely exists in the first place.
You are moving a production environment from local state to a remote backend shared by the team. What design choices would you make around locking, access control, and failure recovery so concurrent work does not corrupt the environment?
Sample Answer
I would move production to a remote backend that supports both shared access and state locking. State is Terraform’s record of what it created, and locking means only one writer can change that record at a time.
Design choices
- Use one backend per environment, so prod does not share state with dev
- Turn on encryption at rest for the backend storage
- Restrict write access to CI and a small break-glass admin group
- Give most engineers read-only access to plans and state history
- Require an exclusive lock for
apply, with a short timeout and clear failure message
Recovery
I would also enable versioning or history so I can recover a prior state file if an apply fails halfway through. If a run breaks, I would not edit state first. I would inspect the lock, compare the current cloud resources with terraform plan -refresh-only, and then decide whether to fix drift, import an orphan, or roll back.
Example
If a colleague applies from their workstation while CI is planning, the lock should stop the second write. That prevents two people from corrupting the same prod state.
You are designing a library whose public API must evolve over many releases. What rules would you set for version numbers, deprecating old calls, evolving any serialized data, and testing that upgrades do not break existing users?
Sample Answer
The idea in plain words
A library's public API is everything users' code can depend on: exported functions, classes and their documented behaviour, configuration keys, command-line flags, error types and any file or wire format the library writes. For a library the contract is a promise you make with version numbers: semantic versioning (SemVer) writes a version as MAJOR.MINOR.PATCH, where a PATCH release fixes bugs without changing the public API, a MINOR release adds backward-compatible features, and a MAJOR release may break things. The rules below make that promise checkable: define what is public, deprecate before removing, version any stored data and let readers arrive before writers, and test every upgrade path against the previous releases rather than trusting review.
Rule 1: define public, and version accordingly
- Write down what is public (documented symbols, documented behaviour, config keys, data formats) and what is not (anything underscore-prefixed, in an
internalmodule or undocumented). Only the public surface is covered by the promise; mark the rest clearly so people know it can move. - Version bumps:
| Change | Bump |
|---|---|
| Bug fix, no public change | PATCH |
| New function, new optional parameter with a default, new optional config key | MINOR |
| Deprecating something (still works) | MINOR |
| Removing or renaming a public symbol, adding a required parameter, changing a return type, changing a documented default, tightening accepted input | MAJOR |
- A behaviour change that users could notice is breaking even if no signature changed (a default timeout from 30 seconds to 10 seconds). Treat it as MAJOR, or ship it behind a new opt-in parameter in a MINOR and change the default only in a MAJOR.
- Before version 1.0.0 SemVer allows anything to change, so release 1.0.0 as soon as people depend on the library.
Worked example (assumptions)
Start at 2.4.1 and apply six changes:
| # | Change | Class | Release |
|---|---|---|---|
| 1 | Fix an off-by-one in a retry counter | PATCH | 2.4.2 |
| 2 | Add optional timeout parameter (default unchanged) | MINOR | 2.5.0 |
| 3 | Deprecate load_config() in favour of read_config(); both work | MINOR | 2.5.0 |
| 4 | Remove load_config() | MAJOR | 3.0.0 |
| 5 | Change the default timeout from 30 to 10 seconds | MAJOR | 3.0.0 |
| 6 | Add a required parameter to connect() | MAJOR | 3.0.0 |
Changes 2 and 3 can go in one MINOR release. Changes 4, 5 and 6 are held and batched into one MAJOR release. Version path, assuming no other releases and that the 6-month window has passed before the MAJOR ships: 2.4.1, then 2.4.2, then 2.5.0, then 3.0.0, and when a MINOR bump happens the PATCH resets to 0, as does the MINOR when MAJOR bumps.
Rule 2: deprecation before removal
- Announce in a MINOR release: mark the symbol deprecated in code with a runtime warning that names the replacement and the version of removal. Most languages have a mechanism (a warning category, a
@Deprecatedannotation, or a lint attribute). - Document it in the changelog and migration notes, with a before-and-after example.
- Keep it working for a stated minimum (a policy to set; for example at least 6 months, counted from the release that deprecated it), and never remove it in a MINOR or PATCH.
- Remove only in the next MAJOR, which lists every removal.
Example warning text:
DeprecationWarning: load_config() is deprecated since 2.5.0 and will be removed in 3.0.0. Use read_config() instead.
Your own tests should fail on deprecation warnings raised by your own code, so the library does not keep calling its deprecated parts.
Rule 3: evolving serialized data
Anything the library writes (files, caches, messages) outlives a release, and old and new versions will meet on the same data. Rules:
- Put an explicit format version in the data (
"format_version": 1), never infer it. - Readers first, writers later. A release that can read both formats ships one release before the release that writes the new one. That keeps a rollback to the previous release possible, because it still understands the files.
- Unknown fields: readers ignore them, and a library that reads and rewrites data should preserve them rather than drop them.
- Read old formats for as long as you can, and drop one only in a MAJOR with a migration tool.
- Never change the meaning of an existing field (a price in cents becomes dollars); add a new field.
Worked example: format 1 stores "name": "Ada Lovelace"; format 2 stores "given_name" and "family_name".
| Release | Reader | Writer |
|---|---|---|
| 2.5.0 | Reads 1 and 2 | Writes 1 (so 2.4 can still read files) |
| 2.6.0 | Reads 1 and 2 | Writes 2 only when write_format=2 is set |
| 3.0.0 | Reads 1 and 2 | Writes 2 by default |
| 4.0.0 | Drops 1, ships a converter | Writes 2 |
Rule 4: tests that prove upgrades do not break users
Five layers:
- Public API snapshot diff: extract the public surface (symbols, signatures) of the last release and of the build, and fail CI on a removal or a signature change not matched by the version bump. Tools exist for most languages; write your own rule list as in Rule 1.
- Old tests against the new code: run the previous release's test suite (its public-API tests) against the new build. Tests that must change are a break by definition.
- Golden data files: keep real files written by every released version in the repository and check that the new build reads them, and that data it writes can be read by the version you promise to interoperate with (round trip, both directions).
- Downstream builds: build and test a list of known dependent projects against a release candidate before publishing.
- Compatibility matrix: run the suites across the supported language or runtime versions and, where applicable, the oldest and newest supported versions of key dependencies.
Add a release checklist that enforces the bump from the snapshot diff, and publish release candidates so users can test before the final release.
Pitfalls
- Fixing a bug that users depend on in a PATCH and calling it safe: some user will rely on the old behaviour, so state in the changelog what changed.
- Deprecation without a replacement or a date.
- Changing the stored format and the reader in the same release.
- Public API by accident, from users importing internal modules; make internal truly inaccessible where the language allows.
The bump table and the retention periods are illustrations. A real policy also needs a support window for old MAJOR lines (security fixes only, for how long), rules for pre-release versions and for dependency version ranges, and a procedure for an accidental break that already shipped (yank the release, publish a corrected one).
How would you unit test and integration test an event-driven microservice that consumes events and emits events? Describe techniques for mocking producers/consumers, using embedded/local brokers for integration tests, deterministic seeding of events, and validating retry/error-handling behavior in CI pipelines.
Sample Answer
Direct answer
Test an event-driven microservice at three levels: unit tests that mock the producer/consumer boundary entirely so business logic is verified in isolation, integration tests that run against a real embedded or local broker so the actual serialization, publish, and consume path is exercised end to end, and both layers use deterministic, explicitly seeded event fixtures so a failing test points at a real bug rather than a flaky, timing-dependent race. Retry and error-handling behavior specifically needs its own test scenarios, not just happy-path coverage, since that is exactly the logic that is hardest to get right and easiest to leave untested.
Structured elaboration
Mocking producers and consumers for unit tests. At the unit level, replace the actual broker client with a fake/mock that records what was published and lets the test inject arbitrary incoming events directly into the handler function, bypassing the network and serialization entirely. This isolates the test to the service's own business logic: given this event payload, does the handler produce the correct follow-on event(s) and the correct side effects, without needing a running broker at all. Keep these tests fast (milliseconds, no I/O) so they run on every commit.
Embedded or local brokers for integration tests. Unit tests alone miss real failure modes: serialization/deserialization bugs, schema mismatches, or broker-client configuration errors. Integration tests should run against a real broker, using either an embedded in-process broker (a lightweight broker implementation that starts and stops within the test process) or a local broker instance managed by the test runner (started fresh per test run, typically via a container the CI pipeline spins up and tears down). This validates the actual wire format and the actual client library configuration, not just the business logic mocked out from it, catching a class of bug unit tests structurally cannot see.
Deterministic seeding of events. Both layers depend on test fixtures being deterministic: a fixed, version-controlled set of input events with known ids, payloads, and (where ordering matters) a known arrival order, rather than randomly generated data on each run. Deterministic seeding means a failing test reproduces identically every time, which is essential for debugging, and it lets assertions check exact expected output rather than a fuzzy "something happened" check. Where randomness is genuinely useful (for fuzz-style coverage), still pin an explicit random seed so a failure is reproducible from the seed value alone.
Validating retry and error-handling behavior in CI. This needs dedicated test scenarios, not incidental coverage from happy-path tests: a handler that throws on a specific input should be asserted to trigger the configured retry policy (correct backoff behavior, correct retry count before giving up); a handler that keeps failing past the retry budget should be asserted to route the message to wherever poison messages go (commonly a dead-letter queue, DLQ) rather than being silently dropped or retried forever; and a handler that successfully processes a message but crashes before acknowledging it should be tested for what happens on redelivery (this is where consumer-side idempotency gets validated: does reprocessing the same event twice produce the same end state, not a duplicated side effect).
Worked example
A unit test for an order-processing handler: inject a fake order-created event with a fixed id (order-created-test-001) directly into the handler, using a mock producer that just records calls. Assert the handler calls the mock producer exactly once with a payment-attempted event whose order_id matches the input and whose trace_id was propagated from the input event, no real broker involved. An integration test for the same service: start an embedded broker in the test's setup step, publish the same fixed order-created-test-001 event to the real input topic using the real client library, then poll the real output topic (with a bounded timeout, not an unbounded wait) and assert the payment-attempted event actually arrives with the expected fields, this time exercising real serialization and the real broker client configuration. A retry-behavior test: configure the handler's downstream call to always throw for a specific test event id, publish that event, and assert the retry count and backoff delays recorded match the configured policy, then assert the event lands in the DLQ topic after the configured retry budget is exhausted, not before and not never.
Trade-offs and pitfalls
Unit tests that mock too much (for example, mocking the handler's own internal logic instead of just the broker boundary) stop testing anything meaningful; the mock boundary should be the I/O edge (the broker client), not the business logic itself. Integration tests against a shared, always-on broker environment (rather than a fresh embedded/local instance per run) are a common source of flaky tests, since leftover state or concurrent test runs from other branches can pollute topics; prefer an ephemeral broker per test run. Skipping explicit retry/error-handling tests is the most common gap in practice, because it requires deliberately engineering a failure, which is more work to write than a happy-path test, and it's exactly the code path most likely to have a subtle bug (an off-by-one retry count, a DLQ route that's never actually exercised until a real incident). Finally, non-deterministic event ordering in a multi-partition integration test can make assertions flaky if the test assumes a specific arrival order that the broker doesn't actually guarantee across partitions; only assert on ordering the system is actually supposed to guarantee.
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