Uber 优步 面经整理合集 Part 1| uber面经 uber面试辅助 面试代面 面试辅导 oa辅导 vo辅导
Uber 面经整理合集 Part 1
想获取更多的服务 请添加微信 leetcode-king 或者扫码
1. Create Tree [Tree, Data Structures, Python]
class Node:
def __init__(self, value):
self.value = value
self.children = []
def count_total_nodes(root):
if not root:
return 0
return 1 + sum(count_total_nodes(child) for child in root.children)
def create_tree(values, connections):
nodes = [Node(val) for val in values]
for parent, child in connections:
nodes[parent].children.append(nodes[child])
return nodes[0]
# Test case: Simple tree
# 1
# /|\
# 2 3 4
root1 = create_tree([1, 2, 3, 4], [(0, 1), (0, 2), (0, 3)])2. Finding Robot Location [Algorithm, 2D Array, Python]
Given a 2D grid with a robot ('O'), empty spaces ('E'), and blockers ('X'), determine the location of the robot based on the distances to the nearest blockers in the four directions (left, top, bottom, right).
from collections import defaultdict
def solution(grid, info):
record = defaultdict(list)
row, column = len(grid), len(grid[0])
top, left = [-1]*column, -1
for i in range(row):
left = -1
for j in range(column):
if grid[i][j] == 'O':
record[(i, j)] = [j-left, i-top[j], None, None]
elif grid[i][j] == 'X':
top[j] = i
left = j
bottom, right = [row]*column, column
for i in range(row-1, -1, -1):
right = column
for j in range(column-1, -1, -1):
if grid[i][j] == 'O':
record[(i, j)][2] = bottom[j] - i
record[(i, j)][3] = right - j
if record[(i,j)] == info:
return [i, j]
elif grid[i][j] == 'X':
bottom[j] = i
right = j
return -13. Leftmost Column with at Least a One [Binary Matrix, Search, Python]
You are given a row-sorted binary matrix. Return the index of the leftmost column with at least one 1. If such an index doesn't exist, return -1.
class Solution:
def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
row, col = binaryMatrix.dimensions()
result = float('inf')
for i in range(row):
left, right = 0, col - 1
while left <= right:
middle = (left + right) // 2
if binaryMatrix.get(i, middle) == 0:
left = middle + 1
else:
right = middle - 1
result = min(result, left)
return -1 if result == col else result4. Bus Routes [Graphs, BFS, Python]
Given bus routes, find the minimum number of buses required to reach the target stop from the source stop. If it is impossible to reach the target, return -1.
class Solution:
def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
if source == target:
return 0
maxStop = 0
for route in routes:
maxStop = max(maxStop, max(route))
if target > maxStop or source > maxStop:
return -1
maxStop += 1
record = [float('inf')] * maxStop
record[source] = 0
change = True
while change:
change = False
for route in routes:
stopSmallest = float('inf')
for stop in route:
stopSmallest = min(stopSmallest, record[stop])
stopSmallest += 1
for stop in route:
if record[stop] > stopSmallest:
change = True
record[stop] = stopSmallest
return record[target] if record[target] != float('inf') else -15. Construct Quad Tree [Quad-Tree, Recursion, Python]
Given an n x n binary matrix grid, represent grid using a Quad-Tree.
class Node:
def __init__(self, val, isLeaf, topLeft=None, topRight=None, bottomLeft=None, bottomRight=None):
self.val = val
self.isLeaf = isLeaf
self.topLeft = topLeft
self.topRight = topRight
self.bottomLeft = bottomLeft
self.bottomRight = bottomRight
class Solution:
def construct(self, grid: List[List[int]]) -> Node:
return self.helper(grid, 0, 0, len(grid))
def helper(self, grid, i, j, w):
if self.allSame(grid, i, j, w):
return Node(grid[i][j] == 1, True)
node = Node(True, False)
node.topLeft = self.helper(grid, i, j, w // 2)
node.topRight = self.helper(grid, i, j + w // 2, w // 2)
node.bottomLeft = self.helper(grid, i + w // 2, j, w // 2)
node.bottomRight = self.helper(grid, i + w // 2, j + w // 2, w // 2)
return node
def allSame(self, grid, i, j, w):
for x in range(i, i + w):
for y in range(j, j + w):
if grid[x][y] != grid[i][j]:
return False
return True6. Minimum Insertion Steps to Make a String Palindrome [Dynamic Programming, Strings, Python]
Given a string s, return the minimum number of steps to make s a palindrome by inserting characters anywhere in the string.
class Solution:
def minInsertions(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1]
else:
dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1
return dp[0][n - 1]7. Word Ladder [Graphs, BFS, Python]
Given two words, beginWord and endWord, and a dictionary of words, return the length of the shortest transformation sequence from beginWord to endWord such that:
- Only one letter can be changed at a time.
- Each transformed word must exist in the word list.
from collections import deque
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0
wordList = set(wordList)
queue = deque([(beginWord, 1)])
while queue:
current_word, level = queue.popleft()
if current_word == endWord:
return level
for i in range(len(current_word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
next_word = current_word[:i] + c + current_word[i+1:]
if next_word in wordList:
wordList.remove(next_word)
queue.append((next_word, level + 1))
return 08. Merge Intervals [Sorting, Intervals, Python]
Given a collection of intervals, merge all overlapping intervals.
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])
return merged9. Binary Tree Maximum Path Sum [Trees, DFS, Python]
Given a non-empty binary tree, find the maximum path sum. A path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
def dfs(node):
if not node:
return 0
left_max = max(dfs(node.left), 0)
right_max = max(dfs(node.right), 0)
current_max = node.val + left_max + right_max
self.global_max = max(self.global_max, current_max)
return node.val + max(left_max, right_max)
self.global_max = float('-inf')
dfs(root)
return self.global_max10. Word Search [Backtracking, DFS, Python]
Given an m x n board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are those horizontally or vertically neighboring.
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def dfs(board, word, i, j, count):
if count == len(word):
return True
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[count]:
return False
temp = board[i][j]
board[i][j] = ''
found = dfs(board, word, i + 1, j, count + 1) or \
dfs(board, word, i - 1, j, count + 1) or \
dfs(board, word, i, j + 1, count + 1) or \
dfs(board, word, i, j - 1, count + 1)
board[i][j] = temp
return found
for i in range(len(board)):
for j in range(len(board[0])):
if dfs(board, word, i, j, 0):
return True
return False