DEV Community: Gouranga Das Samrat

Asymptotic Notations Explained: Big O, Omega, and Theta

Gouranga Das Samrat — Sun, 08 Nov 2026 04:00:00 +0000

Big O is just one of three notations — here's how they all fit together.

Why Three Notations?

In the previous post, we learned that Big O notation describes the upper bound of an algorithm's complexity. But sometimes you want to say more than just "it's at most this slow." Sometimes you want to express a guarantee, a tight bound, or a lower bound.

That's where the three asymptotic notations come in:

Notation	Symbol	Meaning	Describes
Big O	O	Upper bound	Worst case (at most)
Big Omega	Ω	Lower bound	Best case (at least)
Big Theta	Θ	Tight bound	Exact growth rate

Together, these give you a complete picture of an algorithm's behavior.

What "Asymptotic" Means

The word asymptotic comes from mathematics — it refers to the behavior of a function as the input approaches infinity.

We're not interested in small inputs. When n = 5, almost any algorithm is fast. We care about what happens when n = 1,000,000 or n = 10^9. At those scales, the difference between O(n) and O(n²) is the difference between a millisecond and several hours.

Asymptotic analysis ignores:

Machine-specific constants
Low-order terms
Coefficients

It captures only the essential growth rate that dominates at large n.

Big O — Upper Bound (Worst Case)

Formal definition: f(n) = O(g(n)) means there exist positive constants c and n₀ such that:

f(n) ≤ c × g(n)   for all n ≥ n₀

In plain English: from some point onwards, g(n) (multiplied by a constant) is always at least as large as f(n).

Example

f(n) = 3n + 5

We can show this is O(n):

Choose c = 4, n₀ = 5
For all n ≥ 5: 3n + 5 ≤ 4n ✓

Big O is the most commonly used notation because it answers the most practical question: "How bad can this get?"

Common mistake

Many people say "the time complexity is O(n²)" when they really mean "the exact time complexity is Θ(n²)." O(n²) just means "no worse than n²" — technically, an O(n) algorithm is also O(n²)! But in everyday usage, people usually mean the tightest O they can state.

Big Omega (Ω) — Lower Bound (Best Case)

Formal definition: f(n) = Ω(g(n)) means there exist positive constants c and n₀ such that:

f(n) ≥ c × g(n)   for all n ≥ n₀

In plain English: from some point onwards, f(n) is always at least c × g(n). Omega gives you a floor — a guarantee that the algorithm will take at least this long.

Example

Sorting a list of n elements requires at least O(n log n) comparisons in the comparison-based model. This is a lower bound — no comparison-based sorting algorithm can do better. We write:

Sorting complexity = Ω(n log n)

When is Ω useful?

Omega is used in theoretical computer science to prove impossibility results — showing that no algorithm can solve a problem faster than a certain bound.

Big Theta (Θ) — Tight Bound (Exact Growth Rate)

Formal definition: f(n) = Θ(g(n)) if and only if:

f(n) = O(g(n))   AND   f(n) = Ω(g(n))

In other words, f(n) and g(n) grow at the same rate (up to constant factors). Theta is the most precise notation — it pins down both the ceiling and the floor.

Example

Merge sort always performs Θ(n log n) operations — whether the input is sorted, reversed, or random. There's no best-case shortcut.

Contrast that with insertion sort:

Best case (already sorted): Ω(n) — only one pass needed
Worst case (reverse sorted): O(n²)
So insertion sort is not Θ(n log n) — it doesn't have a tight bound that works for all inputs.

Visual Intuition

Imagine f(n) is a curve on a graph, and g(n) is a reference curve:

        ↑
        |         f(n)
        |       /
O(g(n))|----/--------  upper bound (ceiling)
        |  /
Θ(g(n))|/            tight bound (matches both)
        |
Ω(g(n))|____________  lower bound (floor)
        +----------→ n

O says: "f never goes above this ceiling (eventually)"
Ω says: "f never goes below this floor (eventually)"
Θ says: "f is sandwiched between the same ceiling and floor"

Little-o and Little-omega (Bonus Notations)

There are also strict versions of Big O and Omega:

Little-o (o(g(n))): f grows strictly slower than g. The difference is that Big O allows equality; little-o does not.

Example: 2n = o(n²) but n² ≠ o(n²)

Little-omega (ω(g(n))): f grows strictly faster than g.

These are used less often in practice but appear in advanced algorithm analysis.

Comparing the Notations: A Summary

Notation	Intuition	Analogy
O(g)	f ≤ c·g (eventually)	f ≤ g (≤)
Ω(g)	f ≥ c·g (eventually)	f ≥ g (≥)
Θ(g)	Both O and Ω hold	f = g (=)
o(g)	f/g → 0 as n→∞	f < g (<)
ω(g)	g/f → 0 as n→∞	f > g (>)

Practical Takeaways for Everyday Programming

Use Big O when communicating worst-case performance (most common).
Use Theta when you know the exact growth rate (e.g., merge sort is Θ(n log n)).
Use Omega when you want to argue about what's impossible to improve.
Always state which case (best/average/worst) your notation refers to, since the same algorithm can have different complexities in different scenarios.

Examples of All Three in One Algorithm

Linear search in an unsorted array looking for a target:

Best case (target is first element): Ω(1) — found immediately.
Worst case (target is last or not present): O(n) — scan the whole array.
Average case (target is somewhere in the middle): Θ(n/2) = Θ(n).

So linear search is O(n), Ω(1), and its average case is Θ(n). It does not have a single tight-bound Θ that applies to all cases.

Summary

Big O (O) — upper bound. The algorithm runs in at most this time. Most commonly used.
Big Omega (Ω) — lower bound. The algorithm takes at least this long.
Big Theta (Θ) — tight bound. The algorithm's runtime is exactly this growth rate (within constants).
Asymptotic analysis focuses on large n, ignoring constants and lower-order terms.
An algorithm can have different complexities for best, worst, and average cases.

Next up: we'll look at Best, Worst, and Average Case Analysis in depth — and why all three matter depending on your use case.

Time Complexity and Big O Notation: How to Measure Algorithm Speed

Gouranga Das Samrat — Sat, 07 Nov 2026 04:00:00 +0000

Stop guessing whether your code is fast — learn to measure it properly.

The Problem with "It Runs Fast on My Machine"

When two programmers debate whose solution is better, the argument often devolves into: "Mine ran in 0.3 seconds." But that's meaningless. Your colleague might have a faster CPU. The input might be small. The test might have been run under special conditions.

We need a universal, hardware-independent way to describe how fast an algorithm is. That's where time complexity and Big O notation come in.

What Is Time Complexity?

