Solve 12 coding interview problems
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
This multi-problem set evaluates broad algorithmic problem-solving skills, including bitwise reasoning, sliding-window and frequency analysis, stack/monotonic patterns, graph/DP reasoning with constrained jumps, and tree-path parity techniques.
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Loading coding console...
Quick Answer: This multi-problem set evaluates broad algorithmic problem-solving skills, including bitwise reasoning, sliding-window and frequency analysis, stack/monotonic patterns, graph/DP reasoning with constrained jumps, and tree-path parity techniques.
Input: (0,)
Expected Output: 0
Explanation: Already at 0, so no operations are needed.
Input: (1,)
Expected Output: 1
Explanation: Use -1 once.
Input: (3,)
Expected Output: 2
Explanation: One optimal sequence is 3 -> 4 -> 0.
Input: (39,)
Expected Output: 3
Explanation: For example: 39 -> 40 -> 32 -> 0.
def solution(n):
from functools import lru_cache
n = abs(n)
@lru_cache(None)
def dp(x):
if x == 0:
return 0
if x == 1:
return 1
if x % 2 == 0:
return dp(x // 2)
return 1 + min(dp((x - 1) // 2), dp((x + 1) // 2))
return dp(n)
Time complexity: O(log n). Space complexity: O(log n).
Input: ([], 1)
Expected Output: -1
Explanation: There is no subarray at all.
Input: ([1], 1)
Expected Output: 1
Explanation: The single element subarray already has 1 distinct value.
Input: ([1, 2, 1, 3, 4], 3)
Expected Output: 3
Explanation: One shortest good subarray is [2, 1, 3].
Input: ([1, 1, 1], 2)
Expected Output: -1
Explanation: The array contains only one distinct value.
def solution(arr, k):
if k <= 0:
return 0
n = len(arr)
freq = {}
distinct = 0
left = 0
best = n + 1
for right, value in enumerate(arr):
if freq.get(value, 0) == 0:
distinct += 1
freq[value] = freq.get(value, 0) + 1
while distinct >= k:
best = min(best, right - left + 1)
out = arr[left]
freq[out] -= 1
if freq[out] == 0:
del freq[out]
distinct -= 1
left += 1
return -1 if best == n + 1 else best
Time complexity: O(n). Space complexity: O(min(n, number of distinct values)).
Input: ([],)
Expected Output: (0, [])
Explanation: No items means total 0 and no full-price indices.
Input: ([8, 4, 6, 2, 3],)
Expected Output: (15, [3, 4])
Explanation: Final prices are [4, 2, 4, 2, 3].
Input: ([1, 2, 3, 4],)
Expected Output: (10, [0, 1, 2, 3])
Explanation: No item gets a discount.
Input: ([10, 1, 1, 6],)
Expected Output: (16, [2, 3])
Explanation: Final prices are [9, 0, 1, 6].
def solution(prices):
n = len(prices)
final_sum = sum(prices)
stack = []
discounted = [False] * n
for i, price in enumerate(prices):
while stack and prices[stack[-1]] >= price:
idx = stack.pop()
final_sum -= price
discounted[idx] = True
stack.append(i)
full_price_indices = [i for i, used_discount in enumerate(discounted) if not used_discount]
return final_sum, full_price_indices
Time complexity: O(n). Space complexity: O(n).
Input: ([],)
Expected Output: -1
Explanation: There is no start or end index.
Input: ([7],)
Expected Output: 7
Explanation: Start and end are the same index.
Input: ([5, -100, 4, 10],)
Expected Output: 15
Explanation: Jump directly from index 0 to index 3 using length 3.
Input: ([5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 20],)
Expected Output: 25
Explanation: A jump of length 13 skips all the negative values.
def solution(arr):
n = len(arr)
if n == 0:
return -1
if n == 1:
return arr[0]
limit = n - 1
sieve = [True] * (limit + 1)
if limit >= 0:
sieve[0] = False
if limit >= 1:
sieve[1] = False
i = 2
while i * i <= limit:
if sieve[i]:
for j in range(i * i, limit + 1, i):
sieve[j] = False
i += 1
special_primes = [p for p in range(3, limit + 1) if sieve[p] and p % 10 == 3]
dp = [0] * n
dp[0] = arr[0]
for i in range(1, n):
best_prev = dp[i - 1]
for p in special_primes:
if p > i:
break
if dp[i - p] > best_prev:
best_prev = dp[i - p]
dp[i] = best_prev + arr[i]
return dp[-1]
Time complexity: O(n * p), where p is the number of allowed prime jump lengths less than n. Space complexity: O(n + p).
Input: (5, ['a', 'b', 'a', 'c', 'b'], [0, 0, 1, 1], [1, 2, 3, 4], [4, 3, 2, 0])
Expected Output: [3, 1, 2, 1]
Explanation: For node 4, all three ancestor endpoints 4, 1, and 0 are valid.
Input: (4, ['a', 'b', 'a', 'b'], [0, 1, 2], [1, 2, 3], [3, 2])
Expected Output: [3, 2]
Explanation: On the chain, node 3 has three valid ancestor endpoints.
Input: (1, ['z'], [], [], [0])
Expected Output: [1]
Explanation: The only path is the single node itself.
def solution(treeNodes, nodes, nodeFrom, nodeTo, queries):
n = treeNodes
if n == 0:
return [0] * len(queries)
children = [[] for _ in range(n)]
for a, b in zip(nodeFrom, nodeTo):
children[a].append(b)
bits = [1 << (ord(ch) - 97) for ch in nodes]
answers = [0] * n
from collections import defaultdict
freq = defaultdict(int)
freq[0] = 1
stack = [(0, 0, 0)]
while stack:
u, mask, state = stack.pop()
if state == 0:
current = mask ^ bits[u]
total = freq.get(current, 0)
for b in range(26):
total += freq.get(current ^ (1 << b), 0)
answers[u] = total
freq[current] += 1
stack.append((u, current, 1))
for v in reversed(children[u]):
stack.append((v, current, 0))
else:
freq[mask] -= 1
if freq[mask] == 0:
del freq[mask]
return [answers[u] for u in queries]
Time complexity: O(26 * n + q). Space complexity: O(n).
Input: ([4, 2, 7], [3, 1, 2], 5)
Expected Output: 4
Explanation: Raising the 2 up to 4 costs 2, but reaching 5 would cost too much.
Input: ([1, 1, 1], [2, 2, 2], 6)
Expected Output: 2
Explanation: All three services can be raised from 1 to 2 exactly within budget.
Input: ([5], [10], 100)
Expected Output: 15
Explanation: A single service can be raised by 10.
Input: ([3, 8, 6], [1, 2, 3], 0)
Expected Output: 3
Explanation: With zero budget, the current minimum stays unchanged.
def solution(throughput, scale_cost, budget):
if not throughput:
return 0
low = min(throughput)
high = max(throughput) + budget // min(scale_cost) + 1
def can(target):
total = 0
for t, c in zip(throughput, scale_cost):
if t < target:
total += (target - t) * c
if total > budget:
return False
return True
while low + 1 < high:
mid = (low + high) // 2
if can(mid):
low = mid
else:
high = mid
return low
Time complexity: O(n log M), where M is the answer range. Space complexity: O(1).
Input: (0, 5, 2, 3, 10)
Expected Output: 0
Explanation: No movement is required.
Input: (3, 5, 2, 2, 10)
Expected Output: 5
Explanation: Best choice is x = 2, giving total time 4 + 1 = 5.
Input: (4, 1, 5, 1, 3)
Expected Output: 15
Explanation: Best choice is x = 2.
Input: (1, 1, 10, 5, 5)
Expected Output: 10
Explanation: Going fully by elevator is the only feasible option.
def solution(N, e1, t1, e2, c):
if N == 0:
return 0
best = float('inf')
for x in range(N + 1):
stairs = N - x
energy = x * e1
if energy < stairs * e2:
continue
total_time = x * t1
feasible = True
for _ in range(stairs):
if energy <= 0:
feasible = False
break
total_time += (c + energy - 1) // energy
energy -= e2
if energy < 0:
feasible = False
break
if feasible and total_time < best:
best = total_time
return -1 if best == float('inf') else best
Time complexity: O(N^2). Space complexity: O(1).
Input: ([8, 7, 15], [5, 10, 5], 2)
Expected Output: 33
Explanation: Choose tasks 0 and 2 for person A.
Input: ([3, 1, 2], [4, 5, 6], 0)
Expected Output: 15
Explanation: All tasks go to person B.
Input: ([3, 1, 2], [4, 5, 6], 3)
Expected Output: 6
Explanation: All tasks must go to person A.
Input: ([10], [1], 1)
Expected Output: 10
Explanation: The single task goes to person A.
def solution(reward1, reward2, k):
base = sum(reward2)
deltas = sorted((a - b for a, b in zip(reward1, reward2)), reverse=True)
return base + sum(deltas[:k])
Time complexity: O(n log n). Space complexity: O(n).
Input: ([], [], 10)
Expected Output: []
Explanation: No levels means no scores.
Input: ([2, 1, 3], [1, 2, 0], 4)
Expected Output: [1, 2, 1]
Explanation: Starting at index 1 lets you pass levels 1 and 2.
Input: ([5, 1], [0, 0], 4)
Expected Output: [0, 1]
Explanation: Starting at 0 fails immediately because the cost is too high.
Input: ([1, 2, 1, 1], [2, 1, 0, 0], 4)
Expected Output: [3, 3, 2, 1]
Explanation: The first failure from index 0 happens only at the last level.
def solution(layers, energyReq, K):
n = len(layers)
if n == 0:
return []
pref = [0] * (n + 1)
for i, x in enumerate(layers):
pref[i + 1] = pref[i] + x
need = [pref[i + 1] + max(0, energyReq[i]) - K for i in range(n)]
size = 1
while size < n:
size *= 2
seg = [float('-inf')] * (2 * size)
for i, v in enumerate(need):
seg[size + i] = v
for i in range(size - 1, 0, -1):
seg[i] = max(seg[2 * i], seg[2 * i + 1])
def first_greater(node, nl, nr, left, threshold):
if nr <= left or seg[node] <= threshold:
return n
if nr - nl == 1:
return nl
mid = (nl + nr) // 2
res = first_greater(node * 2, nl, mid, left, threshold)
if res != n:
return res
return first_greater(node * 2 + 1, mid, nr, left, threshold)
ans = [0] * n
for i in range(n):
j = first_greater(1, 0, size, i, pref[i])
ans[i] = (n - i) if j == n else (j - i)
return ans
Time complexity: O(n log n). Space complexity: O(n).
Input: ([2, 1, 3, 2, 4], [(1, 3), (2, 6), (5, 10)])
Expected Output: [2, 3, 1]
Explanation: From position 2 with budget 6, you can buy 1 + 3 + 2.
Input: ([5], [(1, 4), (1, 5)])
Expected Output: [0, 1]
Explanation: The first budget is too small; the second buys exactly one item.
Input: ([3, 3, 3], [(2, 2), (2, 3), (1, 9)])
Expected Output: [0, 1, 3]
Explanation: The full budget 9 buys all three items from the start.
def solution(prices, queries):
from bisect import bisect_right
pref = [0]
for p in prices:
pref.append(pref[-1] + p)
ans = []
for pos, amount in queries:
start = pos - 1
target = pref[start] + amount
right = bisect_right(pref, target) - 1
ans.append(right - start)
return ans
Time complexity: O((n + q) log n). Space complexity: O(n).
Input: (1, [])
Expected Output: [0]
Explanation: A single node needs no reversals.
Input: (3, [[0, 1], [2, 1]])
Expected Output: [1, 0, 1]
Explanation: Root 1 already has all edges effectively pointing toward it.
Input: (4, [[0, 1], [0, 2], [0, 3]])
Expected Output: [3, 2, 2, 2]
Explanation: With root 0, all three edges must be reversed.
def solution(n, edges):
if n == 0:
return []
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append((b, 1))
adj[b].append((a, 0))
res = [0] * n
parent = [-1] * n
order = []
stack = [0]
while stack:
u = stack.pop()
order.append(u)
for v, w in adj[u]:
if v == parent[u]:
continue
parent[v] = u
res[0] += w
stack.append(v)
for u in order:
for v, w in adj[u]:
if v == parent[u]:
continue
res[v] = res[u] + (1 if w == 0 else -1)
return res
Time complexity: O(n). Space complexity: O(n).
Input: ([],)
Expected Output: []
Explanation: No values means no answers.
Input: ([1],)
Expected Output: [1]
Explanation: The set {1} always forms a contiguous block.
Input: ([4, 1, 3, 2],)
Expected Output: [1, 0, 1, 1]
Explanation: For w = 3, the positions of 1, 2, and 3 span exactly length 3.
Input: ([2, 1, 4, 3, 5],)
Expected Output: [1, 1, 0, 1, 1]
Explanation: Values 1 and 2 are adjacent, but values 1..3 are not in one block.
def solution(perm):
n = len(perm)
if n == 0:
return []
pos = [0] * (n + 1)
for i, value in enumerate(perm):
pos[value] = i
ans = []
lo = n
hi = -1
for w in range(1, n + 1):
p = pos[w]
if p < lo:
lo = p
if p > hi:
hi = p
ans.append(1 if hi - lo + 1 == w else 0)
return ans
Time complexity: O(n). Space complexity: O(n).