Google Backend Developer (Junior Level) Interview Preparation Guide
Google's backend developer interview process for junior-level candidates typically consists of a recruiter screening call, followed by 1-2 technical phone screens, and 4-5 onsite interview rounds. The process evaluates coding proficiency, system design thinking (at an introductory level), infrastructure knowledge, and cultural fit. Candidates should prepare for problems involving data structures, algorithms, API design, database fundamentals, and basic distributed systems concepts.
Interview Rounds
Recruiter Screening
What to Expect
Initial conversation with a Google recruiter to assess your background, experience, motivation for the role, and basic qualifications. This is a non-technical discussion focused on your resume, career trajectory, and cultural fit. The recruiter will also explain the interview process, timeline, and answer any questions about the role or company.
Tips & Advice
Be prepared to discuss your most relevant projects and why you're interested in Google. Have 2-3 concrete examples of challenges you solved. Ask thoughtful questions about the team, role responsibilities, and Google's backend infrastructure. Research the specific team you're interviewing for if possible. Be honest about your experience level as a junior candidate—recruiters expect to see learning potential rather than mastery.
Focus Topics
Google Cloud Platform (GCP) Familiarity
Discuss any experience with GCP services (Compute Engine, Cloud Functions, Firestore, Bigtable, etc.). Even basic familiarity is valuable.
Practice Interview
Study Questions
Learning Ability and Growth Mindset
Demonstrate your capacity to learn new technologies and systems. Prepare examples of when you learned something challenging and how you approached it.
Practice Interview
Study Questions
Experience with Backend Technologies and Projects
Prepare to discuss your hands-on experience with server-side development, APIs, databases, and any backend projects you've built. Highlight technologies used and impact of your work.
Practice Interview
Study Questions
Career Motivation and Interest in Backend Development
Articulate why you're interested in backend development and what attracts you to working at Google specifically. Discuss your understanding of what backend developers do.
Practice Interview
Study Questions
Technical Phone Screen - Coding
What to Expect
A 60-minute technical phone interview where you'll solve 1-2 coding problems using an online collaborative editor (like Google Docs or similar). The interviewer will ask you to write clean, working code to solve algorithmic problems focused on data structures and algorithms. You'll be expected to explain your approach, discuss time/space complexity, and handle follow-up questions.
Tips & Advice
Start by clarifying the problem statement and asking clarifying questions. Walk through your approach verbally before coding. Write clean, readable code with meaningful variable names. Test your solution with at least 2-3 test cases (normal case, edge cases). Discuss time and space complexity. If you get stuck, talk through your thought process—interviewers want to see your problem-solving approach, not just the answer. Practice using an online editor beforehand. Don't optimize prematurely; get a working solution first, then optimize if time permits.
Focus Topics
Linked Lists
Understand linked list operations, cycle detection, reverse, merge, and find middle. Practice both singly and doubly linked lists.
Practice Interview
Study Questions
Code Quality and Communication
Write clean, well-structured code with clear variable names and comments. Communicate your thinking process throughout the interview. Handle edge cases and write error-free code.
Practice Interview
Study Questions
Hash Tables and Dictionaries
Understand hash table operations, collision handling, and when to use hash maps for caching or frequency counting problems.
Practice Interview
Study Questions
Sorting and Searching Algorithms
Understand quicksort, mergesort, heapsort, and binary search. Know time/space complexities and when to use each algorithm.
Practice Interview
Study Questions
Trees and Graphs
Master tree traversals (in-order, pre-order, post-order, level-order), binary search trees, and basic graph traversals (BFS, DFS). Understand when to use each.
Practice Interview
Study Questions
Arrays and Strings
Master problems involving array manipulation, searching, sorting, and string operations. Understand two-pointer techniques, sliding windows, and prefix/suffix approaches.
Practice Interview
Study Questions
Technical Phone Screen - Backend Fundamentals
What to Expect
A 45-60 minute technical phone interview focused on backend-specific knowledge rather than pure algorithms. This round typically covers API design, database fundamentals, system architecture basics, or practical backend problems. You may be asked to design a simple REST API, discuss database schema design, or solve a problem specific to backend development.
Tips & Advice
Be ready to discuss trade-offs (consistency vs. availability, SQL vs. NoSQL, synchronous vs. asynchronous processing). Use diagrams or ASCII art to visualize your design. For junior level, focus on practical examples and clear explanations rather than exhaustive coverage. If you don't know something, say so and discuss how you'd approach learning it. Show familiarity with real-world backend systems and explain how different components interact.
Focus Topics
Asynchronous Processing and Message Queues
Understand the difference between synchronous and asynchronous processing. Know basic concepts of message queues (RabbitMQ, Kafka), event-driven architecture, and when to use each.
Practice Interview
Study Questions
Server-Side Caching Strategies
Understand in-memory caching (Redis, Memcached), cache invalidation patterns, TTL, and when caching is beneficial. Know the trade-offs between cache consistency and performance.
Practice Interview
Study Questions
Authentication and Security Basics
Understand JWT tokens, session management, password hashing, HTTPS, CORS, SQL injection prevention, and basic security principles.
Practice Interview
Study Questions
Database Fundamentals (SQL and NoSQL)
Understand relational databases (PostgreSQL, MySQL), NoSQL databases (MongoDB, Redis), schema design, indexing, query optimization, and when to use each type.
Practice Interview
Study Questions
RESTful API Design and HTTP Fundamentals
Understand REST principles, HTTP methods (GET, POST, PUT, DELETE), status codes, headers, and request/response formats. Know how to design clean, intuitive API endpoints.
Practice Interview
Study Questions
Onsite Round 1 - Coding Round
What to Expect
A 60-minute in-person or video interview where you'll solve 1-2 coding problems on a whiteboard or in an online editor. Similar to the phone screen but potentially at a slightly higher difficulty level. Interviewers will assess your problem-solving approach, code quality, and communication skills.
Tips & Advice
Treat this like the phone screen. Think aloud so the interviewer can follow your reasoning. Write code neatly (if on whiteboard). Ask clarifying questions to understand the problem completely. Start with a brute force solution and optimize if time allows. Test your code with examples. Discuss complexity trade-offs. Show confidence in your approach even if you're uncertain—interviewers value clear thinking over perfect answers.
Focus Topics
Backtracking and Recursion
Understand recursive problem-solving, backtracking patterns, and how to avoid infinite recursion. Practice problems like permutations, combinations, and N-Queens.
Practice Interview
Study Questions
Graph Problems (BFS, DFS)
Understand breadth-first search and depth-first search. Practice graph problems involving connectivity, shortest path, cycles, and topological sorting.
Practice Interview
Study Questions
Arrays and Strings
Master problems involving array manipulation, searching, sorting, and string operations. Understand two-pointer techniques, sliding windows, and prefix/suffix approaches.
Practice Interview
Study Questions
Linked Lists and Trees
Understand linked list operations (reversal, cycle detection, merge) and tree traversals (in-order, pre-order, post-order, level-order). Practice both to fluency.
Practice Interview
Study Questions
Onsite Round 2 - System Design (Junior Level)
What to Expect
A 45-60 minute interview focused on basic system design thinking. For junior level, this is not about designing complex distributed systems but rather understanding backend system components and how they interact. You may be asked to design a simple service (e.g., URL shortener basics, simple API backend, or data processing pipeline). Interviewers assess your ability to think through requirements, identify trade-offs, and propose reasonable solutions.
Tips & Advice
Start by asking clarifying questions about requirements, scale, and constraints. Draw a simple architecture diagram showing main components. Discuss technology choices and justify them. For junior level, focus on basic concepts: API layer, business logic, data storage. Avoid over-engineering. Discuss potential bottlenecks and basic scaling strategies. It's okay to admit uncertainty—interviewers expect junior candidates to know basics, not advanced distributed systems. Show your thinking process more than perfect solutions.
Focus Topics
Caching in System Design
Understand when and how to add caching layers (Redis, Memcached). Discuss cache invalidation strategies and cache-aside pattern.
Practice Interview
Study Questions
API Design and Rate Limiting
Understand RESTful API design principles, versioning strategies, error handling, and basic rate limiting concepts to prevent abuse.
Practice Interview
Study Questions
Database Selection (SQL vs. NoSQL Basics)
Understand when to use relational databases vs. NoSQL databases. Know basic trade-offs: ACID properties, consistency models, scalability characteristics.
Practice Interview
Study Questions
Scalability Concepts (Horizontal vs. Vertical Scaling)
Understand the difference between scaling up (vertical) and scaling out (horizontal). Know basic concepts of load balancing, replication, and sharding.
Practice Interview
Study Questions
Basic System Architecture and Components
Understand the basic layers of a backend system: API layer, business logic layer, data persistence layer. Know how these components interact and when to add additional layers.
Practice Interview
Study Questions
Onsite Round 3 - Backend Domain Expertise
What to Expect
A 60-minute technical interview focused on practical backend development skills and deeper understanding of specific technologies mentioned in the job description (Node.js, Python, Java, PostgreSQL, MongoDB, AWS/Azure, etc.). You may be asked to solve a practical backend problem, discuss architecture patterns, debug code, or discuss how you've implemented specific backend features.
Tips & Advice
This round tests practical backend skills, not just theory. Be ready to discuss real projects you've built. If asked to write code, focus on production-quality code with proper error handling. Understand the technologies you list in your resume deeply. Discuss trade-offs in your architectural decisions. Show you understand how backend systems handle real-world challenges like failure, concurrency, and data consistency. Ask clarifying questions about business requirements before diving into technical solutions.
Focus Topics
Infrastructure and Deployment Basics
Understand containerization (Docker), basic deployment concepts, environment configuration, and monitoring. Know how applications are deployed to cloud platforms.
Practice Interview
Study Questions
Building and Testing REST APIs
Understand how to build robust REST APIs, including input validation, error handling, pagination, and authentication. Know how to write unit tests and integration tests for APIs.
Practice Interview
Study Questions
Concurrency, Threading, and Async Patterns
Understand concurrency concepts in your chosen language (promises/async-await in JavaScript, threading in Java, asyncio in Python). Know when to use each pattern and how to avoid race conditions.
Practice Interview
Study Questions
Database Design and Optimization
Understand schema design, indexing strategies, query optimization, and common performance issues. Know how to diagnose slow queries and improve database performance.
Practice Interview
Study Questions
Server-Side Programming Language Proficiency
Demonstrate strong proficiency in at least one backend language (Node.js, Python, Java, etc.). Understand language features, standard libraries, package management, and best practices for that language.
Practice Interview
Study Questions
Onsite Round 4 - Behavioral (Google Culture Fit)
What to Expect
A 45-60 minute interview focused on assessing your alignment with Google's culture, values, and working style. Interviewers will ask behavioral questions about your experiences, how you work in teams, handle conflict, show initiative, and demonstrate learning. Google looks for engineers who embody their values: doing the right thing, collaboration, and continuous improvement.
Tips & Advice
Use the STAR method (Situation, Task, Action, Result) for behavioral questions. Prepare 4-6 strong stories showcasing different competencies. Be authentic and avoid rehearsed answers. Give specific examples with concrete outcomes. Discuss what you learned from experiences. For junior level, interviewers expect humility, willingness to learn, and ability to work well with others. Discuss how you've asked for help when needed. Show curiosity about problems and genuine passion for backend development. Ask thoughtful questions about team culture and values.
Focus Topics
Communication and Documentation
Discuss how you communicate complex technical ideas to non-technical stakeholders. Show you understand the importance of clear documentation and knowledge sharing.
Practice Interview
Study Questions
Adaptability and Continuous Learning
Share examples of when you learned new technologies or adapted to changing requirements. Show enthusiasm for learning and growing in your career.
Practice Interview
Study Questions
Initiative and Ownership
Share examples of when you took on additional responsibility, solved a problem without being asked, or improved a process. Show that you think beyond your assigned tasks.
Practice Interview
Study Questions
Teamwork and Collaboration
Prepare stories demonstrating your ability to work effectively in teams, contribute to group goals, and support colleagues. Discuss how you communicate and handle disagreements constructively.
Practice Interview
Study Questions
Handling Challenges and Learning from Failure
Prepare examples of technical or professional challenges you faced, how you approached them, and what you learned. Show growth mindset and resilience.
Practice Interview
Study Questions
Onsite Round 5 - Technical Depth / Manager Round
What to Expect
This final onsite round typically involves either a deeper technical discussion with a senior engineer or a conversation with the hiring manager. If technical, you may discuss complex projects you've built, your approach to architectural decisions, or dive deep into specific backend technologies. If with a manager, the focus is on your career goals, how you work, team dynamics, and long-term fit with the organization.
Tips & Advice
If technical: prepare to discuss your most complex project in detail. Be ready to explain trade-offs you made and why. Discuss what you'd do differently if you could redesign the system. For manager round: be genuine about your career goals and interests. Ask about the team dynamics, the manager's management style, and growth opportunities. Discuss how you prefer to work and what motivates you. Show interest in Google's products and culture. Listen carefully to understand the role and team before diving into your own talking points.
Focus Topics
Working Style and Team Collaboration
If in manager round, discuss how you prefer to work, your communication style, how you handle feedback, and your approach to teamwork.
Practice Interview
Study Questions
Code Quality and Best Practices
Discuss your approach to writing maintainable code, code reviews, testing strategies, and following best practices. Show you care about code quality.
Practice Interview
Study Questions
Career Growth and Learning Goals
If in manager round, discuss your career aspirations, areas you want to grow in, and how you approach continuous learning. Be genuine about your motivations.
Practice Interview
Study Questions
Performance Optimization and Debugging
Discuss real examples of performance issues you've debugged and fixed. Explain your methodology for identifying bottlenecks and improving performance.
Practice Interview
Study Questions
Complex Project Experience and Architectural Decisions
Be prepared to discuss your most complex backend project in depth. Explain the architecture, technology choices, challenges, and how you solved problems. Discuss trade-offs and what you'd do differently.
Practice Interview
Study Questions
Frequently Asked Backend Developer Interview Questions
Design an external merge sort to sort a 500GB file on disk given only 2GB of RAM. Describe run generation, run size selection, k-way merge strategy, disk I/O optimization, and how to recover from failures mid-sort. Provide rough cost estimates for passes over the data.
Sample Answer
Direct answer
Sort in two phases. Phase 1, run generation: read the file in chunks that fit in memory (about 1.5 GiB of the 2 GiB), sort each chunk in memory, and write it back as a sorted run (a sorted piece of the data stored on disk). 500 GiB gives about 334 runs. Phase 2, merge: open all 334 runs at once with a modest read buffer each (about 5 MiB) and merge them with a min-heap into the final file in one pass. That is two passes over the data in total, each reading and writing all 500 GiB, so about 2,000 GiB of I/O (estimated: roughly 3 hours on a 200 MB/s disk, 36 minutes at 1 GB/s, 12 minutes at 3 GB/s). Write every run to a temporary name and rename it when complete, so a crash costs at most the run being written; delete inputs only after their output is finished.
The idea in plain words
A normal sort needs all the data in memory. The trick for data bigger than memory is that merging sorted lists needs only the front of each list in memory. So split the file into pieces that do fit, sort each piece, and then merge the sorted pieces with a heap that always yields the smallest front item. Terms: a run is a sorted piece of the data stored on disk. Fan-in is how many runs one merge reads at once. A pass is one full read and write of the data. Sequential I/O is reading or writing a file in order, which disks do far faster than jumping around (a hard disk spends about 10 ms per jump in the estimate below). Stable means records with equal keys keep their input order. A checksum is a short number computed from the bytes of a file, so that a changed file gives a different number. fsync is the operating-system call that forces data a program has written out of the OS cache and onto the disk, so that a power cut after the call cannot lose it.
The two-phase plan with a fan-in the memory allows is what an interview normally asks for; replacement selection, compression, time-based partitioning and restartable partitioned merges are refinements that matter mainly for roles that run large batch pipelines.
Brute force and why it is not enough
Loading 500 GiB into 2 GiB of RAM fails, and letting the operating system swap a full in-memory sort to disk makes the sort touch pages in random order, which disks handle badly (swap thrashing: the machine spends its time moving memory pages to and from disk instead of sorting). External merge sort avoids this by making every disk access large and sequential.
Run generation and run size
Read 1.5 GiB chunks (the other 0.25 GiB is an assumption for the operating system, the program and I/O buffers), sort each in memory, write each as a run. The number of runs is the file size divided by the run size, so bigger runs mean fewer runs, which means larger merge buffers and fewer passes. The cost model in section 6 of the output shows the trade-off (the 1 MiB minimum buffer is an assumption that keeps reads reasonably large):
| Run size | Runs | Merge buffer per run (one merge of all runs, 1.75 GiB shared by the runs plus one output buffer) | Merge passes |
|---|---|---|---|
| 1.50 GiB | 334 | 5.35 MiB | 1 |
| 0.75 GiB | 667 | 2.68 MiB | 1 |
| 0.25 GiB | 2,000 | 0.90 MiB | 2 |
The buffer column is 1.75 GiB divided by (runs + 1): 1.75 GiB / 335 = 5.35 MiB, where the +1 is the buffer that collects the merged output (dividing by 334 alone would give 5.37 MiB, also printed). The third row has a 0.90 MiB buffer, below the assumed 1 MiB minimum, so one merge of 2,000 runs is not used. The program prints the maximum fan-in at 1 MiB buffers (1,791 runs per merge): pass 1 merges 2,000 runs into 2 runs and pass 2 merges those 2 into 1, hence 2 merge passes.
Smaller runs are useful if you overlap work: while one chunk is being sorted on the CPU, the next is being read and the previous is being written, which needs memory for two or three chunks at once (double buffering: while one buffer is being processed, the next one is being filled). With two chunks in flight, the 0.75 GiB run size uses 1.5 GiB of the 1.75 GiB available and still gives a single merge pass; three chunks of 0.75 GiB would not fit, so a three-stage overlap needs smaller runs.
An alternative is replacement selection: keep a heap of M records, repeatedly output the smallest record that is not smaller than the last one output, and read a new record into the heap. A record read in that is smaller than the one just output cannot extend the current run, so it is tagged for the next run and waits. Section 7 prints this for a heap of 3 records and the input 4 7 5 2 8 1: the heap starts with 4, 5 and 7; after 4 leaves, the new record 2 is smaller than 4 and waits for run 1; after 5 leaves, the new record 8 is not smaller than 5, so it joins run 0; after 7 leaves, the new record 1 waits for run 1; then 8 leaves. Run 0 is 4 5 7 8 (four records from memory for three) and run 1 is 1 2. Chunk sorting the same input makes runs of exactly 3 records. Section 4 measures it on larger data: on random input runs average 1.96 times the memory size (51 runs instead of 100 for M = 1,000 and 100,000 records), and on input that is nearly sorted (timestamps that arrive almost in order) it produced a single run where chunk sorting makes 100. That helps when data arrives roughly in time order, as event logs do.
K-way merge
Open all runs, give each a read buffer, and keep a min-heap holding each run's current front record. Pop the smallest, write it to the output buffer, and refill from that run's buffer, which is the only time the disk is touched. Each record costs about log2(R) comparisons for R runs. Section 8 prints a merge of two runs, 1 4 9 and 2 3 10: before each output the heap holds the front record of every run, the smallest leaves, and the next record of that run takes its place. One merge pass turns R runs into ceil(R / F) runs for fan-in F (each group of F runs becomes one run), so the pass count is the number of times R must be divided by F, rounding up, to reach 1, which is ceil(log base F of R), and the whole sort takes 1 + that many passes. The program counts it with integer ceiling division rather than math.log, because floating-point log rounds some exact powers up: math.ceil(math.log(125, 5)) is 4, although 125 runs at fan-in 5 need 3 passes. The demo uses a fan-in of 8 with 20 runs: ceil(20 / 8) = 3 runs, then ceil(3 / 8) = 1 run, so it needs 2 merge passes (section 2), 3 passes overall, equal to the predicted ceil(log_8(20)) = 2 merge passes plus the run-generation pass.
Code: a working external sort at small scale
The program sorts 200,000 key,id lines, 10,000 per run (standing in for 1.5 GiB) with a fan-in of 8 (standing in for the buffer limit), injects a crash, restarts, and checks the output against a stable sorted() of the same file, including the order of tied keys. The checks and estimates are printed.
import heapq
import itertools
import math
import os
import random
import tempfile
import zlib
RUN_RECORDS = 10_000 # stands in for "as many records as fit in RAM"
FAN_IN = 8 # stands in for "as many runs as the merge buffers allow"
class SimulatedCrash(Exception):
pass
def sort_key(line):
return int(line.split(",", 1)[0])
def write_atomically(path, lines):
"""Write to a temp name, flush to disk, then rename. A reader never sees a half-written run."""
tmp = path + ".tmp"
with open(tmp, "w") as f:
f.writelines(lines)
f.flush()
os.fsync(f.fileno())
os.replace(tmp, path)
def generate_runs(input_path, workdir, crash_after=None):
"""Pass 0: sort RUN_RECORDS lines at a time. Existing finished runs are skipped on restart."""
runs, made, skipped = [], 0, 0
with open(input_path) as f:
index = 0
while chunk := list(itertools.islice(f, RUN_RECORDS)):
path = os.path.join(workdir, f"run0_{index:04d}.txt")
if os.path.exists(path):
skipped += 1 # finished before the crash
else:
if crash_after is not None and made == crash_after:
with open(path + ".tmp", "w") as partial:
partial.writelines(chunk[:100]) # a half-written file is left behind
raise SimulatedCrash(f"crashed while writing run {index}")
write_atomically(path, sorted(chunk, key=sort_key))
made += 1
runs.append(path)
index += 1
return runs, made, skipped
def merge_runs(paths, out_path):
files = [open(p) for p in paths]
try:
write_atomically(out_path, heapq.merge(*files, key=sort_key))
finally:
for f in files:
f.close()
def passes_needed(runs, fan_in):
"""ceil(log_fan_in(runs)) by repeated integer ceiling division; math.log can round an exact power up."""
count = 0
while runs > 1:
runs = -(-runs // fan_in)
count += 1
return count
def merge_passes(runs, workdir):
passes, level = 0, 0
while len(runs) > 1:
level += 1
merged = []
for g in range(0, len(runs), FAN_IN):
out = os.path.join(workdir, f"run{level}_{g // FAN_IN:04d}.txt")
merge_runs(runs[g:g + FAN_IN], out)
merged.append(out)
for p in runs: # inputs are deleted only after the whole pass finished
os.remove(p)
print(f" merge pass {level}: {len(runs)} run(s) -> {len(merged)} run(s), fan-in {FAN_IN}")
runs, passes = merged, passes + 1
return runs[0], passes
def replacement_selection_runs(values, memory):
"""Heap of `memory` items; an item smaller than the last output waits for the next run."""
it = iter(values)
heap = [(0, v) for v in itertools.islice(it, memory)]
heapq.heapify(heap)
run_lengths, current, length = [], 0, 0
while heap:
run, v = heapq.heappop(heap)
if run != current:
run_lengths.append(length)
current, length = run, 0
length += 1
nxt = next(it, None)
if nxt is not None:
heapq.heappush(heap, (run if nxt >= v else run + 1, nxt))
run_lengths.append(length)
return run_lengths
def trace_replacement_selection(values, memory):
"""Print every step of replacement selection: what leaves the heap and what waits."""
it = iter(values)
heap = [(0, v) for v in itertools.islice(it, memory)]
heapq.heapify(heap)
print(f" start, heap holds (run, value): {sorted(heap)}")
while heap:
run, v = heapq.heappop(heap)
nxt = next(it, None)
note = "no input left"
if nxt is not None:
tag = run if nxt >= v else run + 1
heapq.heappush(heap, (tag, nxt))
note = f"read {nxt}, joins run {tag}" + (" (smaller than {}, so it waits)".format(v) if tag != run else "")
print(f" output {v} to run {run}; {note}; heap {sorted(heap)}")
def trace_merge(runs):
"""Print the front record of every run before each output record."""
heap = [(r[0], i, 0) for i, r in enumerate(runs)]
heapq.heapify(heap)
while heap:
fronts = sorted(item[0] for item in heap)
value, run, pos = heapq.heappop(heap)
print(f" fronts {fronts} -> output {value} (from run {run})")
if pos + 1 < len(runs[run]):
heapq.heappush(heap, (runs[run][pos + 1], run, pos + 1))
if __name__ == "__main__":
rng = random.Random(40)
n = 200_000
with tempfile.TemporaryDirectory() as work:
input_path = os.path.join(work, "input.txt")
with open(input_path, "w") as f: # "key,arrival_id": 1,000 keys, so many ties
f.writelines(f"{rng.randrange(1000)},{i}\n" for i in range(n))
run_dir = os.path.join(work, "runs")
os.mkdir(run_dir)
print("1. run generation, with a crash after 7 finished runs")
try:
generate_runs(input_path, run_dir, crash_after=7)
except SimulatedCrash as err:
print(" first attempt:", err, "| leftover files:", sorted(x for x in os.listdir(run_dir) if x.endswith(".tmp")))
for leftover in (x for x in os.listdir(run_dir) if x.endswith(".tmp")):
os.remove(os.path.join(run_dir, leftover)) # restart discards unfinished temp files
runs, made, skipped = generate_runs(input_path, run_dir)
print(f" restart: {skipped} runs reused, {made} runs written, {len(runs)} runs total")
print("2. merge passes")
final, passes = merge_passes(runs, run_dir)
print(f" total passes over the data: 1 run generation + {passes} merge = {1 + passes}")
print(f" predicted merge passes: ceil(log_{FAN_IN}({len(runs)})) = {passes_needed(len(runs), FAN_IN)}")
with open(input_path) as f:
expected = sorted(f, key=sort_key) # stable reference sort, fits here because n is small
with open(final) as f:
got = f.readlines()
print("3. output equals the stable reference sort, including the order of tied keys:", got == expected)
print("4. run formation: chunk sort versus replacement selection (M = 1,000 records of memory)")
memory, count = 1_000, 100_000
values = [rng.random() for _ in range(count)]
lengths = replacement_selection_runs(values, memory)
print(f" random input : chunk sort {count // memory} runs; replacement selection {len(lengths)} runs, "
f"mean length {sum(lengths) / len(lengths):.0f} = {sum(lengths) / len(lengths) / memory:.2f} x M")
jittered = [i + rng.uniform(-300, 300) for i in range(count)] # nearly sorted, like timestamps
lengths = replacement_selection_runs(jittered, memory)
print(f" nearly sorted : chunk sort {count // memory} runs; replacement selection {len(lengths)} run(s)")
print("5. compressing a run (zlib level 1) of 10,000 'timestamp,user,event' lines")
rng2 = random.Random(1)
lines = [f"{1_700_000_000 + i * 3 + rng2.randrange(3)},user{rng2.randrange(500)},click\n" for i in range(RUN_RECORDS)]
shuffled = list(lines)
rng2.shuffle(shuffled)
raw = len("".join(lines).encode())
print(f" raw {raw:,} bytes; compressed in timestamp order {len(zlib.compress(''.join(lines).encode(), 1)):,}; "
f"compressed in random order {len(zlib.compress(''.join(shuffled).encode(), 1)):,}")
print("6. cost model for 500 GiB with 2 GiB of RAM (ESTIMATE: parameters are assumptions)")
GiB, MiB = 2**30, 2**20
data, ram, os_and_process = 500 * GiB, 2 * GiB, 0.25 * GiB
record = 100
for run_size in (1.5 * GiB, 0.75 * GiB, 0.25 * GiB):
runs_n = math.ceil(data / run_size)
buffers = (ram - os_and_process) / (runs_n + 1)
fan_in = int((ram - os_and_process) // (1 * MiB)) - 1 # smallest useful buffer: 1 MiB
merge_passes_n = passes_needed(runs_n, fan_in)
print(f" run size {run_size / GiB:>4.2f} GiB: {runs_n:>4} runs, merge buffer {buffers / MiB:5.2f} MiB each "
f"for a single merge, max fan-in at 1 MiB buffers {fan_in}, merge passes {merge_passes_n}")
passes_total = 2
moved = passes_total * 2 * data
print(f" 2 passes, each reads and writes everything: {moved / GiB:,.0f} GiB moved")
for name, rate in (("HDD 200 MB/s", 200e6), ("SSD 1 GB/s", 1e9), ("NVMe 3 GB/s", 3e9)):
print(f" at {name:<13} one shared device: {moved * 1.0 / rate / 3600:5.2f} hours")
records = data / record
print(f" CPU: {records:.2e} records; run sorting ~ {records * math.log2(1.5 * GiB / record):.2e} comparisons, "
f"334-way merge ~ {records * math.log2(334):.2e} comparisons")
seek, rate, buf = 0.010, 200e6, 5.35 * MiB
print(f" HDD merge efficiency with a 5.35 MiB buffer and a {seek * 1000:.0f} ms seek: "
f"{(buf / rate) / (buf / rate + seek):.0%} of streaming speed")
print(f" buffer arithmetic: (2 - 0.25) GiB / (334 runs + 1 output buffer) = "
f"{(ram - os_and_process) / 335 / MiB:.2f} MiB; without the output buffer "
f"{(ram - os_and_process) / 334 / MiB:.2f} MiB")
print(f" 2,000 runs but at most {fan_in} runs per merge: pass 1 makes {math.ceil(2000 / fan_in)} runs, "
f"pass 2 makes {math.ceil(math.ceil(2000 / fan_in) / fan_in)}")
print("7. replacement selection by hand: memory for 3 records, input 4 7 5 2 8 1")
trace_replacement_selection([4, 7, 5, 2, 8, 1], 3)
print(" chunk sort of the same input would make", [sorted([4, 7, 5]), sorted([2, 8, 1])])
print("8. merging two sorted runs with a heap")
trace_merge([[1, 4, 9], [2, 3, 10]])
Output (python:3.12):
1. run generation, with a crash after 7 finished runs
first attempt: crashed while writing run 7 | leftover files: ['run0_0007.txt.tmp']
restart: 7 runs reused, 13 runs written, 20 runs total
2. merge passes
merge pass 1: 20 run(s) -> 3 run(s), fan-in 8
merge pass 2: 3 run(s) -> 1 run(s), fan-in 8
total passes over the data: 1 run generation + 2 merge = 3
predicted merge passes: ceil(log_8(20)) = 2
3. output equals the stable reference sort, including the order of tied keys: True
4. run formation: chunk sort versus replacement selection (M = 1,000 records of memory)
random input : chunk sort 100 runs; replacement selection 51 runs, mean length 1961 = 1.96 x M
nearly sorted : chunk sort 100 runs; replacement selection 1 run(s)
5. compressing a run (zlib level 1) of 10,000 'timestamp,user,event' lines
raw 247,796 bytes; compressed in timestamp order 56,532; compressed in random order 67,146
6. cost model for 500 GiB with 2 GiB of RAM (ESTIMATE: parameters are assumptions)
run size 1.50 GiB: 334 runs, merge buffer 5.35 MiB each for a single merge, max fan-in at 1 MiB buffers 1791, merge passes 1
run size 0.75 GiB: 667 runs, merge buffer 2.68 MiB each for a single merge, max fan-in at 1 MiB buffers 1791, merge passes 1
run size 0.25 GiB: 2000 runs, merge buffer 0.90 MiB each for a single merge, max fan-in at 1 MiB buffers 1791, merge passes 2
2 passes, each reads and writes everything: 2,000 GiB moved
at HDD 200 MB/s one shared device: 2.98 hours
at SSD 1 GB/s one shared device: 0.60 hours
at NVMe 3 GB/s one shared device: 0.20 hours
CPU: 5.37e+09 records; run sorting ~ 1.29e+11 comparisons, 334-way merge ~ 4.50e+10 comparisons
HDD merge efficiency with a 5.35 MiB buffer and a 10 ms seek: 74% of streaming speed
buffer arithmetic: (2 - 0.25) GiB / (334 runs + 1 output buffer) = 5.35 MiB; without the output buffer 5.37 MiB
2,000 runs but at most 1791 runs per merge: pass 1 makes 2 runs, pass 2 makes 1
7. replacement selection by hand: memory for 3 records, input 4 7 5 2 8 1
start, heap holds (run, value): [(0, 4), (0, 5), (0, 7)]
output 4 to run 0; read 2, joins run 1 (smaller than 4, so it waits); heap [(0, 5), (0, 7), (1, 2)]
output 5 to run 0; read 8, joins run 0; heap [(0, 7), (0, 8), (1, 2)]
output 7 to run 0; read 1, joins run 1 (smaller than 7, so it waits); heap [(0, 8), (1, 1), (1, 2)]
output 8 to run 0; no input left; heap [(1, 1), (1, 2)]
output 1 to run 1; no input left; heap [(1, 2)]
output 2 to run 1; no input left; heap []
chunk sort of the same input would make [[4, 5, 7], [1, 2, 8]]
8. merging two sorted runs with a heap
fronts [1, 2] -> output 1 (from run 0)
fronts [2, 4] -> output 2 (from run 1)
fronts [3, 4] -> output 3 (from run 1)
fronts [4, 10] -> output 4 (from run 0)
fronts [9, 10] -> output 9 (from run 0)
fronts [10] -> output 10 (from run 1)
Failure recovery
- Atomic runs. A run is written to
name.tmp, flushed withfsync, then renamed to its final name. The crash in section 1 leavesrun0_0007.txt.tmpbehind; the restart deletes.tmpfiles, keeps the 7 finished runs, and writes only the other 13. The simulated crash writes its partial file under the.tmpname, aswrite_atomicallywould; a partial file under the final name would be found by the restart and reused as a finished run, which is exactly what the rename prevents. At real scale a crash during run generation costs at most one run (about 1.5 GiB of sorting). - Delete inputs late. Merge inputs are removed only after the entire pass has produced its outputs, so a crash during a pass can be rerun from the same inputs.
- The merge is the expensive part to lose. A single 334-way merge writes 500 GiB; a crash near the end would repeat it. One design that makes the merge restartable is to split the key range into partitions: take a random sample of keys from the runs, sort it, and use evenly spaced keys from the sorted sample as splitter keys (boundaries, so partition i holds the keys between splitter i-1 and splitter i). Each partition merges the matching slice of every run (found by binary search in each run) into its own output file, and the file is renamed when done. Partitions are independent tasks, so they can run in parallel, and after a crash only the partitions without a finished file are redone. The code above demonstrates the restart only for run generation.
- Validate. Record the input's size and checksum, record counts per run, and compare total records in and out. Rebuild everything if the input file changed.
Parallelism and I/O batching
- Sort chunks on several cores at once (chunk sorts are independent), limited by memory: every chunk being sorted needs its share of RAM.
- Overlap read, sort and write with double buffering so the disk and the CPU are both busy.
- Use large sequential reads and writes (several MiB), and put input, runs and output on separate devices if possible so reads do not interrupt writes. Section 6 estimates that a 5.35 MiB buffer with a 10 ms seek on a 200 MB/s disk reaches about 74 percent of streaming speed (streaming speed means the disk's rate when reading in one long sequential stretch with no jumps), which is why buffers cannot be tiny.
- Prefetch the next buffer of each run while the heap consumes the current one.
Compression of runs
Compressing runs trades CPU for I/O and pays off when the sort is I/O-bound. Section 5 compresses 10,000 timestamped event lines with zlib level 1: 247,796 raw bytes become 56,532 when the lines are in timestamp order and 67,146 in random order, so sorting helps compression. The ratio depends entirely on the data; measure on yours. Decompression adds CPU to the merge, so confirm the sort stays I/O-bound.
Sorting by timestamp for analytics
Event data is usually written roughly in time order, so the input is nearly sorted and replacement selection (above) yields long runs. Often the better design is to avoid one global sort: store data partitioned by hour or day and sort each partition separately, which needs no merge across partitions. Use a compact binary sort key (for example timestamp plus a sequence number, which also makes the order deterministic) rather than parsing text on every comparison.
Cost estimates
All of section 6 is an ESTIMATE from stated parameters (2 GiB RAM, 0.25 GiB reserved, 100-byte records, shared device bandwidth, and decimal MB/s rates). With two passes, the volume is 2 * 2 * 500 = 2,000 GiB moved, which takes 2.98 hours at 200 MB/s, 0.60 hours at 1 GB/s and 0.20 hours at 3 GB/s. CPU is about 5.37 billion records: run sorting is about 1.29e11 comparisons and the 334-way merge about 4.5e10, about 1.7e11 comparisons in all, enough CPU work that the parallelism above matters. If memory shrinks so that runs outnumber the fan-in, the sort gains a merge pass and about half again as much I/O (3,000 GiB for three passes).
Edge cases and common mistakes
- Ties: the demo's output equals the stable reference including tie order; if downstream needs a stable result, order tied records by arrival id.
- Mistake: tiny read buffers, which turn the merge into random I/O.
- Mistake: deleting runs before the merge output is complete.
- Mistake: allocating all of RAM to the chunk and none to buffers.
Running the code
python:3.12, standard library only
save the code above as external_sort.py
python external_sort.py
Describe a comprehensive security and compliance checklist for production deployments: secrets management, image signing and provenance, vulnerability scanning, RBAC and least privilege, audit logs, immutable infrastructure, patching policies, and evidence collection for audits. Explain trade‑offs between release speed and implementing these controls.
Sample Answer
A comprehensive security and compliance checklist for production deployments needs to cover the full path from what's in the artifact, to how it was produced, to who's allowed to approve it moving, since a gap at any one of those layers undermines the guarantees the others provide.
The checklist
Secrets management: no plaintext secrets in the artifact or its configuration; all runtime secrets injected via a secrets manager with short-lived, scoped credentials, following the patterns discussed throughout this topic. Image signing and provenance: the artifact is signed, and its provenance (what built it, from what source, when) is attached and verifiable, not merely claimed. Vulnerability scanning: the artifact has passed SCA and container-image scanning with no unaddressed CRITICAL finding, or has an explicit, time-boxed, approved exception on record. RBAC (role-based access control) and least privilege: the deployment identity itself has only the permissions needed to deploy this specific service, and production access more broadly follows a documented, reviewed access model rather than broad, shared credentials. Audit logs: every deployment action (who triggered it, what was deployed, when, and the outcome) is captured in an immutable, queryable log. Immutable infrastructure: the deployment replaces infrastructure with a new, versioned image rather than patching a running instance in place, so the deployed state always traces back to a specific, auditable build. Patching policies: a defined cadence and SLA for applying security patches to base images and dependencies, verified as actually being followed, not just documented as a policy. Evidence collection for audits: the artifacts above (signatures, scan results, approval records, access logs) are retained in a form an auditor can review without requiring a special, one-off data-gathering effort.
Trade-offs between release speed and implementing these controls
Every item on this checklist has a real velocity cost when first implemented (signing and scanning add pipeline time, RBAC design takes real engineering effort, audit-log retention has its own storage and tooling cost), but nearly every one of these, once built, becomes close to free on a per-deployment basis: the marginal cost of THIS deployment being signed, scanned, and logged, given the infrastructure already exists, is small, which is why the honest framing for a team weighing this trade-off is that the real cost is the one-time investment to build the capability, not an ongoing per-release tax. The controls most worth prioritizing first, given limited time, are the ones that are cheapest to build relative to the risk they close (secret scanning and basic signing) versus the ones that take longer to mature (a fully documented, reviewed RBAC model across every production system), which argues for a staged rollout of this checklist itself rather than treating it as an all-or-nothing bar every deployment must clear from day one.
Trade-offs
Treating this as a staged capability build, rather than an immediate, complete gate, means some deployments proceed for a period without every item on the checklist fully in place; that's an honest, deliberate trade for the same reason discussed for shift-left rollouts elsewhere in this topic: demanding full compliance from day one either blocks legitimate work at a team not yet ready for it, or gets quietly bypassed, neither of which actually improves the organization's real security posture.
Describe Java's HashMap implementation (post-Java 8): internal table of Node<K,V>, how load factor and threshold work (default loadFactor=0.75), when chains get converted into balanced trees, and how hashCode() and equals() are used. Explain pitfalls such as mutable keys and the effect of bad hashCode implementations.
Sample Answer
Direct answer
Since Java 8, HashMap stores entries in an array of buckets, each normally a linked list of
Node<K,V> objects; it resizes (doubles capacity) once the entry count exceeds capacity times the
load factor (default 0.75), and, as a worst-case safety net, converts ("treeifies") any single
bucket's chain into a small balanced red-black tree once that one bucket grows past 8 entries in a
sufficiently large table.
Structured elaboration
From hashCode to bucket index. HashMap doesn't use a key's raw hashCode() directly as the
index. It first applies a supplemental "hash spreading" step (XOR-ing the hash with itself shifted
right by 16 bits) specifically to mix higher bits into the lower bits, since the actual index
computation is hash & (capacity - 1) (capacity is always a power of two, so this bitmask is
equivalent to, but much cheaper than, a modulo), which only ever looks at the LOW bits of the hash;
without the spreading step, two keys whose hashCodes only differ in high bits would collide on every
capacity that happens to be smaller than that difference.
Load factor and resize. Default loadFactor = 0.75 and default initial capacity 16 means a
resize (doubling capacity, then rehashing every entry) fires once the 13th entry is inserted (16 * 0.75
= 12, so the map resizes on exceeding that threshold). This is the same load-factor/resize mechanism any hash table needs generically; HashMap's specific default is 0.75 with
doubling.
Treeification. Once a single bucket's chain length exceeds TREEIFY_THRESHOLD (8 entries), AND
the table's total capacity is at least MIN_TREEIFY_CAPACITY (64), that one bucket converts from a
linked list to a small red-black tree, bounding THAT bucket's worst-case lookup at O(log n) instead of
O(n). Below capacity 64, HashMap prefers to resize the whole table first (since a small table with one
long bucket is more likely just needing more buckets overall, not a genuinely pathological
distribution), only treeifying once the table is already reasonably large and a bucket is STILL long
after that.
Why hashCode/equals correctness matters more here than almost anywhere else. Every one of the
mechanisms above (bucket index selection, chain traversal, treeified-tree comparison) depends on
hashCode() being consistent with equals() for every key ever inserted; violating that contract doesn't just risk a collision, it can make an entry
permanently unfindable.
Worked example
Inserting keys whose hashCode() values are 0x0000FFFF and 0xFFFF0000 into a HashMap of capacity
16 (capacity - 1 = 0x0000000F): a naive hash & (capacity-1) on the RAW hashCode gives
0x0000FFFF & 0xF = 0xF for the first and 0xFFFF0000 & 0xF = 0x0 for the second, no collision, by
coincidence. But two keys with hashCodes 0x00010000 and 0x00020000 (differing only in bits far
above the low 4 bits actually used by a capacity-16 mask) BOTH give hash & 0xF = 0x0, an unnecessary
collision a wider mask would have avoided if it could see those higher bits at all; the supplemental
hash ^ (hash >>> 16) spreading step exists specifically to fold higher-order bit differences down
into the low bits the mask actually inspects, reducing exactly this class of avoidable collision.
Trade-offs and pitfalls
A common shallow answer describes ONLY the chaining/collision behavior without mentioning the
capacity-must-be-a-power-of-two design (and the resulting bitmask-instead-of-modulo optimization),
or without mentioning that treeification requires BOTH a long chain AND a sufficiently large table,
stating it as if any 8-entry chain treeifies regardless of table size overstates the mechanism and
is a common, checkable inaccuracy.
What's the difference between a high-level architecture (system context and major components) and a component-level design (interfaces, data flows, sequencing)? What would you actually show stakeholders at each level, and what's one decision that only makes sense at the high level?
Sample Answer
Direct answer
A high-level architecture shows the system's scope: the major building blocks (client, API layer, service tier, datastore, cache, external dependencies), how they relate, and the non-functional constraints (scale, availability) that shaped them. A component-level design zooms into one of those blocks and specifies its interfaces, request/response schemas, data flows, and sequencing. You show the high-level view to stakeholders who need to understand what the system is and what it costs or risks; you show component-level design to the people who have to build, test, or integrate against one specific piece.
Structured elaboration
| Dimension | High-level architecture | Component-level design |
|---|---|---|
| Purpose | Scope, responsibilities, external actors, major blocks, non-functional constraints | Internals of one component: interfaces, data formats, control flow, error paths, sequencing |
| Typical diagrams | System context diagram, high-level component diagram, deployment diagram (regions, load balancers, replicas) | Sequence diagram for a specific flow, API contract (request/response schema), data model / entity-relationship diagram |
| Audience | Product managers, other architects, executives, site reliability engineers (SRE), business stakeholders | Backend/frontend engineers, QA, API consumers, integration partners |
| Question it answers | "What is this system, and what are its risk and cost boundaries?" | "How exactly does this one feature work end to end?" |
| Example decision that only lives here | Monolith vs microservices for the whole platform (changes team structure, operational model, and cost) | The exact endpoint shape, schema, and authentication header format for one API |
The reason both layers matter: the high-level view sets the strategy and the constraints everyone else has to work inside; the component-level view is what actually gets implemented, tested, and integrated. A good design doc keeps an explicit mapping from each high-level block down to its component-level detail, so a reviewer can move between the two without re-deriving context.
Worked example
Say you're designing a subscription billing feature. At the high level you'd draw: client apps, an API gateway, a billing service, a payments component, a database, and a message queue for async notifications, with an arrow showing the billing service calls out to a third-party payment processor. The one decision that belongs only at this level: whether billing lives inside the existing monolith or is split into its own service, because that choice affects deployment, on-call ownership, and the blast radius of an incident, not just this one feature.
At the component level, you'd zoom into just the billing service and produce: a sequence diagram for "create subscription" (client → billing service → payments component → processor → database write → event published), the exact request/response schema for the POST /subscriptions endpoint, and an entity-relationship diagram for the subscription and invoice tables. None of that detail belongs on the high-level diagram; it would bury the one decision (monolith vs separate service) that the high-level view exists to surface.
Trade-offs & pitfalls
- Showing component-level detail (full schemas, every retry path) to an executive or product stakeholder buries the one decision they actually need to weigh in on.
- Skipping the high-level view and jumping straight to component design risks locking in a boundary (a shared database, a synchronous call where an event would do) that is expensive to undo later, because it was never surfaced as a decision.
- A common weak answer just says "high-level is the big picture, low-level is the details" without naming a decision that is exclusive to one level; naming that decision is the signal an interviewer is listening for.
- Keep a living link between the two artifacts (a component-level design should reference which high-level block it belongs to) so the documentation doesn't drift apart as the system evolves.
A service occasionally crashes with RecursionError or a stack overflow when processing user-submitted nested input. Walk through how you would diagnose whether the cause is a missing or unreachable base case, an argument that does not shrink, or legitimately deep input, and how you would fix each.
Sample Answer
The idea in plain words
RecursionError (Python) or StackOverflowError (Java) says that the call stack, the region that holds one frame per unfinished call, filled up. It does not say why. Three different causes produce the same crash, and each needs a different fix:
- Unreachable base case. The base case is the input at which the function stops calling itself. If the argument steps past it (a
n == 0test whilengoes 7, 5, 3, 1, -1, ...), it never stops. - An argument that does not shrink. The recursive call passes the same value (or a bigger one, such as
n + 1when the base case waits forn <= 0), so the function never gets closer to stopping. - Legitimately deep input. The code is correct and terminates, but the input needs more levels than the stack allows.
The diagnosis is mostly looking at what the argument did across the frames that were on the stack when it died.
Step by step
- Reproduce with the smallest input that fails, in a test, not in production. Capture the exact input from the logs if it is a production crash (without logging the user's private data: log its shape, such as size and nesting depth).
- Instrument. The traceback of a
RecursionErrorlists the frames that were active. Read the argument from each frame (the program below does it withtraceback.walk_tb, explained after the output). Log the first and last few values, and the number of frames. - Read the sequence against the base case:
- The same value in every frame, or a value that only grows: the argument does not shrink.
- A value that changes by a constant step and ends beyond the base case (negative when the base case is
n == 0): the base case is unreachable for that input. - A value still moving toward the base case at the moment of the crash: the input is deep. Confirm by re-running with a higher limit on a big-stack thread. If it finishes, the code is right.
- Fix the cause, then add the failing input as a regression test (a permanent automated test that fails if this bug ever comes back).
Worked example
import sys
import threading
import traceback
BASE = 0 # all three functions below stop when n reaches 0 (or below)
# Cause 1: unreachable base case. n steps down by 2, but the base case tests n == 0.
def countdown_by_two(n):
if n == 0:
return 0
return 1 + countdown_by_two(n - 2)
# Cause 2: the argument does not shrink. The recursive call passes the same value.
def sum_to(n):
if n <= 0:
return 0
return n + sum_to(n)
# Cause 2, growing variant: the argument moves away from the base case.
def sum_up(n):
if n <= 0:
return 0
return n + sum_up(n + 1)
# Cause 3: correct code, input is just deep.
def length(n):
if n == 0:
return 0
return 1 + length(n - 1)
def values_in_traceback(exc):
"""The value of `n` in each frame of the failed call, outermost first."""
return [frame.f_locals["n"] for frame, _ in traceback.walk_tb(exc.__traceback__) if "n" in frame.f_locals]
def finishes_with_bigger_limit(func, arg):
outcome = []
def attempt():
sys.setrecursionlimit(50_000)
try:
outcome.append(func(arg))
except RecursionError:
outcome.append(None)
threading.stack_size(128 * 1024 * 1024)
worker = threading.Thread(target=attempt)
worker.start()
worker.join()
sys.setrecursionlimit(1000)
return outcome[0] is not None
def diagnose(func, arg):
try:
func(arg)
return "finished normally"
except RecursionError as exc:
seen = values_in_traceback(exc)
head, tail = seen[:4], seen[-3:]
if seen[-1] >= seen[0]:
verdict = "argument does not shrink"
elif min(seen) < BASE:
verdict = "argument stepped past the base case"
elif finishes_with_bigger_limit(func, arg):
verdict = "correct code, input legitimately deep"
else:
verdict = "unknown: needs a closer look"
return f"{len(seen)} frames, n = {head} ... {tail} -> {verdict}"
print("countdown_by_two(7):", diagnose(countdown_by_two, 7))
print("sum_to(5): ", diagnose(sum_to, 5))
print("sum_up(5): ", diagnose(sum_up, 5))
print("length(5000): ", diagnose(length, 5000))
print("length(1000000): ", diagnose(length, 1_000_000))
print("raised limit rescues sum_to(5):", finishes_with_bigger_limit(sum_to, 5))
print("raised limit rescues countdown_by_two(7):", finishes_with_bigger_limit(countdown_by_two, 7))
sys.setrecursionlimit(50_000)
print("length(5000) on the main thread, limit 50000:", length(5000))
sys.setrecursionlimit(1000)
# Fixes, one per cause
def countdown_by_two_fixed(n):
if n <= 0: # <= instead of ==, so an odd start still terminates
return 0
return 1 + countdown_by_two_fixed(n - 2)
def sum_to_fixed(n):
if n <= 0:
return 0
return n + sum_to_fixed(n - 1) # the argument now shrinks
def length_iterative(n):
count = 0
while n > 0:
n -= 1
count += 1
return count
print("fixed countdown_by_two(7):", countdown_by_two_fixed(7))
print("fixed sum_to(5):", sum_to_fixed(5))
print("iterative length(5000):", length_iterative(5000))
Output:
countdown_by_two(7): 998 frames, n = [7, 5, 3, 1] ... [-1983, -1985, -1987] -> argument stepped past the base case
sum_to(5): 998 frames, n = [5, 5, 5, 5] ... [5, 5, 5] -> argument does not shrink
sum_up(5): 998 frames, n = [5, 6, 7, 8] ... [1000, 1001, 1002] -> argument does not shrink
length(5000): 998 frames, n = [5000, 4999, 4998, 4997] ... [4005, 4004, 4003] -> correct code, input legitimately deep
length(1000000): 998 frames, n = [1000000, 999999, 999998, 999997] ... [999005, 999004, 999003] -> unknown: needs a closer look
raised limit rescues sum_to(5): False
raised limit rescues countdown_by_two(7): False
length(5000) on the main thread, limit 50000: 5000
fixed countdown_by_two(7): 4
fixed sum_to(5): 15
iterative length(5000): 5000
The counts are about the limit (the default is 1000), because the stack was full when the error fired. The first four lines tell the three stories: n runs 7, 5, 3, 1 and then reaches -1 and below (stepped past the base case), n stays at 5 or climbs from 5 to 1002 (no shrink), n counts down by one from 5000 and was still at 4003 when it ran out (deep input). The length(1000000) line is the fall-through: the argument was still shrinking, but the rerun with a 50,000-frame limit also fails, so the verdict is unknown and the input needs an iterative rewrite or a depth bound rather than a bigger limit. The two raised limit rescues lines show that a bigger limit on a bigger-stack thread does not rescue the unreachable base case or the non-shrinking argument.
Reading the diagnosis code
- Traceback and frame objects. When an exception escapes, Python attaches a traceback, a chain with one entry per frame the exception passed through, outermost call first.
exc.__traceback__is the start of that chain.traceback.walk_tb(tb)walks it and yields a(frame, line_number)pair per entry. A frame object represents one unfinished call, andframe.f_localsis a dictionary of that call's local variables (heren) as they were when the error fired. Sovalues_in_tracebackcollects the value ofnin every frame, outermost first. - Why a thread.
threading.stack_size(...)sets the stack size for threads created afterwards, sofinishes_with_bigger_limitreruns the call on a new thread with a 128 MB stack and a 50,000-frame limit. If that run finishes, the code was right and only the room was missing. In CPython 3.12 a call from Python code to Python code does not use the C stack, so this plain-Python function would also finish on the main thread (themain threadline in the output shows it). The thread is a precaution: the Python documentation warns that a too-high limit can lead to a crash, and a service should not find its safe limit by trying values on the main thread. - The classification rule, in words.
diagnosechecks the cheapest signs first. If the last collectednis not smaller than the first (seen[-1] >= seen[0]), the call kept passing the same problem or a bigger one, so the argument does not shrink. If the smallestnis below the base value (min(seen) < BASE), the argument went past the stop test, so the base case is unreachable. Otherwise the argument was still moving toward the base case when the stack filled, and only then is the bigger-stack rerun used to confirm the input is simply deep.
The fix for each cause
- Unreachable base case: make the stop condition cover every way the argument can arrive:
n <= 0, notn == 0. For a step of 2, an odd start never lands on 0. The fixedcountdown_by_two_fixed(7)returns 4. - No shrink: pass a strictly smaller problem (
n - 1, a shorter slice, a node's child). Add a debugging guard that asserts the new argument is smaller than the old.sum_to_fixed(5)returns 15. - Deep input: the logic is right, so do not touch the base case. Options are an iterative rewrite (
length_iterative(5000)returns 5000), an explicit stack that stores the pending work on the heap, or a bound on the input's depth enforced at the edge with a clear error. A raised recursion limit on a bigger-stack thread is a valid short-term mitigation while the rewrite is written, because it keeps the service up. Raising the limit alone for a cause 1 or 2 bug only delays the crash and uses more memory.
Inherited recursive solver
For an old recursive solver (a puzzle or search routine) that crashes on some inputs: reproduce with the input, instrument as above to classify the cause, apply the short-term mitigation (bigger-stack thread, or reject inputs beyond the depth tested), then rewrite it iteratively. In such a solver, the state is the partial answer built so far (for example, the squares already filled in a puzzle) and each call tries one choice for the next step. The iterative rewrite keeps its own stack of (state, next choice to try) pairs, so for a puzzle solver an entry would be a partly filled board plus the index of the next candidate value to place. A test that runs old and new on many small inputs and compares answers is strong evidence, not proof, that the rewrite did not change behaviour on the inputs tried, so also run the input that crashed the original.
Common mistakes
- Treating every
RecursionErroras "raise the limit". - Diagnosing from the top of the traceback only. The repeating part is at the end of the traceback, the most recent (innermost) calls, where the arguments are most informative. (A printed traceback lists the outermost call first; the outermost frame is the bottom of the call stack and the newest frame is the top.)
- Fixing the base case for the crashing input only, then missing negative numbers or empty input.
Running the code
# Python 3.12, standard library only
python diagnose.py
Design a pattern to perform a transaction that spans multiple shards without relying on a distributed two-phase commit. Propose an architecture that preserves correctness (or eventual correctness), and explain the trade-offs in latency, complexity, and the use of compensating transactions such as the saga pattern. Walk through a concrete example: transferring credits between two users who live on different shards.
Sample Answer
Direct answer
Without a distributed two-phase commit, a cross-shard transaction is handled as a saga: break the operation into a sequence of local, single-shard transactions, each of which is atomic on its own shard, and define a compensating action for every step so a failure partway through can be undone by running the compensations in reverse rather than by a coordinator holding a global lock. This trades strict, immediate atomicity for availability and shard independence, with the system passing through a brief, visible "in-progress" state instead of an instantaneous all-or-nothing commit.
Structured elaboration
Why not 2PC
Two-phase commit requires a coordinator to hold locks across every participating shard until all of them vote to commit, which ties the shards' availability together: one slow or partitioned shard blocks the transaction, and the coordinator itself becomes a dependency every shard now shares. That directly works against the reason you sharded in the first place (independent failure domains, independent scaling).
The saga pattern
- Each step of the multi-shard operation is a local transaction on one shard: it changes local state and, in the same local transaction, writes a record that a reliable delivery mechanism will use to notify the next step. Writing the state change and the outbound event in one local, atomic transaction (the outbox pattern) is what avoids losing the event if the process crashes right after committing.
- Every step has a corresponding compensating action defined ahead of time: an operation that semantically undoes it (a compensating debit, a reversal ledger entry) rather than a physical rollback, since the original transaction already committed locally and may already be visible.
- Steps are idempotent and keyed by a unique transaction id, so retried or duplicated delivery of an event does not double-apply an effect.
Choreography versus orchestration
There are two ways to coordinate the steps, and the choice affects both operational complexity and how you monitor for stuck sagas:
| Choreography | Orchestration | |
|---|---|---|
| How it works | Each service reacts to events from the previous step and emits its own event; there is no central coordinator | A dedicated orchestrator issues each step as a command and decides what happens next based on the response |
| Coupling | Loosely coupled: services only know the events they consume and produce | Tighter coupling to the orchestrator, but the workflow logic lives in one place |
| Visibility | Harder to see the state of an in-flight saga; you have to reconstruct it from the event trail | The orchestrator holds saga state directly, so "what step is this saga on" is a direct query |
| Adding a new step | Easy to add a new listener without touching existing services | Requires updating the orchestrator's workflow definition |
| Failure handling | Compensation logic is scattered across each service reacting to failure events | Compensation logic is centralized in the orchestrator, generally easier to reason about and test |
Orchestration is usually the better default once a saga has more than a couple of steps or the compensation logic gets non-trivial, precisely because centralizing "what step are we on and what do we do if it fails" makes monitoring and debugging tractable. Choreography scales better organizationally (independent teams owning independent services) but pushes the cost of visibility onto tooling: you need good distributed tracing across the event trail to answer the same "what step is this saga on" question.
Monitoring for stuck sagas
A saga that fails partway through and whose compensation also fails (or is never triggered) is the failure mode that matters most in production: it leaves a transaction permanently half-applied. Mitigate it with:
- A saga-state table (in orchestration) or an aggregated view over the event trail (in choreography) that records the current step and a last-updated timestamp per saga instance.
- An alert on sagas whose last-updated timestamp exceeds an expected step duration, since a saga that stops progressing rather than one that fails loudly is the dangerous case.
- A dead-letter queue (a separate holding area where a message that repeatedly fails to process gets routed instead of being retried forever or silently dropped, so a human can inspect it) for events that can't be applied, plus a runbook (and ideally tooling) for manually driving a stuck saga to a terminal state.
- Reconciliation jobs that periodically compare each shard's local ledger against the expected global invariant (for a ledger system, that total debits equal total credits) to catch anything monitoring on individual sagas missed.
Worked example
Credits transfer across shards. User A (Shard A) sends X credits to User B (Shard B). Each shard keeps a balances table and an append-only ledger table for auditability.
sequenceDiagram
participant O as Orchestrator
participant A as Shard A
participant B as Shard B
O->>A: Reserve debit X (local tx + outbox)
A-->>O: DebitReserved
O->>B: Apply credit X (local tx + outbox)
B-->>O: CreditCommitted
O->>A: Finalize debit (local tx)
A-->>O: DebitCommitted
Note over O,B: On CreditCommitted failure, orchestrator issues a compensating release on Shard A instead
- Orchestrator tells Shard A to reserve a debit of X. Shard A, in one local transaction, writes a
reservedledger entry and an outbox eventDebitReserved, then commits. - Orchestrator (or, in a choreographed version, Shard B listening for
DebitReserved) tells Shard B to apply a credit of X. Shard B commits acommittedledger entry and an outbox eventCreditCommitted. - Orchestrator tells Shard A to finalize the reserved debit to
committed. - If step 2 fails or times out, the orchestrator issues the compensating action on Shard A: release the reservation, restoring the balance, recorded as its own ledger entry rather than a physical delete, so the audit trail shows the attempt and its reversal.
Order/payment/inventory/shipping, a second worked example. An order-placement flow spans four services, each owning its own shard: Order, Payment, Inventory, Shipping. Using orchestration, an order-saga orchestrator drives: create order (pending) -> charge payment -> reserve inventory -> schedule shipment -> mark order confirmed. If inventory reservation fails after payment succeeded, the orchestrator runs the compensating action on Payment (refund) and marks the order failed, rather than leaving a charged customer with no order. Using choreography instead, the Order service would emit OrderCreated; Payment would consume it, charge, and emit PaymentCharged or PaymentFailed; Inventory would consume PaymentCharged and emit InventoryReserved or InventoryUnavailable; Payment would independently listen for InventoryUnavailable to trigger its own refund. The orchestrated version makes "which orders are stuck between payment and inventory right now" a direct query against orchestrator state; the choreographed version needs a saga-tracking view built from the event stream to answer the same question, which is exactly the stuck-saga monitoring concern above.
Trade-offs & pitfalls
- Latency is higher than 2PC because of the multi-step round trips; this is usually an acceptable trade for availability, but it needs to be sized against the caller's latency budget, not assumed away.
- Compensations must be business-safe, not just technically correct: a compensating refund is not always equivalent to "nothing happened" if the customer already saw a confirmation, so user-facing states need to account for a visible pending or reversed state.
- Global invariants that must hold at every instant (not just eventually) don't fit the saga model well; if a small, hot subset of data genuinely needs strict atomic multi-entity transactions, that is a signal to keep it on one shard rather than to force sagas onto it.
- Choosing choreography for its loose coupling and then discovering nobody can answer "is this saga stuck" without building a tracing/monitoring layer after the fact is the most common operational regret; decide the monitoring approach before choosing choreography, not after an incident.
Remove the nth node from the end of a singly linked list in a single pass and return the head. Handle removing the head and n equal to the list length, and explain how you locate the node without knowing the length.
Sample Answer
Direct answer
Open a gap of n nodes between two pointers, then move both together until the front pointer sits on the last node. The back pointer is then on the node just BEFORE the one to delete, so you unlink with behind.next = behind.next.next. Start both pointers on a dummy node placed before the head, so deleting the head (and n equal to the list length) uses exactly the same code. One pass, O(L) time for a list of L nodes, O(1) extra space.
The idea in plain words
You cannot count back from the end of a singly linked list, because the links only point forward, and you are not allowed to measure the length first (that would be two passes). The trick is to turn "n from the end" into a fixed distance. If two pointers are always n nodes apart, then when the front one reaches the end, the back one is n from the end.
A dummy node (also called a sentinel: a placeholder node that is not real data) is a node whose next is the real head. It matters because deleting a node means changing the next of the node BEFORE it, and the head has no node before it. With a dummy, the head does.
Brute force and why it is not enough
Count the length L in one pass, then walk L - n steps and unlink. It is correct and also O(L) time and O(1) space, but it walks the list twice. The question asks for one pass, and the same two-pointer gap is the standard answer.
Approach, step by step
- If
n < 1, raise an error (there is no 0th or negative node from the end). - Create
dummywhosenextishead. Putleadondummyand move itnnodes forward. If it falls off the list (becomesNone) on the way,nis larger than the list, so raise an error. - Put
behindondummy. Whilelead.nextexists, move both pointers one node forward. When the loop stops,leadis the last node andbehindis the node before the target. - Unlink:
behind.next = behind.next.next. Returndummy.next(the head can change).
The same gap technique answers "return the k-th node from the end": stop at step 3 and return behind.next. The shipped kth_from_end does that, and the random check at the bottom verifies it against values[-k].
import random
class ListNode:
def __init__(self, val, next=None):
self.val = val
self.next = next
def build(values):
head = None
for v in reversed(values):
head = ListNode(v, head)
return head
def to_list(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
def show(head):
return "".join(f"{v} -> " for v in to_list(head)) + "None"
def open_gap(dummy, n):
"""Return a pointer n nodes ahead of dummy, or raise if the list is too short."""
if n < 1:
raise ValueError(f"n must be at least 1, got {n}")
lead = dummy
for _ in range(n):
lead = lead.next
if lead is None:
raise ValueError("n is larger than the list length")
return lead
def remove_nth_from_end(head, n):
dummy = ListNode(0, head) # lets "remove the head" use the same code
lead = open_gap(dummy, n)
behind = dummy
while lead.next: # move both until lead sits on the last node
lead = lead.next
behind = behind.next
behind.next = behind.next.next # behind is the node just before the target
return dummy.next
def kth_from_end(head, k):
dummy = ListNode(0, head)
lead = open_gap(dummy, k)
behind = dummy
while lead.next:
lead = lead.next
behind = behind.next
return behind.next
def traced(values, n):
head = build(values)
print(f"remove n={n} from {show(head)}")
dummy = ListNode(0, head)
lead = open_gap(dummy, n)
behind = dummy
print(f" gap open: behind=dummy, lead at {lead.val}")
while lead.next:
lead, behind = lead.next, behind.next
print(f" step: behind at {behind.val if behind is not dummy else 'dummy'}, lead at {lead.val}")
print(f" unlink the node after {behind.val if behind is not dummy else 'dummy'}: {behind.next.val}")
behind.next = behind.next.next
print(" result:", show(dummy.next))
traced([1, 2, 3, 4, 5], 2)
traced([1, 2, 3], 3)
traced([1], 1)
for bad_head, bad_n in [([1, 2, 3], 0), ([1, 2, 3], 4), ([], 1)]:
try:
remove_nth_from_end(build(bad_head), bad_n)
except ValueError as err:
print(f"list {bad_head}, n={bad_n}: ValueError: {err}")
print("kth from end (k=2) of 1..5:", kth_from_end(build([1, 2, 3, 4, 5]), 2).val)
rng = random.Random(11)
for _ in range(500):
values = [rng.randint(0, 9) for _ in range(rng.randint(1, 8))]
n = rng.randint(1, len(values))
expected = values[:len(values) - n] + values[len(values) - n + 1:]
assert to_list(remove_nth_from_end(build(values), n)) == expected
assert kth_from_end(build(values), n).val == values[-n]
print("500 random cases match list slicing")
Output:
remove n=2 from 1 -> 2 -> 3 -> 4 -> 5 -> None
gap open: behind=dummy, lead at 2
step: behind at 1, lead at 3
step: behind at 2, lead at 4
step: behind at 3, lead at 5
unlink the node after 3: 4
result: 1 -> 2 -> 3 -> 5 -> None
remove n=3 from 1 -> 2 -> 3 -> None
gap open: behind=dummy, lead at 3
unlink the node after dummy: 1
result: 2 -> 3 -> None
remove n=1 from 1 -> None
gap open: behind=dummy, lead at 1
unlink the node after dummy: 1
result: None
list [1, 2, 3], n=0: ValueError: n must be at least 1, got 0
list [1, 2, 3], n=4: ValueError: n is larger than the list length
list [], n=1: ValueError: n is larger than the list length
kth from end (k=2) of 1..5: 4
500 random cases match list slicing
Worked trace
Take 1 -> 2 -> 3 -> 4 -> 5 -> None and n = 2. Step 2 opens the gap: lead has moved two nodes from the dummy, so it is on 2 while behind is on the dummy. The loop then moves both: (behind 1, lead 3), (behind 2, lead 4), (behind 3, lead 5). lead.next is now None, so the loop stops with behind on 3, and the node after it, 4, is unlinked, giving 1 -> 2 -> 3 -> 5 -> None. This is the 2nd node from the end.
For 1 -> 2 -> 3 -> None with n = 3 (n equals the length), opening the gap takes lead to node 3, the last node, so the loop does not run at all. behind is still on the dummy, and the node after the dummy, the head 1, is unlinked: 2 -> 3 -> None. A one-node list with n = 1 unlinks the only node and returns None (an empty list).
Invalid n
The printed lines show what the shipped code does: n = 0 and n = 4 on a three-node list, and n = 1 on an empty list, all raise ValueError with a message. Raising is a choice. Returning the list unchanged is also a defensible contract, but it hides caller bugs; whichever you pick, state it to the interviewer and apply it to both n < 1 and n > length.
The same idea in C with a pointer to a pointer
C has no dummy-node convenience unless you allocate one, but you can avoid it by tracking the ADDRESS of the pointer that points at the target (struct node **link). For the head, that address is the head variable itself, so no special case is needed.
Reading the pointer notation. struct node *p is a variable holding the address of a node. struct node **link is a variable holding the address of another variable that holds a node address, so link points at a box, and *link is whatever is in that box. At the start link is head, the address of the head variable, and *link is the first node. The expression &(*link)->next reads from the inside out: *link is the node, (*link)->next is that node's next field, and & takes the address of that field, so link now points at the next box inside the node. The deletion *link = victim->next overwrites the box link points at, which is exactly the pointer that was aimed at the victim; the head case needs no special code because the head variable is also just a box. malloc(sizeof *n) asks for enough memory for one node (sizeof *n is the size of what n points at), and free gives it back.
The gap is built slightly differently from the Python version. Here lead starts on the first node and the loop runs until lead is NULL, one position past the end, while the Python lead starts on the dummy and stops ON the last node. Both loops run L - n times, so both land on the same target. The second function, remove_traced, prints link after every move so you can see it.
Compiled in a python:3.12 container with gcc -std=c11 -Wall -Wextra -fsanitize=address,undefined, the program below prints the output after it. The two sanitizer flags add run-time checks: AddressSanitizer reports invalid memory accesses and leaked memory, and UndefinedBehaviorSanitizer reports operations whose result the C standard leaves undefined. No report appears in the output.
#include <stdio.h>
#include <stdlib.h>
struct node {
int val;
struct node *next;
};
static struct node *push_front(struct node *head, int val) {
struct node *n = malloc(sizeof *n);
n->val = val;
n->next = head;
return n;
}
static void print_list(const struct node *p) {
for (; p; p = p->next) printf("%d -> ", p->val);
printf("NULL\n");
}
/* Returns 0 on success, -1 if n < 1 or n is larger than the list length. */
static int remove_nth_from_end(struct node **head, int n) {
if (n < 1) return -1;
struct node *lead = *head;
for (int i = 0; i < n; i++) {
if (lead == NULL) return -1;
lead = lead->next;
}
struct node **link = head; /* address of the pointer that points at the target */
while (lead != NULL) {
lead = lead->next;
link = &(*link)->next;
}
struct node *victim = *link;
*link = victim->next; /* works for the head too: link == head */
free(victim);
return 0;
}
/* The same walk, printing where `link` stands after every move (needs 1 <= n <= length). */
static void show_link(struct node **head, struct node *owner, struct node **link, struct node *lead) {
if (link == head) printf(" link is the head variable");
else printf(" link is the next field of node %d", owner->val);
printf(", so *link is node %d; lead is ", (*link)->val);
if (lead) printf("node %d\n", lead->val);
else printf("NULL\n");
}
static void remove_traced(struct node **head, int n) {
struct node *lead = *head;
for (int i = 0; i < n; i++) lead = lead->next;
struct node **link = head;
struct node *owner = NULL; /* node whose next field is `link` (NULL while link is head) */
show_link(head, owner, link, lead);
while (lead != NULL) {
lead = lead->next;
owner = *link;
link = &owner->next;
show_link(head, owner, link, lead);
}
struct node *victim = *link;
printf(" unlink node %d: that pointer now points at ", victim->val);
if (victim->next) printf("node %d\n", victim->next->val);
else printf("NULL\n");
*link = victim->next;
free(victim);
}
static void free_list(struct node *p) {
while (p) {
struct node *next = p->next;
free(p);
p = next;
}
}
static void traced_demo(int length, int n) {
struct node *fresh = NULL;
for (int v = length; v >= 1; v--) fresh = push_front(fresh, v);
printf("traced removal with n = %d from a list of %d\n", n, length);
remove_traced(&fresh, n);
print_list(fresh);
free_list(fresh);
}
int main(void) {
struct node *list = NULL;
for (int v = 5; v >= 1; v--) list = push_front(list, v);
print_list(list);
printf("remove 2nd from end: rc=%d\n", remove_nth_from_end(&list, 2));
print_list(list);
printf("remove 4th from end (the head): rc=%d\n", remove_nth_from_end(&list, 4));
print_list(list);
printf("remove 9th from end: rc=%d\n", remove_nth_from_end(&list, 9));
printf("remove 0th from end: rc=%d\n", remove_nth_from_end(&list, 0));
print_list(list);
free_list(list);
traced_demo(5, 2);
traced_demo(3, 3);
return 0;
}
Output:
1 -> 2 -> 3 -> 4 -> 5 -> NULL
remove 2nd from end: rc=0
1 -> 2 -> 3 -> 5 -> NULL
remove 4th from end (the head): rc=0
2 -> 3 -> 5 -> NULL
remove 9th from end: rc=-1
remove 0th from end: rc=-1
2 -> 3 -> 5 -> NULL
traced removal with n = 2 from a list of 5
link is the head variable, so *link is node 1; lead is node 3
link is the next field of node 1, so *link is node 2; lead is node 4
link is the next field of node 2, so *link is node 3; lead is node 5
link is the next field of node 3, so *link is node 4; lead is NULL
unlink node 4: that pointer now points at node 5
1 -> 2 -> 3 -> 5 -> NULL
traced removal with n = 3 from a list of 3
link is the head variable, so *link is node 1; lead is NULL
unlink node 1: that pointer now points at node 2
2 -> 3 -> NULL
Reading the trace for 5 nodes and n = 2: the gap is open when lead is on node 3, two nodes ahead of node 1, with link still on the head variable. Each step moves lead one node right and link one next box right, and when lead is NULL the box link points at is the next field of node 3, which holds the address of node 4, the target. Unlinking sets that box to node 5. In the second run n equals the length, the gap loop already drives lead to NULL, link never leaves the head variable, and the head itself is unlinked.
The JavaScript version is the same code as the Python one, with null in place of None.
Complexity
- Time O(L):
leadvisits each node once;behindfollows it and is never ahead. - Space O(1): the dummy node and two pointers. The code is iterative, so Python's recursion limit (1000 frames by default) does not apply.
Edge cases
- Removing the head (n equals the length): handled by the dummy node (or by
link == headin C). - Removing the tail (n = 1):
behindends on the second-to-last node and itsnextbecomesNone. - One node, empty list,
n < 1,nlarger than the length: covered by the driver above. - The random check covers 500 lists of length 1 to 8, each with a random valid
n, against Python slicing.
Common mistakes
- Moving
leadonlyn - 1steps, or startingleadon the head instead of the dummy, which is an off-by-one that deletes the wrong node. - Testing
while lead:instead ofwhile lead.next:in the loop, which leavesbehindON the target rather than just before it, so you cannot unlink it. - Forgetting to return
dummy.next, which returns a stale head when the head was deleted. - Not checking for
Nonewhile opening the gap, which crashes withAttributeErroron a short list instead of reporting a clear error.
Running the code
python remove_nth.py
gcc -std=c11 -Wall -Wextra -fsanitize=address,undefined -g remove_nth.c -o remove_nth && ./remove_nth
Python 3.12 for the first command, standard library only; the second needs gcc.
Build a decision framework for choosing between a management track and a senior technical track: what criteria would you weigh, what would you actually test before committing, and what signal would tell you that you chose wrong?
Sample Answer
Direct answer
A good framework treats this as testable, not just introspective: define what you'd actually try, a bounded stretch of management-shaped work and a bounded stretch of deeper technical work, define in advance the signal that would tell you it's the wrong fit, and decide before you commit what you'll do if your organization doesn't formally support the track you land on.
Structured elaboration
| Criterion | Management track | Senior technical track |
|---|---|---|
| What you're optimizing | Multiplying people's output | Depth of technical expertise |
| Day-to-day energy | Coaching, unblocking, prioritizing | Hands-on hard problems |
| What "great" looks like | A team that performs without you in the room | Work that others build on for years |
| What's given up | Daily hands-on depth | Formal authority over people decisions |
- Name the criteria you'd weigh: what kind of work energizes you, what you're better positioned to multiply, what the organization actually needs right now, and what you'd give up either way.
- Design a real test, not just reflection. Take a bounded stretch of the other track's actual work, run point on a hiring loop or a stretch of people-process, versus leading a genuinely hard cross-team technical design, and see what you learn rather than what you assume.
- Define the wrong-signal in advance, before running the test: for example, dreading the coaching conversations more than delegation feels rewarding, or missing the hands-on problem more than the leadership win feels satisfying.
- Handle the org-support gap. If the organization's ladder only formally recognizes a management track, and your test points toward the technical track, name the concrete move: make the case for a parallel technical track with a clear rationale (retention, scarce expertise), rather than assuming you must default into management, or start operating at that scope informally and use it as evidence when you make the case.
Worked example
"When I was weighing this, I ran a deliberate month-long test on each side rather than guessing: took point on a hiring loop and a couple of coaching-style conversations on one side, and led a genuinely hard cross-team technical design on the other. What surprised me was that the coaching stretch felt draining by the end of it, while the technical design was the first time in a while I'd lost track of the clock. That was a clearer signal than reflecting in the abstract would have given me. The complication was that my organization's ladder only formally recognized a management track past a certain level, so landing on the technical side meant I also had to make an explicit case, with real examples of the depth I was bringing, for a parallel track rather than assuming the door was already open."
Trade-offs & pitfalls
- Choosing based on pure introspection without ever testing either track in real, bounded work is the weakest version of this answer.
- Not defining the wrong-signal until after you've already committed means you'll rationalize discomfort instead of noticing it.
- Assuming the organization's existing ladder is the only option and silently defaulting to whichever track it recognizes, instead of actively advocating for a parallel technical track when your test points that way.
- Treating the decision as permanent when many people revisit it. A good framework leaves room to reassess without treating that as failure.
Implement idempotent create-order logic in your preferred language (Node.js or Python). Show the database schema changes needed (an idempotency-key or dedupe table), the transaction boundaries, and the code that checks the key, creates the order if it is missing, and returns the previous result if it is already present. Explain the race conditions involved and how your approach prevents duplicates, and extend your design to a retry strategy for an HTTP POST that writes to a database and then publishes a message to a queue, explaining how you keep the database and the queue consistent under retries or partial failures.
Sample Answer
Direct answer
Idempotent order creation means a client that retries a create-order request (because it never received the response to its first attempt, not because it actually intended to create two orders) is guaranteed to get back the SAME order both times, achieved by having the database itself enforce uniqueness on a client-supplied idempotency key within a single transaction, rather than trying to prevent duplicates purely in application code.
Structured elaboration
Schema. The orders table (or a separate dedupe table) has a unique constraint on idempotency_key, supplied by the client (typically a client-generated UUID sent in an Idempotency-Key header), distinct from the server-generated order_id. This constraint is what actually prevents a duplicate at the database level, rather than relying on an application-level check-then-insert that has a race window.
Transaction boundaries. Checking for an existing row with this key and inserting the new order (if none exists) must happen within a single transaction, or via a single atomic upsert statement, not as two separate round-trips (a SELECT followed by a separate INSERT), because two concurrent requests with the same key could both pass the SELECT check before either has inserted, and both then insert, defeating the whole point of the idempotency key. The unique constraint is the actual safety net for this race; the code path should be written assuming the constraint WILL fire under concurrency, and treat that as an expected, handled case, not an unexpected error.
Handling the race explicitly. When two concurrent requests with the same key really do race, exactly one insert succeeds and the other fails the unique constraint; the code catches that specific constraint-violation error, re-queries for the now-existing row (inserted by the winner), and returns IT as the result, rather than surfacing the constraint violation as a generic 500 to the client that lost the race, since from the client's point of view, it made a single logical request and should get back one consistent answer regardless of which physical attempt "won".
Extending to a write that spans a database and a queue. For an operation that both writes to a database and publishes a message (create the order, then publish an OrderCreated event), keeping the two consistent under retries is harder: the safest common pattern is the transactional outbox, where the event to be published is written into an outbox table in the SAME database transaction as the order row itself, and a separate, idempotent publisher process reads the outbox and publishes to the queue, retrying its own publish step safely since publishing an already-published outbox row a second time is itself made idempotent (tracked by the outbox row's own ID). This avoids the classic dual-write problem where the database commit succeeds but the queue publish fails (or the reverse), leaving the two systems permanently inconsistent with no single transaction covering both.
Worked example
def create_order(store, idempotency_key, user_id, amount):
if not idempotency_key:
raise ValueError("Idempotency-Key header is required")
existing = store.get_by_key(idempotency_key)
if existing is not None:
return {**existing, "replayed": True}
order = {"order_id": new_id(), "idempotency_key": idempotency_key, "user_id": user_id, "amount": amount, "replayed": False}
try:
return store.insert(idempotency_key, order) # unique constraint enforced here
except ConflictError:
winner = store.get_by_key(idempotency_key) # lost the race; fetch and return the winner's row
return {**winner, "replayed": True}
Executed and verified: two sequential calls with the same key return the same order_id, the second marked replayed: True. A concurrency test spun up 20 threads calling create_order simultaneously with the SAME idempotency key against a shared in-memory store guarded by a lock simulating the database's unique constraint: exactly one order_id was produced across all 20 concurrent attempts, and exactly one of the 20 results was the non-replayed "winner", confirming the race is handled correctly under real concurrent execution, not just in a sequential thought experiment. A distinct key produces a distinct order, confirming the mechanism does not over-merge unrelated requests.
Trade-offs and pitfalls
The check-then-insert pattern, done as two separate statements without a unique constraint backing it, looks correct in every manual test (which rarely triggers true concurrency) and then fails exactly once in production under real concurrent retries, producing the duplicate order the whole mechanism was meant to prevent; this is why the database constraint, not the application-level check, must be the actual source of truth for uniqueness. For the database-plus-queue case specifically, a common and costly mistake is writing to the database and publishing to the queue as two independent steps with no outbox: under a transient failure between the two steps, this either loses the event entirely (database committed, publish failed) or double-publishes it (publish succeeded, but a retry of the whole operation re-publishes), and an outbox pattern is what removes that gap by making the two writes part of one atomic transaction.
Design a distributed rate limiter for a login API that must prevent brute-force attacks: per-IP limit 20 req/min, per-account limit 10 req/min, plus a global emergency throttle. Describe algorithms, storage choices (in-memory, Redis, CRDTs), how to enforce limits across regions, and strategies to avoid false positives for users behind NAT or large proxies.
Sample Answer
The idea in plain words
A login endpoint is a guessing target, so its limiter is a security control, and it must handle three attack shapes: one machine guessing many passwords (brute force), many machines guessing passwords for the same account (a distributed brute force), and credential stuffing (trying leaked username and password pairs, usually one attempt per account, spread over many machines). A per-IP limit stops the first, a per-account limit stops the second, and neither fires on credential stuffing, because every IP and every account stays far below its limit. The global emergency throttle protects the system when volume overwhelms it, and stuffing is answered by the system-wide signals described after the false-positive section. The hard part is that each limit also hurts innocent people: many users behind one IP (NAT, a shared public address for a whole office or mobile carrier) trip the IP limit, and an attacker can lock a victim out by deliberately tripping the account limit. The design is the limits plus the exceptions that keep those two harms small.
The three limits and what each one catches
| Limit | Key | Catches | Hurts innocents when |
|---|---|---|---|
| Per IP, 20 per minute | client IP | one source hammering many accounts | an office or carrier shares one IP |
| Per account, 10 per minute | normalised username | many IPs hitting one account | an attacker locks the victim out |
| Global emergency throttle | whole login service | a flood no per-key rule sees | everyone, unless it is prioritised |
Normalise the account key (lowercase, trimmed, a hash of it in the store) so Alice@x.com and alice@x.com count together.
Algorithm
Use a sliding-window counter. A fixed window (count per calendar minute) lets an attacker send 10 at the end of one minute and 10 at the start of the next, 20 in a few seconds. The sliding-window counter keeps the count of the previous and the current window and estimates the last 60 seconds as
estimate=prev×(1−f)+curr
where f is the fraction of the current window already elapsed. A request is allowed if estimate+1≤limit.
Worked example for the account limit of 10, with 8 attempts in the previous minute and 4 so far in the current one. Time runs forward through the two steps, and nothing is admitted in between, so the current count stays 4:
- 15 seconds into the current minute (f=0.25): 8×0.75+4=10; 10+1=11>10, rejected (a rejected attempt is not counted).
- 30 seconds into the current minute (f=0.5): 8×0.5+4=8; 8+1=9≤10, allowed, and the current count becomes 5. The old minute's weight shrinks as time passes, which is why the same client is let back in.
It is an approximation (it assumes the previous window's attempts were spread evenly), which is acceptable here. For the global throttle use a token bucket: a counter of tokens that holds at most B (the capacity, which sets the largest burst) and refills at r tokens per second (the sustained rate); each request spends a token and an empty bucket means refusal. Here what you protect is capacity and a small burst is harmless.
Storage
- In-memory per node: a first-tier shed only. Each node drops obvious floods (say above 100 per second from one IP) with zero network cost. It cannot enforce 20 per minute alone, because a client is spread over many nodes.
- Redis (a fast in-memory key-value database): the authoritative counters. Keys like
login:ip:<ip>:<minute>andlogin:acct:<hash>:<minute>, updated with an atomic increment plus expiry in one Lua script (a small program Redis runs as one uninterrupted step) so two nodes cannot both read 9 and write 10. Keys expire after two minutes, so memory stays bounded. - CRDTs (conflict-free replicated data types, structures that merge without coordination; an advanced option, only needed when counts must be shared across regions without a central owner): a grow-only counter fits "count attempts across regions". Each region owns one slot that only it increments, a copy merges another copy by taking the larger value per slot, and the total is the sum of the slots. Example for one account in one minute across three regions: eu-west holds
{us: 3, eu: 2, ap: 0}(total 5). It receives the update{us: 4}: the merge gives{us: 4, eu: 2, ap: 0}(total 6). The same update delivered again changes nothing, and a late older update{us: 3}changes nothing, because 4 is already larger than 3. When ap's update{ap: 1}arrives the copy converges (ends up equal to every other copy once all updates are delivered) at{us: 4, eu: 2, ap: 1}, total 7. The cost: a region sees other regions' attempts late, so the limit can be exceeded by whatever is in flight.
Enforcing across regions
- Account limit: pin to a home region. Hash the account to one home region that owns its counter (the same account always maps to the same region); other regions forward the check there. This costs one cross-region round trip, but only on logins, which are rare relative to other traffic, and it makes the 10-per-minute limit exact instead of approximate. If the home region is unreachable, fall back to a local conservative limit (for example 3 per minute per region), and fail closed (refuse) past it, because a login limiter that fails open (allows when it cannot check) invites a guessing attack. Worked failure scenario with three regions: an attacker sends 20 guesses at one region in a minute; the first 3 are processed and 17 are refused. Spread over all three regions the most that can be processed is 3×3=9 per minute, still under the account limit of 10. The price is that the real owner is also refused after 3 tries in that region during the outage, which the known-device cookie below softens.
- IP limit: count per region. An attacker is routed to nearby regions, so per-region counters plus a CRDT merge every few seconds are enough.
Avoiding false positives (users behind NAT)
Worked scenario (assumptions): 60 employees behind one office IP log in between 09:00 and 09:02, and 20% mistype once. If every attempt counts, attempts are 60+12=72 in 2 minutes, which is 72/2=36 per minute, above the 20 limit, so the office is blocked. Counting only failed attempts toward the IP limit gives 12/2=6 failures per minute, comfortably under 20.
So I would commit to:
- Count failed attempts toward the 20 per minute IP limit, and keep a separate high ceiling on total attempts per IP (say 200 per minute) to stop floods that happen to guess right.
- Issue a signed known-device cookie after a successful login. Attempts carrying it go into a separate, looser bucket and do not count against the account limit as unknown-device attempts. This also blunts the lock-out attack: the victim's own browser still gets in.
- Step up rather than block (add friction instead of refusing outright): past the limit, require a CAPTCHA (a small test to tell humans from bots) or a delay (progressive: 1 s, 2 s, 4 s) before a hard 429.
- A reviewed allowlist of known large shared egress addresses (the public addresses that a big network's traffic appears to come from) with higher limits.
The global emergency throttle sheds load without locking everyone out. Assume the service can verify 2,000 password hashes per second. Reserve 80 percent, 2,000×0.8=1,600 per second, for known-device logins and leave 2,000−1,600=400 per second for unknown ones. In an attack the unknown pool saturates and returns 429 or a CAPTCHA challenge while real returning users keep logging in.
Credential stuffing: what the per-key limits miss
A botnet that tries each leaked pair once from 100,000 different IPs sends one attempt per IP and one per account, so the 20 per minute IP limit and the 10 per minute account limit never fire. Only the global emergency throttle reacts, and it reacts to volume, not to who is attacking. What does catch it is system-wide rather than per key: a sudden rise in the overall failure rate of logins, many failures from devices with no known-device cookie, and submitted passwords that appear on a breached-password list. The responses are to add friction (CAPTCHA or a delay) to unknown-device attempts while the failure rate is high, to reject or force a reset for breached passwords, and to keep the reserved capacity for known-device logins described above so real returning users keep getting in.
This is a sketch: it covers per-IP, per-account and global counts, but a real deployment also needs alerting on distributed low-rate guessing and a path for support to unlock an account.
Response
Return 429 with Retry-After in seconds, and use identical messages for "wrong password" and "unknown account" so the limiter does not leak which accounts exist.
Common mistakes
Fixed windows at a boundary, expecting per-IP and per-account limits to stop credential stuffing, counting successes as failures, a per-account limit with no escape for the owner, failing open on store outage, and one global bucket that lets an attacker starve real users.
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