HardTechnical

43 practiced

Model geospatial data to support proximity queries at scale (e.g., find nearest restaurants within 5 km). Discuss coordinate representation options (lat/long, geohash, S2 cells), indexing approaches (R-tree/GiST, geohash prefix), sharding and partitioning by geography, and techniques to minimize false positives and extra distance calculations.

Sample Answer

Clarify requirements first: expected QPS, read vs write ratio, point vs polygon data, accuracy (ellipsoidal vs planar), and latency. With that, choose representations, indexes, partitioning, and query flow.

Coordinate representations- Lat/Long (WGS84): canonical, needed for final distance; expensive for spherical math if used everywhere.- Geohash: base32 prefix encodes location into hierarchical string — good for prefix-search and coarse bounding boxes; non-uniform cell shape/size and edge-crossing issues.- S2 cells: hierarchical, roughly equal-area cells on sphere, good cell-adjacency and locality, avoids pole distortions; preferred for large-scale proximity.

Indexing approaches- R-tree / GiST (PostGIS): spatial indexes that store bounding boxes; precise for polygons and vector queries; great for single-node DBs.- Geohash prefix index: store geohash at multiple precisions and query neighbor prefixes to get candidates; simple and fast in key-value stores.- S2 cell id index: store smallest S2 cell covering point at chosen level; to query radius, compute covering cells and issue IN queries; scales well in distributed stores.

Sharding & partitioning- Geo-hash or S2 prefix as shard key ensures spatial locality; pick level to balance shard size.- Hybrid: shard by coarse geography (country/state) + hash within region to avoid hotspots in dense cities.- Rebalancing: use time-based or load metrics; support overflow partitions for hotspots.

Minimizing false positives & extra calculations- Use a two-phase filter: cheap bounding box/cell filter (geohash/S2 cover) to produce candidates, then exact great-circle distance (Haversine or Vincenty for precision) to filter.- When generating covering cells, choose minimal cell set to cover circle (S2 RegionCoverer) to reduce extra candidates.- Handle edge-crossing by including neighboring prefixes/cells.- Use indexed attributes (e.g., city id, popularity) to narrow scans.- Cache frequent nearby-query results and precompute k-NN for very dense hotspots.

Trade-offs- R-tree/GiST gives accurate geometry ops but harder to scale horizontally.- Geohash is simple for K-V stores but suffers irregular cell sizes.- S2 offers balanced cells and robust libraries for cover generation — best for global, high-scale proximity.

Example flow (S2 + distributed KV): store points with lat/lon and S2 cell at level L; on query, compute S2 covering cells for radius R, fetch candidates by cell id ranges (and neighbor cells), apply Haversine filter and sort by distance; return top-k.

HardSystem Design

34 practiced

Design a zero-downtime online schema migration plan for a live PostgreSQL database with millions of rows. Include steps for adding a new non-null column and backfilling data in the background, using views or triggers during migration, rolling back safely, and what metrics and alerts you would monitor during the migration.

Sample Answer

Requirements & constraints:- Zero downtime for reads/writes; table has millions of rows; new column must be NOT NULL with backfilled values.- Safe rollback, minimal lock time, observability.

High-level plan (phased, reversible):1. Add nullable column (cheap, no full-table rewrite) - ALTER TABLE my_table ADD COLUMN new_col data_type;2. Deploy application code that writes to new_col (dual-writes) - App writes both existing_col and new_col; safe if new_col NULL on reads.3. Backfill in background (batched, idempotent) - Use a worker that updates ranges in small batches (e.g., 1k–10k rows) with WHERE new_col IS NULL ORDER BY id LIMIT N. - Example:

sql

-- run in transaction per batch
UPDATE my_table
SET new_col = compute_value(...)
WHERE id BETWEEN 100000 AND 100999
  AND new_col IS NULL;

- Throttle and track progress in migration table: migration_progress(batch_start, batch_end, status, last_updated).4. Use a view or trigger to present NOT NULL semantics during migration - Create view that exposes COALESCE(new_col, compute_value(...)) AS new_col for readers while backfill runs:

sql

CREATE VIEW my_table_v AS
SELECT id, other_cols, COALESCE(new_col, compute_value(...)) AS new_col
FROM my_table;

