Featured image of post 面向外企就业的 LeetCode/NeetCode 记录
techStudy

面向外企就业的 LeetCode/NeetCode 记录

记录面向外企的 LeetCode/NeetCode 刷题题单、内容、解法、总结与反思，持续更新中

LeetCode 刷题方法

路线图

算法清单

外企基石，必须闭眼手撕：

  • 哈希表
  • 双指针
  • 滑动窗口
  • 二分查找
  • 链表
  • 二叉树（含二叉搜索树 BST）

工程进阶，拉开差距的关键：

  • 回溯算法（排列/组合/子集）
  • 堆/优先队列
  • 栈与队列
  • 图论基础（仅限 BFS / DFS / 拓扑排序）

高级护城河，面试冲刺期再看：

  • 动态规划（仅限 1D DP 和基础背包/最长公共子序列）
  • 字典树 (Trie)
  • 并查集 (Union-Find)
  • 前缀和技巧

题单

设计模式

1. 单例模式 (Singleton) —— C++ 面试必考八股

  • 这是什么：保证一个类只有一个实例，并提供一个全局访问点。
  • 外企考点：不仅会让你手写，还会结合 C++ 问你“线程安全的单例怎么写？”（Meyers Singleton，利用局部静态变量的特性）。
  • 如何融合进你的项目：你的 GPU 监控探针（Agent）运行在 5090 服务器上，它需要读取配置信息（比如本机的 IP、监控频率）。这个 ConfigManager 配置管理器，就必须是一个单例。你在简历上面试时可以说：“为了避免多次读取配置文件造成 I/O 浪费，我用 C++11 的 std::call_once（或局部静态变量）实现了一个线程安全的单例配置中心。”

2. 观察者模式 (Observer) —— 监控系统的灵魂

  • 这是什么：一个对象状态改变，所有依赖它的对象都会收到通知。（也就是发布-订阅机制）。
  • 外企考点：解耦。面试官常问：“如果我加一个新的监控维度，你的代码需要大改吗？”
  • 如何融合进你的项目：你的 5070 Ti 是一直在变化的（温度忽高忽低，显存忽大忽小）。你可以把本地的显卡作为一个 Subject（被观察者），把负责发送网络请求的模块、负责写本地日志的模块作为 Observer（观察者）。显存一旦超过阈值，主动“通知”这些模块报警，而不是让它们写个 while(true) 死循环去轮询。

3. 工厂模式 (Factory) —— 告别满屏的 if-else

  • 这是什么：把创建对象的具体逻辑隐藏起来，提供一个统一的接口。
  • 外企考点：考察你对开闭原则（对扩展开放，对修改封闭）的理解。
  • 如何融合进你的项目：你的调度系统未来不仅能收集 5090 的数据，可能还要收集 AMD 显卡，甚至普通 CPU 的数据。写一个 DeviceFactory，传入 “NVIDIA”，它就吐出一个调用 NVML API 的对象；传入 “CPU”，它就吐出一个读取 /proc/cpuinfo 的对象。

4. 策略模式 (Strategy) —— 调度系统的核心

  • 这是什么：定义一系列算法，把它们一个个封装起来，并且使它们可相互替换。
  • 外企考点：极其高频的设计题。比如“设计一个打车软件的计费模块”。
  • 如何融合进你的项目：你的核心是算力调度。怎么调度？你可以有“轮询策略（Round Robin）”、“最低显存优先策略（Least Loaded）”。把这些策略抽象成接口，运行时动态插拔。这就是顶级的基础设施架构。

刷题记录

NeetCode Roadmap

Contains Duplicate (LeetCode 217)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# 最经典的哈希表题。用一个 Set 来记录我们见过的数字，一边遍历一边查这个数字在不在 Set 里。
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen = set() # 创建一个空的哈希集合
        
        for num in nums:
            if num in seen:  # 查字典：这个数字我之前见过吗？
                return True  # 见过！直接返回 True
            seen.add(num)    # 没见过，把它记在小本本上
            
        return False # 全都查完了也没重复，返回 False

1
2
3
4

# Pythonic 的一行解法，利用 set() 去重特性，直接比较原数组长度和去重后 Set 的长度。
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(nums) != len(set(nums))
time/space complexity
  • time complexity: $O(n)$
  • space complexity: $O(n)$
  • 如果你的数组非常大，且重复元素大概率出现在很靠前的位置，解法 1 更优，因为它能“及时止损”。
  • 如果你的数组没有重复元素，或者重复元素在最后面，解法 2 更优，因为底层 C 语言的执行速度会碾压 Python 的 for 循环。