Time complexity describes how the runtime of an algorithm grows as the size of the input grows.

We don't measure actual seconds. We count the number of basic operations — comparisons, assignments, additions — in terms of the input size n.

For example, if an algorithm does 3n + 5 operations for an input of size n, we say its time complexity is roughly O(n) — linear.

Big O Notation: The Language of Efficiency

Big O (written O(...)) describes an upper bound on an algorithm's growth rate. It tells you the worst case: no matter what, this algorithm will take at most this many steps.

The key rules of Big O:

Drop constants — O(2n) becomes O(n). We care about growth rate, not exact counts.
Drop lower-order terms — O(n² + n) becomes O(n²). At large n, the dominant term wins.
Different inputs get different variables — If a function loops over array A (size a) and array B (size b), it's O(a + b), not O(n²).

The Big O Hierarchy (From Best to Worst)

Notation	Name	Example
O(1)	Constant	Array index access
O(log n)	Logarithmic	Binary search
O(n)	Linear	Linear search
O(n log n)	Linearithmic	Merge sort, heap sort
O(n²)	Quadratic	Bubble sort, nested loops
O(n³)	Cubic	Triple nested loops
O(2ⁿ)	Exponential	Recursive Fibonacci (naive)
O(n!)	Factorial	Brute-force permutations

As inputs grow, the difference between these complexities becomes enormous. For n = 1,000:

O(log n) → ~10 operations
O(n) → 1,000 operations
O(n²) → 1,000,000 operations
O(2ⁿ) → 10^301 operations (the universe would end first)

O(1) — Constant Time

An algorithm runs in constant time when its number of operations doesn't change with input size.

def get_first(arr):
    return arr[0]  # Always 1 operation, no matter the array size

Accessing an element by index in an array is O(1). It doesn't matter if the array has 10 elements or 10 billion — the computer jumps directly to that memory address.

O(n) — Linear Time

An algorithm runs in linear time when the number of operations scales directly with input size.

def linear_search(arr, target):
    for element in arr:          # n iterations in the worst case
        if element == target:
            return True
    return False

If the array doubles in size, the loop takes twice as long. Classic linear time.

O(n²) — Quadratic Time

Quadratic time typically comes from nested loops.

def has_duplicates(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):   # Nested loop → O(n²)
            if arr[i] == arr[j]:
                return True
    return False

If n = 100, this does ~5,000 comparisons. If n = 1,000, it does ~500,000. Quadratic algorithms become very slow for large inputs.

O(log n) — Logarithmic Time

Algorithms that halve the search space on each step are logarithmic.

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Binary search on 1,000 elements takes at most ~10 steps. On 1,000,000 elements, at most ~20 steps. That's the power of logarithmic complexity.

Calculating Big O: Step-by-Step

Rule 1 — Single loops are O(n):

for i in range(n):
    do_something()   → O(n)

Rule 2 — Nested loops multiply:

for i in range(n):
    for j in range(n):
        do_something()  → O(n × n) = O(n²)

Rule 3 — Sequential blocks add:

for i in range(n):     → O(n)
    ...
for j in range(n):     → O(n)
    ...
Total: O(n + n) = O(2n) = O(n)

Rule 4 — Halving loops are O(log n):

while n > 1:
    n = n // 2      → O(log n)

Space Complexity

Big O doesn't just apply to time — it applies to memory too.

Space complexity measures how much extra memory an algorithm uses as input grows.

def double_array(arr):
    result = []            # Creates a new array of size n → O(n) space
    for x in arr:
        result.append(x * 2)
    return result

An in-place algorithm that modifies the input without creating new data structures uses O(1) extra space.

Common Mistakes When Analyzing Big O

Mistake 1 — Including input size in space complexity.
Input always takes O(n) space. We measure the extra space the algorithm uses, not the storage of the input itself.

Mistake 2 — Assuming nested loops are always O(n²).
If the inner loop doesn't depend on the outer loop variable, it might still be O(n²), or it might be O(n × m) for different-sized inputs.

Mistake 3 — Forgetting recursion uses stack space.
A recursive function that calls itself n times uses O(n) stack space, even if each call does O(1) work.

A Quick Reference

O(1)       < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
Constant     Log         Linear  N-Log-N      Quad     Exp      Factorial

When you write code, always ask: "What is the Big O of this?" It becomes second nature with practice.

Summary

Time complexity measures how operations grow with input size — not actual time in seconds.
Big O notation gives an upper bound, describing worst-case growth.
Drop constants and lower-order terms.
Common complexities from best to worst: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!).
Space complexity applies the same idea to memory usage.
Nested loops multiply; sequential blocks add.

In the next post, we'll go deeper into the three types of asymptotic notations — Big O, Omega (Ω), and Theta (Θ).

Getting Started with Data Structures and Algorithms: A Beginner's Guide

Gouranga Das Samrat — Sun, 01 Nov 2026 04:00:00 +0000

The foundation every programmer needs — explained simply.

What Are Data Structures?

Before you can write efficient programs, you need to understand how to organize and store data. A data structure is simply a way of arranging data in a computer's memory so that it can be used efficiently.

Think of it like a kitchen. You could throw all your utensils into one big drawer — that works, but finding a specific spoon takes forever. Instead, most people use organizers: one slot for forks, one for knives, one for spoons. That's the idea behind data structures.

Some common data structures include:

Arrays — A fixed-size, ordered collection of elements stored contiguously in memory.
Linked Lists — A chain of nodes where each node points to the next.
Stacks — A last-in, first-out (LIFO) structure.
Queues — A first-in, first-out (FIFO) structure.
Trees — Hierarchical structures with a root and child nodes.
Graphs — A set of nodes connected by edges.
Hash Tables — Key-value stores with near-instant lookup.

What Are Algorithms?

An algorithm is a step-by-step set of instructions to solve a specific problem. Every program you write uses algorithms — even something as simple as adding two numbers involves a procedure.

Good algorithms are:

Correct — They produce the right output for all valid inputs.
Efficient — They use as little time and memory as possible.
Clear — They are easy to understand and maintain.

Why Learn DSA?

You might wonder: "My code works fine without knowing this stuff. Why bother?"

Here's the honest answer — it depends on scale. A naive algorithm that works in milliseconds for 100 items might take hours for 1,000,000 items. Real-world systems process massive amounts of data constantly. DSA gives you the tools to write software that scales.

Beyond performance, DSA is also:

Essential for coding interviews — Nearly every tech company (Google, Amazon, Meta, etc.) tests DSA heavily.
A gateway to advanced topics — Machine learning, compilers, databases, and operating systems are all built on DSA concepts.
A way of thinking — Learning DSA trains you to break down problems and think logically.

