Uber NG 2026高频面试题精讲：数组/树/图/链表全解析｜SDE面试刷题指南

Uber New Grad / SDE 面试全流程：简历筛选 → 在线测评 → 电话面试 → 两轮编码面试。核心考察：解题速度、边界处理、复杂度意识。

---

写在前面：Uber 面试到底在考察什么？

如果你正在准备 Uber 的 New Grad 或 SDE 技术面，首先需要理解一件事：Uber 的编码面试不考偏题，但极度看重你对时间复杂度的敏感度。面试官期望你在看到题目后的第一反应不是"能不能暴力"，而是"最优解是什么"，并且能清晰解释为什么这个解法是 O(n) 而不是 O(n²)。

本文基于 2025-2026 年大量真实面经整理，系统梳理 Uber 面试中反复出现的 LeetCode 高频题型，覆盖数组、树、图、链表、滑动窗口、单调栈、动态规划七大核心类别。每道题附代码实现与复杂度分析，并给出针对性的面试建议。

---

一、数组与双指针：Uber 最偏爱的入门赛道

Uber 对数组题的考察明显高于行业平均水平，且更倾向于进阶变体而非裸题。双指针是这一板块的核心工具。

LeetCode 15 — Three Sum

题目概述： 给定数组，找出所有不重复的三元组，使得三数之和为零。

解题思路： 先排序，外层遍历固定一个元素，内层使用双指针向中间逼近。去重是本题最容易丢分的地方。

def threeSum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    res = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        lo, hi = i + 1, len(nums) - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                res.append([nums[i], nums[lo], nums[hi]])
                while lo < hi and nums[lo] == nums[lo + 1]:
                    lo += 1
                while lo < hi and nums[hi] == nums[hi - 1]:
                    hi -= 1
                lo += 1
                hi -= 1
    return res

复杂度： 时间 O(n²)，空间 O(1)（不计结果存储和排序开销）。

LeetCode 16 — Three Sum Closest

题目概述： 在数组中找三个数，使其和最接近目标值。

解题思路： 与 LC 15 完全一致的双指针框架，只是用 min 维护差值最小值而非等于零的精确匹配。

def threeSumClosest(nums: list[int], target: int) -> int:
    nums.sort()
    best = float('inf')
    for i in range(len(nums) - 2):
        lo, hi = i + 1, len(nums) - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if abs(s - target) < abs(best - target):
                best = s
            if s < target:
                lo += 1
            else:
                hi -= 1
    return best

复杂度： 时间 O(n²)，空间 O(1)。

LeetCode 11 — Container With Most Water

题目概述： 在高度数组中选两根竖线，与 x 轴围成的面积最大。

解题思路： 从两端向中间收缩双指针。每次移动较短的那根——因为面积由短边和间距共同决定，移动长边不可能增大面积。这个单调性证明是面试官最爱追问的点。

def maxArea(height: list[int]) -> int:
    lo, hi = 0, len(height) - 1
    ans = 0
    while lo < hi:
        area = min(height[lo], height[hi]) * (hi - lo)
        ans = max(ans, area)
        if height[lo] < height[hi]:
            lo += 1
        else:
            hi -= 1
    return ans

复杂度： 时间 O(n)，空间 O(1)。

LeetCode 42 — Trapping Rain Water

题目概述： 给定高度图，计算能接住多少雨水。

解题思路： 双指针维护左右两侧的最大高度。当前位置的储水量等于 min(left_max, right_max) - height[i]。

def trap(height: list[int]) -> int:
    lo, hi = 0, len(height) - 1
    left_max, right_max = 0, 0
    ans = 0
    while lo < hi:
        if height[lo] < height[hi]:
            left_max = max(left_max, height[lo])
            ans += left_max - height[lo]
            lo += 1
        else:
            right_max = max(right_max, height[hi])
            ans += right_max - height[hi]
            hi -= 1
    return ans

复杂度： 时间 O(n)，空间 O(1)。

Uber 面试 Tips： 面试官对 O(n²) 解法非常敏感。如果 LC 11/42 你给出了暴力解，大概率会被直接追问"能否做到单次遍历"。在编码前花 30 秒口述复杂度思路，可以大幅加分。

---

二、树形结构与递归语义

树题在 Uber 面试中出现频率不算最高，但一旦出现，通常用来考察递归思维深度和对树结构的直觉把握。

LeetCode 236 — Lowest Common Ancestor of a Binary Tree

题目概述： 在二叉树中找到两个节点的最近公共祖先。