summary:
  1. 时间复杂度 (Time Complexity)
  • $O(1)$ 常数级：终极目标。代码特征：直接通过索引取值 nums[0]，或者在字典/集合中查值 if key in my_dict:。
  • $O(\log n)$ 对数级：极快。代码特征：二分查找。每次操作砍掉一半（如 while left < right: 配合 mid）。
  • $O(n)$ 线性级：外企最爱的标准解法。代码特征：一层无嵌套的 for 循环，从头到尾扫一遍。
  • $O(n \log n)$：通常是排序的极限。代码特征：代码里调用了 nums.sort()，或者用了归并/快速排序。
  • $O(n^2)$ 平方级：面试危险信号。代码特征：两层嵌套的 for 循环。面试官通常会让你把它优化到 $O(n)$。
  1. 空间复杂度 (Space Complexity)
  • $O(1)$：只新建了几个变量（如双指针 left, right），没有开辟随数据规模增大的新空间。
  • $O(n)$：新建了一个和原数组一样大的字典（哈希表）、集合（Set）或新数组。外企极度喜欢用空间换时间。
  1. Hash (Dict / Set) 用法速查

底层皆为哈希表，查找/插入的时间复杂度均摊为 $O(1)$。

  • dict (字典)：存键值对。

  • 初始化：d = {}

  • 增/改：d[key] = value

  • 查：if key in d:

  • set (集合)：存无序不重复元素。

  • 初始化：s = set()

  • 增：s.add(value)

  • 查：if value in s:

  1. Pythonic 循环

抛弃 for(int i=0; i<n; i++)，只记以下三种：

  • 只取值：for num in nums:
  • 只取索引：for i in range(len(nums)):
  • 既要索引又要值：for i, num in enumerate(nums):
  1. 核心标准库 (绝不重复造轮子)
  • collections.Counter (计数器)
  • 场景：完成词频/元素频率统计。直接替代 count[i] = count[i] + 1 循环。
  • 用法：
1
2

from collections import Counter
count = Counter(nums)
  • collections.deque (双端队列)
  • 场景：做 BFS（广度优先搜索）必用。两头增删都是 $O(1)$，绝不用普通 list 做队列。
  • 用法：
1
2
3
4

from collections import deque
q = deque([1, 2])
q.append(3)      # 尾部进队
q.popleft()      # 头部出队
  • heapq (优先队列 / 堆)
  • 场景：解决 “Top K” (前K个最大/最小) 问题。替代 C++ 的 std::priority_queue。
  • 用法：
1
2
3
4

import heapq
heapq.heapify(nums)      # $O(n)$ 原地建堆
heapq.heappush(nums, 2)  # 压入元素
val = heapq.heappop(nums) # 弹出最小值

words list

  • integer 整数
  • distinct 不同的
  • duplicate 重复的
  • constraint 约束条件
  • approach 方法
  • time/space complexity 时间/空间复杂度

tips

1. 语言与阵地

  • 语言死绑 Python：追求极简 API 和开发速度，避开 C++ 繁琐的模板代码。
  • 平台死绑美区：只在 LeetCode.com 刷，强迫适应全英文题目与约束条件。

2. 路线与开销

  • 唯一指定路线：只刷 NeetCode Roadmap。打通它 = 自动通关 Blind 75 + NeetCode 150。
  • 绝不打周赛：外企不考竞赛级偏门题，别浪费周末断联日。
  • 零氪金原则：绝不买 $297 NeetCode Premium。只在收到面试通知的前一个月，买 $35 LeetCode 官方会员突击公司专属题库 (Company Tags)。

3. 核心刷题 SOP (15分钟法则)

  • Step 1 (闭卷 15 分钟)：拿到题自己想，没思路或写不出立刻停手，绝生死磕。
  • Step 2 (开卷偷师)：看 NeetCode 免费视频，学 Python 模板和英文思路 (Think Out Loud)。
  • Step 3 (半闭卷手敲)：关掉视频，凭记忆自己敲到 AC。允许随时查 Python API（如字典操作、内置函数），现阶段不要为默写语法浪费时间。

4. 兜底退路与国内大厂补丁 (Pivot 方案)

  • 唯一需要加练的（考前 1 个月突击）：外企不考中间件的死记硬背。但如果在 2027 年春招/秋招前决定转面国内互联网业务岗，需额外花 1个月 狂背“国产特色八股文”：MySQL 底层（B+树索引）、Redis（缓存穿透/雪崩）、以及各类高并发锁机制。 仅作为临时补丁，勿在日常备战中分散精力。

5. NeetCode 的正确打开方式

NeetCode 的 Visualize the algorithm step by step 功能非常便于理解算法流程，至少对我来说，可视化地过一遍算法流程，就很清晰了。

链接

© 2023 - 2026 李寒的小窝
潇洒人间一键仙
使用 Hugo 构建
主题 Stack 由 Jimmy 设计