How Memory Works (The Very Basics)

To understand data structures, you need a mental model of memory.

Imagine your computer's RAM as a long strip of numbered boxes. Each box holds one unit of data (typically a byte). When your program needs to store something, it claims some boxes.

Memory addresses:
[100][101][102][103][104][105]...
  5    12   3    8    7    2  ...

A variable like int x = 5 simply puts the value 5 at some address, say 100.

An array of 5 integers occupies 5 consecutive boxes. A linked list, on the other hand, can scatter its data across non-consecutive addresses and uses pointers (addresses) to connect each piece.

This fundamental difference — contiguous vs. non-contiguous storage — is at the heart of most data structure trade-offs.

Static vs. Dynamic Data Structures

Property	Static (e.g., Array)	Dynamic (e.g., Linked List)
Size	Fixed at creation	Grows/shrinks at runtime
Memory	Allocated upfront	Allocated on demand
Access speed	Fast (O(1) random access)	Slower (O(n) traversal)
Insertion/Delete	Expensive (shifting)	Cheap (pointer update)

Primitive vs. Non-Primitive Data Types

Primitive data types are built into the language: int, float, char, bool. They hold a single value.

Non-primitive (or composite) data types are built from primitives. They include arrays, structures, classes, and all the data structures you'll learn throughout this series.

Linear vs. Non-Linear Data Structures

Linear structures store data sequentially:

Arrays
Linked Lists
Stacks
Queues

Non-linear structures organize data hierarchically or as a network:

Trees
Graphs

Linear structures are generally simpler to implement. Non-linear structures model real-world relationships (like file systems or social networks) more naturally.

The Relationship Between Data Structures and Algorithms

Data structures and algorithms are two sides of the same coin. The data structure you choose directly affects which algorithms you can use — and how fast they'll run.

For example:

Searching is O(n) in a linked list but O(log n) in a binary search tree.
Insertion is O(1) at the head of a linked list but O(n) for a sorted array.

Choosing the right data structure for your problem is often the most important design decision you'll make.

A Roadmap for Learning DSA

Here's a suggested learning path (roughly what this blog series follows):

Basics ← You are here
Time Complexity & Big O Notation
Asymptotic Notations
Best, Worst & Average Case Analysis
Abstract Data Types (ADTs)
Arrays & Array Operations
Linear vs. Binary Search
Linked Lists (Singly, Doubly, Circular)
Stacks
Queues
Trees & Binary Trees
Sorting Algorithms

Summary

A data structure is a way of organizing data in memory.
An algorithm is a step-by-step procedure to solve a problem.
Memory is a linear sequence of addressable boxes.
Data structures are either static (fixed size) or dynamic (resizable).
Data is either stored linearly (arrays, lists) or non-linearly (trees, graphs).
Choosing the right structure is critical to writing efficient software.

In the next post, we'll dive into Time Complexity and Big O Notation — the language we use to talk about how fast (or slow) an algorithm really is.

Google Says It's Not on Termux. It Is. Here's How to Install It.

Gouranga Das Samrat — Mon, 26 Oct 2026 16:00:00 +0000

Search "install Zed on Termux" and you'll get a pile of answers that boil down to "not supported." Same for Ghostty. Same for DBeaver. Same for half the tools I maintain.

They're wrong, and it's not entirely Google's fault.

Official install docs list Linux, macOS and Windows. Termux isn't on that list, so a search engine reading those pages concludes it doesn't exist. Meanwhile the real answer is sitting in a package repository that search engines don't index as readable pages. Zed's own docs point people to Repology for a current list of third-party packages, which tells you where the truth lives.

So here's the short version of how to install things, written for people who got told "not available" and gave up.

Step 0: make sure your Termux isn't the problem

Half of the "package not found" reports I see come from the wrong Termux build.

The official sources are F-Droid and the GitHub releases of termux/termux-app. The Google Play build is deprecated: it doesn't get updates and ships outdated repository URLs. If you installed Termux from the Play Store, nothing below will work properly, and no amount of googling will fix it.

Two rules when you switch:

Don't mix sources. Termux and every plugin (Termux:API, Termux:Styling, Termux:Widget and so on) have to come from the same place, because the signatures differ.
Uninstall everything first, and back up anything you care about. The Termux wiki has a backup guide.

Step 1: update before you search

A stale package index is the second most common cause of "Unable to locate package."

pkg update && pkg upgrade

If updates fail or the mirror looks dead, switch mirrors with the tool Termux ships for exactly this:

termux-change-repo

Step 2: check whether the package exists

Don't ask Google. Ask the package manager.

pkg search ghostty
pkg list-all | grep -i dbeaver
pkg show bun

If pkg search comes back empty for something that should exist, you probably haven't enabled the right repository. That's the next step.

Step 3: enable x11-repo for anything with a window

Termux splits GUI software into a separate repository that isn't turned on by default. Everything with a graphical interface lives there: Zed, Ghostty, DBeaver, Thonny, Bruno, CopyQ, Albert, and Playwright.

pkg install x11-repo
pkg update

That's the trick. A huge number of "not available" answers are really "you haven't enabled x11-repo yet."

Step 4: install the command line tools

These are in the main repository. No extra setup:

# JS and Go tooling
pkg install bun pnpm golangci-lint gosec govulncheck goreleaser sqlc

# database clients
pkg install pgcli mycli litecli iredis mongosh

# HTTP and load testing
pkg install httpie hurl k6 oha hey

# cloud CLIs
pkg install azure-cli oci-cli doctl

# git and Rust tooling
pkg install jujutsu bacon git-cliff cargo-audit

Install what you need, not the whole list. A phone has limited storage, and some of these are large.

If a command isn't found after installing, check where the files went:

dpkg -L <package-name> | grep bin/

Step 5: GUI apps need a display

Graphical packages need something to draw on. I already wrote up that setup, from the Termux:X11 app to a full XFCE desktop, in Turn Your Android Into a Full Desktop, No Root Needed. Do that once. After that, a GUI app is just another package:

pkg install dbeaver zed ghostty bruno

These are big. On a phone with limited storage, install them one at a time.

Step 6: Playwright

Browser automation on a phone sounds ridiculous until you need it. Both packages live in x11-repo:

pkg install playwright python-playwright

The Python package is patched to use the system driver instead of the one bundled in the wheel, so don't pip install playwright over the top of it. You'll replace the working setup with the one that doesn't run.

When it still doesn't work

