tag

#systems

31 pages tagged

Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.4 Building an Event Scheduler

20.4 Building an Event Scheduler Problem Design an event scheduler that stores tasks, orders them by time, executes ready tasks, and handles updates such as cancellation or rescheduling. Schedulers appear in job queues, calendar reminders, cron systems, workflow engines, retry systems, simulation engines, distributed databases, and operating systems. The core algorithmic problem is simple: always find the next event that should run. The engineering problem is more subtle because real...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.1 Building an Autocomplete Engine

20.1 Building an Autocomplete Engine Problem Design an autocomplete engine that provides search suggestions while a user types. The system must return relevant completions with low latency, support millions of phrases, rank results by popularity, and scale as the dataset grows. Autocomplete appears in search engines, e-commerce websites, code editors, IDEs, messaging applications, and command-line interfaces. Although the user experiences a simple dropdown of suggestions, the underlying system combines multiple...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.12 Building a Cache Eviction Policy

20.12 Building a Cache Eviction Policy Problem Design a cache that stores recently used values and evicts entries when capacity is full. Caches appear in databases, operating systems, compilers, web servers, API clients, CDNs, search systems, build tools, and application frameworks. They reduce latency by keeping expensive results close to where they are needed. A cache answers two questions: Do we already have this value? If the cache is full,...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.7 Building a Log Deduplication System

20.7 Building a Log Deduplication System Problem Design a system that receives a stream of log events and removes duplicates before storage or analysis. Duplicate logs appear in distributed systems for many reasons. A service may retry sending an event after a timeout. A collector may restart and replay buffered data. A queue may provide at-least-once delivery. A client may emit the same telemetry event multiple times. If duplicates are...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.16 Building a Packet Routing Simulation

20.16 Building a Packet Routing Simulation Problem Design a simulation that routes packets through a network of routers and links. The simulator should model topology, forwarding decisions, link costs, queues, packet delivery, and packet loss. Packet routing appears in computer networks, distributed systems, data centers, sensor networks, peer-to-peer systems, and game networking. A simulator lets you test routing policies without deploying them to real infrastructure. Given this topology: A --1--...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.25 Building an Algorithm Engineering Playbook

20.25 Building an Algorithm Engineering Playbook Problem You have learned dozens of algorithms and data structures. You know how to implement binary search, heaps, graphs, dynamic programming, string matching, spatial indexes, streaming systems, schedulers, and constraint solvers. The challenge now is different. Real-world algorithm design rarely begins with: Which algorithm should I implement? It usually begins with: Why is the system slow? Why is memory growing? Why is this query...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.9 Building a Recommendation Prototype

20.9 Building a Recommendation Prototype Problem Design a recommendation system that suggests items to users based on past behavior. The system should take user-item interactions, estimate which unseen items a user may like, and return a ranked list of recommendations. Recommendation systems appear in e-commerce, video platforms, music apps, news feeds, online learning systems, developer tooling, and search products. The interface is simple: recommend items for user U The internal...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.14 Building a Static Analyzer

20.14 Building a Static Analyzer Problem Design a static analyzer that scans source code and reports likely defects without running the program. Static analyzers appear in compilers, linters, security tools, code review systems, IDEs, CI pipelines, and migration tools. They answer questions such as: Is this variable used before assignment? Is this branch unreachable? Can this value be null? Does this function violate a style rule? Does this code contain...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.13 Building a Web Crawler Frontier

20.13 Building a Web Crawler Frontier Problem Design a crawler frontier that decides which URLs a web crawler should visit next. A crawler frontier is the scheduling core of a web crawler. It stores discovered URLs, avoids duplicates, respects host politeness, prioritizes important pages, and feeds workers with crawl tasks. The crawler may discover millions or billions of URLs, but each worker only needs one answer at a time: What...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.22 Building an External Merge Sort

20.22 Building an External Merge Sort Problem Design a sorting tool that can sort data larger than available memory. External sorting appears in databases, log processors, search indexing pipelines, ETL jobs, compilers, analytics engines, and storage systems. In-memory sorting is straightforward when all records fit in RAM. When the input is larger than memory, the algorithm must use disk. Suppose you need to sort this file: 42 7 19 3...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.11 Building a Rate Limiter

20.11 Building a Rate Limiter Problem Design a rate limiter that controls how often a client can perform an operation. Rate limiters appear in APIs, login systems, payment services, message queues, search endpoints, web crawlers, background workers, and distributed systems. They protect services from overload, enforce fair usage, reduce abuse, and smooth traffic spikes. A rate limiter answers one question: Should this request be allowed right now? Example policy: Allow...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.6 Building a Compression Tool

