Uber Interview Questions
- DSA
- LLD
- HLD
Q1: Number of Islands II
Given a 2D matrix with 1’s and 0’s, exactly 2 islands exist in the matrix. Devise an algorithm to count and operate on these islands under constraints.
Example
Input: m = 3, n = 3, positions = [[0][0], [0][1], [1][2], [2][1]]
Output: [1][1][2][3]
Explanation: Initially the grid is all water. After adding land at (0,0), we have one island. After adding (0,1): still one island (connected horizontally). Adding (1,2): new disconnected land, two islands now. Adding (2,1): forms a third distinct island.
Q2: LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache, supporting get and put operations in O(1) time.
Example :
Input: LRUCache(2) put(1, 1), put(2, 2), get(1), put(3, 3), get(2), put(4, 4), get(1), get(3), get(4)
Output: [1, -1, -1, 3, 4]
Explanation: Cache capacity is 2. put(1,1): {1=1}. put(2,2): {1=1, 2=2}. get(1): returns 1, (1) becomes most recently used. put(3,3): evicts (2), now {1=1, 3=3}. get(2): not found, returns -1. put(4,4): evicts (1), now {3=3, 4=4}. get(1): not found, returns -1. get(3): returns 3. get(4): returns 4.
Q3: Find Median from Data Stream
Design a data structure to efficiently add numbers from a stream and retrieve the median at any time.
Example :
Input: [5][15][1][3][2][8]
Output: [5.00, 10.00, 5.00, 4.00, 3.00, 4.00]
Explanation: Add 5: → median 5. Add 15: → median (5+15)/2 = 10. Add 1: → median is 5. Add 3: → median (3+5)/2 = 4. Add 2: → median = 3. Add 8: → median (3+5)/2 = 4.
Q4: Alien Dictionary
Given a list of words sorted lexicographically (but in an unknown language), figure out the order of characters in the language.
Example:
Input: words = ["baa", "abcd", "abca", "cab", "cad"]
Output: "bdac"
Explanation: Comparing each adjacent pair: “baa” vs “abcd” → ‘b’ before ‘a’. “abcd” vs “abca” → ‘d’ before ‘a’. “abca” vs “cab” → ‘a’ before ‘c’. “cab” vs “cad” → ‘b’ before ‘d’. Topologically sorting gives “bdac”.
Q5: Clone Graph
Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.
Example :
Input: adjList = [[2][4],[1][3],[2][4],[1][3]]
Output:[[2][4],[1][3],[2][4],[1][3]]
Explanation: There are 4 nodes: Node 1 → 2, 4. Node 2 → 1, 3. Node 3 → 2, 4. Node 4 → 1, 3. Cloning yields an identical graph structure.
Q6: Top K Frequent Elements
Given a non-empty array of integers, return the k most frequent elements.
Example:
Input: nums = [1][1][1][2][2][3], k = 2
Output: [1][2]
Explanation: Number 1 appears 3 times, 2 appears 2 times, 3 appears 1 time. Top 2 frequent elements are.
Q7: Elimination Coding Round: Longest Continuous Subarray With Absolute Diff ≤ Limit
Given: An array of integers nums and an integer limit.
Task: Return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is ≤ limit.
Example
Input: nums = [8][2][4][7], limit = 4
Output: 2
Explanation: All subarrays: with max max diff |8-8| = 0 ≤ 4. with max diff |8-2| = 6 > 4. with max diff |2-2| = 0 ≤ 4. with max diff |2-4| = 2 ≤ 4. with max diff |4-7| = 3 ≤ 4. Therefore, the longest subarray size is 2
Q8: DSA + DSU (Disjoint Set Union) - "Cab Sharing Logs"
Input: Logs in format UserA-Shared-UserB-timestamp (UserA and UserB share a cab).
Version 1: For each log, return how many cabs are currently running (track number of connected components).
Version 2: For given logs, return the timestamp when all users are in one cab (all connected in a single set).
Example:
Input: logs = ["A-Shared-B-1", "B-Shared-C-2", "D-Shared-E-3"]
Output: [1][1][2] (number of connected components after each log)
Explanation: Initially all users are separate. After A-B share: 1 component {A,B}, others separate. After B-C share: 1 component {A,B,C}, others separate. After D-E share: 2 components {A,B,C} and {D,E}.
Q9: Minimum Cost Path with Arrows in Matrix
Description: Given an n×m grid with arrows pointing in different directions, calculate the minimum cost from the top-left to bottom-right, where moving in the direction of the arrow costs 0 and moving in any other direction costs
Example:
Input: grid = [[1,1,1,1], [2,2,2,2], [1,1,1,1]] arrows = [[“RIGHT”,”RIGHT”,”DOWN”], [“DOWN”,”RIGHT”,”RIGHT”], [“RIGHT”,”RIGHT”,”RIGHT”]]
Output: 2
Explanation: Path from (0,0) to (2,3): Follow RIGHT arrows at cost 0, then when moving against arrow direction, cost is 1. Optimal path: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)→(2,3) with total cost 2.
Q10: Next Greater Palindrome Number
Description: Given a number, find the next greater palindrome using a mirror and carry propagation approach.
Example:
Input: num = "1221"
Output: "2112"
Explanation: The next greater palindrome using same digits: mirror left half “12” to get “1221”, increment to get next permutation “21”, then mirror to get “2112”.
Q11: Expiry Counter Class (Machine Coding)
Description: Implement a class with methods put_element(k), get_element_count(k), and get_total_elements(), tracking expiry for elements after t seconds.
Example:
Input: put_element(“A”), put_element(“B”), put_element(“A”) get_element_count(“A”) at t=1 get_total_elements() at t=5 (assuming t=2 expiry)
Output: 2, 0
Explanation: put_element(“A”) at t=0, put_element(“B”) at t=0, put_element(“A”) at t=0. At t=1, “A” count is 2. At t=5, all elements expired (assuming 2-second TTL), so total is 0.
Q12: Reconstruct Itinerary
Given a list of airline tickets represented as pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets form at least one valid itinerary. If there are multiple valid itineraries, return the itinerary that has the smallest lexical order when read as a single string.
Example:
Input: tickets = [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]
Output: ["JFK","KUL","JFK","NRT","JFK"]
Explanation: Start from JFK. Multiple paths exist: JFK→KUL, then JFK→NRT→JFK vs JFK→NRT→JFK→KUL. Lexicographically smaller path is JFK→KUL first.
Q13: Optimal Cost to Construct Binary Search Tree
Description: Given keys and their frequencies, find the optimal cost to construct the binary search tree such that the total cost of all searches is minimized. The cost of a BST is the sum of all keys multiplied by the depth of the keys.
Example:
Input: keys = [10][12][20], freq = [34][8][50]
Output: 142
Explanation: Tree with root 20: left subtree has 10(freq 34), 12(freq 8); right subtree empty. Cost = 50×1 + 34×2 + 8×3 = 50 + 68 + 24 = 142.
Q14: Odd Zero Counter
Given an array of integers, count how many elements have an odd number of occurrences of the digit 0 in their decimal representation.
Example:
Input: [20][10][10070]
Output: 3
Explanation: 20 has one zero (odd count). 10 has one zero (odd count). 10070 has three zeros (odd count). Total elements with odd number of zeros: 3.
Q15: Sensor Digit Frequency
Given an array of non-negative integers representing sensor readings, find the digit (0-9) that appears most frequently across all readings written in decimal form. If multiple digits tie, return the smallest digit among them.
Example:
Input: [123][111][222]
Output: 1
Explanation: Digit frequencies: 1 appears 4 times, 2 appears 4 times, 3 appears 1 time. Digits 1 and 2 tie with 4 occurrences each. Return smallest digit: 1.
Q16: Stepwise Structures
Given an array of integers where each integer represents the height of a structure, calculate the minimum total increment required to transform the array into either a strictly ascending or strictly descending stepwise sequence (where each element differs by exactly 1 from the previous) by only increasing heights (no decreases).
Example :
Input: [1][2][3]
Output: 4
Explanation: For ascending: target , current , increment needed = 0. For descending: target , need →. Increment 1 to 3 (+2), keep 2 as 2 (+0), need 3 to be 1 but can’t decrease so increment by +2 for . Total = 4.
Q17: Bubble Explosion Simulation
Given a 2D grid of bubbles denoted by integers (0 means empty), simulate one round of explosions and gravity as follows:
- A bubble explodes if it has at least two adjacent bubbles of the same color (up, down, left, right).
- Exploding bubbles trigger their adjacent same-colored bubbles to explode.
- After explosion, bubbles above empty spaces fall down.
Return the resulting grid after one round of explosions and gravity.
Example:
Input: grid = [[1,1,0], [2,2,2], [0,1,1]]
Output: [[0,0,0], [0,0,0], [2,2,2]]
Explanation: Row 2 has three 2’s (adjacent same colors) → explodes. After explosion, remaining bubbles fall down due to gravity. Row 1’s 1’s also explode (adjacent). Final state after gravity.
Q1. Multithreaded Code—Producer/Consumer, Thread Pools, etc
Write and design multithreaded code handling concurrency in object-oriented problems, touching on synchronization, thread safety, and extensibility.
Q2. Design TinyURL/URL Shortening Service
Create a low-level design (classes, APIs) for a service converting long URLs into short, unique ones with encoding and redirection features.
Q3. Round 2: Train-Platform Management System
- Core functionalities:
- Assign trains to platforms based on input.
- Query which train is at a given platform at a specific time.
- Query which platform a train is at, at a specific time.
- Expectations:
- Write runnable code (Java), use design patterns, and demonstrate extensibility.
- Focus on scheduling, time-based queries, and mappings between trains/platforms.
- Used a minHeap strategy for scheduling and also discussed random assigning.
- Explain OOD decisions, and write only required variables/methods for clarity and brevity.
Q4. Machine Coding Round: Class Design & Implementation (CodeSignal)
- Description: Design and implement a set of classes based on a given set of use cases, encapsulating required functionality. Code should be extensible and well-structured, following proper OOP principles.
- Focus: Class relationships, methods, data handling, and compliance with requirements.
- Context: Conducted on CodeSignal platform for a 1-hour slot.
Q5. Design Meeting Scheduler
- Problem Statement:
Design a system to manage bookings for n meeting rooms. Requests come continuously with start and end times, and the system should allocate any available room for the requested time slot. If no rooms are available, the booking should be rejected or queued.
Q1. Design Uber's Ride-Matching System
Architect a scalable service to match nearby riders and drivers in real time, factoring in dynamic locations, surge pricing, ETA, and robustness at scale.
Q2. Design Google Maps/Navigation System
Design a service similar to Google Maps with efficient map data storage, live routing, address parsing, and traffic-aware pathfinding.
Q3. Real-Time Location Tracking System
Design a scalable system for live real-time GPS updates for millions of users.
Q4. Design a Pub-Sub System Using Java Threads
- Description: Design and implement a publish-subscribe (pub-sub) messaging system that supports multiple publishers and subscribers. The system should simulate concurrency using Java threads with proper synchronization, thread safety, and message delivery guarantees.
- Focus Areas:
- Thread creation and management in Java.
- Synchronization primitives (locks, wait/notify).
- Message queues and buffering between publishers and subscribers.
- Handling multiple producers and consumers concurrently.
- Recommended Prep: Brush up on Java concurrency, thread synchronization, and concurrent data structures.
Q5. Design Uber Eats Homepage
- Focus Areas:
- Location-based search (use GeoHashing & GeoIndexing).
- API design for homepage and search results.
- Schema design for Restaurants, Dishes, Orders.
- DB choice and justification (SQL vs NoSQL).
- Use of caching for homepage/search performance.
- Metrics to handle:
- Most ordered restaurant.
- Most ordered dish.
- Orders per restaurant.
- Tools/Process:
- Used design whiteboard for architecture diagrams.
- Heavy focus on trade-offs, mistakes, and architecture critique.
Q6. Design Bus Booking System
- Problem Statement:
Design a system to handle bus ticket bookings. The system should allow users to search for buses on specific routes and dates, view available seats, book tickets, and handle cancellations. The system should ensure seat availability is accurately maintained and prevent double-bookings. - Key Requirements:
- Maintain bus schedules with routes, timings, and seat capacity.
- Support seat selection and booking transactions.
- Handle concurrent booking requests and ensure data consistency.
- Provide ticket cancellation and refund functionality.
- Support user profiles and booking history.
Q7. Uber Driver Heatmap Dashboard
- Description: Design a system to create a real-time and batch dashboard for Uber driver location heatmaps for city analytics.
- Key Points:
- Real-time: Consume GPS events from Kafka, bucket by geohash, aggregate in Flink, cache in Redis.
- Batch: Aggregate hourly data into Postgres for historical analytics.
- Discussed aspects: Fault tolerance, scalability, API/data contracts, use of DynamoDB/Postgres, windowing, choice of cache store.
Q1. Discussion
- Behavioral and manager round focused on:
- Own coding practices, team and project ownership, and previous work impact.
- Questions on good code, teamwork, and values.
- Opportunity for candidate to ask about the team, role advancement, etc.
Q2. What does receiving a "waitlist"
What does receiving a “waitlist” email after the Uber Online Assessment (OA) likely indicate, and how is it used in the selection process? Explain the scenarios in which candidates receive the waitlist email and what it means for further interview eligibility.
- Context:
- Candidates who solved all problems rapidly, those who solved fewer, and even some who did not attempt the OA at all received the same waitlist email.
- Backend confirmation from an SDE-2 at Uber that this message is an automated (silent rejection) response, not an actual waitlist for interview rounds.
- Only those who were moving forward to interviews received their scheduling/updates prior to the mass distribution of the waitlist messages.
Q3. Technical Leadership & Project Monologue
- Description: Discussion on impactful projects, technical and non-technical challenges faced, reasons for job change, future interests, and contribution to team/company.
- Category: Behavioral (not DSA, LLD, HLD directly, but vital for bar raiser/managerial rounds).
Q4. Behavioral Interview Using STAR Framework
- Focus: Discuss past projects, ownership, technical and interpersonal challenges, motivation for role change, and future goals.
- Key Points:
- Situation, Task, Action, Result (STAR) method to structure answers.
- Emphasize impact and learning.
- Align past experience to the role’s demands and company values.
