Algorithmic Complexity & Code-Level Optimization Questions

Clarify goal & assumptions

• Tight loop: process N 32-bit integers (e.g., add, multiply, compare).
• Target CPU: x86-64 typical server core; know core frequency, SIMD width (e.g., AVX2 256-bit = 8x int32), cache sizes, memory bandwidth.

High-level approach

1. Estimate per-element instruction mix and cycles:
   • Count scalar instructions per element (loads, ALU, stores, loop overhead).
   • Convert to uop throughput using CPU throughput numbers (e.g., add = 1 cycle per 2 on port).
2. Account for SIMD:
   • Replace scalar ALU counts by vector lanes: effective elements per instruction = SIMD_width / element_size.
   • Adjust loads/stores: use aligned vector loads; use non-temporal if streaming.
3. Include memory effects:
   • Estimate cache hit rate; compute average memory latency contribution: misses * memory access cost.
   • Consider memory bandwidth: compute bytes transferred per element and compare to peak bandwidth.
4. Branch prediction:
   • If loop has predictable branches, assume near-zero misprediction rate; otherwise add penalty: mispredictions * ~15–20 cycles each.
5. Combine to predict time:
   • Total cycles ≈ max(compute_cycles, memory_bound_cycles) + branch_penalty + loop_overhead.
   • Use roofline idea to classify boundness.

Formulas:

execution_time_seconds = total_cycles / cpu_frequency_hz

memory_time = (bytes_per_element * N) / peak_memory_bandwidth_bytes_per_sec

compute_time = total_compute_cycles / cpu_frequency_hz

Practical measurement

• Use perf/pcm/likwid to get instructions, cycles, cache-misses, bandwidth.
• Microbenchmark scalar vs vector compile; measure speedup.
• Inspect assembler to verify unrolled/SIMD code and loop-carried dependencies.

Decide compute- vs memory-bound

• If compute_time > memory_time by a comfortable margin ⇒ compute-bound.
• If memory_time dominates or measured bandwidth near peak ⇒ memory-bound.
• Cross-check: CPU utilization low but memory BW saturated ⇒ memory-bound.

Example: simple add loop: scalar: ~2 loads + 1 add + 1 store per element → vectorizing 8x reduces ALU+loop cycles by ~8x; if bytes/element = 12 and memory BW is 40 GB/s, max throughput = BW / 12. Use perf to confirm.

Brief framing — why avg vs worst-case matter
Average-case guides expected latency under normal traffic; worst-case bounds matter for SLAs, DoS resilience, and tail latency. For a public API you must protect against attacker-controlled inputs that could force worst-case behavior.

Algorithm comparison

• Quicksort

  • Average: O(n log n)
  • Worst: O(n^2) (bad pivots)
  • Memory: O(log n) stack average; in-place
  • Stability: not stable (unless modified)
  • Notes: fast in practice but vulnerable to adversarial payloads unless randomized pivots or introspection used.

• Mergesort

  • Average: O(n log n)
  • Worst: O(n log n)
  • Memory: O(n) extra for merging (can be O(1) in linked-list variants)
  • Stability: stable
  • Notes: predictable worst-case and stable—good for APIs where consistent latency and order-preserving behavior matter.

• Heapsort

  • Average: O(n log n)
  • Worst: O(n log n)
  • Memory: O(1) extra; in-place
  • Stability: not stable
  • Notes: predictable time and low memory but typically slower constant factors than quicksort.

Adversarial inputs & production choice

• For attacker-controlled lists, avoid algorithms with exploitable worst-case (plain quicksort). Use randomized quicksort or introsort (switch to heapsort when recursion deep) to combine quicksort speed and safe worst-case.
• If stability and reproducible ordering are required, use mergesort (or stable external sort) despite higher memory.
• Also enforce size limits, rate-limit, validate input, and set timeouts to protect API from resource exhaustion.

Choose: introsort or randomized quicksort for speed + safety; mergesort when stability or constant worst-case latency is prioritized.

Clarify assumptions

• Each request issues 2 reads of ~10 KB each → 20 KB read per request from DB (plus minimal resp. headers).
• Given parameters: DB_read_throughput (R_db, reads/sec), app_instance_bandwidth (B_inst, bytes/sec), instance_concurrency (C_inst, concurrent requests), headroom factor H (>1, e.g., 1.2).

Core formulas

Requests consume reads:

RPS_db_limit = R_db / 2

Network limit per instance (requests/sec):

RPS_net_inst = B_inst / (20_480)   # 20 KB = 20,480 bytes per request

Instance concurrency limit:

RPS_concurrency_inst = C_inst / L   # L = average request latency (s)

Per-instance sustainable RPS:

RPS_inst = min(RPS_net_inst, RPS_concurrency_inst)

Cluster-level RPS before headroom:

RPS_cluster_raw = min(R_db_total / 2, N_inst * RPS_inst)

Include headroom H:

RPS_cluster_safe = RPS_cluster_raw / H

Replication / read-replica impact

• If DB has R replicas serving reads, and load-balanced evenly, effective read capacity multiplies:

R_db_total = R_primary_reads + R * R_replica_reads_capacity
# Simplify: if all reads go to replicas: R_db_total = R * R_single_node

• Account for replication lag: optimistic only if replicas are fresh; otherwise route critical reads to primary (reduces effective capacity).

Example

