Uber 优步 面经整理合集 Part 3 | Python远程面试代面 面试技巧 面试通关代面
Uber 面经整理合集 Part 3
想获取更多的服务 请添加微信 leetcode-king 或者扫码
21. Search in Rotated Sorted Array [Binary Search, Arrays, Python]
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. You are given a target value to search. If found in the array, 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
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -122. Combination Sum [Backtracking, Recursion, Python]
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def backtrack(remaining, combo, start):
if remaining == 0:
res.append(list(combo))
return
elif remaining < 0:
return
for i in range(start, len(candidates)):
combo.append(candidates[i])
backtrack(remaining - candidates[i], combo, i)
combo.pop()
res = []
backtrack(target, [], 0)
return res23. Valid Parentheses [Stack, Strings, Python]
Given a string s containing just the characters '(', ')', '{', '}', '[', and ']', determine if the input string is valid.
class Solution:
def isValid(self, s: str) -> bool:
stack = []
mapping = {")": "(", "}": "{", "]": "["}
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)
return not stack24. Spiral Matrix [Matrix, Simulation, Python]
Given an m x n matrix, return all elements of the matrix in spiral order.
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
res = []
while matrix:
res += matrix.pop(0)
if matrix and matrix[0]:
for row in matrix:
res.append(row.pop())
if matrix:
res += matrix.pop()[::-1]
if matrix and matrix[0]:
for row in matrix[::-1]:
res.append(row.pop(0))
return res25. Permutations [Backtracking, Recursion, Python]
Given an array nums of distinct integers, return all possible permutations.
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def backtrack(start):
if start == len(nums):
res.append(nums[:])
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start]
backtrack(start + 1)
nums[start], nums[i] = nums[i], nums[start]
res = []
backtrack(0)
return resUber Coding Interview Questions
26. House Robber [Dynamic Programming, Arrays, Python]
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, and the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) <= 2:
return max(nums)
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]27. Course Schedule [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]. Determine if you can finish all courses.
from collections import defaultdict, deque
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
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])
count = 0
while queue:
node = queue.popleft()
count += 1
for neighbor in graph[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
return count == numCourses28. Find Peak Element [Binary Search, Arrays, Python]
A peak element is an element that is strictly greater than its neighbors. Given an integer array nums, find a peak element, and return its index. The array may contain multiple peaks, in that case, return the index to any one of the peaks.
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[mid + 1]:
right = mid
else:
left = mid + 1
return left29. Kth Largest Element in an Array [Heap, Sorting, Python]
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
import heapq
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
return heapq.nlargest(k, nums)[-1]30. Palindrome Partitioning [Backtracking, Dynamic Programming, Python]
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
class Solution:
def partition(self, s: str) -> List[List[str]]:
def is_palindrome(sub):
return sub == sub[::-1]
def backtrack(start, path):
if start == len(s):
res.append(path[:])
return
for end in range(start + 1, len(s) + 1):
if is_palindrome(s[start:end]):
path.append(s[start:end])
backtrack(end, path)
path.pop()
res = []
backtrack(0, [])
return res