How to Solve an HLD Interview

package main

import (
	"fmt"
	"strings"
)

// The 45-minute plan, in minutes.
var plan = []struct {
	step    string
	minutes int
}{
	{"clarify requirements", 5},
	{"estimate", 5},
	{"API and data model", 5},
	{"high-level design", 10},
	{"deep dives", 15},
	{"trade-offs and wrap-up", 5},
}

type problem struct {
	name                    string
	writesPerDay, readsPerX int64 // reads per write
	bytesPerItem            int64
	realtime                bool
}

// commas writes 1234567 as 1,234,567.
func commas(n int64) string {
	s := fmt.Sprint(n)
	var b strings.Builder
	for i, c := range s {
		if i > 0 && (len(s)-i)%3 == 0 {
			b.WriteByte(',')
		}
		b.WriteRune(c)
	}
	return b.String()
}

// size prints a byte count as GB, TB or PB with one decimal.
func size(b int64) string {
	units := []string{"GB", "TB", "PB"}
	unit, i := int64(1_000_000_000), 0
	for i < len(units)-1 && b >= unit*1000 {
		unit *= 1000
		i++
	}
	tenths := (b*10 + unit/2) / unit
	return fmt.Sprintf("%d.%d %s", tenths/10, tenths%10, units[i])
}

// design turns the numbers into decisions. Each rule says which number triggered it.
func design(p problem) {
	const day, peak, years, copies = 86_400, 3, 5, 3
	writeQPS := p.writesPerDay / day * peak
	readQPS := p.writesPerDay * p.readsPerX / day * peak
	stored := p.writesPerDay * 365 * years * p.bytesPerItem * copies

	fmt.Printf("%s\n", p.name)
	fmt.Printf("  peak writes %s/s, peak reads %s/s, storage in %d years with %d copies: %s\n", commas(writeQPS), commas(readQPS), years, copies, size(stored))
	decisions := []string{"load balancer + at least 2 stateless app servers"}
	if readQPS > 1_000 {
		decisions = append(decisions, fmt.Sprintf("cache hot reads (reads %s/s > 1,000)", commas(readQPS)))
	}
	if p.readsPerX >= 10 {
		decisions = append(decisions, fmt.Sprintf("read replicas (%d reads per write)", p.readsPerX))
	}
	if writeQPS > 1_000 || stored > 10_000_000_000_000 {
		decisions = append(decisions, fmt.Sprintf("shard the data (writes %s/s, storage %s)", commas(writeQPS), size(stored)))
	} else {
		decisions = append(decisions, "one primary database is enough for now")
	}
	if p.realtime {
		decisions = append(decisions, "WebSocket gateways + pub/sub between them (real-time delivery)")
	}
	for _, d := range decisions {
		fmt.Printf("  - %s\n", d)
	}
}

func main() {
	var steps []string
	total := 0
	for _, s := range plan {
		steps = append(steps, fmt.Sprintf("%s %d", s.step, s.minutes))
		total += s.minutes
	}
	fmt.Printf("45-minute plan (%d min): %s\n", total, strings.Join(steps, ", "))

	design(problem{"URL shortener: 100M new links a month, 100 reads each, 500 B per link", 100_000_000 / 30, 100, 500, false})
	design(problem{"chat: 50M daily users, 40 messages each a day, 2 reads per message, 200 B", 50_000_000 * 40, 2, 200, true})
}

# The 45-minute plan, in minutes.
PLAN = [
    ("clarify requirements", 5),
    ("estimate", 5),
    ("API and data model", 5),
    ("high-level design", 10),
    ("deep dives", 15),
    ("trade-offs and wrap-up", 5),
]


def commas(n: int) -> str:
    return f"{n:,}"


