High-Score (Bugfree Users) Uber India L5 Interview Experience

A compact, targeted walkthrough of a high-scoring interview loop for Uber India L5 (SSE). This loop blends core DSA problems with systems and design depth: tree DP and timing, grid-robot preprocessing, near real-time Uber Eats metrics design, low-level design for meeting-room booking, and a heavy-machine (HM) deep dive focused on trade-offs.

Below I rephrase each round, explain likely approaches, highlight interviewer expectations, and give practical tips so you can reproduce a similarly strong performance.

---

R1 — Tree with parent pointers: "race from root vs leaf" (timing + scoring)

Problem sketch

• You are given a tree (parent pointers available). Two agents move along the tree (one from root, one from some leaf or other node). Each node has points. Based on arrival time at a node, the node's points may be awarded fully, partially (half), or not at all. The task: compute the maximum points achievable (or compute final score distribution) given movement rules and timing.

Reasonable approach

1. Clarify the exact movement model and scoring rules before coding (speeds, simultaneous arrival rule, half/full/zero thresholds).
2. Convert parent pointers into an adjacency representation if needed and compute distances (depths) from relevant sources (root and the other start node). BFS/DFS works since this is a tree.
3. Compute arrival times for both agents for every node. Compare arrival times to decide score allocation (full to earlier, half if equal, etc.).
4. If the problem asks to optimize some choice (e.g., choose the leaf to start from or pick a route): reduce to dynamic programming on the tree, computing best outcomes for subtrees, or run a DP along the unique path connecting the two starting points.

Complexity & tips

• Distances on a tree: O(N) with one or two DFS/BFS sweeps.
• If a choice must be optimized over many candidate leaves, precompute depths/parent jumps (binary lifting) to get O(log N) LCA/distance queries.
• Interviewer cues: explain arrival-time logic, consider edge cases (ties, zero-time nodes), and explicitly state time/space bounds.

What interviewers look for

• Clear problem restatement and assumptions.
• Correct distance computation and arrival-time comparison.
• Clean DP or path simulation if optimization is required.
• Attention to corner cases and complexity.

---

R2 — Grid robots: precompute nearest blockers (L/T/B/R) and answer queries

Problem sketch

• You have a grid with obstacles. Robots or queries ask how far a robot can move or whether two robots' moves conflict. A fast solution requires precomputing nearest blockers in all four directions for every cell.

Preprocessing approaches

1. Four directional sweeps (DP):
   • Left-to-right sweep to compute nearest blocker to the left for each cell.
   • Right-to-left for the right blocker.
   • Top-to-bottom and bottom-to-top for top/bottom.
   • Each sweep is O(R*C) for an R x C grid.
2. Monotonic stack approaches can help for certain constraints but are usually unnecessary for simple nearest-blocker queries.

Query answering

• Use the precomputed bounds per cell to determine reachable ranges in O(1) per query.
• For multi-step movement, combine ranges or simulate jumps using precomputed extents.

Complexity & tips

• Preprocessing: O(RC). Memory: O(RC) for four direction arrays.
• For many queries, this is ideal. If the grid changes often, consider dynamic structures (segment trees per row/column) but that complicates implementation and interview time.

What interviewers look for

• Correctness of preprocessing and reasoning about boundary conditions.
• Ability to translate precomputation into O(1) query logic.
• Considerations about mutability of grid and trade-offs for updates.

---

R3 — System design: Near real-time Uber Eats metrics (order value + Top-K items over 1h/1d/1w)

Requirements to clarify

• Input: stream of orders (adds/updates/cancels). Expected QPS? Event size? Late/duplicated events?
• Output: near real-time total order value and Top-K items for windows of 1 hour, 1 day, 1 week.
• SLOs: acceptable latency, freshness, accuracy (exact vs approximate), cost constraints.
• API surface and read QPS (dashboard vs internal service).

High-level architecture

1. Ingestion: Kafka (or Kinesis) with partitions keyed by item_id or region.
2. Stream processing: Apache Flink / Spark Structured Streaming / Kafka Streams
   • Maintain windowed aggregations for sum(order_value) and heavy-hitters (Top-K).
   • Use event-time processing and watermarks to handle lateness.
3. State store: RocksDB (embedded in Flink) or an external store (Redis for low-latency reads; Cassandra for longer retention).
4. Top-K approach:
   • For exact Top-K within small windows: maintain ordered heaps or balanced BSTs per window. This can be expensive at scale.
   • For large-scale cost/latency trade-offs: use stream sketches like Space-Saving (Misra-Gries) or Count-Min Sketch + Heavy Keeper to approximate frequent items with bounded memory and mergeability.
