Career Prep 2027

Appearance

Set / Map ​

目标：面向秋招算法题，能够根据“是否只需要存在性”与“是否需要附加状态”快速选择 Set 或 Map，并能设计 Map 的 key/value。

一句话理解 ​

text
Set
→ 只关心 key 是否存在
→ membership

Map
→ key → value
→ 除了存在性，还需要保存与 key 关联的状态

常见语言对应：

text
Python: set / dict
Java: HashSet / HashMap
C++: unordered_set / unordered_map

Set / Map 更接近使用层面的抽象；Hash Table 是它们非常常见的底层实现。

Set 高频模式 ​

适合：

  • 去重；
  • 判断是否出现过；
  • 判断是否重复；
  • 判断两个集合是否存在交集；
  • DFS/BFS 中的 visited。

标准问题：

“这个元素以前有没有出现过？”

示例：判断数组是否存在重复元素。

python
seen = set()

for x in nums:
    if x in seen:
        return True
    seen.add(x)

return False

平均时间复杂度：

text
O(n)

额外空间：

text
O(n)

Map 高频模式 ​

Map 适合保存：

text
元素 → 出现次数
元素 → 下标
元素 → 最近位置
类别 → 对象列表
对象 → 状态

设计 Map 时优先问两个问题：

text
未来我要通过谁来查询？
→ key

查询以后还需要得到什么？
→ value

即：

key = 查询对象；value = 与该对象关联、未来真正需要的状态。

Frequency Counting ​

python
count = {}

for x in nums:
    count[x] = count.get(x, 0) + 1

此时：

text
key   = 元素
value = 出现次数

count.get(x, 0) 表示：若 x 已存在则读取当前计数，否则使用默认值 0。

Position / Latest State ​

如果题目需要“最后一次出现的位置”：

python
last = {}

for i, x in enumerate(nums):
    last[x] = i

保存：

text
元素 → 最近下标

Map 不需要保存全部历史，只保存未来解题真正需要的状态。

这是一个重要原则：

不保存所有发生过的事情，只保存未来查询所需要的最小状态。

One-to-Many Mapping ​

Map 的 value 不一定是一个数字，也可以是 list / set / object。

例如按班级分组：

text
班级 → 学生列表
python
groups = {
    1: ["张三", "王五"],
    2: ["李四"]
}

Two Sum ​

一遍 Hash Map 的常见写法：

python
pos = {}

for i, x in enumerate(nums):
    need = target - x

    if need in pos:
        return [pos[need], i]

    pos[x] = i

推荐固定的 mental model：

text
key   = 已经出现的数
value = 该数对应的下标

算法模式：

text
遍历当前元素 x
→ 推导需要查询的对象 need
→ 在历史状态中平均 O(1) 查询
→ 保存当前状态供未来使用

也可以反向设计为“补数 → 当前下标”，但秋招中优先熟悉“已出现的值 → 下标”的标准写法。

Set vs Map Decision Tree ​

text
需要记录历史信息？
│
├── 否
│   └── 不一定需要 Hash
│
└── 是
    │
    ├── 只关心有没有？
    │   └── Set
    │
    └── 还需要次数 / 下标 / 状态 / 对象？
        └── Map

可以压缩为：

text
Set = membership
Map = membership + state

Review Focus ​

后续通过真实算法题继续强化：

  • 去重 / 重复检测；
  • Frequency Counting；
  • Complement Lookup；
  • 最近位置；
  • visited；
  • 后续 Sliding Window + Hash。

Practice:

04_Practice/CS_MCQs/Data_Structure_Lesson_2.md

Mistakes:

05_Mistakes/CS.md

Interview QA:

06_Interview/CS_QA/Data_Structure.md