What you see	What it usually means
`Unable to locate package`	x11-repo isn't enabled, your index is stale, or the package isn't built for your architecture. Run `pkg update`, then check `uname -m`.
`Bad system call`	Android's seccomp filter killed a syscall the program tried. This is a packaging bug, not something you did wrong. Open an issue.
App closes on its own after a while	Android is killing background processes. Newer Android versions are aggressive about it. Search for "Termux phantom process killer" and apply the fix for your Android version.
Package installs but the command is missing	The binary has a different name than the package. Use `dpkg -L` as shown above.
Everything is weird and old	You're on the Play Store build. See Step 0.

On architecture: run uname -m if a package refuses to install. Most modern phones report aarch64. Not every package is built for every architecture, so something can exist on one device and not on another.

Help fix the search results

Search engines learn from pages. If you got something running, write about it, post the commands, and mention Termux in the title. That's the fastest way to push the "not available" answers down.

If you're an upstream maintainer, adding one line to your install docs saying "Termux: pkg install yourtool" does more than any SEO trick I know.

Everything I maintain is listed on Repology. If a package fails for you, or you want something packaged that isn't there yet, find me on GitHub and open an issue.

DSA — Beginner to Advance: Complete Curriculum

Gouranga Das Samrat — Mon, 26 Oct 2026 02:00:00 +0000

Every topic, every date. Bookmark this and follow along.

Data Structures and Algorithms — the one thing that separates a developer who passes interviews from one who doesn't. More importantly, it separates code that works from code that scales.

This series takes you from zero to interview-ready, week by week.

🟢 Beginner — Foundations

#	Topic	Publish Date
1	Getting Started with Data Structures and Algorithms	Nov 1
2	Time Complexity and Big O Notation	Nov 7
3	Asymptotic Notations Explained	Nov 8
4	Best, Worst, and Average Case Analysis	Nov 14
5	Abstract Data Types (ADTs)	Nov 15
6	Arrays and Array Operations	Nov 21
7	Linear Search vs. Binary Search	Nov 22
8	Linked Lists: Dynamic Memory and Pointers	Nov 28
9	Circular and Doubly Linked Lists	Nov 29
10	Stacks: The LIFO Structure	Dec 5
11	Queues: The FIFO Structure	Dec 6

🔵 Intermediate — Core Data Structures

#	Topic	Publish Date
12	Trees and Binary Trees: Hierarchical Data	Dec 12
13	Binary Search Trees: Ordered Trees	Dec 13
14	Sorting Algorithms: From Bubble Sort to Merge Sort	Dec 19
15	Hash Tables: The Magic Behind O(1) Lookups	Dec 20
16	Graphs: The Most Powerful Data Structure	Dec 26
17	Heaps and Priority Queues	Dec 27
18	AVL Trees and Red-Black Trees	Jan 2
19	Tries (Prefix Trees): Data Structure Behind Autocomplete	Jan 3

🔴 Advanced — Algorithms

#	Topic	Publish Date
20	Dynamic Programming: Breaking Hard Problems	Jan 9
21	Advanced Graph Algorithms: MST, SCC, and More	Jan 10
22	Segment Trees and Fenwick Trees	Jan 16
23	Greedy Algorithms: Locally Optimal Choices	Jan 17
24	Backtracking: Systematic Search Through All Possibilities	Jan 23
25	String Algorithms: KMP, Rabin-Karp, and Z-Algorithm	Jan 24
26	Divide and Conquer: Split, Solve, Combine	Jan 30
27	Advanced Hashing and Bloom Filters	Jan 31

📅 How to Follow This Series

New posts drop every Saturday & Sunday
Start from #1 — every concept builds on the previous
Each post includes examples and complexity analysis

Follow to get notified when each post drops.

Zed, Bun, Ghostty: Hard Mode Packaging on Android

Gouranga Das Samrat — Sun, 25 Oct 2026 16:00:00 +0000

The hard tier is software that assumes a full desktop Linux box. GPU loaders, shared memory, process watchers, JIT engines, and dependency trees so big nobody on the upstream team has read all of them.

I maintain a good chunk of that tier for Termux. Here's what the patches look like, and what each one is really saying.

Bun: nine patches, three of them syscalls

Bun has the longest patch stack I deal with regularly. The filenames tell most of the story:

Patch	What it fixes
`0001` default to symlink install backend	`bun install` uses symlinks by default
`0002` remove Werror and unsupported flags	Build stops failing on warnings and flags this toolchain lacks
`0003` disable close_range	Skip a syscall Android may refuse
`0004` set termux tmpdir	Temp files go to `$PREFIX/tmp` instead of `/tmp`
`0005` fix bash completion empty regex	Completion generation no longer chokes
`0006` fix symlink bin chmod	`chmod` on symlinked binaries stops failing
`0007` disable pidfd_open	Another filtered syscall, another fallback
`0008` disable statx	Same story
`0009` android link rust as machine code	Linking fix for the Rust-built part on Android

Read that list again. Three of nine are the same bug wearing different hats: the runtime probes a modern kernel feature, Android's filter objects. Upstream already carries fallbacks for old kernels, so the patch is mostly "pretend you're on an old kernel."

I like this class of fix because it's small and honest. It doesn't fork the project. It doesn't rewrite anything. It switches off a fast path and lets the existing slow path run.

Ghostty: GPU terminal, six patches

Ghostty is a good example of a project that makes zero Android assumptions, which is fair, it's a desktop terminal. Six patches got it running:

Patch	Problem it solves
`0001` dcimgui use desktop GL loader on android	The UI layer picks the wrong GL loader for the target
`0002` kitty graphics no shm_open on android	Bionic has no `shm_open`, so the image protocol needs another path
`0003` global skip xev io_uring probe on android	The `io_uring` feature probe is a `SIGSYS` waiting to happen
`0004` android default shell, home and /bin/sh	Sensible defaults when there's no `/bin/sh` and no standard home
`0005` os file android tmpdir	Yes, `/tmp` again
`0006` termio android process watcher without pidfd	Watch child processes without `pidfd`

If you've read part one, you've already seen four of those problems. Only the GL loader is new. The same short list of Android quirks keeps showing up in completely unrelated codebases, and that's the main thing I've learned. After the first dozen ports, a failure stops being a mystery and becomes a checklist.

Zed: when the dependency tree is the problem

Zed is where the approach changes. The editor itself is fine. The trouble is in the crates underneath it. My recipe carries patches for alacritty_terminal, ipc-channel, trash, wasmtime-internal-jit-icache-coherence, wayland-cursor, x11rb-protocol and zed-scap, plus a workspace-level patch that wires them together.

Patching code that lives in other people's crates is where Rust packaging gets fiddly. The workable approach is to vendor the dependencies, patch the vendored sources, and tell Cargo to build from them:

