Uber 优步 面经整理合集 Part 4 | 编程测试代做 技术问答代面 职业规划代面
Uber 面经整理合集 Part 4
想获取更多的服务 请添加微信 leetcode-king 或者扫码
Uber Coding Interview Questions
31. LRU Cache [Design, Data Structures, Python]
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class with the following methods:
get(key): Retrieve the value of the key if it exists, otherwise return-1.put(key, value): Update the value of the key if it exists, or add the key-value pair if not. Evict the least recently used key when the cache reaches its capacity.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)32. Merge Two Sorted Lists [Linked List, Recursion, Python]
Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l233. Climbing Stairs [Dynamic Programming, Recursion, Python]
You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]34. Maximum Product Subarray [Dynamic Programming, Arrays, Python]
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
class Solution:
def maxProduct(self, nums: List[int]) -> int:
cur_max, cur_min = nums[0], nums[0]
global_max = nums[0]
for num in nums[1:]:
if num < 0:
cur_max, cur_min = cur_min, cur_max
cur_max = max(num, cur_max * num)
cur_min = min(num, cur_min * num)
global_max = max(global_max, cur_max)
return global_max35. Evaluate Reverse Polish Notation [Stack, Math, Python]
Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, and /. Each operand may be an integer or another expression.
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for token in tokens:
if token not in "+-*/":
stack.append(int(token))
else:
b, a = stack.pop(), stack.pop()
if token == '+':
stack.append(a + b)
elif token == '-':
stack.append(a - b)
elif token == '*':
stack.append(a * b)
else:
stack.append(int(a / b)) # integer division
return stack[0]Uber Coding Interview Questions
36. Group Anagrams [Hash Map, Strings, Python]
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
anagrams = defaultdict(list)
for s in strs:
sorted_s = ''.join(sorted(s))
anagrams[sorted_s].append(s)
return list(anagrams.values())37. Subsets [Backtracking, Recursion, Python]
Given an integer array nums of unique elements, return all possible subsets (the power set).
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
def backtrack(start, path):
res.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
res = []
backtrack(0, [])
return res38. Binary Search [Binary Search, Arrays, Python]
Given a sorted array of n integers and a target value, write a function to search for the target in the array. If the target exists, return its index. Otherwise, return -1.
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -139. Letter Combinations of a Phone Number [Backtracking, Strings, Python]
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
phone = {
"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
}
def backtrack(index, path):
if index == len(digits):
res.append(''.join(path))
return
for letter in phone[digits[index]]:
path.append(letter)
backtrack(index + 1, path)
path.pop()
res = []
backtrack(0, [])
return res40. 3Sum [Two Pointers, Sorting, Python]
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
res.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return resUber Coding Interview Questions
41. Find the Duplicate Number [Binary Search, Two Pointers, Python]
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive, there is only one repeated number in nums, return this repeated number.
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
slow = fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow42. Rotate Image [Matrix, Python]
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix)
for i in range(n):
for j in range(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for i in range(n):
matrix[i].reverse()43. Unique Paths [Dynamic Programming, Math, Python]
A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. How many possible unique paths are there?
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1]44. Reverse Linked List [Linked List, Recursion, Python]
Reverse a singly linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
return prev45. Container With Most Water [Two Pointers, Arrays, Python]
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines that together with the x-axis forms a container, such that the container contains the most water.
class Solution:
def maxArea(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
max_area = 0
while left < right:
max_area = max(max_area, min(height[left], height[right]) * (right - left))
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_areaUber Coding Interview Questions
46. Merge k Sorted Lists [Linked List, Divide and Conquer, Python]
You are given an array of k linked lists, each linked list is sorted in ascending order. Merge all the linked lists into one sorted linked list and return it.
import heapq
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
min_heap = []
for l in lists:
while l:
heapq.heappush(min_heap, l.val)
l = l.next
dummy = ListNode(0)
current = dummy
while min_heap:
current.next = ListNode(heapq.heappop(min_heap))
current = current.next
return dummy.next47. Top K Frequent Elements [Heap, Hash Map, Python]
Given a non-empty array of integers, return the k most frequent elements.
import heapq
from collections import Counter
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
count = Counter(nums)
return heapq.nlargest(k, count.keys(), key=count.get)48. Number of Islands [DFS, BFS, Matrix, Python]
Given a 2D grid map of 1s (land) and 0s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water.
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
def dfs(grid, r, c):
if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] == '0':
return
grid[r][c] = '0'
dfs(grid, r + 1, c)
dfs(grid, r - 1, c)
dfs(grid, r, c + 1)
dfs(grid, r, c - 1)
count = 0
for r in range(len(grid)):
for c in range(len(grid[0])):
if grid[r][c] == '1':
dfs(grid, r, c)
count += 1
return count49. Product of Array Except Self [Arrays, Prefix Sum, Python]
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
answer = [1] * n
prefix = 1
for i in range(n):
answer[i] = prefix
prefix *= nums[i]
suffix = 1
for i in range(n - 1, -1, -1):
answer[i] *= suffix
suffix *= nums[i]
return answer50. Valid Sudoku [Hash Set, Matrix, Python]
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
- Each row must contain the digits
1-9without repetition. - Each column must contain the digits
1-9without repetition. - Each of the nine
3 x 3sub-boxes of the grid must contain the digits1-9without repetition.
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
for r in range(9):
for c in range(9):
val = board[r][c]
if val == '.':
continue
if val in rows[r] or val in cols[c] or val in boxes[(r // 3) * 3 + c // 3]:
return False
rows[r].add(val)
cols[c].add(val)
boxes[(r // 3) * 3 + c // 3].add(val)
return True