AI-Agent 面试题汇总 - 数据结构与算法篇

一、背景知识

1. Python 数据结构

Python常见内置数据结构有：list、tuple、dict、set、str。面试重点通常是时间复杂度和应用场景：

list：动态数组，支持随机访问，尾部增删快，头部插入删除慢
tuple：不可变序列，适合只读数据，哈希友好
dict：哈希表实现，键查找/插入平均O(1)
set：不重复集合，去重和成员判断高效（平均O(1)）
str：不可变字符串，切片会创建新对象

# 常见复杂度示例
arr = [1, 2, 3]
arr.append(4)        # 平均 O(1)
arr.insert(0, 0)     # O(n)

d = {"a": 1}
print(d.get("a"))    # 平均 O(1)

s = set([1, 2, 2, 3])
print(s)             # {1,2,3}

2. 插件（这里可理解为算法刷题环境插件/工具链）

在算法面试准备中，“插件”通常指提升编码效率与调试质量的工具：

编辑器插件（代码补全、语法检查、格式化）
单元测试插件（快速验证边界case）
复杂度分析/性能分析工具
可视化调试工具（断点、变量追踪）

核心价值是降低低级错误，提高编码和验证效率。

二、热身

1. 两数之和（LeetCode 1）

概念：给定数组和目标值，返回和为目标值的两个下标。最优思路是哈希表：遍历当前值 x，检查 target-x 是否已出现。时间复杂度 O(n)，空间复杂度 O(n)。

def two_sum(nums, target):
    mp = {}
    for i, x in enumerate(nums):
        if target - x in mp:
            return [mp[target - x], i]
        mp[x] = i
    return []

三、排序

1. 经典排序

常见排序算法与复杂度（平均）：

冒泡/选择/插入：O(n²)
快速排序：O(nlogn)（最坏O(n²)）
归并排序：O(nlogn)，稳定，需额外空间
堆排序：O(nlogn)，原地，非稳定

面试高频关注：1）快排分区思想2）归并“分治+合并”3）稳定性与应用场景

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2]
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + mid + quick_sort(right)

2. 148. 排序链表

概念：链表排序要求 O(nlogn) 时间，通常用归并排序（快排不适合链表随机访问差）。步骤：快慢指针找中点 -> 递归排序左右链表 -> 合并有序链表。

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

def merge(a, b):
    dummy = cur = ListNode()
    while a and b:
        if a.val < b.val:
            cur.next, a = a, a.next
        else:
            cur.next, b = b, b.next
        cur = cur.next
    cur.next = a or b
    return dummy.next

def sortList(head):
    if not head or not head.next:
        return head
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None
    left = sortList(head)
    right = sortList(mid)
    return merge(left, right)

四、滑动窗口算法

1. 3. 无重复字符的最长子串

窗口维护“当前无重复子串”，右指针扩展，重复时左指针收缩。时间复杂度 O(n)。

def lengthOfLongestSubstring(s):
    st, l, ans = set(), 0, 0
    for r, ch in enumerate(s):
        while ch in st:
            st.remove(s[l]); l += 1
        st.add(ch)
        ans = max(ans, r - l + 1)
    return ans

2. 76. 最小覆盖子串

核心是“可行窗口 + 尽量收缩”：右侧扩张满足覆盖条件后，左侧不断收缩直到刚好不满足，再继续扩张。典型哈希计数 + need/have 控制。

from collections import Counter

def minWindow(s, t):
    need = Counter(t)
    missing = len(t)
    l = start = end = 0
    for r, ch in enumerate(s, 1):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        if missing == 0:
            while l < r and need[s[l]] < 0:
                need[s[l]] += 1
                l += 1
            if end == 0 or r - l < end - start:
                start, end = l, r
            need[s[l]] += 1
            missing += 1
            l += 1
    return s[start:end]

3. 438. 找到字符串中所有字母异位词

固定长度窗口（长度=len(p)）+ 频次比较。可用数组计数优化为 O(n)。

def findAnagrams(s, p):
    if len(p) > len(s): return []
    res = []
    cnt_p = [0]*26
    cnt_w = [0]*26
    for ch in p:
        cnt_p[ord(ch)-97] += 1
    for i, ch in enumerate(s):
        cnt_w[ord(ch)-97] += 1
        if i >= len(p):
            cnt_w[ord(s[i-len(p)])-97] -= 1
        if cnt_w == cnt_p:
            res.append(i-len(p)+1)
    return res