• R_db_total = 10,000 reads/s → RPS_db_limit = 5,000 RPS
• B_inst = 100 Mbps = 12.5 MB/s → RPS_net_inst = 12_500_000 / 20_480 ≈ 610 RPS
• N_inst = 10 → cluster net limit ≈ 6,100 RPS
• RPS_cluster_raw = min(5,000, 6,100) = 5,000
• With H=1.25 → RPS_cluster_safe = 4,000 RPS

Notes & trade-offs

• Include latency L for concurrency; measure actual payloads (headers, JSON).
• Monitor replica lag, connection limits, and CPU/IO on DB.
• If network-bound, compress responses or increase instance bandwidth; if DB-bound, add replicas or cache reads.

Clarify constraints

• Small table S ≈100 rows, large table L ≈1B rows, endpoint returns ≈100 rows per request, low-latency target, read-heavy.

Approach summary

• Use indexed lookups and predicate pushdown as baseline, then consider broadcasting S, pre-joining/denormalization, materialized views, caching, and read replicas depending on query patterns and freshness needs.

Strategies, complexities and trade-offs

1. Indexed lookups (preferred baseline)

• What: Ensure L has covering indexes on join key + filter/sort columns; use index-only scans when possible.
• Complexity: O(k log N) per request where k≈100 matched rows; I/O proportional to pages for matched rows.
• Trade-offs: Low storage overhead, simple; poor if join requires touching many rows before applying limit without good index.

2. Broadcast/join small table in app or DB

• What: Load S in-memory (100 rows) and drive point lookups into L using IN or multiple indexed queries.
• Complexity: ~100 indexed probes -> O(m log N) with m=#keys sent.
• Trade-offs: Minimal I/O if queries are selective; increases number of round-trips unless batched. Good for selective keys.

3. Pre-join / denormalization

• What: Store denormalized rows in L (copy S attributes into L) or maintain a separate table D with pre-joined results.
• Complexity: Query is O(page reads for 100 rows), very low latency.
• Trade-offs: Higher storage and write complexity (update propagation), eventual consistency challenges.

4. Materialized views

• What: MV holding frequent join results (possibly partitioned by frequent filters).
• Complexity: Query fast (index scans on MV); MV maintenance cost depends on refresh strategy.
• Trade-offs: Freshness vs refresh cost; incremental refresh reduces I/O.

5. Caching (CDN / in-memory / application)

• What: Cache endpoint responses or sub-results (e.g., S content, query pages) in Redis or CDN.
• Complexity: O(1) cache hit; miss falls back to DB cost.
• Trade-offs: High latency improvement, staleness; requires cache invalidation logic.

6. Read replicas and sharding

• What: Route reads to replicas to reduce primary load; shard L by join key if scale demands.
• Complexity: Same per-query complexity; system-level throughput increases.
• Trade-offs: Replication lag, increased operational complexity; sharding complicates joins—ensure S broadcastable or denormalized per shard.

Recommendation

• First, add/verify covering indexes and use prepared statements with LIMIT; profile query plan (EXPLAIN ANALYZE). If still slow, broadcast S in-app to issue batched indexed lookups or create a denormalized column and maintain via triggers/CDC. Add Redis cache for hot endpoints and read replicas for scale. Use materialized views for complex aggregations with scheduled/incremental refresh where acceptable.

Clarify goal and constraints

• Single-pair point-to-point on a road graph: 30M nodes, 100M edges. Backend needs low-latency queries, moderate memory budget, occasional map updates.

Which is better in practice: Dijkstra vs Bidirectional A*

• Dijkstra (O(E log V)) is robust but explores large portions of the graph for long routes; on this scale a vanilla Dijkstra can visit millions of nodes and cost hundreds of ms–seconds per query.
• Bidirectional A* with an admissible geographic heuristic (e.g., great-circle distance scaled by max speed) prunes search dramatically. In practice bidirectional A* typically reduces explored nodes by orders of magnitude vs Dijkstra for road graphs and yields much lower latency (tens to low hundreds of ms depending on route length and implementation).
• Conclusion: for point-to-point without preprocessing, bidirectional A* is the better practical choice.

How preprocessing changes the trade-offs

• Contraction Hierarchies (CH)
  • Preprocessing: expensive (minutes–hours for huge graphs) and offline; creates shortcuts by contracting nodes.
  • Query time: extremely fast (microseconds–low ms) for point-to-point; predictable latency ideal for backend SLAs.
  • Space: index stores extra shortcuts; for 30M nodes this can be tens of GB depending on implementation and edge profiles.
  • Updates: costly to maintain; best for mostly static networks.
• Landmark-based A* / ALT
  • Preprocessing: choose k landmarks and store distances to all nodes (k small, e.g., 8–16).
  • Query time: much faster than plain A*, typically tens of ms; less dramatic than CH.
  • Space: O(k·V) — with k=16 and 30M nodes storing 4-byte ints ≈ ~2GB plus graph.
  • Updates: easier to handle than CH; incremental updates okay.
• Trade-offs summary
  • No preprocessing: Bidirectional A* — moderate latency, minimal extra storage.
  • Moderate preprocessing (ALT): good balance — lower latency, small extra storage, easier dynamic updates.
  • Heavy preprocessing (CH): best latency and throughput for high QPS routing backend at cost of offline compute and large index size; harder for frequent edge-weight changes.

Operational recommendations for a backend developer

• If you need sub-10ms point-to-point for high QPS, invest in CH and serve queries from in-memory index with careful memory sharding.
• If map updates are frequent or memory is constrained, use ALT or hybrid (partial CH + dynamic adjustments).
• Always measure: benchmark with real route distributions, profile memory, and plan update pipelines (batched reprocessing, shadow index, or local rerouting for temporary closures).