← Uber Interview InsightsSoftware Engineer

Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Uber SWE coding round, one main algorithm problem with a bunch of follow-ups tacked on. The core question wasn't too bad but the interviewer kept pushing after the solution was done, which is where things got more interesting.

Questions Asked (3)

Q1

Given plain-text ride-sharing logs (each entry has a timestamp and indicates that user A shared a ride with user B) and a list of all users, find the earliest timestamp at which every user becomes connected.

Algorithms & Data Structures
Author's notes

Used Union Find, which felt like the right call and the interviewer seemed fine with it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize this as a classic Union-Find (Disjoint Set Union) problem combined with a binary search or linear scan over sorted timestamps. Sort the ride-sharing log entries by timestamp, then incrementally union users as rides are processed, stopping the moment all users belong to a single connected component. This approach efficiently tracks connectivity in near-linear time.

Pro tip: Mention that in a real Uber system, logs could be massive and distributed, so briefly acknowledging how you'd handle streaming data or offline batch processing (e.g., using a sorted merge of partitioned logs) shows senior-level thinking beyond the algorithmic solution.

1. Clarify the Problem

Confirm edge cases: what if a user never shares a ride (isolated node), are timestamps guaranteed unique, and what should be returned if full connectivity is never achieved? Establishing these constraints prevents incorrect assumptions.

2. Choose the Right Data Structure

Propose Union-Find (DSU) with path compression and union by rank, explaining that it supports near O(1) amortized union and find operations. Initialize each user as its own component and track the number of distinct components.

3. Sort and Process Log Entries

Sort all log entries by timestamp in ascending order, then iterate through them, performing a union operation for each ride-sharing pair. After each union, decrement the component count if two previously separate components were merged.

4. Detect Full Connectivity

After each union step, check if the number of distinct components has reached 1 — if so, return the current timestamp as the answer. This avoids unnecessary processing of remaining log entries.

5. Analyze Complexity and Edge Cases

State the time complexity as O(N log N) for sorting plus O(M · α(N)) for union-find operations, where N is the number of log entries and M is the number of users. Address the edge case where full connectivity is never reached by returning -1 or null.

Key Points to Mention

  • Union-Find (DSU) with path compression and union by rank for efficient component tracking
  • Sorting log entries by timestamp as a prerequisite before processing
  • Tracking the number of connected components and terminating early when it reaches 1
  • Time complexity analysis: O(N log N) sorting + O(M · α(N)) DSU operations
  • Edge cases: isolated users who never appear in logs, duplicate timestamps, or logs that never achieve full connectivity
  • Scalability consideration: handling large or distributed log files in a real-world Uber context

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

Q2

How would you modify your solution if the log file contained more than one type of log entry, not just ride-sharing events?

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

This is where I stumbled a bit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Frame your answer around extensibility and separation of concerns — explain how you would introduce a parsing layer that identifies and routes different log entry types before applying type-specific processing logic. Emphasize designing for open/closed principle so new log types can be added without modifying existing code. Ground your answer in concrete data structures and patterns rather than staying abstract.

Pro tip: Mention real-world Uber context: production logs at scale contain mixed entries (driver events, payment events, surge pricing, errors), so demonstrating awareness of schema versioning, backward compatibility, and performance implications of type-dispatching will signal senior-level thinking.

1. Identify the Problem with Mixed Log Types

Acknowledge that a heterogeneous log file means entries have different schemas, fields, and processing requirements. Clarify that a single monolithic parser will become brittle and hard to maintain as new log types are introduced.

2. Introduce a Type Detection and Routing Layer

Describe adding a dispatcher or factory that reads a common header field (e.g., 'event_type' or 'log_category') from each entry and routes it to the appropriate handler. This decouples type identification from type-specific business logic.

3. Define a Common Interface / Abstract Base

Propose an abstract LogEntry interface or base class with shared fields (timestamp, source, severity) and a process() method, with concrete subclasses for each log type (RideEvent, PaymentEvent, ErrorLog). This enforces a consistent contract while allowing specialization.

4. Address Data Structure and Storage Implications

Discuss how mixed types affect downstream storage — you may need separate data structures, queues, or output streams per log type to avoid polluting aggregations. Mention filtering, partitioning, or using a tagged union / discriminated union approach.

5. Consider Scale, Performance, and Extensibility Trade-offs

Highlight trade-offs such as parsing overhead for type detection on every line, memory footprint of maintaining multiple handler objects, and how to handle unknown or malformed log types gracefully. Conclude by noting how the design makes adding a new log type a matter of adding a new class and registering it, not rewriting existing logic.

Key Points to Mention

  • Strategy or Factory pattern for dispatching log entries to type-specific parsers
  • Common interface or abstract base class to enforce a consistent LogEntry contract
  • Graceful handling of unknown or malformed log types (e.g., dead-letter queue or skip-with-warning)
  • Performance considerations: single-pass parsing vs. multi-pass, and the cost of type detection at scale
  • Schema versioning and backward compatibility when log formats evolve over time
  • Separation of concerns: parsing, validation, transformation, and storage should be independent stages

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

Q3

What is the approximate time complexity of your solution?

Algorithms & Data Structures
Author's notes

Answered it, but I fumbled the Union Find amortized analysis for a second.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clearly identifying the dominant operations in your solution and express the complexity in Big-O notation for both time and space. Walk the interviewer through your reasoning step-by-step, referencing specific loops, recursive calls, or data structure operations rather than just stating a final answer. This demonstrates analytical depth and communicates that you understand *why* the complexity is what it is, not just what it is.

Pro tip: Proactively discuss trade-offs — if a more optimal solution exists, acknowledge it and explain why you chose your current approach (e.g., simplicity, readability, or constraints). Interviewers at companies like Uber value engineers who are aware of the full solution space, not just the one they implemented.

1. Identify the Input Variables

Define what 'n' (or other variables) represents in the context of your problem — e.g., number of nodes, length of array, or size of a graph. Being explicit about input variables prevents ambiguity and shows precision.

2. Analyze Each Major Operation

Break down your solution into its key components — loops, recursive calls, sorting steps, or data structure lookups — and state the complexity of each individually. This structured decomposition shows the interviewer your systematic thinking.

3. Combine and Identify the Dominant Term

Combine the complexities of individual components using addition (sequential steps) or multiplication (nested steps), then drop lower-order terms and constants to arrive at the final Big-O. Clearly state your final time and space complexity.

4. Discuss Best, Average, and Worst Cases

Briefly mention if the complexity differs across cases — for example, quicksort is O(n log n) on average but O(n²) in the worst case. This shows maturity and awareness of real-world performance behavior.

5. Acknowledge Trade-offs and Optimizations

Mention whether a more optimal solution exists and what trade-offs your current approach makes (e.g., sacrificing space for speed). This signals engineering judgment and readiness for follow-up questions.

Key Points to Mention

  • Big-O notation and what it represents (upper bound on growth rate)
  • Time complexity vs. space complexity — address both proactively
  • Impact of nested loops, recursion depth, and data structure operations (e.g., hash map O(1) lookup, heap O(log n) insertion)
  • Best-case, average-case, and worst-case distinctions where relevant
  • How input size and constraints influence the acceptable complexity (e.g., O(n²) may be fine for n ≤ 1000 but not n ≤ 10⁶)
  • Any potential optimizations and why you chose the current approach over them

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.