20.6 Building a Compression Tool Problem Design a compression tool that reduces the size of textual data while preserving the original information. The tool should accept an input stream, generate a compact representation, and later reconstruct the original content exactly. Compression appears throughout computing. Source code repositories compress objects before storage. Databases compress pages to improve cache efficiency. Network protocols reduce bandwidth consumption. Log systems compress archives to reduce storage...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.2 Building a Search Ranking Pipeline

20.2 Building a Search Ranking Pipeline Problem Design a search ranking pipeline that receives a user query, retrieves candidate documents, scores them, and returns a ranked result list. Given a query: graph shortest path the system should return documents that discuss graph algorithms, shortest path algorithms, Dijkstra's algorithm, Bellman-Ford, A* search, and related topics. A naive implementation might scan every document and count query words, but that becomes too slow...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.24 Building a Verified Algorithm Sketch

20.24 Building a Verified Algorithm Sketch Problem Design a small workflow for checking an algorithm's correctness argument against its implementation. Most algorithm implementations are tested. Fewer are verified. Tests show that an algorithm works on selected inputs. Verification tries to show that an algorithm satisfies a specification for all valid inputs. A full formal proof may require a proof assistant or a verification-aware language. This section uses a lighter approach:...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.5 Building a Text Diff Tool

20.5 Building a Text Diff Tool Problem Design a text diff tool that compares two versions of a document and reports what changed. A diff tool appears in version control systems, code review tools, document editors, database migration systems, configuration management tools, and synchronization engines. The user wants a readable answer to a simple question: What changed between version A and version B? Given two texts: A: the quick brown...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.17 Building a Task Dependency Planner

20.17 Building a Task Dependency Planner Problem Design a planner that receives a set of tasks and dependencies, then returns a valid execution order. Task dependency planners appear in build systems, workflow engines, CI pipelines, package managers, deployment systems, data pipelines, compilers, and project schedulers. A task may not run until all of its prerequisites are complete. Example: parse_source depends on read_files type_check depends on parse_source generate_code depends on type_check...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.21 Building a Streaming Analytics System

20.21 Building a Streaming Analytics System Problem Design a system that consumes events continuously and computes live metrics such as counts, rates, unique users, moving averages, and top items. Streaming analytics appears in observability platforms, fraud detection, ad systems, IoT pipelines, financial monitoring, game telemetry, product analytics, and security systems. Unlike batch analytics, the input does not have a fixed end. Example event stream: 10:00:01 user=42 action=view page=/home 10:00:02 user=51...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.23 Building a Matchmaking System

20.23 Building a Matchmaking System Problem Design a matchmaking system that pairs users, players, tasks, or entities according to compatibility rules. Matchmaking appears in multiplayer games, marketplaces, job platforms, tutoring systems, dating apps, mentoring programs, ride-sharing systems, reviewer assignment tools, and distributed work schedulers. The input is a set of participants and preferences. The output is a set of matches. Example: players: A rating=1200 region=asia B rating=1230 region=asia C rating=1700...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.3 Building a Shortest Path Service

20.3 Building a Shortest Path Service Problem Design a service that answers shortest path queries over a graph. The service should receive a source node and a target node, compute a low-cost route, and return both the distance and the path. This appears in road navigation, network routing, game maps, warehouse robots, dependency planners, and knowledge graph traversal. The underlying problem is classical, but a service design adds practical constraints:...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.18 Building a Plagiarism Detector

20.18 Building a Plagiarism Detector Problem Design a plagiarism detector that compares documents and reports suspicious similarity. Plagiarism detection appears in education platforms, publishing systems, code review tools, legal workflows, hiring assessments, and content moderation systems. The input is a collection of documents. The output should identify pairs or passages that are unusually similar. A naive implementation compares every document against every other document character by character. That approach is...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.15 Building a Mini Database Index

20.15 Building a Mini Database Index Problem Design a small database index that supports fast lookup by key and efficient range scans. A database table may contain millions of rows. Without an index, a query such as: SELECT * FROM users WHERE id = 42; requires scanning rows until the target appears. A range query such as: SELECT * FROM users WHERE id BETWEEN 1000 AND 2000; requires scanning the...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.8 Building a Graph Analytics Job