解题思路： 后序遍历。递归返回的含义是"在当前子树中是否找到 p 或 q"。当左右子树都返回非空时，当前节点就是 LCA。

def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root
    return left if left else right

复杂度： 时间 O(n)，空间 O(h)（递归栈）。

LeetCode 124 — Binary Tree Maximum Path Sum

题目概述： 找出一条路径，使路径上所有节点值之和最大。路径不必经过根。

解题思路： 区分"对父节点有用的最大单臂路径"和"全局最大路径"。前者只返回单边，后者取左+根+右的最大值。

def maxPathSum(root):
    best = [float('-inf')]
    def dfs(node):
        if not node:
            return 0
        left = max(dfs(node.left), 0)
        right = max(dfs(node.right), 0)
        best[0] = max(best[0], node.val + left + right)
        return node.val + max(left, right)
    dfs(root)
    return best[0]

复杂度： 时间 O(n)，空间 O(h)。

LeetCode 543 — Diameter of Binary Tree

题目概述： 计算二叉树中任意两节点间的最长路径（边的数量）。

def diameterOfBinaryTree(root):
    best = [0]
    def depth(node):
        if not node:
            return 0
        l, r = depth(node.left), depth(node.right)
        best[0] = max(best[0], l + r)
        return 1 + max(l, r)
    depth(root)
    return best[0]

复杂度： 时间 O(n)，空间 O(h)。

LeetCode 199 — Binary Tree Right Side View

题目概述： 从右侧观察二叉树，返回能看到的节点值列表。

解题思路： BFS 层序遍历，每层取最后一个节点。

from collections import deque

def rightSideView(root):
    if not root:
        return []
    res, q = [], deque([root])
    while q:
        res.append(q[-1].val)
        q = deque(child for n in q
                   for child in (n.left, n.right) if child)
    return res

复杂度： 时间 O(n)，空间 O(n)。

Uber 面试 Tips： Uber 面试官非常喜欢追问递归返回值的具体含义。在讲解 LC 236/124 时，务必口述清楚"这个 return 代表什么、父节点用它做了什么"——这直接决定了面试官对你递归功底的评价。

---

三、图论与网格遍历

Uber 的图题几乎不会抽象出题，而是包装成二维网格或实际业务场景。BFS 和 DFS 是两大核心武器。

LeetCode 200 — Number of Islands

题目概述： 计算二维字符网格中岛屿（'1' 连通的区域）数量。

解题思路： 遍历每个格子，遇到 '1' 就启动 DFS/BFS 将其连通区域全部标记，计数器 +1。

def numIslands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    def dfs(r, c):
        if 0 <= r < rows and 0 <= c < cols and grid[r][c] == '1':
            grid[r][c] = '0'
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                dfs(r + dr, c + dc)
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1
    return count

复杂度： 时间 O(rows × cols)，空间 O(rows × cols)（递归栈）。

LeetCode 695 — Max Area of Island

题目概述： 与 LC 200 类似，但要求最大岛屿面积而非数量。

解题思路： 框架相同，DFS 返回值从 void 改为 int（当前连通区域大小）。

def maxAreaOfIsland(grid):
    rows, cols = len(grid), len(grid[0])
    def dfs(r, c):
        if 0 <= r < rows and 0 <= c < cols and grid[r][c] == 1:
            grid[r][c] = 0
            return 1 + sum(dfs(r+dr, c+dc) for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)))
        return 0
    return max(dfs(r, c) for r in range(rows) for c in range(cols))

复杂度： 时间 O(rows × cols)，空间 O(rows × cols)。

LeetCode 994 — Rotting Oranges

题目概述： 每分钟腐烂的橘子会感染相邻新鲜橘子，求最短时间。

解题思路： 多源 BFS。初始将所有腐烂橘子入队，每轮扩展一层代表一分钟。

from collections import deque

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    q = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                q.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while q and fresh:
        for _ in range(len(q)):
            r, c = q.popleft()
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    q.append((nr, nc))
                    fresh -= 1
        minutes += 1
    return minutes if fresh == 0 else -1

复杂度： 时间 O(rows × cols)，空间 O(rows × cols)。

LeetCode 286 — Walls and Gates

题目概述： 填充每个空房间到最近门的距离。

解题思路： 多源 BFS 的另一个经典变体。从所有门同时出发，逐层扩散。