- Or create BEFORE INSERT/UPDATE trigger to populate new_col for legacy writers.5. Validate backfill correctness - Compare counts and checksums: SELECT count(*) where new_col IS NULL; run sampling checksums on old vs new logic.6. Make new_col NOT NULL (fast if column is already populated) - After backfill completes and validation passes: ALTER TABLE my_table ALTER COLUMN new_col SET NOT NULL; - This acquires a brief lock but typically fast when no NULLs exist.7. Cleanup - Remove view/trigger and migration metadata; stop dual-writes if desired.

Rollback strategy:- Before SET NOT NULL, you can: - Stop background backfill, revert app to stop writing new_col (it’s nullable). - If a batch causes issues, mark it failed in migration_progress and reverse by updating affected rows back or restoring from backup for that range.- Always take logical backups (pg_dump) or point-in-time recovery base backup before migration start; test rolling back a small subset.- If altering to NOT NULL causes issues, revert by ALTER TABLE ... DROP CONSTRAINT/SET NULL_allowed; or restore DB to pre-migration snapshot (rare).

Safety & operational notes:- Use explicit transactions per batch; idempotent updates (WHERE new_col IS NULL) avoid double work.- Run backfill workers on replica/read replica where possible, but primary updates required for schema changes—consider pg_repack or logical replication if heavy rewrite needed.- Test on staging with production-sized data.

Metrics & alerts to monitor:- Database: lock wait time, longest-running transactions, active connections, write / commit latency, replication lag.- Migration progress: rows backfilled, batches per minute, % complete, errors per batch.- System resources: CPU, memory, I/O utilization, WAL generation rate.- Application: increased error rates, latency (p50/p95) for endpoints touching table.- Alerts: - Lock wait > threshold (e.g., >5s) or long-running transaction > X minutes - Replication lag > acceptable limit - Error rate spike or CPU/I/O > 80% - Backfill stuck (no progress for Y minutes) or batch failures > N- Dashboard examples: Grafana panels for backfill progress, pg_stat_activity, pg_stat_replication, disk/WAL metrics.

Trade-offs and alternatives:- For extremely large tables, consider logical replication to a new table with desired schema and cutover via rename—more complex but avoids heavy locks.- Using triggers adds overhead per write; views add complexity when ORM expectations differ.- pg_repack can rebuild tables online but still creates temp copy and WAL—suitable when ALTER TABLE would rewrite the table.

This approach minimizes locking, provides a reversible, observable path, and maintains correctness through dual-writes, idempotent backfills, and validation before enforcing NOT NULL.

HardTechnical

35 practiced

A popular product row becomes a hotspot with thousands of concurrent reads and updates, causing locks, contention, and degraded performance. Propose a multi-layer mitigation plan: data-model changes (sharded counters, per-region aggregates), access-pattern changes (request coalescing, batching, optimistic concurrency), and infrastructure changes (read-replicas, write routing). Analyze trade-offs and implementation complexity.

Sample Answer

Requirements & constraints (assumed): thousands of concurrent reads & bursts of updates to one “hot” product row; strong read freshness not strictly required for some UI use-cases; ACID-level consistency only for critical fields (e.g., inventory), otherwise eventual consistency acceptable.

Multi-layer mitigation plan

1) Data-model changes- Sharded counters: split a single counter into N shards (product_counter_{id}_{shard}). On increment, pick a random shard and increment. Read aggregates by summing shards. - Example: write path: increment shard via atomic increment in DB/Redis. Read path: parallel SUM across shards (cache the sum for frequent reads). - Trade-off: eventual consistency across shards; read requires aggregation cost; complexity linear in N; choose N based on throughput.- Per-region / per-tenant aggregates: maintain regional totals to localize writes and reads, then periodically merge into global view (merge via background job or CRDTs). - Trade-off: increased storage and merge complexity, but reduces cross-region latency and contention.

2) Access-pattern changes- Request coalescing & batching: front-end or API gateway coalesce multiple client requests into one backend read, and batch updates (buffer increments for short windows, flush periodically). - Benefit: reduces QPS; trade-off: added latency or small staleness.- Optimistic concurrency for critical fields: use CAS/compare-and-swap (version numbers or etags). Retry on conflict with backoff. - Use for updates that must be consistent but low-conflict (e.g., metadata).- Client-side rate limiting and write de-duplication: avoid duplicate writes (idempotency keys).