5. Windowing strategy:
   • Use tumbling windows (1h) and sliding windows (e.g., 1h sliding every minute) depending on freshness needs.
   • For 1d/1w, either keep separate window computations or compose windows using aggregated sub-windows (hierarchical rollups) to reduce state.
6. Serving layer:
   • Materialize results into a read-optimized store (Redis or an HTTP cache). API servers read from this cache.
   • For ad-hoc windows, fall back to query historical aggregates in a store like Presto/Cassandra.

Key trade-offs

• Latency vs correctness: Exactly-once semantics (with checkpointing) increase complexity but reduce double-counting. At-least-once with idempotency can be simpler.
• Accuracy vs cost: Sketches drastically reduce memory but give approximate Top-K. If the product needs exact lists, you must provision more resources.
• Window granularity vs storage: many small windows mean more state. Use hierarchical aggregation to amortize cost.

Scaling & reliability

• Partition streams by item_id or geography to scale processing.
• Monitor watermark progression and late events; tune watermarks and retention.
• Provide fallbacks for read APIs when state is rebuilding (stale data indicators).

What interviewers look for

• Clear requirements clarification and clear SLAs.
• Architecture diagram with components and data flow.
• Precise trade-offs: why choose sketches or exact, how to handle late events, how to scale and monitor.

---

R4 — LLD: Meeting room booking with history and schedules (deliver working code fast)

Essential domain model

• Entities: Room, Booking (start_time, end_time, user_id, room_id), User.
• APIs: createBooking, cancelBooking, listAvailability, getBookingHistory.

Core design choices

1. Conflict detection
   • For each room, keep bookings sorted by start_time. To check conflict for a new booking, binary search the nearest bookings (O(log n) for search; O(n) worst-case for insert in array but O(log n) with a BST).
   • Use interval trees (augmented BST) for efficient overlap queries.
2. Concurrency
   • Optimistic concurrency: try insert and fail on conflict; return a friendly error to retry.
   • Or use per-room locks (coarse but simple) if QPS is modest.
3. History
   • Store booking events in an append-only log for audit/history queries. Expose paginate-able history API.
4. Quick working implementation
   • Start with an in-memory per-room sorted list or TreeMap. Implement APIs with clear interfaces and unit tests.
   • Then persist bookings to a DB (Postgres/Cassandra) and add transactional/locking semantics.

What interviewers look for

• Good entity modeling and pagination for history queries.
• Efficient conflict detection and a strategy for concurrency.
• A pragmatic path from a working prototype to production-grade design.

---

R5 — HM deep dive: trade-offs, stack choices, learnings

Content to be ready with

• Be prepared to explain language/runtime choices (e.g., Java vs Go for streaming), libraries (Flink, Kafka, RocksDB), and their trade-offs (latency, ecosystem, operational cost).
• Trade-offs in algorithmic choices: exact Top-K vs approximate, windowing strategies, state size vs retention, read-latency vs update-latency.
• Observability: what metrics you’d report (event lag, watermark delay, state size, error rates) and how you’d debug issues.
• Operational concerns: rolling upgrades, state migration, disaster recovery, and backpressure handling.

Interview emphasis

• Show depth on one or two trade-offs you made. Use past learnings: e.g., how approximate algorithms reduced cost by X% while keeping 99% of important items.
• Demonstrate ability to reason about failure modes and mitigations.

---

General interview tips (applies across rounds)

• Clarify requirements first. Restate to confirm.
• Discuss complexity and memory before coding. Time-box implementation.
• Use examples and run through small cases out loud to validate logic.
• Keep code readable; prioritize correctness and edge cases.
• For system design, emphasize trade-offs, scaling, and monitoring.

---

Final notes

This loop tests a balanced mix of algorithmic rigor and pragmatic system design. Candidates who do well typically:

• Ask clarifying questions early.
• Separate correctness from optimization: get a correct approach down first, then optimize.
• Explain trade-offs during design and show awareness of operational constraints.

If you want, I can:

• Flesh out a full solution for any of the DSA problems with code (Python/Java).
• Draw a diagram or provide a sample Flink pipeline and schema for the Eats metrics design.

Good luck — and focus on clarity, correctness, and thoughtful trade-offs.

#SoftwareEngineering #SystemDesign #InterviewPrep