def wallsAndGates(rooms):
    if not rooms:
        return
    rows, cols = len(rooms), len(rooms[0])
    q = deque((r, c) for r in range(rows) for c in range(cols) if rooms[r][c] == 0)
    while q:
        r, c = q.popleft()
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols
                and rooms[nr][nc] == float('inf')):
                rooms[nr][nc] = rooms[r][c] + 1
                q.append((nr, nc))

复杂度： 时间 O(rows × cols)，空间 O(rows × cols)。

Uber 面试 Tips： Uber 的图题 follow-up 很常见。LC 200 被追问成"最大岛屿面积"或"岛屿周长"的概率极高。面试中务必在解决主问题后主动问一句"是否考虑过 follow-up"，这体现了你对复杂度的前瞻性。visited 处理是否合理也是面试官重点检查的对象。

---

四、链表操作

链表题在 Uber 面试中出现频率中等，但一旦考查，通常围绕指针操作的正确性和空间复杂度展开。以下四道题代表了核心考点。

LeetCode 2 — Add Two Numbers

题目概述： 两个逆序存储的非负整数链表，返回它们的和（也是逆序链表）。

解题思路： 双指针同步遍历，维护进位 carry。注意处理最后进位和多长度差异。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(l1, l2):
    dummy = ListNode()
    cur, carry = dummy, 0
    while l1 or l2 or carry:
        s = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
        carry = s // 10
        cur.next = ListNode(s % 10)
        cur = cur.next
        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None
    return dummy.next

复杂度： 时间 O(max(m, n))，空间 O(max(m, n))。

LeetCode 19 — Remove Nth Node From End of List

题目概述： 删除链表的倒数第 n 个节点。

解题思路： 快慢指针。快指针先走 n 步，然后同步移动，慢指针到达目标前驱时删除。

def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)
    slow = fast = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next:
        slow = slow.next
        fast = fast.next
    slow.next = slow.next.next
    return dummy.next

复杂度： 时间 O(n)，空间 O(1)。

LeetCode 25 — Reverse Nodes in k-Group

题目概述： 每 k 个节点一组反转链表，不足 k 个的保持原样。

解题思路： 先检查剩余节点是否足够 k 个，不够则直接返回；否则反转一段并递归/迭代处理后续。

def reverseKGroup(head, k):
    dummy = ListNode(0, head)
    prev = dummy
    while True:
        tail = prev
        for _ in range(k):
            tail = tail.next
            if not tail:
                return dummy.next
        # reverse from prev.next to tail
        first = prev.next
        curr = first.next
        for _ in range(k - 1):
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        first.next = curr
        nxt = prev
        prev = first
        first = nxt

复杂度： 时间 O(n)，空间 O(1)。

LeetCode 148 — Sort List

题目概述： O(n log n) 时间复杂度内排序链表。

解题思路： 归并排序——快慢指针找中点分割，递归排序后合并。

def sortList(head):
    if not head or not head.next:
        return head
    # slow-fast to find midpoint
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None
    left, right = sortList(head), sortList(mid)
    # merge
    dummy = ListNode()
    cur = dummy
    while left and right:
        if left.val < right.val:
            cur.next, left = left, left.next
        else:
            cur.next, right = right, right.next
        cur = cur.next
    cur.next = left or right
    return dummy.next

复杂度： 时间 O(n log n)，空间 O(log n)（递归栈）。

Uber 面试 Tips： 链表题的难点在于边界条件（空链表、单节点、k 不整除等）。面试时建议使用 dummy 节点统一处理头节点边界——这体现了工程素养。Uber 面试官会仔细检查你的指针操作是否有内存泄漏风险。

---

五、滑动窗口与字符串处理

八大算法类别及其对应的 LeetCode 高频题号一览。

LeetCode 3 — Longest Substring Without Repeating Characters

解题思路： 用哈希表记录每个字符最后出现的位置，滑动窗口的左边界由重复字符决定。

def lengthOfLongestSubstring(s: str) -> int:
    char_pos = {}
    left = ans = 0
    for right, ch in enumerate(s):
        if ch in char_pos and char_pos[ch] >= left:
            left = char_pos[ch] + 1
        char_pos[ch] = right
        ans = max(ans, right - left + 1)
    return ans

复杂度： 时间 O(n)，空间 O(min(n, 字符集大小))。

LeetCode 76 — Minimum Window Substring

解题思路： 经典滑动窗口。用计数器维护窗口内是否满足 t 中所有字符需求，满足时尝试收缩左边界。

