Uber 优步 面经整理合集 Part 2 | Java面试代面 技术面试作弊 编程面试代面
Uber 面经整理合集 Part 2
想获取更多的服务 请添加微信 leetcode-king 或者扫码
11. Minimum Window Substring [Sliding Window, Strings, Python]
Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window, return the empty string "".
from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
if not s or not t:
return ""
dict_t = Counter(t)
required = len(dict_t)
l, r = 0, 0
formed = 0
window_counts = {}
ans = float("inf"), None, None
while r < len(s):
character = s[r]
window_counts[character] = window_counts.get(character, 0) + 1
if character in dict_t and window_counts[character] == dict_t[character]:
formed += 1
while l <= r and formed == required:
character = s[l]
if r - l + 1 < ans[0]:
ans = (r - l + 1, l, r)
window_counts[character] -= 1
if character in dict_t and window_counts[character] < dict_t[character]:
formed -= 1
l += 1
r += 1
return "" if ans[0] == float("inf") else s[ans[1]: ans[2] + 1]12. Longest Palindromic Substring [Dynamic Programming, Strings, Python]
Given a string s, return the longest palindromic substring in s.
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n == 0:
return ""
dp = [[False] * n for _ in range(n)]
start, max_length = 0, 1
for i in range(n):
dp[i][i] = True
for i in range(n-1):
if s[i] == s[i+1]:
dp[i][i+1] = True
start = i
max_length = 2
for length in range(3, n+1):
for i in range(n-length+1):
j = i+length-1
if s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = True
start = i
max_length = length
return s[start:start+max_length]13. Maximum Subarray [Dynamic Programming, Arrays, Python]
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
current_sum = max_sum = nums[0]
for num in nums[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum14. Jump Game [Dynamic Programming, Greedy, Python]
Given an array of non-negative integers nums, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.
class Solution:
def canJump(self, nums: List[int]) -> bool:
max_reachable = 0
for i, jump in enumerate(nums):
if i > max_reachable:
return False
max_reachable = max(max_reachable, i + jump)
return True15. Sort Colors [Sorting, Two Pointers, Python]
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.
class Solution:
def sortColors(self, nums: List[int]) -> None:
left, right, current = 0, len(nums) - 1, 0
while current <= right:
if nums[current] == 0:
nums[left], nums[current] = nums[current], nums[left]
left += 1
current += 1
elif nums[current] == 2:
nums[right], nums[current] = nums[current], nums[right]
right -= 1
else:
current += 116. Decode Ways [Dynamic Programming, Strings, Python]
A message containing letters from A-Z can be encoded into numbers using the following mapping: 'A' -> 1, 'B' -> 2, ..., 'Z' -> 26. Given a non-empty string containing only digits, determine the total number of ways to decode it.
class Solution:
def numDecodings(self, s: str) -> int:
if not s:
return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 0 if s[0] == '0' else 1
for i in range(2, n + 1):
one_digit = int(s[i-1:i])
two_digits = int(s[i-2:i])
if 1 <= one_digit <= 9:
dp[i] += dp[i-1]
if 10 <= two_digits <= 26:
dp[i] += dp[i-2]
return dp[-1]17. Implement Trie (Prefix Tree) [Trie, Data Structures, Python]
Implement a trie with insert, search, and startsWith methods.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word: str) -> bool:
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
def startsWith(self, prefix: str) -> bool:
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True18. Word Break [Dynamic Programming, Strings, Python]
Given a non-empty string s and a dictionary of words wordDict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in wordDict:
dp[i] = True
break
return dp[-1]19. Set Matrix Zeroes [Matrix, Arrays, Python]
Given an m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
rows, cols = len(matrix), len(matrix[0])
row_zero = False
for i in range(rows):
for j in range(cols):
if matrix[i][j] == 0:
matrix[0][j] = 0
if i > 0:
matrix[i][0] = 0
else:
row_zero = True
for i in range(1, rows):
for j in range(1, cols):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if matrix[0][0] == 0:
for i in range(rows):
matrix[i][0] = 0
if row_zero:
for j in range(cols):
matrix[0][j] = 020. Longest Consecutive Sequence [Union Find, Arrays, Python]
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if not nums:
return 0
nums_set = set(nums)
longest_streak = 0
for num in nums_set:
if num - 1 not in nums_set:
current_num = num
current_streak = 1
while current_num + 1 in nums_set:
current_num += 1
current_streak += 1
longest_streak = max(longest_streak, current_streak)
return longest_streak