Meta

Binary Search on a Non-Decreasing \(f: \mathbb{R} \to \mathbb{R}\)

Given a number \(L\) and a non-decreasing function \(f: \mathbb{R} \to \mathbb{R}\), find the greatest \(x\) such that \(f(x) \le L\). To start, there are two numbers \(lo\) and \(hi\), such that \(f(lo) \le L < f(hi)\).

Algorithm

double binary_search(double lo, double hi, double lim) {
  while (hi - lo > precision) {
    const double mid = (hi + lo) / 2;
    if (lim < f(mid)) hi = mid; // Search in left half
    else lo = mid; // Search in right half
  }
  return lo;
}

Sample Problem

You are given two integer arrays:

• greeds, where greeds[i] represents the minimum size of a cookie that a child needs to to be satisfied.
• cookies, where cookies[j] represents the size of a cookie.

Assign cookies such that as many children as possible are satisfied. Each child can receive at most one cookie, and each cookie can be given to only one child.

A Greedy Algorithm

def num_satisfied_children(greeds: List[int], cookies: List[int]) -> int:
  greeds.sort()
  cookies.sort()

  count = 0
  g_idx, c_idx = 0, 0
  while g_idx < len(greeds) and c_idx < len(cookies):
    if cookies[c_idx] >= greeds[g_idx]:
      count += 1
      g_idx += 1

    c_idx += 1

  return count

The Event Loop

The event loop contains a collection of jobs to be run. Some jobs are added by application code, and others indirectly by asyncio. The event loop takes a job from its backlog and invokes it (“gives it control”). Once that job pauses or completes, it returns control to the event loop which then selects another job from the backlog and invokes it. When there are no jobs to be done, the event loop rests (doesn’t waster CPU cycles) and comes back when more jobs are enqueued.

Web Caching

Web caching was the original motivation for consistent hashing. With a web cache, if a browser requests a URL that is not in the cache, the page is downloaded from the server, and the result is sent to both the browser and the cache. On a second request, the page is served from the cache without contacting the server.

Notes

Sharding comes up when a single database won’t work (e.g., hit storage limits, write throughput limits, or read throughput limits) and you need to split your data across multiple independent servers.

For a user-centric social media app, sharding by user_id means all of a user’s posts, likes, and comments live on one shard. User-scoped queries are fast, but “trending posts across all users” become expensive because of hitting every shard and aggregating results. Mutating transations need to account for the distributed nature of the shards, making them complex and slow.

Notes

At a basic level, understand how services talk to each other and what happens when those connections fail or get slow.

For 90% of the use cases, default to HTTP over TCP.

WebSockets and Server-Sent Events (SSE) come up when you need real-time updates. SSE is unidirectional - the client makes an initial HTTP request to open the connection, and the server pushes data down that connection. WebSockets handle bidirectional communication where both sides send messages freely.

Notes

Indexes make database queries fast. Most relational databases use B-trees, which support exact lookups (find user with email X) and range queries (find all orders between date A and date B). Hash indexes are faster for exact matches but can’t do range queries.

There are external systems that go beyond what the primary DB provider has. Elasticsearch is the go-to for full-text search. PostGIS in Postgres is popular for geospatial queries. Such extensions typically sync from your primary DB and so the search index will lag slightly behind. However, the increased functionality is usually worth it.

Notes

Choosing what data to store and how to structure it directly affects performance, scalability, and maintenance.

Relational databases are useful when you have structured data with clear relationships and need strong consistency (transaction-based actions, enforcing foreign key constraints). NoSQL databases shine for flexible schemas or when you need to scale horizontally across many servers without complex joins.

Normalization refers to splitting data across tables to avoid duplication, e.g., you have a users table, and orders table, and a products table, where each order references a userId and productId. Normalized data is easy to keep consistent, e.g., updating a product name is limited to the products table. However, getting complete data needs joins, which get expensive on huge/many tables.

Notes

The CAP theorem states that you can only have 2 of 3 properties at once:

• Consistency: All nodes see the same data.
• Availability: Every request gets a response.
• Partition Tolerance: System works even when network connections fail between nodes.

In practice, network partitions are unavoidable in distributed system. Choosing consistency means some nodes will refuse to serve requests rather than return potentially stale data. Choosing availability means different nodes might temporarily have different data.

Notes

For read-heavy applications, storing frequently accessed data in fast memory (e.g., Redis) allows you to skip the DB entirely for some reads. A cache hit on Redis takes ~1ms compared to 20-50ms for a typical DB query, and this speedup is impactful in the order of millions of requests.

Caching requires a solution for invalidating stale data, e.g., user updates their profile in the DB. Strategies include invalidating the cache immediately after writes, using short TTLs, etc.