def minWindow(s: str, t: str) -> str:
    from collections import Counter
    need = Counter(t)
    have, formed = {}, 0
    left = 0
    ans = float('inf'), None, None
    for right, ch in enumerate(s):
        have[ch] = have.get(ch, 0) + 1
        if ch in need and have[ch] == need[ch]:
            formed += 1
        while formed == len(need):
            if right - left + 1 < ans[0]:
                ans = (right - left + 1, left, right)
            have[s[left]] -= 1
            if s[left] in need and have[s[left]] < need[s[left]]:
                formed -= 1
            left += 1
    return s[ans[1]:ans[2]+1] if ans[0] != float('inf') else ""

复杂度： 时间 O(n + m)，空间 O(字符集大小)。

Uber 面试 Tips： Uber 面试官不会只看你"能不能跑通"，还会检查窗口收缩的触发条件是否精确。如果你在面试中机械地套用模板但无法解释为什么收缩时机是正确的，大概率会被追问到露馅。

---

六、HashMap 与前缀和

LeetCode 560 — Subarray Sum Equals K

解题思路： 前缀和 + 哈希表。记录每个前缀和出现的次数，当 prefix_sum - k 在表中存在时，说明有一段子数组和为 k。

def subarraySum(nums: list[int], k: int) -> int:
    count = {0: 1}
    prefix, ans = 0, 0
    for num in nums:
        prefix += num
        ans += count.get(prefix - k, 0)
        count[prefix] = count.get(prefix, 0) + 1
    return ans

复杂度： 时间 O(n)，空间 O(n)。

LeetCode 525 — Contiguous Array

解题思路： 将 0 替换为 -1 后转化为"找和为零的最长子数组"，与 LC 560 同构。

def findMaxLength(nums: list[int]) -> int:
    first_occurrence = {0: -1}
    balance, ans = 0, 0
    for i, num in enumerate(nums):
        balance += 1 if num == 1 else -1
        if balance in first_occurrence:
            ans = max(ans, i - first_occurrence[balance])
        else:
            first_occurrence[balance] = i
    return ans

复杂度： 时间 O(n)，空间 O(n)。

LeetCode 128 — Longest Consecutive Sequence

解题思路： 用集合存储所有元素，只从每个连续序列的最小值开始扩展。

def longestConsecutive(nums: list[int]) -> int:
    s = set(nums)
    ans = 0
    for n in s:
        if n - 1 not in s:  # only start from the smallest
            curr = 1
            while n + 1 in s:
                n += 1
                curr += 1
            ans = max(ans, curr)
    return ans

复杂度： 时间 O(n)（每个元素最多被访问两次），空间 O(n)。

LeetCode 347 — Top K Frequent Elements

import heapq
from collections import Counter

def topKFrequent(nums: list[int], k: int) -> list[int]:
    return [item for item, _ in heapq.nlargest(k, Counter(nums).items(), key=lambda x: x[1])]

复杂度： 时间 O(n log k)，空间 O(n)。

Uber 面试 Tips： Uber 面试官非常看重你"能否自然想到前缀和 + HashMap"而不是暴力枚举。在 LC 560 上如果你先给出 O(n²) 解法，面试官通常会直接提示"能不能 O(n)"，然后观察你是否有思路转向。

---

七、单调栈与括号匹配

LeetCode 739 — Daily Temperatures

解题思路： 单调递减栈，维护待匹配更高温度的索引。

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    stack, ans = [], [0] * len(temperatures)
    for i, t in enumerate(temperatures):
        while stack and t > temperatures[stack[-1]]:
            j = stack.pop()
            ans[j] = i - j
        stack.append(i)
    return ans

复杂度： 时间 O(n)，空间 O(n)。

LeetCode 84 — Largest Rectangle in Histogram

解题思路： 对每个柱子，找左边第一个比它矮的和右边第一个比它矮的，这就是它能延伸的最大宽度。单调栈一次遍历完成。

def largestRectangleArea(heights: list[int]) -> int:
    stack = [-1]
    ans = 0
    for i, h in enumerate(heights):
        while stack[-1] != -1 and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            width = i - stack[-1] - 1
            ans = max(ans, height * width)
        stack.append(i)
    for i in range(len(heights)):
        while stack[-1] != -1 and heights[stack[-1]] >= 0:
            height = heights[stack.pop()]
            width = len(heights) - stack[-1] - 1
            ans = max(ans, height * width)
    return ans

复杂度： 时间 O(n)，空间 O(n)。

Uber 面试 Tips： Uber 对单调栈的接受度高于多数公司。LC 84 在 Senior 或表现优秀的 NG 面试中并不罕见。能写出思路清晰的单调栈解法会留下深刻印象。

