Question 1: Concurrent Web Crawler Implementation

Design and implement a multi-threaded web crawler that efficiently crawls a specific domain and counts unique URLs

Requirements:

  • Handle circular references and invalid URLs
  • implement rate limiting and exponential back off
  • Process robots.txt compliance
  • Support different URL schemes and redirects
  • Optimize for memory usage with large datasets

Overview

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
[Seed URLs]
    |
  [Frontier in-memory queue] <--- [Persistent overflow queue (RocksDB/file)]
    |
  [Worker Pool: N threads]
    |---> [RobotsCache] (check)
    |---> [URL Normalizer]
    |---> [Seen: BloomFilter (mem) + RocksDB (exact)]
    |---> [RateLimiter per-host]
    |---> [Fetcher (HTTP client)] --> [Redirect Handler]
    |                                   |
    |                                   v
    |                                  [Parser (streaming)]
    |                                   |
    |------- enqueue new links ---------------
    |
  [Storage: only metadata (URL, status, timestamp)]
    |
  [Metrics/Logging/Monitor]

Frontier

1
2
3
4
5
6
7
8
function offer(url):
    if not isValid(url): return
    if inmemoryQueue.size < MAX_INMEM: push(inmemoryQueue, url)
    else persistQueue.append(url)


function refillWorker():
    if inmemoryQueue.isEmpty: load up to N from persistQueue

The Frontier is the URL scheduling center. To control the memory usage, I use a bounded in-memory queue to store active tasks, and RocksDB or files as an overflow queue. When the in-memory queue is empty, I load URLs in batches from the persistent queue, avoiding loading a massive number of URLs in to memory at once.

Worker Pool

1
2
3
4
5
6
7
8
9
10
11
12
while running:
    try:
        # timeout=1 it means check running status every second to prevent program from exiting
        url = inmemoryQueue.get(timeout=1) 
    except Empty: # queue is empty, it will raise an exception
        continue
        
    try:
        fetch(url)
        process(url)
    except Exception as e:
        log.error(f"Error processing {url}: {e}")

Since crawling is I/O bound, I would use a fixed-size worker pool. The number of threads should be configurable and combined with per-host rate limiting, so concurrency improve throughput without violating politeness rules.

Seen (BloomFilter + RocksDB)

1
2
3
4
5
6
7
8
9
10
11
12
13
if bloom.mightContain(url):
    if rocksdb.contains(url):
        return false
    else:
        rocksdb.put(url, meta)
        bloom.put(url)
        uniqueCount++
        return true
else:
    bloom.put(url)
    rocksdb.put(url, meta)
    uniqueCount++
    return true

For correctness under concurrency, deduplication must be atomic. A simple contains-then-put can cause race conditions, so I would use put-if-absent semantics or protect the check-and-insert operation with lock striping.

URL Normalization

1
2
3
4
5
6
7
def normalize(u):
    p = urlparse(u)
    scheme = p.scheme.lower()
    host = p.hostname.lower()
    port = '' if p.port in (80,443,None) else f":{p.port}"
    q = sorted([(k,v) for k,v in parse_qsl(p.query) if not is_tracking_param(k)])
    return urlunparse((scheme, host+port, norm_path(p.path), '', urlencode(q), ''))
  • unify scheme and host to lowercase
  • remove default ports (80 for http, 443 for https)
  • sort query parameters and remove tracking parameters
  • normalize path (remove dot segments, trailing slashes)

URL canonicalization is essential for deduplication. Without it, the crawler may crawl the same resource many times under slightly different URL forms.

isValid

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def isValid(url):
    if not url:
        return False
        
    # 1. remove leading/trailing whitespace
    url = url.strip()
    
    try:
        p = urlparse(url)
    except Exception:
        return False
        
    # 2. Check scheme
    if p.scheme not in ('http', 'https'): 
        return False
        
    # 3. Check and normalize hostname
    hostname = p.hostname
    if not hostname: 
        return False
        
    # remove trailing dots and convert to lowercase
    hostname = hostname.rstrip('.').lower()
    
    # 4. Blacklist check
    if isBlacklisted(hostname): 
        return False
        
    return True

I would reject unsupported schemes such as mailto, javascript and tel, and only allow HTTP/HTTPS URLs. I would also validate host, path, URL length, and optionally block private IP ranges for security.

Robots.txt

1
2
3
4
5
6
7
8
if not robotsCache.has(host):
    rules = fetchRobots(host)
    robotsCache.put(host, rules)
if not rules.isAllowed(userAgent, path):
    skip
else
    crawlDelaySeconds = rules.getCrawlDelayOrDefault()
    hostRateLimiter.setRate(host, 1/crawlDelaySeconds)

Robots rules should be cached per host with TTL. Before fetching a URL, each worker checks whether the path is allowed for the configured user agent. Crawl-delay should be translated into a per-host request rate.

Rate Limiter

1
2
lim = hostLimit.computeIfAbsent(host, h -> new TokenBucket(defaultRate, burst))
lim.acquire()

A per-host token bucket ensures politeness. Even if we have many worker threads, requests to the same host are throttled independently.