3) Infrastructure changes- Read replicas & caching: add read-replicas and multi-layer cache (edge CDN for static product info; in-memory cache like Redis for counters). Serve reads from cache; write-through or write-behind depending on freshness needs. - Trade-off: replication lag; design expiry/invalidations.- Write routing / leader-per-shard: route writes to shard-specific leader or partition using consistent hashing. For hot product, promote dedicated write shard or use a lightweight leader to sequence writes. - Trade-off: operational complexity but reduces lock contention.- Use connection pooling, tuned DB knobs (shorter transactions, row-level locking), and partitioned/semi-relational stores (e.g., DynamoDB with hot-partition mitigation patterns).

Implementation complexity & roadmap- Short term (weeks): add caching + read replicas; implement request coalescing at API layer; idempotency keys.- Mid term (1-2 months): sharded counters, batching with flush windows, optimistic concurrency for metadata.- Long term (2-6 months): per-region aggregates, write routing with consistent hashing, operational tooling for shard management and monitoring.

Risks & trade-offs- Staleness vs latency: most approaches trade strict freshness for throughput.- Complexity & correctness: sharding + batching increases code paths and testing needs (race conditions, double-counting). Use thorough metrics, dashboards, and staged rollouts.- Cost: more infra (replicas, Redis clusters) and operational overhead.

Metrics to validate success- Reduced tail latency for reads and writes- Lower DB lock wait times and deadlocks- Increase in sustainable write QPS- Error/retry rates and eventual consistency window

This layered approach lets you quickly reduce contention (caching, coalescing) then progressively add durable solutions (shards, routing) while monitoring consistency and operational burden.

EasyTechnical

44 practiced

What is a database index? Explain at a high level how B-tree indexes and hash indexes are structured, their typical use-cases, and limitations (for example, range scans, ordering, partial matches). Give examples of queries that benefit from each index type.

MediumTechnical

55 practiced

Compare pagination strategies for large datasets: OFFSET/LIMIT vs keyset (seek) pagination. Provide example SQL for keyset pagination on table orders(id BIGINT, created_at timestamptz) that returns the next page after a known last (id, created_at). Explain how keyset avoids large offsets and why index choice matters.

Sample Answer

To compare: OFFSET/LIMIT is simple but degrades for large offsets because the DB must scan/skip N rows (cost grows with offset). Keyset (seek) pagination uses the last-seen key(s) to fetch the next page directly via indexed range scans — constant work per page (O(page_size)) and predictable latency.

Approach: use a stable sort key (created_at, id) and filter for rows strictly after the last returned tuple. Tie-break with id to ensure deterministic ordering when timestamps are equal.

Example SQL (next page after known last (last_created_at, last_id), newest first):

sql

-- params: :last_created_at (timestamptz), :last_id (bigint), :page_size (int)
SELECT id, created_at, ... 
FROM orders
WHERE (created_at < :last_created_at)
   OR (created_at = :last_created_at AND id < :last_id)
ORDER BY created_at DESC, id DESC
LIMIT :page_size;

Why this avoids large offsets:- The WHERE + ORDER BY lets the optimizer do an index range scan starting at the given key instead of scanning and discarding O(offset) rows. Each page fetch touches only the rows returned.

Why index choice matters:- Create an index that matches the ORDER BY and filter pattern for efficient range scans: for descending pagination example, use CREATE INDEX ON orders (created_at DESC, id DESC);- If the index order or columns don’t match, the DB may perform a full scan or sort, losing keyset benefits.

Notes & caveats:- Keyset cannot jump to arbitrary page N without repeated requests or maintaining cursors.- Ensure stable ordering (unique tie-breaker like id).- Deleted/inserted rows between pages may affect perceived continuity; cursor semantics are best-effort. Alternative: opaque cursor tokens (base64) carrying last key values.

Data Model Design and Access Patterns Questions

Sample Answer

Sample Answer

Sample Answer

Sample Answer

Sample Answer

Unlock Full Question Bank