20.8 Building a Graph Analytics Job Problem Design a batch job that analyzes a large graph and computes useful metrics such as degree counts, connected components, PageRank-style importance scores, and community structure. Graph analytics appears in social networks, fraud detection, recommendation systems, dependency graphs, knowledge graphs, infrastructure topology, citation networks, and web crawlers. The input is usually simple: source,target A,B A,C B,D C,D E,F The output should answer questions such...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.19 Building a Geometry Query Engine

20.19 Building a Geometry Query Engine Problem Design a geometry query engine that stores spatial objects and answers geometric questions efficiently. Geometry query engines appear in maps, CAD tools, games, robotics, logistics, GIS systems, layout engines, collision detection systems, and spatial databases. The input is a set of objects such as points, rectangles, line segments, or polygons. The query asks for objects that match a spatial condition. Common queries include:...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.10 Building a Spell Checker

20.10 Building a Spell Checker Problem Design a spell checker that detects misspelled words and suggests likely corrections. Spell checking appears in search boxes, document editors, messaging apps, code editors, command-line tools, OCR cleanup systems, and data-entry workflows. The user types: algoritm The system should suggest: algorithm A useful spell checker must do more than find dictionary words. It must rank plausible corrections, handle common typing errors, and avoid replacing...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook ›

Chapter 20. End-to-End Case Studies

Chapter 20. End-to-End Case Studies
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 20. End-to-End Case Studies ›

20.20 Building a Constraint Solver

20.20 Building a Constraint Solver Problem Design a small constraint solver that assigns values to variables while satisfying a set of rules. Constraint solvers appear in scheduling systems, puzzle engines, configuration tools, package managers, type checkers, layout engines, test-case generators, compilers, and planning systems. They answer questions such as: Can these requirements all be satisfied? Which assignment satisfies them? Which constraints conflict? A simple example is map coloring. Adjacent regions...
algorithms case-studies systems Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.15 External Sorting

6.15 External Sorting External sorting handles datasets that do not fit in main memory. The cost model changes from CPU time to I O. The goal is to minimize disk reads and writes by organizing the algorithm around sequential access and large transfers. Problem You have a dataset too large to fit into memory. You want to sort it using limited RAM and disk storage. Model Assume: N = number...
algorithms sorting external-sorting systems May 4, 2026
Programming › Algorithm Cookbook › Chapter 5. Hashing and Maps ›

5.25 Case Studies

5.25 Case Studies Problem You need to see how hash-based structures behave in complete systems rather than isolated operations. Real performance and correctness issues usually appear only when hashing interacts with full workflows: streaming data, graphs, caches, and distributed systems. This section consolidates patterns from previous recipes into concrete end-to-end designs. Case Study 1: Frequency Analysis Pipeline You need to compute frequencies over a large stream of events. Design Use...
algorithms hashing case-studies systems streaming May 4, 2026
Programming › Algorithm Cookbook › Chapter 5. Hashing and Maps ›

5.23 Cache-Aware Hashing

5.23 Cache-Aware Hashing Problem Hash tables often fail to achieve their theoretical performance because memory access patterns dominate runtime. Even with good hashing and controlled load factor, repeated cache misses can make operations significantly slower than expected. You need a design that aligns hash table behavior with CPU cache structure. Solution Structure the hash table to maximize spatial locality and reduce pointer chasing. Core strategies: - use contiguous storage for...
algorithms hashing cache performance systems May 4, 2026
Programming › Algorithm Cookbook › Chapter 5. Hashing and Maps ›

5.17 Cache Behavior

5.17 Cache Behavior Problem Hash tables are expected constant time structures, but real performance often deviates from that expectation due to memory hierarchy effects. Poor cache locality can dominate runtime even when asymptotic complexity is optimal. You need to understand how hash table design interacts with CPU caches and memory access patterns. Solution Design hash-based structures to maximize spatial locality and minimize unpredictable memory access. Key principles: - Prefer contiguous...
algorithms hashing performance cache systems May 4, 2026
Programming › Algorithm Cookbook › Chapter 5. Hashing and Maps ›

5.24 Real-World Hash Table Design

5.24 Real-World Hash Table Design Problem You need to choose and implement a hash table that performs reliably under real workloads: mixed key types, uneven access patterns, deletions, resizing, and possible adversarial input. Pure theoretical designs often fail in production due to constant factors, memory layout, and edge cases. Solution Design the hash table as a layered system with explicit responsibilities: - hashing layer - indexing layer - collision handling...
algorithms hashing design systems performance May 4, 2026