HTTP Fetcher

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def handle_request_stream(url):
    try:
        # follow_redirects=False: we handle redirects manually to avoid losing control over the URL normalization and deduplication process
        with httpx.Client() as client:
            with client.stream("GET", url, follow_redirects=False, timeout=10.0) as response:
                status = response.status_code

                if 200 <= status < 300:
                    # process the response body in a streaming fashion to avoid loading the entire content into memory
                    process_body(response.iter_bytes())
                    
                elif 300 <= status < 400:
                    location = response.headers.get('location')
                    if location:
                        handle_redirect(location)
                    else:
                        logger.error(f"3xx redirect missing Location header for URL: {url}")
                        
                elif status == 429 or status >= 500:
                    retry_with_backoff(url)
                    
                else:
                    logger.warning(f"Client error {status}, dropping request: {url}")

    except httpx.HTTPError as e:
        logger.error(f"Network error executing request {url}: {e}")
        retry_with_backoff(url)
  • 200 OK -> parse HTML
  • 301 Moved Permanently -> redirect to new URL
  • 302 Found -> redirect to new URL
  • 404 Not Found -> record and skip
  • 429 Too Many Requests -> decrement rate limit and retry with backoff
  • 500/502/503/504 -> retry with backoff

I would only parse response with HTML content type and enforce timeouts and max body size to avoid downloading huge files.

Redirect Handler

  1. parse redirect URL from Location header
  2. resolve relative path to absolute path based on the original URL
  3. normalize the absolute path
  4. check again whether the domain is the same
  5. check robots.txt again for the new URL
  6. limit the number of redirects to avoid infinite loops (e.g., max 5 redirects)

Redirects should be followed up to a configured maximum depth (e.g., 5). Each redirect URL should be normalized and checked against the seen set to avoid infinite loops. If a redirect points to a different domain, it should be treated as a new URL and processed accordingly.

Exponential Backoff + Jitter

sleep = base * 2^attempt + random(0, jitter)

1
2
3
4
5
6
7
8
for attempt in 0..max:
    try fetch()
    if status ok: break
    if status is retryable: // 429, 500, 502, 503, 504
        sleep = min(maxBackoff, base * 2^attempt)
        sleep = random(0, sleep) // full jitter
        sleepMillis(sleep)
    else break

I would retry only transient failures such as 429, 5xx and network timeouts. The retry delay uses exponential backoff with full jitter to prevent retry storms.

Parser

1
2
3
for link in streamingParse(htmlStream):
    abs = resolve(baseUrl, link)
    if isSameDomain(abs): offer(abs)

I would use a streaming HTML parser and avoid storing full page content. The crawler only stores metadata and extracted links.

Same Domain

Only crawl URLs that belong to the same domain as the seed URL. This prevents the crawler from wandering off into unrelated sites.
For example, if the seed URL is https://example.com, the crawler should only follow links that resolve to example.com or its subdomains.

1
2
3
https://example.com/a
https://www.example.com/b    // check subdomain, allow
https://blog.example.com/c   // check subdomain, allow

Storage

Storage: only metadata (URL, status, timestamp)

Monitor

Prometheus metrics + Grafana dashboards

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
frontier_queue_size
persistent_queue_size
active_workers
fetch_success_count
fetch_failure_count
retry_count
redirect_count
robots_blocked_count
unique_url_count
duplicate_url_count
per_host_request_rate
average_fetch_latency
p95_fetch_latency
memory_usage
rocksdb_write_latency

whole process

Question 2: Distributed LLM Inference System Design

Design a high-throughput system for serving large language model inference requests at scale.

Requirements:

  • Support 15,000+ requests per second
  • Handle multiple model variants and sizes
  • Implement dynamic load balancing
  • Achieve sub0100ms latency for standard requests
  • Support zero-downtime model updates
  • Include comprehensive monitoring and alerting

Question 3: High-Performance Document Similarity Search

Implement an efficient algorithm for finding top-k most similar documents from a massive corpus

Requirements:

  • Handle 15M+ document corpus
  • Average document length: 1500+ words
  • Query response time: < 30 ms
  • Support real-time document additions
  • Optimize memory footprint

Question 4: Distributed System Debugging Challenge

Debug a meesage queue system experiencing performance degradation under high load

Common Issues:

  • Race conditions in concurrent message processing
  • Memory leaks from unclosed connections
  • Improper error handling causing silent failures
  • Inefficient connection pooling strategies
  • Deadlocks in multi-threaded environment

Question 5: Real-time Data Processing Pipeline

Design a system for processing streaming data with low latency and high reliability.

Requirements:

  • Process 100,000+ events per second
  • Maintain exactly-once processing semantics
  • Support complex event transformations
  • Handle out-of-order events
  • Implement fault tolerance and recovery

Question 6: Machine Learning Model Serving Optimization

Optimize an existing ML model serving system for better performance and resource utilization

Focus Areas:

  • Batch processing optimization
  • GPU memory management
  • Model parallelism strategies
  • Caching mechanisms for predictions
  • Auto-scaling based on demand

Question 7: Database Performance Tuning

Analyze and optimize a database system experiencing slow query performance.

Common Problems:

  • Missing or inefficient indexes
  • Poor query optimization
  • Lock contention issues
  • Inadequate connection pooling
  • Suboptimal schema design