Uber 优步 面经整理合集 Part 5 | 面试代面 留学生面试代面 OA代做
Uber 面经整理合集 Part 5
想获取更多的服务 请添加微信 leetcode-king 或者扫码
Uber Coding Interview Questions
51. Reverse Bits [Bit Manipulation, Python]
Reverse bits of a given 32 bits unsigned integer.
class Solution:
def reverseBits(self, n: int) -> int:
result = 0
for i in range(32):
result = (result << 1) | (n & 1)
n >>= 1
return result52. Coin Change [Dynamic Programming, Python]
You are given coins of different denominations and a total amount of money. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -153. Power of Three [Math, Recursion, Python]
Given an integer n, return true if it is a power of three. Otherwise, return false.
class Solution:
def isPowerOfThree(self, n: int) -> bool:
if n < 1:
return False
while n % 3 == 0:
n //= 3
return n == 154. Implement Stack using Queues [Stack, Queue, Python]
Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).
from collections import deque
class MyStack:
def __init__(self):
self.queue1 = deque()
self.queue2 = deque()
def push(self, x: int) -> None:
self.queue2.append(x)
while self.queue1:
self.queue2.append(self.queue1.popleft())
self.queue1, self.queue2 = self.queue2, self.queue1
def pop(self) -> int:
return self.queue1.popleft()
def top(self) -> int:
return self.queue1[0]
def empty(self) -> bool:
return not self.queue155. Hamming Distance [Bit Manipulation, Python]
The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, calculate the Hamming distance.
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
return bin(x ^ y).count('1')Uber Coding Interview Questions
56. Subarray Sum Equals K [Hash Map, Prefix Sum, Python]
Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
count = 0
sum_dict = {0: 0}
current_sum = 0
for num in nums:
current_sum += num
if current_sum - k in sum_dict:
count += sum_dict[current_sum - k]
sum_dict[current_sum] = sum_dict.get(current_sum, 0) + 1
return count57. Find All Anagrams in a String [Sliding Window, Hash Map, Python]
Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.
from collections import Counter
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
p_count = Counter(p)
s_count = Counter()
result = []
for i in range(len(s)):
s_count[s[i]] += 1
if i >= len(p):
if s_count[s[i - len(p)]] == 1:
del s_count[s[i - len(p)]]
else:
s_count[s[i - len(p)]] -= 1
if p_count == s_count:
result.append(i - len(p) + 1)
return result58. Linked List Cycle [Linked List, Two Pointers, Python]
Given head, the head of a linked list, determine if the linked list has a cycle in it.
class Solution:
def hasCycle(self, head: ListNode) -> bool:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False59. Implement Queue using Stacks [Stack, Queue, Python]
Implement a first-in-first-out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, pop, peek, and empty).
class MyQueue:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, x: int) -> None:
self.stack1.append(x)
def pop(self) -> int:
self.peek()
return self.stack2.pop()
def peek(self) -> int:
if not self.stack2:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2[-1]
def empty(self) -> bool:
return not self.stack1 and not self.stack260. Course Schedule II [Graphs, Topological Sort, Python]
There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1. Some courses may have prerequisites, for example, to take course 0 you have to first take course 1, which is expressed as a pair: [0, 1]. Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
from collections import defaultdict, deque
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
graph = defaultdict(list)
indegree = [0] * numCourses
for dest, src in prerequisites:
graph[src].append(dest)
indegree[dest] += 1
queue = deque([i for i in range(numCourses) if indegree[i] == 0])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == numCourses else []Uber Coding Interview Questions
61. Meeting Rooms [Intervals, Sorting, Python]
Given an array of meeting time intervals consisting of start and end times [[s1, e1], [s2, e2], ...] (inclusive), determine if a person could attend all meetings.
class Solution:
def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
intervals.sort(key=lambda x: x[0])
for i in range(1, len(intervals)):
if intervals[i][0] < intervals[i - 1][1]:
return False
return True62. Meeting Rooms II [Intervals, Heap, Python]
Given an array of meeting time intervals consisting of start and end times [[s1, e1], [s2, e2], ...] (inclusive), return the minimum number of conference rooms required.
import heapq
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
if not intervals:
return 0
free_rooms = []
intervals.sort(key=lambda x: x[0])
heapq.heappush(free_rooms, intervals[0][1])
for i in range(1, len(intervals)):
if intervals[i][0] >= free_rooms[0]:
heapq.heappop(free_rooms)
heapq.heappush(free_rooms, intervals[i][1])
return len(free_rooms)63. Maximum Subarray Sum with One Deletion [Dynamic Programming, Arrays, Python]
Given an array of integers, return the maximum sum of the array after deleting exactly one element.
class Solution:
def maximumSum(self, arr: List[int]) -> int:
n = len(arr)
if n == 1:
return arr[0]
forward = [0] * n
backward = [0] * n
forward[0] = arr[0]
for i in range(1, n):
forward[i] = max(arr[i], forward[i - 1] + arr[i])
backward[-1] = arr[-1]
for i in range(n - 2, -1, -1):
backward[i] = max(arr[i], backward[i + 1] + arr[i])
max_sum = max(forward)
for i in range(1, n - 1):
max_sum = max(max_sum, forward[i - 1] + backward[i + 1])
return max_sum64. Maximal Square [Dynamic Programming, Matrix, Python]
Given a 2D binary matrix filled with 0s and 1s, find the largest square containing only 1s and return its area.
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
if not matrix:
return 0
m, n = len(matrix), len(matrix[0])
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_side = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if matrix[i - 1][j - 1] == '1':
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
max_side = max(max_side, dp[i][j])
return max_side * max_side65. Longest Increasing Subsequence [Dynamic Programming, Binary Search, Python]
Given an integer array nums, return the length of the longest strictly increasing subsequence.
import bisect
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
sub = []
for num in nums:
pos = bisect.bisect_left(sub, num)
if pos == len(sub):
sub.append(num)
else:
sub[pos] = num
return len(sub)Uber Coding Interview Questions
66. Binary Tree Level Order Traversal [Tree, BFS, Python]
Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
queue = deque([root])
result = []
while queue:
level = []
for i in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result67. Word Ladder II [Graphs, BFS, Backtracking, Python]
Given two words, beginWord and endWord, and a dictionary's word list, find all the shortest transformation sequence(s) from beginWord to endWord, such that:
- Only one letter can be changed at a time.
- Each transformed word must exist in the word list. Return all sequences in any order.
from collections import defaultdict, deque
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
wordList = set(wordList)
if endWord not in wordList:
return []
level = {beginWord: [[beginWord]]}
while level:
new_level = defaultdict(list)
for word in level:
if word == endWord:
return level[word]
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + c + word[i+1:]
if new_word in wordList:
new_level[new_word] += [j + [new_word] for j in level[word]]
wordList -= set(new_level.keys())
level = new_level
return []68. Decode String [Stack, Recursion, Python]
Given an encoded string, return its decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times.
class Solution:
def decodeString(self, s: str) -> str:
stack = []
current_num = 0
current_string = ''
for c in s:
if c.isdigit():
current_num = current_num * 10 + int(c)
elif c == '[':
stack.append((current_string, current_num))
current_string = ''
current_num = 0
elif c == ']':
last_string, num = stack.pop()
current_string = last_string + num * current_string
else:
current_string += c
return current_string69. Find Median from Data Stream [Heap, Design, Python]
The MedianFinder class will be implemented to find the median from a data stream.
import heapq
class MedianFinder:
def __init__(self):
self.small = []
self.large = []
def addNum(self, num: int) -> None:
heapq.heappush(self.small, -num)
if self.small and self.large and -self.small[0] > self.large[0]:
heapq.heappush(self.large, -heapq.heappop(self.small))
if len(self.small) > len(self.large) + 1:
heapq.heappush(self.large, -heapq.heappop(self.small))
if len(self.large) > len(self.small):
heapq.heappush(self.small, -heapq.heappop(self.large))
def findMedian(self) -> float:
if len(self.small) > len(self.large):
return -self.small[0]
return (-self.small[0] + self.large[0]) / 270. Design Tic-Tac-Toe [Design, Python]
Design a TicTacToe class that allows players to play the game. The class will have a move method to place a mark on the board.
class TicTacToe:
def __init__(self, n: int):
self.rows = [0] * n
self.cols = [0] * n
self.diagonal = 0
self.anti_diagonal = 0
self.n = n
def move(self, row: int, col: int, player: int) -> int:
add = 1 if player == 1 else -1
self.rows[row] += add
self.cols[col] += add
if row == col:
self.diagonal += add
if row + col == self.n - 1:
self.anti_diagonal += add
if (abs(self.rows[row]) == self.n or
abs(self.cols[col]) == self.n or
abs(self.diagonal) == self.n or
abs(self.anti_diagonal) == self.n):
return player
return 0Uber Coding Interview Questions
71. K Closest Points to Origin [Heap, Sorting, Python]
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).
import heapq
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
return heapq.nsmallest(k, points, key=lambda p: p[0]**2 + p[1]**2)72. Alien Dictionary [Graphs, Topological Sort, Python]
There is a new alien language that uses the English alphabet. However, the order among letters is unknown to you. You are given a list of strings words from the alien language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
from collections import defaultdict, deque
class Solution:
def alienOrder(self, words: List[str]) -> str:
graph = defaultdict(set)
indegree = {c: 0 for word in words for c in word}
for i in range(len(words) - 1):
first, second = words[i], words[i + 1]
min_length = min(len(first), len(second))
if len(first) > len(second) and first[:min_length] == second[:min_length]:
return ""
for j in range(min_length):
if first[j] != second[j]:
if second[j] not in graph[first[j]]:
graph[first[j]].add(second[j])
indegree[second[j]] += 1
break
queue = deque([c for c in indegree if indegree[c] == 0])
result = []
while queue:
c = queue.popleft()
result.append(c)
for neighbor in graph[c]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
if len(result) < len(indegree):
return ""
return "".join(result)