# illustrative shape; real recipes differ per package
termux_step_pre_configure() {
    termux_setup_rust

    cd "$TERMUX_PKG_SRCDIR"
    cargo vendor --locked vendor > /dev/null

    mkdir -p .cargo
    cat >> .cargo/config.toml <<-EOF
        [source.crates-io]
        replace-with = "vendored-sources"

        [source.vendored-sources]
        directory = "vendor"
    EOF

    for diff in "$TERMUX_PKG_BUILDER_DIR"/*.vendor.diff; do
        patch -p1 < "$diff"
    done

    # Cargo verifies vendored files against recorded checksums.
    # Patched files fail that check, so clear the file list.
    for f in vendor/*/.cargo-checksum.json; do
        sed -i 's/"files":{[^}]*}/"files":{}/' "$f"
    done
}

The checksum step is the one that eats an afternoon. You patch a vendored crate, run the build, and Cargo tells you a file changed. It's correct, you did change it. Emptying the files map in .cargo-checksum.json is how you tell it that's intentional.

Zed also ships a zed-shim.sh. I use shims when an app needs environment set up before it starts, and I'd rather wrap it than fork it:

#!@TERMUX_PREFIX@/bin/sh
# illustrative shape
export TMPDIR="${TMPDIR:-@TERMUX_PREFIX@/tmp}"
exec "@TERMUX_PREFIX@/opt/example/bin/example" "$@"

Bruno has the same kind of shim, alongside two patches of its own: one to lazy-load node-pty, and one so the machine-id lookup doesn't try to execute anything.

Browser automation on a phone

Playwright is the one that makes people do a double take. Browser automation needs a browser, a driver, and a runtime that agree with each other. The recipe has android-support.patch, two Firefox patches (firefox-support and firefox-single-window), and a path-matching fix. The Python side, python-playwright, has a use-system-driver.patch, so it talks to the driver installed on the system instead of the one bundled in the wheel.

That bundled driver is a good example of a general rule: anything that ships its own prebuilt binary is a candidate for "swap it for the system one."

The small stuff matters too

Not every patch is dramatic. Some of my favorites are tiny:

numbat disables Android plotting support, because the plotting backend has no business running here.
pnpm builds sha2 without asm.
uutils-coreutils carries fixes for 32-bit devices: an auxv fix, a 32-bit stat mode fix in tail, and a small syncfs.c. A lot of phones are still 32-bit, and nobody tests for them.
thonny needed four patches around mypy, shell detection and path opening.
albert has six patches for its XDG handling, system utilities and plugin loading.

What I'd tell anyone starting

Read the failure literally. ENOENT is a path problem. SIGSYS is a syscall problem. A missing symbol is a Bionic gap. Most of the work is classifying the failure correctly.

Prefer small, guarded patches. Wrap the change in __ANDROID__ or the language equivalent, and keep it narrow. Those are patches upstream might actually accept.

Shim before you fork. An env-setting wrapper script is easier to maintain than a diverged repository.

And be honest about the cost. Every version bump is a rebase. Nine patches on Bun means nine things that can break on the next release. That's the part nobody writes blog posts about, and it's most of the job.

Where to find it

Everything I maintain is tracked on Repology, and I'm on GitHub if you want to see the work, open an issue, or tell me which package you'd like to see next.

Termux has limits. I just don't agree with where most people think they are.

Rate Limiter Designs

Gouranga Das Samrat — Sun, 25 Oct 2026 04:00:00 +0000

Rate limiting is a classic system design topic. Know ALL the algorithms — not just one.

Why Rate Limit?

Protect APIs from abuse (DDoS, scraping)
Ensure fair usage across clients
Protect downstream services from overload
Enforce business rules (free tier: 100 req/day)

Algorithm 1: Fixed Window Counter

Window: 00:00 → 01:00
Limit: 100 requests per hour

User sends request at 00:59:59 → counter = 100 → allowed ✅
User sends request at 01:00:01 → new window, counter = 1 → allowed ✅

Problem: Boundary burst attack

00:59 → 100 requests (at limit)
01:00 → 100 requests (new window reset)
Total: 200 requests in 2 seconds 💥

✅ Simple, low memory
❌ Allows 2x traffic at window boundaries

Algorithm 2: Sliding Window Log

Store timestamp of every request in a log (sorted set)
On new request: remove timestamps older than window, count remaining
If count < limit → allow

Limit: 5 requests per minute
Log: [00:00:10, 00:00:30, 00:00:45, 00:00:55]
New request at 00:01:20:
  Remove entries < 00:00:20 → log: [00:00:30, 00:00:45, 00:00:55]
  Count = 3, limit = 5 → allow ✅
  Add 00:01:20 to log

✅ Perfectly accurate, no boundary problem
❌ High memory — store every request timestamp
❌ Doesn't scale to millions of users

Algorithm 3: Sliding Window Counter (Hybrid)

Combine fixed window simplicity with sliding accuracy
Use weighted count from current + previous window

Limit: 100 req/min
Previous window count: 80
Current window count: 30
Time into current window: 25% elapsed

Estimated rate = 80 * (1 - 0.25) + 30 = 90 → under limit ✅

✅ Memory efficient (only 2 counters)
✅ Good approximation (Cloudflare uses this)
❌ Slightly approximate, not exact

Algorithm 4: Token Bucket 🪣

Bucket capacity: 10 tokens
Refill rate: 1 token/second

Each request consumes 1 token
If bucket empty → reject request

Bucket refills continuously at fixed rate

Allows bursts up to bucket capacity
Smooth average rate enforced over time
✅ Natural burst handling (users expect some burst tolerance)
✅ Low memory (capacity + current tokens + last refill time)
✅ Used by: AWS API Gateway, Stripe, most cloud providers

Implementation with Redis:

tokens = redis.get(key)
now = time.time()
tokens = min(capacity, tokens + (now - last_refill) * rate)
if tokens >= 1:
    tokens -= 1
    redis.set(key, tokens)
    allow()
else:
    reject()

Algorithm 5: Leaky Bucket 🚿

Requests enter a queue (bucket)
Queue drains at fixed rate (the "leak")
If queue full → reject new requests

Output is ALWAYS at fixed rate — no bursts
✅ Smooths out traffic perfectly
✅ Good for protecting downstream services that can't handle spikes
❌ Requests queue up — adds latency
❌ Burst requests at start of window get queued, not rejected fast

Difference from Token Bucket:

Token Bucket: allows bursts at token bucket capacity
Leaky Bucket: forces steady rate, queues or drops excess

Where to Implement Rate Limiting