---

八、动态规划

LeetCode 53 — Maximum Subarray

解题思路： Kadane 算法，O(n) 一次遍历。

def maxSubArray(nums: list[int]) -> int:
    cur = best = nums[0]
    for n in nums[1:]:
        cur = max(n, cur + n)
        best = max(best, cur)
    return best

复杂度： 时间 O(n)，空间 O(1)。

LeetCode 198 — House Robber

def rob(nums: list[int]) -> int:
    prev2, prev1 = 0, 0
    for n in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + n)
    return prev1

复杂度： 时间 O(n)，空间 O(1)。

LeetCode 300 — Longest Increasing Subsequence

解题思路： 维护一个有序数组 tails，每个位置表示长度为 i 的递增子序列的最小尾元素。用二分查找优化到 O(n log n)。

import bisect

def lengthOfLIS(nums: list[int]) -> int:
    tails = []
    for n in nums:
        idx = bisect.bisect_left(tails, n)
        if idx < len(tails):
            tails[idx] = n
        else:
            tails.append(n)
    return len(tails)

复杂度： 时间 O(n log n)，空间 O(n)。

LeetCode 322 — Coin Change

def coinChange(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if i >= c:
                dp[i] = min(dp[i], dp[i - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

复杂度： 时间 O(amount × len(coins))，空间 O(amount)。

Uber 面试 Tips： Uber 的 DP 题通常不会特别深（偏一维或简单二维），但面试官非常关注状态转移方程的推导过程。在面试中务必边写边解释：dp[i] 代表什么、转移方程怎么来的、初始条件是什么。

---

九、Uber 面试实战策略总结

经过对 2025-2026 年大量面经的系统分析，以下是备战 Uber 技术面试的核心策略：

1. 复杂度意识是第一优先级

Uber 面试官对时间复杂度极其敏感。在编码前花 30-60 秒口述你的复杂度分析，说明为什么选择这个算法而非暴力解法。能主动区分 O(n) 和 O(n log n) 场景的候选人，在 Uber 的评价体系中优势明显。

2. 边界条件先想清楚

在写第一行代码前，先讨论边界情况：空输入、单元素、全相同元素、极大值/极小值。Uber 的工程文化强调"先考虑失败模式"。

3. Follow-up 准备

Uber 面试官喜欢在解决主问题后抛 follow-up。常见模式包括：

• LC 200（岛屿数量）→ LC 695（最大岛屿面积）→ 岛屿周长
• LC 128（最长连续序列）→ 允许删除 k 个元素后求最长
• LC 300（LIS）→ 从 O(n²) 追问到 O(n log n)

4. 代码整洁度

Uber 重视代码可读性。使用有意义的变量名、合理的函数拆分、清晰的注释。避免在面试中写出"能跑就行"的代码——Uber 的工程标准远高于此。

5. 主动沟通

遇到不确定的题目，主动与面试官讨论比沉默思考更有价值。Uber 面试官愿意给提示，关键是你是否展现出协作和问题拆解的能力。

---

高频题目速查表

类别	LeetCode 题号	难度	核心考点
数组/双指针	15, 16, 11, 42	中-难	排序+双指针、单调性证明
字符串/滑动窗口	3, 76, 567, 424	中	窗口状态维护、收缩条件
HashMap/前缀和	560, 525, 128, 347	中	前缀和转化、哈希优化
图/BFS/DFS	200, 695, 994, 286	中	网格遍历、多源BFS、visited
树/递归	236, 124, 543, 199	中-难	递归语义、层序遍历
单调栈	20, 739, 84	易-难	单调性、历史极值
动态规划	53, 198, 300, 322	易-中	状态转移、空间优化
链表	2, 19, 25, 148	中-难	指针操作、dummy节点、归并

---

需要更专业的面试辅导？

如果你希望获得一对一的 Uber 面试模拟、代码 Review、或者针对特定岗位的准备方案，欢迎联系我们的面试辅助团队。

👉 立即预约免费咨询

我们提供：

• 1v1 模拟编码面试（真实面试官水平）
• 代码逐行 Review 与优化建议
• 个性化刷题路径规划
• 行为面试（Behavioral）辅导
• 薪资谈判指导

点击这里开始，我们的团队会第一时间与你取得联系。

---

本文内容基于 2025-2026 年大量真实面试经验整理。LeetCode 题号以官方编号为准。面试题目随时可能变化，请以最新面经为准。

© 2026 interview-help.live — 专业 SDE 面试辅助平台