def size(b: int) -> str:
    """A byte count as GB, TB or PB with one decimal."""
    units = ["GB", "TB", "PB"]
    unit, i = 1_000_000_000, 0
    while i < len(units) - 1 and b >= unit * 1000:
        unit *= 1000
        i += 1
    tenths = (b * 10 + unit // 2) // unit
    return f"{tenths // 10}.{tenths % 10} {units[i]}"


def design(name: str, writes_per_day: int, reads_per_write: int, bytes_per_item: int, realtime: bool) -> None:
    """Turn the numbers into decisions. Each rule says which number triggered it."""
    day, peak, years, copies = 86_400, 3, 5, 3
    write_qps = writes_per_day // day * peak
    read_qps = writes_per_day * reads_per_write // day * peak
    stored = writes_per_day * 365 * years * bytes_per_item * copies

    print(name)
    print(f"  peak writes {commas(write_qps)}/s, peak reads {commas(read_qps)}/s, storage in {years} years with {copies} copies: {size(stored)}")
    decisions = ["load balancer + at least 2 stateless app servers"]
    if read_qps > 1_000:
        decisions.append(f"cache hot reads (reads {commas(read_qps)}/s > 1,000)")
    if reads_per_write >= 10:
        decisions.append(f"read replicas ({reads_per_write} reads per write)")
    if write_qps > 1_000 or stored > 10_000_000_000_000:
        decisions.append(f"shard the data (writes {commas(write_qps)}/s, storage {size(stored)})")
    else:
        decisions.append("one primary database is enough for now")
    if realtime:
        decisions.append("WebSocket gateways + pub/sub between them (real-time delivery)")
    for d in decisions:
        print(f"  - {d}")


total = sum(m for _, m in PLAN)
print(f"45-minute plan ({total} min): {', '.join(f'{s} {m}' for s, m in PLAN)}")

design("URL shortener: 100M new links a month, 100 reads each, 500 B per link", 100_000_000 // 30, 100, 500, False)
design("chat: 50M daily users, 40 messages each a day, 2 reads per message, 200 B", 50_000_000 * 40, 2, 200, True)

// The 45-minute plan, in minutes.
const PLAN: [string, number][] = [
  ["clarify requirements", 5],
  ["estimate", 5],
  ["API and data model", 5],
  ["high-level design", 10],
  ["deep dives", 15],
  ["trade-offs and wrap-up", 5],
];

// Storage reaches about 2.2e15 bytes, below 2^53 (about 9e15), so plain numbers stay exact.
const div = (a: number, b: number) => Math.floor(a / b);
/** 1234567 as 1,234,567, without depending on the machine's locale. */
const commas = (n: number) => String(n).replace(/\B(?=(\d{3})+(?!\d))/g, ",");

/** A byte count as GB, TB or PB with one decimal. */
function size(b: number): string {
  const units = ["GB", "TB", "PB"];
  let unit = 1_000_000_000;
  let i = 0;
  while (i < units.length - 1 && b >= unit * 1000) {
    unit *= 1000;
    i++;
  }
  const tenths = div(b * 10 + unit / 2, unit);
  return `${div(tenths, 10)}.${tenths % 10} ${units[i]}`;
}

/** Turn the numbers into decisions. Each rule says which number triggered it. */
function design(name: string, writesPerDay: number, readsPerWrite: number, bytesPerItem: number, realtime: boolean) {
  const [day, peak, years, copies] = [86_400, 3, 5, 3];
  const writeQPS = div(writesPerDay, day) * peak;
  const readQPS = div(writesPerDay * readsPerWrite, day) * peak;
  const stored = writesPerDay * 365 * years * bytesPerItem * copies;

  console.log(name);
  console.log(`  peak writes ${commas(writeQPS)}/s, peak reads ${commas(readQPS)}/s, storage in ${years} years with ${copies} copies: ${size(stored)}`);
  const decisions = ["load balancer + at least 2 stateless app servers"];
  if (readQPS > 1_000) decisions.push(`cache hot reads (reads ${commas(readQPS)}/s > 1,000)`);
  if (readsPerWrite >= 10) decisions.push(`read replicas (${readsPerWrite} reads per write)`);
  if (writeQPS > 1_000 || stored > 10_000_000_000_000) decisions.push(`shard the data (writes ${commas(writeQPS)}/s, storage ${size(stored)})`);
  else decisions.push("one primary database is enough for now");
  if (realtime) decisions.push("WebSocket gateways + pub/sub between them (real-time delivery)");
  for (const d of decisions) console.log(`  - ${d}`);
}

const total = PLAN.reduce((sum, [, m]) => sum + m, 0);
console.log(`45-minute plan (${total} min): ${PLAN.map(([s, m]) => `${s} ${m}`).join(", ")}`);

design("URL shortener: 100M new links a month, 100 reads each, 500 B per link", div(100_000_000, 30), 100, 500, false);
design("chat: 50M daily users, 40 messages each a day, 2 reads per message, 200 B", 50_000_000 * 40, 2, 200, true);

// The 45-minute plan, in minutes.
const PLAN: [(&str, i64); 6] = [
    ("clarify requirements", 5),
    ("estimate", 5),
    ("API and data model", 5),
    ("high-level design", 10),
    ("deep dives", 15),
    ("trade-offs and wrap-up", 5),
];

/// 1234567 as 1,234,567.
fn commas(n: i64) -> String {
    let s = n.to_string();
    let mut out = String::new();
    for (i, c) in s.chars().enumerate() {
        if i > 0 && (s.len() - i) % 3 == 0 {
            out.push(',');
        }
        out.push(c);
    }
    out
}

/// A byte count as GB, TB or PB with one decimal.
fn size(b: i64) -> String {
    let units = ["GB", "TB", "PB"];
    let (mut unit, mut i) = (1_000_000_000i64, 0usize);
    while i < units.len() - 1 && b >= unit * 1000 {
        unit *= 1000;
        i += 1;
    }
    let tenths = (b * 10 + unit / 2) / unit;
    format!("{}.{} {}", tenths / 10, tenths % 10, units[i])
}

/// Turn the numbers into decisions. Each rule says which number triggered it.
fn design(name: &str, writes_per_day: i64, reads_per_write: i64, bytes_per_item: i64, realtime: bool) {
    let (day, peak, years, copies) = (86_400, 3, 5, 3);
    let write_qps = writes_per_day / day * peak;
    let read_qps = writes_per_day * reads_per_write / day * peak;
    let stored = writes_per_day * 365 * years * bytes_per_item * copies;

    println!("{name}");
    println!(
        "  peak writes {}/s, peak reads {}/s, storage in {years} years with {copies} copies: {}",
        commas(write_qps),
        commas(read_qps),
        size(stored)
    );
    let mut decisions = vec!["load balancer + at least 2 stateless app servers".to_string()];
    if read_qps > 1_000 {
        decisions.push(format!("cache hot reads (reads {}/s > 1,000)", commas(read_qps)));
    }
    if reads_per_write >= 10 {
        decisions.push(format!("read replicas ({reads_per_write} reads per write)"));
    }
    if write_qps > 1_000 || stored > 10_000_000_000_000 {
        decisions.push(format!("shard the data (writes {}/s, storage {})", commas(write_qps), size(stored)));
    } else {
        decisions.push("one primary database is enough for now".to_string());
    }
    if realtime {
        decisions.push("WebSocket gateways + pub/sub between them (real-time delivery)".to_string());
    }
    for d in decisions {
        println!("  - {d}");
    }
}

fn main() {
    let total: i64 = PLAN.iter().map(|(_, m)| m).sum();
    let steps: Vec<String> = PLAN.iter().map(|(s, m)| format!("{s} {m}")).collect();
    println!("45-minute plan ({total} min): {}", steps.join(", "));

    design("URL shortener: 100M new links a month, 100 reads each, 500 B per link", 100_000_000 / 30, 100, 500, false);
    design("chat: 50M daily users, 40 messages each a day, 2 reads per message, 200 B", 50_000_000 * 40, 2, 200, true);
}

import java.util.ArrayList;
import java.util.List;

public class Main {
    // The 45-minute plan, in minutes.
    static final String[] STEPS = {"clarify requirements", "estimate", "API and data model", "high-level design", "deep dives", "trade-offs and wrap-up"};
    static final int[] MINUTES = {5, 5, 5, 10, 15, 5};

    /** 1234567 as 1,234,567, without depending on the machine's locale. */
    static String commas(long n) {
        String s = Long.toString(n);
        StringBuilder b = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (i > 0 && (s.length() - i) % 3 == 0) b.append(',');
            b.append(s.charAt(i));
        }
        return b.toString();
    }

    /** A byte count as GB, TB or PB with one decimal. */
    static String size(long b) {
        String[] units = {"GB", "TB", "PB"};
        long unit = 1_000_000_000L;
        int i = 0;
        while (i < units.length - 1 && b >= unit * 1000) { unit *= 1000; i++; }
        long tenths = (b * 10 + unit / 2) / unit;
        return tenths / 10 + "." + tenths % 10 + " " + units[i];
    }

    /** Turn the numbers into decisions. Each rule says which number triggered it. */
    static void design(String name, long writesPerDay, long readsPerWrite, long bytesPerItem, boolean realtime) {
        final long day = 86_400, peak = 3, years = 5, copies = 3;
        long writeQPS = writesPerDay / day * peak;
        long readQPS = writesPerDay * readsPerWrite / day * peak;
        long stored = writesPerDay * 365 * years * bytesPerItem * copies;

        System.out.println(name);
        System.out.printf("  peak writes %s/s, peak reads %s/s, storage in %d years with %d copies: %s%n", commas(writeQPS), commas(readQPS), years, copies, size(stored));
        List<String> decisions = new ArrayList<>(List.of("load balancer + at least 2 stateless app servers"));
        if (readQPS > 1_000) decisions.add("cache hot reads (reads " + commas(readQPS) + "/s > 1,000)");
        if (readsPerWrite >= 10) decisions.add("read replicas (" + readsPerWrite + " reads per write)");
        if (writeQPS > 1_000 || stored > 10_000_000_000_000L) decisions.add("shard the data (writes " + commas(writeQPS) + "/s, storage " + size(stored) + ")");
        else decisions.add("one primary database is enough for now");
        if (realtime) decisions.add("WebSocket gateways + pub/sub between them (real-time delivery)");
        for (String d : decisions) System.out.println("  - " + d);
    }

    public static void main(String[] args) {
        int total = 0;
        List<String> steps = new ArrayList<>();
        for (int i = 0; i < STEPS.length; i++) {
            steps.add(STEPS[i] + " " + MINUTES[i]);
            total += MINUTES[i];
        }
        System.out.printf("45-minute plan (%d min): %s%n", total, String.join(", ", steps));

        design("URL shortener: 100M new links a month, 100 reads each, 500 B per link", 100_000_000L / 30, 100, 500, false);
        design("chat: 50M daily users, 40 messages each a day, 2 reads per message, 200 B", 50_000_000L * 40, 2, 200, true);
    }
}

#include <cstdint>
#include <cstdio>
#include <string>
#include <utility>
#include <vector>

using i64 = std::int64_t;

// The 45-minute plan, in minutes.
const std::vector<std::pair<std::string, int>> kPlan = {
    {"clarify requirements", 5}, {"estimate", 5},    {"API and data model", 5},
    {"high-level design", 10},   {"deep dives", 15}, {"trade-offs and wrap-up", 5},
};

// 1234567 as 1,234,567.
std::string commas(i64 n) {
    std::string s = std::to_string(n), out;
    for (size_t i = 0; i < s.size(); i++) {
        if (i > 0 && (s.size() - i) % 3 == 0) out += ',';
        out += s[i];
    }
    return out;
}

// A byte count as GB, TB or PB with one decimal.
std::string size(i64 b) {
    const char* units[] = {"GB", "TB", "PB"};
    i64 unit = 1'000'000'000;
    int i = 0;
    while (i < 2 && b >= unit * 1000) {
        unit *= 1000;
        i++;
    }
    i64 tenths = (b * 10 + unit / 2) / unit;
    return std::to_string(tenths / 10) + "." + std::to_string(tenths % 10) + " " + units[i];
}

// Turn the numbers into decisions. Each rule says which number triggered it.
void design(const char* name, i64 writesPerDay, i64 readsPerWrite, i64 bytesPerItem, bool realtime) {
    const i64 day = 86'400, peak = 3, years = 5, copies = 3;
    i64 writeQPS = writesPerDay / day * peak;
    i64 readQPS = writesPerDay * readsPerWrite / day * peak;
    i64 stored = writesPerDay * 365 * years * bytesPerItem * copies;

    std::printf("%s\n", name);
    std::printf("  peak writes %s/s, peak reads %s/s, storage in %lld years with %lld copies: %s\n", commas(writeQPS).c_str(),
                commas(readQPS).c_str(), static_cast<long long>(years), static_cast<long long>(copies), size(stored).c_str());
    std::vector<std::string> decisions = {"load balancer + at least 2 stateless app servers"};
    if (readQPS > 1'000) decisions.push_back("cache hot reads (reads " + commas(readQPS) + "/s > 1,000)");
    if (readsPerWrite >= 10) decisions.push_back("read replicas (" + std::to_string(readsPerWrite) + " reads per write)");
    if (writeQPS > 1'000 || stored > 10'000'000'000'000LL)
        decisions.push_back("shard the data (writes " + commas(writeQPS) + "/s, storage " + size(stored) + ")");
    else
        decisions.push_back("one primary database is enough for now");
    if (realtime) decisions.push_back("WebSocket gateways + pub/sub between them (real-time delivery)");
    for (const auto& d : decisions) std::printf("  - %s\n", d.c_str());
}

int main() {
    int total = 0;
    std::string steps;
    for (size_t i = 0; i < kPlan.size(); i++) {
        steps += (i ? ", " : "") + kPlan[i].first + " " + std::to_string(kPlan[i].second);
        total += kPlan[i].second;
    }
    std::printf("45-minute plan (%d min): %s\n", total, steps.c_str());

    design("URL shortener: 100M new links a month, 100 reads each, 500 B per link", 100'000'000LL / 30, 100, 500, false);
    design("chat: 50M daily users, 40 messages each a day, 2 reads per message, 200 B", 50'000'000LL * 40, 2, 200, true);
}