Layer	Tool	Notes
Edge/CDN	Cloudflare Rate Limiting	Best for DDoS protection
API Gateway	AWS API Gateway, Kong	Easy to configure
Application	Redis-based counter	Most flexible, custom logic
Database	pg_rate_limit, etc	Rare, usually too late

In distributed systems: Use a centralized store (Redis) so all API server instances share the same counter.

Rate Limit Response

HTTP 429 Too Many Requests
Headers:
  X-RateLimit-Limit: 100
  X-RateLimit-Remaining: 0
  X-RateLimit-Reset: 1704067260
  Retry-After: 60

⚖️ Which Algorithm to Choose?

Scenario	Algorithm
Simple API limits	Fixed Window (simple to implement)
Accurate sliding limits	Sliding Window Counter
Allow burst, limit average	Token Bucket ✅ (most common answer)
Smooth output rate	Leaky Bucket

Default interview answer: Token Bucket — it's what AWS uses and it handles real-world traffic patterns well.

Termux Isn't Linux. I Packaged 70+ Tools for It Anyway

Gouranga Das Samrat — Sat, 24 Oct 2026 11:13:39 +0000

Termux looks like Linux right up until you try to build something that matters.

You get a shell, a package manager, a familiar prompt. Then you clone a project, run its build script, and watch it die on a path that doesn't exist, a syscall you aren't allowed to make, or a libc function that was never there.

I got tired of watching it fail, so I started fixing it. I now maintain 70+ packages for Termux, including things people assume can't run on a phone: Bun, Zed, Ghostty, Playwright, Codex, DBeaver. This is the first of two posts. This one is about the wall. The next one is about what's on the other side.

What Termux actually is

Termux is not a Linux distro that happens to run on Android. It's a userland compiled against Android's own C library, Bionic, living inside a private app directory.

$ echo $PREFIX
/data/data/com.termux/files/usr

$ ls /bin /tmp /usr
ls: cannot access '/bin': No such file or directory
ls: cannot access '/tmp': No such file or directory
ls: cannot access '/usr': No such file or directory

Three consequences, and every build failure I've fixed traces back to one of them:

No glibc. Bionic is smaller and has gaps. It has no shm_open, for example, and a lot of upstream code never checks.
No standard filesystem layout. Everything lives under $PREFIX. You can't create /tmp or /bin/sh without root, and I'm not interested in solutions that need root.
A syscall filter. Android sandboxes apps with seccomp. Depending on the Android version, calling a filtered syscall doesn't return ENOSYS. It kills the process with SIGSYS.

There is a route where you drag glibc along with a runner and execute stock Linux binaries. It works for some things. I'd rather ship native packages, so the person on the other end types pkg install and moves on with their day.

Fix 1: rewrite the paths, don't emulate them

Upstream code hardcodes /usr/share/whatever and /etc/whatever. Fighting that at runtime is a losing game. Patch it at build time, once:

termux_step_pre_configure() {
    sed -i "s|\"/usr/share/example-tool\"|\"$TERMUX_PREFIX/share/example-tool\"|" \
        src/paths.c
}

When the same placeholder shows up in several files, I use a token like @TERMUX_PREFIX@ in a patch and substitute it in the recipe, so the patch stays readable and the real path gets injected at build time.

Shebangs are the same problem in a different costume. #!/bin/bash and #!/usr/bin/env python point at nothing:

termux-fix-shebang script.sh
head -1 script.sh
# #!/data/data/com.termux/files/usr/bin/bash

termux-exec papers over some of this at runtime, but it only covers exec. It does nothing when a program calls open("/tmp/foo").

Fix 2: hardcoded temp dirs

/tmp is the most common offender. Bun needed a patch for it. Ghostty needed one. The shape is always the same:

-    const char *dir = "/tmp";
+    const char *dir = getenv("TMPDIR");
+    if (!dir || !*dir) dir = "@TERMUX_PREFIX@/tmp";

Tiny diff. Takes an hour to find, because the failure shows up three layers away from the cause, usually as "permission denied" on a path you didn't know the program was using.

Fix 3: syscalls, or how to get killed by a feature probe

This is the nasty one. Modern runtimes try fast paths: close_range, pidfd_open, statx, io_uring. On a normal Linux box, an old kernel answers ENOSYS and the program falls back to the slow path. On Android, the filter can answer with SIGSYS and your build dies with "Bad system call".

Bun needed three separate patches for this: close_range, pidfd_open, and statx. Ghostty needed two: one to skip an io_uring probe, and one to replace its pidfd-based process watcher.

The fix is almost boring:

 // illustrative shape, not a verbatim patch
-    if (close_range(3, ~0U, 0) == 0) return;
+#ifndef __ANDROID__
+    if (close_range(3, ~0U, 0) == 0) return;
+#endif
+    close_fds_slowly(3);

Upstream already maintains the fallback because it supports old kernels. All I do is make Android look like an old kernel. Compile the fast path out, let the slow path run, move on.

Fix 4: let the toolchain do the cross-compiling

Most of my packages are Go and Rust, and that's not an accident. Both cross-compile cleanly, and Termux's build system ships helpers for them. A Go CLI recipe is nearly trivial:

TERMUX_PKG_HOMEPAGE=https://github.com/example/example-tool
TERMUX_PKG_DESCRIPTION="Example Go CLI"
TERMUX_PKG_LICENSE="MIT"
TERMUX_PKG_MAINTAINER="@GourangaDasSamrat"
TERMUX_PKG_VERSION=1.2.3
TERMUX_PKG_SRCURL=https://github.com/example/example-tool/archive/v$TERMUX_PKG_VERSION.tar.gz
TERMUX_PKG_SHA256=<sha256>
TERMUX_PKG_BUILD_IN_SRC=true

termux_step_make() {
    termux_setup_golang
    go build -trimpath -o example-tool ./cmd/example-tool
}

termux_step_make_install() {
    install -Dm755 example-tool "$TERMUX_PREFIX/bin/example-tool"
}

Rust is the same idea with termux_setup_rust, plus a pile of crate-specific pain I'll get to in part two.

Python packages with native extensions are their own category. pip install on a phone means compiling Rust or C on a phone, which is a bad time. That's why things like python-rpds-py, python-pynacl, python-crc32c and python-jellyfish exist as packages: one build on my side, an instant install on yours.

What this buys you

Once the wall is down, a phone stops being a toy terminal. From Termux you can now:

talk to databases with pgcli, mycli, litecli, iredis and mongosh
drive cloud accounts with azure-cli, oci-cli and doctl
lint and secure Go code with golangci-lint, gosec and govulncheck
cut releases with goreleaser and git-cliff
load test an API with k6, oha or hey
use jujutsu instead of git, if you're that kind of person

