Uber Hard Interview Questions

Uber has a feature to notify drivers of nearby ride requests in real-time. Implement a Twitter-like feed system that delivers updates to users based on user subscriptions to certain categories, allowing users to add, remove, and fetch their feeds.- class Feed:
- def add_category(self, user_id: int, category: str) -> None — Add a category to the user's subscription.
- def remove_category(self, user_id: int, category: str) -> None — Remove a category from the user's subscription.
- def get_feed(self, user_id: int) -> List[str] — Return the feed of updates for the user.Example 1:
Input: feed = Feed(), feed.add_category(1, 'Ride'), feed.add_category(1, 'Promo'), feed.get_feed(1)
Output: ['Ride', 'Promo']
Explanation: User 1 subscribes to 'Ride' and 'Promo' categories.Example 2:
Input: feed.remove_category(1, 'Promo'), feed.get_feed(1)
Output: ['Ride']
Explanation: User 1 unsubscribes from 'Promo'.Constraints:
- The maximum number of users is 1 <= user_id <= 10^4.
- The maximum number of categories is 1 <= category_count <= 100.

With millions of users, Uber needs an efficient way to cache frequently requested ride demand data. Implement an LRU (Least Recently Used) cache that allows adding, retrieving, and evicting ride demand based on their usage.- class LRUCache:
- def __init__(self, capacity: int) — Initializes the LRU cache.
- def get(self, key: int) -> int — Returns the value of the key if the key exists.
- def put(self, key: int, value: int) — Updates the value of the key or adds the key-value pair.Example 1:
Input: lru = LRUCache(2), lru.put(1, 1), lru.put(2, 2), lru.get(1)
Output: 1
Explanation: Key 1 is present, returning its value.Example 2:
Input: lru.put(3, 3), lru.get(2)
Output: -1
Explanation: Key 2 was evicted because it was least recently used.Constraints:
- The capacity of the cache is 1 <= capacity <= 10^4.
- All keys and values are in the range of 1 <= key, value <= 10^5.

Uber aims to maximize revenue by optimizing surge pricing during peak hours. The challenge is to calculate the maximum number of rides that can occur in any contiguous window of time.
Given an array representing the number of rides requested at each time interval, implement a function that finds the maximum number of rides that can be accommodated within a contiguous window of size k.- def max_rides_in_window(rides: List[int], k: int) -> int
- Returns the maximum number of rides in any contiguous window of size k.Example 1:
Input: rides = [2, 1, 5, 1, 3, 2], k = 3
Output: 9
Explanation: The maximum rides in the window [5, 1, 3] is 9.Example 2:
Input: rides = [1, 2, 3, 4, 5], k = 2
Output: 9
Explanation: The maximum rides in the window [4, 5] is 9.Constraints:
- 1 <= len(rides) <= 10^5
- 1 <= rides[i], k <= 10^4.

Uber's ride-sharing services rely on efficient routing to minimize wait times and optimize driver assignments. The goal is to find the shortest path between two locations in a network of paths.
Given a graph represented as an adjacency list where each edge has a non-negative weight, implement a function that finds the shortest distance from a starting node to a destination node.- def dijkstra(graph: Dict[int, List[Tuple[int, int]]], start: int, destination: int) -> int
- Returns the shortest distance from start to destination.Example 1:
Input: graph = {0: [(1, 1), (2, 4)], 1: [(2, 2), (3, 6)], 2: [(3, 1)], 3: []}, start = 0, destination = 3
Output: 3
Explanation: The path 0 -> 1 -> 2 -> 3 has a total weight of 3.Example 2:
Input: graph = {0: [(1, 2)], 1: [(2, 3)], 2: [(3, 1)], 3: []}, start = 0, destination = 3
Output: 6
Explanation: The path 0 -> 1 -> 2 -> 3 has a total weight of 6.Constraints:
- 1 <= len(graph) <= 10^4
- 0 <= start, destination < len(graph)
- Each edge's weight is a positive integer.