Notes

For 90% of interviews, default to REST, which maps resources to URLs and uses HTTP methods to manipulate them, e.g., POST /events/{id}/bookings for creating a booking.

When returning large result sets, pagination comes into play. Cursor-based pagination works better for real-time data where new items get added frequently. Offset-based pagination is fine for most cases.

Requirements (~5min)

Functional Requirements

Completions for “Users/Clients should be able to…”, e.g., for Twitter: post tweets, follow other users, and see tweets from users they follow. Keep the list targeted and prioritized (e.g., top 3) as your job is to develop a system that meets those requirements.

Non-Functional Requirements

Completions for “The system should be…”, e.g., for Twitter:

• Highly available, prioritizing availability over consistency.
• Scale to support 100M+ daily active users.
• Low latency, rendering feeds in under 200ms.

#intervals-algorithms

Merge Overlapping Intervals

Problem Statement: Merge Overlapping Intervals

Given an integer array intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of the non-overlapping intervals. For example \([[1,3],[2,6],[8,10],[15,18]] \to [[1,6],[8,10],[15,18]]\) because \([1,3]\) and \([2,6]\) overlap and merge into \([1,6]\).

Solution: Sort by Start Time and then Linear Scan

Like Minimum Size Subarray Sum , contiguity hints at a linear scan being useful. If we sort intervals by start, then it’s a matter of starting at some intervals[i] and expanding until some intervals[j], \(j > i\) is no longer overlapping.

Problem

printNumber(7) prints 7 to the console. You are given an instance of the ZeroEvenOdd class with 3 functions: zero outputs 0s, even outputs even numbers, and odd outputs odd numbers. The same ZeroEvenOdd instance is passed to three different threads, where thread A calls zero(), thread B calls even(), and thread C calls odd(). Modify ZeroEvenOdd such that given n=6, it outputs 010203040506.

Solution

Use a Condition to pass the baton between zero, even, and odd. I had trouble setting up the correct loop-exit conditions. Debugging deadlocks takes some getting used to!

Problem Statement

You’re given the FooBar class:

class FooBar:
  def __init__(self, n):
    self.n = n

  def foo(self, printFoo: "Callable[[], None]") -> None:
    for _ in range(self.n):
      printFoo()

  def bar(self, printBar: "Callable[[], None]") -> None:
    for _ in range(self.n):
      printBar()

… and the same instance of FooBar will be passed to two different threads. Thread A will call foo() while thread B will call bar(). Modify the program to output foobar n times.

Solution

Two Events

We can use two Events to communicate whose turn it is to print.

from threading import Event
from typing import Callable


class FooBar:
    def __init__(self, n):
        self.n = n
        self.foos_turn = Event()
        self.bars_turn = Event()
        self.foos_turn.set()

    def foo(self, printFoo: "Callable[[], None]") -> None:
        for _ in range(self.n):
            self.foos_turn.wait()
            printFoo()
            self.foos_turn.clear()
            self.bars_turn.set()

    def bar(self, printBar: "Callable[[], None]") -> None:
        for _ in range(self.n):
            self.bars_turn.wait()
            printBar()
            self.bars_turn.clear()
            self.foos_turn.set()

Problem Statement

There are \(L\) possible land rides and \(W\) possible water rides, with \(1 \le L, W \le 5 \times 10^4\). A tourist must experience exactly one ride from each category, in either order. A ride may be started at its opening time or any later moment. Immediately after finishing one ride, the tourist may board the other if it’s already open or wait until it opens. Return the earliest possible time at which the tourist can finish both rides.

Introduction

Threads are smaller units of a process that allow executing tasks in parallel, sharing memory space. Threads are particularly useful for I/O bound tasks, where much of the time is spent waiting for external resources.

MATT. “All part of God’s plan.” What a beautiful phrase. Kind of covers it all. Dark. Light. Don’t get yourself bothered. It’s all God’s plan. Nothing you could have done about it in any case. I understand the attraction. It’s a nice bit of hand-waving. A catchall that pushes aside the necessity for deeper examination of responsibility.

MATT. Rage. It’s everywhere in this city. People are terrified. Of what’s happened, of what might happen. Everyone is everyone’s enemy. Anyone who needs help is weak. They can’t let themselves be weak. Not in this world. They tell themselves they’re strong. They’re just afraid.

Suppose we have a class:

public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}

… and the same instance of Foo is passed to three different threads. Thread A will call first(), thread B will call second() and thread C will call third(). Design Foo such that second() is executed after first(), and third() is executed after second().

See Thread-Based Parallelism - Python for a quick primer on Python’s synchronization primitives.