None of those work out of the box. Each one has a recipe, and some have a pile of patches behind them.

Why I bother

Because "Termux can't do that" is almost never true. It's usually "nobody has patched /tmp yet."

If you want to see the full list of what I maintain, it's on Repology. The recipes and patches live in the Termux packages repo, and my other work is on GitHub.

Part two gets into the hard cases: a JavaScript runtime with nine patches, a GPU-accelerated terminal, and a code editor whose dependency tree needed surgery.

If you've hit a Bad system call in Termux and couldn't figure out why, drop it in the comments. I've probably seen it.

Leader Election

Gouranga Das Samrat — Sat, 24 Oct 2026 04:00:00 +0000

In a distributed system, sometimes exactly ONE node must act as the "leader". How do you pick it?

Why Leader Election?

Some tasks must run on exactly one node:

Sending scheduled emails (don't send twice)
Coordinating distributed transactions
Acting as primary in a database cluster
Processing a specific partition of a queue

Problem: Nodes can crash. The leader must be detected as dead and a new one elected.

Algorithms

Bully Algorithm

Node with highest ID wins
When a node thinks the leader is dead → sends election messages to all higher-ID nodes
If no response → declares itself leader
✅ Simple | ❌ Many messages, assumes ordered IDs

Raft Consensus

Nodes vote for a leader candidate
Candidate needs majority vote (quorum)
Leader sends heartbeats; if missed → new election
✅ Well-proven, used in production systems
Used by: etcd, CockroachDB, TiKV

ZooKeeper / etcd-based Leader Election (Practical)

All nodes race to create an ephemeral node:
  /election/leader

First node to create it → wins leadership
Others watch the node for deletion (leader crash)
On deletion → race again

✅ Battle-tested, you don't implement the algorithm yourself
✅ Ephemeral nodes auto-delete when the session dies (crash detection built in)
❌ Adds ZooKeeper/etcd as dependency

Split-Brain Problem

What if the network partitions and both halves elect a leader?

Two leaders making conflicting decisions = data corruption
Solution: quorum — leader must maintain majority (N/2 + 1) connections
If minority partition can't reach quorum → steps down

Real-World Usage

System	Leader Election
Kafka	ZooKeeper (legacy) / KRaft (new) for controller
Elasticsearch	Zen Discovery / Raft-based
Redis Sentinel	Sentinel quorum for primary election
PostgreSQL HA	Patroni uses etcd/ZooKeeper

Distributed Cron Jobs

Gouranga Das Samrat — Sun, 18 Oct 2026 04:00:00 +0000

Regular cron runs on one server. What happens when you have 10 servers? Each runs the job 10 times. That's a problem.

The Problem

Single server cron: ✅ Job runs once at 2am
10-server fleet:    ❌ Job runs 10 times at 2am — duplicate emails, double charges!

Solutions

1. Dedicated Scheduler Node

One designated machine runs all cron jobs
✅ Simple
❌ Single point of failure — if this node dies, no cron jobs run

2. Leader Election + Cron

Cluster elects a leader (using etcd/ZooKeeper)
Only the leader runs cron jobs
If leader dies → new leader elected → cron resumes
✅ No SPOF | ❌ Leader election complexity

3. Distributed Lock Before Job Execution

def run_job():
    lock = redis.set("cron:daily-email", "locked", nx=True, ex=300)  # 5min TTL
    if not lock:
        return  # another node is running it
    try:
        send_daily_emails()
    finally:
        redis.delete("cron:daily-email")

✅ Simple, works with existing Redis
❌ Lock expiry must be > job duration, or use heartbeat extension

4. Dedicated Scheduling Services

AWS EventBridge Scheduler — cron without servers
Temporal.io — workflow orchestration with scheduling
Airflow — DAG-based job scheduling
Sidekiq-Cron (Ruby), Bull (Node.js)

Exactly-Once Execution

For critical jobs (billing, emails):

Use idempotency keys in the job itself
Record execution in DB before running: INSERT INTO job_runs (job_id, run_date) ON CONFLICT DO NOTHING → if 0 rows inserted, skip
Use a distributed lock with heartbeat

Observability for Cron

Alert if a job DIDN'T run (missed heartbeat)
Track job duration — sudden increase = something is wrong
Log job result (success/failure, records processed)
Tool: Healthchecks.io — cron monitoring via ping

Cache Invalidation Patterns

Gouranga Das Samrat — Sat, 17 Oct 2026 04:00:00 +0000

"There are only two hard things in computer science: cache invalidation and naming things." — Phil Karlton

The Core Problem

Cache = stale data risk. Every caching strategy is a trade-off between:

Freshness — how up-to-date is cached data?
Performance — how often do we go to the DB?
Consistency — does every user see the same thing?

Strategy 1: TTL (Time-To-Live) Expiry

cache.set("user:123", userData, ttl=300)  # expires in 5 minutes

Simplest strategy — let cache entries age out
✅ No invalidation logic needed
❌ Stale window = TTL duration (user sees old data for up to 5 min)
❌ Cache stampede on expiry (see below)

Choose TTL by data freshness requirement:

User profile: 5-15 minutes
Product price: 1-5 minutes
News article: 1 hour
Static config: 1 day
Currency rates: 1 minute

Strategy 2: Write-Through Cache

Application writes → Cache AND DB simultaneously
Read → always hits cache (always warm)

✅ Cache always up-to-date (no stale reads)
✅ Reads always fast
❌ Write latency doubles (must write both)
❌ Cache may fill with data never read (write-heavy workloads waste memory)

Best for: Read-heavy workloads where writes are infrequent

Strategy 3: Write-Behind (Write-Back) Cache

Application writes → Cache only (async)
Background worker → flushes cache to DB periodically

✅ Very fast writes (no DB in critical path)
❌ Data loss risk if cache crashes before flush
❌ Complexity — need background flusher, failure handling

Best for: High-write scenarios where some data loss is acceptable (analytics, counters)

Strategy 4: Cache-Aside (Lazy Loading)

Read request:
  Check cache → HIT: return ✅
              → MISS: query DB → store in cache → return

Write request:
  Write to DB
  Invalidate (delete) cache entry

Most common pattern
✅ Cache only contains data that's actually requested
✅ Cache failure doesn't affect writes
❌ Cache miss = extra DB round trip (cold start penalty)
❌ Race condition: two reads can populate stale data simultaneously

Race condition fix: Use a short TTL even when invalidating, or use versioned keys.

Strategy 5: Event-Driven Invalidation

DB changes → emit event (via Kafka, SNS, CDC) → cache service → delete/update cache

✅ Cache invalidated immediately on change
✅ Decoupled — cache logic separate from write logic
❌ Event delay = brief stale window
❌ Event loss = permanently stale cache (need retry/DLQ)

CDC (Change Data Capture):

Debezium reads Postgres WAL → emits change events → Kafka → cache invalidation service
Low-latency, no application code change required

⚡ Cache Stampede (Thundering Herd)

When a popular cache key expires → thousands of concurrent requests all hit DB simultaneously → DB overloaded → slow responses → everyone waits → chaos.

Solutions:

Mutex/Lock on Cache Miss

def get_user(id):
    data = cache.get(f"user:{id}")
    if data: return data

    # Acquire lock — only one thread fetches from DB
    with redis.lock(f"lock:user:{id}", timeout=5):
        data = cache.get(f"user:{id}")  # double-check after lock
        if data: return data
        data = db.get_user(id)
        cache.set(f"user:{id}", data, ttl=300)
        return data

Early Expiry / Probabilistic Refresh

Refresh cache before it actually expires
Background thread proactively refreshes popular keys at ~80% of TTL

Stale-While-Revalidate

Serve stale data immediately
Async: fetch fresh data in background, update cache
Users see slightly stale but fast response

Strategy 6: Versioned Cache Keys

Instead of invalidating → use new key:

# v1 data at key: user:123:v1
# After update → write to user:123:v2
# Old key auto-expires, new key is fresh

✅ No invalidation race conditions
✅ Old and new data can coexist during rollout
❌ Old keys accumulate (need GC / short TTL on old versions)

⚖️ Summary — Which Pattern When?

Pattern	Best For
TTL	Simple cases, infrequent updates
Write-Through	Read-heavy, must-be-fresh
Write-Behind	High write throughput, some loss OK
Cache-Aside	General purpose ← default choice
Event-driven	Complex systems, CDC, microservices
Versioned keys	Zero-downtime cache updates

Default interview answer: Cache-aside + TTL + event-driven invalidation for critical data.

API Design — Advanced

Gouranga Das Samrat — Sun, 11 Oct 2026 04:00:00 +0000

You know the basics. Here's what separates good API design from great API design.

📄 Pagination Strategies

Never return unbounded lists. Always paginate.

1. Offset-Based Pagination

GET /posts?limit=20&offset=40

Simple, easy to implement
✅ Jump to any page directly ("go to page 5")
❌ Page drift: if items are added/deleted between requests, you miss or duplicate items
❌ Performance degrades at high offsets (OFFSET 100000 scans 100k rows and discards them)
Use when: small datasets, admin panels, search results

2. Cursor-Based Pagination (Recommended for feeds)

GET /posts?limit=20&cursor=eyJpZCI6MTIzfQ==
Response: { data: [...], nextCursor: "eyJpZCI6MTQ0fQ==" }

Cursor = encoded pointer to last item seen (e.g., base64 of {id: 123})
✅ Stable — no page drift even if new items inserted
✅ Efficient — WHERE id > 123 LIMIT 20 uses index perfectly
❌ Can't jump to arbitrary pages
Use when: infinite scroll, Twitter/Instagram feeds, real-time data

3. Keyset Pagination

Variant of cursor — uses actual column values (not encoded)

GET /posts?limit=20&after_id=123&after_created_at=2024-01-15

Multi-column sort support
Works naturally with DB indexes

4. Page-Based (Simple)

GET /posts?page=3&per_page=20

Like offset but friendlier naming
Same problems as offset

🔍 Filtering & Sorting

Filtering Patterns

# Simple equality
GET /users?status=active&role=admin

# Range filters
GET /orders?created_after=2024-01-01&created_before=2024-12-31
GET /products?price_min=10&price_max=100

# Multi-value
GET /products?category=electronics,phones

# Search
GET /users?search=john

DB implications:

Each filter = potential WHERE clause
Ensure composite indexes match common filter combinations
status + role both filtered → composite index (status, role)

Sorting

GET /products?sort=price&order=asc
GET /products?sort=-created_at          # prefix - for desc
GET /products?sort=price,-created_at    # multi-sort

Sort key must be indexed (or full table scan)
For cursor pagination: sort field must be part of the cursor

📊 GraphQL Basics

REST: client gets what the server decides to send.
GraphQL: client asks for exactly what it needs.

# REST: GET /users/123 returns ALL user fields
# GraphQL: client specifies exactly what it wants

query {
  user(id: "123") {
    name
    email
    posts(limit: 3) {
      title
      createdAt
    }
  }
}

Problems GraphQL solves:

Over-fetching: REST returns 50 fields, you need 3
Under-fetching: Need to call 3 REST endpoints to build one page
Type safety: Schema defines exactly what's available

When to use GraphQL:

Multiple clients (mobile, web, third-party) with different data needs
Rapidly evolving APIs (add fields without breaking clients)
Complex, interconnected data (think: social graph)

When to stick with REST:

Simple CRUD APIs
Public APIs (REST is more universally understood)
File uploads, streaming (REST handles these better)
Small team — GraphQL has operational overhead

N+1 Problem:

query {
  users {
    posts {
      comments
    }
  }
}
# Without DataLoader: 1 + N + N*M queries 🔥
# With DataLoader: batch loads → 3 queries total ✅

🏷️ API Versioning

You mentioned this — here's the full picture:

URL Versioning (Most common)

GET /v1/users
GET /v2/users

✅ Very explicit, easy to route
❌ URL "should" be a resource, not a version

Header Versioning

GET /users
Accept: application/vnd.myapi.v2+json

✅ Clean URLs
❌ Harder to test (can't just paste URL in browser)

Query Parameter

GET /users?version=2

✅ Easy to test
❌ Optional params = easy to forget → inconsistent behavior

Sunset Policy

Announce deprecation date for old versions
Return Deprecation and Sunset headers on old endpoints
Give clients 6–12 months to migrate

🔒 API Best Practices (Interview Checklist)

Topic	Best Practice
Auth	Bearer token in `Authorization` header, not URL
Errors	Consistent error format: `{ error: { code, message, details } }`
Rate Limiting	Return `Retry-After` header, 429 status
Idempotency	POST with `Idempotency-Key` header for safe retries
Status Codes	Use them correctly: 201 Created, 204 No Content, 409 Conflict
HATEOAS	Return links to related resources (optional but impressive)
Compression	gzip responses > 1KB

⚖️ Trade-offs

⚖️ REST vs GraphQL at interview:

Default to REST for simplicity
Propose GraphQL when: multiple client types, complex data graph, bandwidth-sensitive (mobile)

⚖️ Offset vs Cursor pagination:

Default to cursor for production feeds
Use offset for admin/search (random access needed)