限时模拟面试：简单与中等难度问题
在 45 分钟计时内解决三个问题，像真实面试中一样口述思考过程，并在之后复习最优解法。
限时模拟面试：简单与中等难度问题 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
如何使用这场模拟面试
本课将模拟一次真实的编程面试。对于每道题，您应该：（1）阅读一次，（2）在 60 秒内识别模式，（3）说明您的方法和复杂度，（4）编写解法，以及（5）使用示例进行测试。请设置一个计时器。简单题应花费 10-15 分钟，中等题应花费 20-25 分钟。
不要提前查看解法——那样会失去练习的意义。如果 5 分钟后仍然卡住，请重新阅读题目描述，并寻找能揭示模式的信号词（已排序？最小值？所有组合？子数组？）。自行摆脱困境的能力，与快速解题的能力同样重要。
# Mock interview timer simulation
import time
class InterviewTimer:
def __init__(self, total_minutes):
self.total = total_minutes * 60
self.start = None
def begin(self, problem_name):
self.start = time.time()
print(f'TIMER STARTED: {problem_name}')
print(f'You have {self.total//60} minutes. Go!')
def checkpoint(self, label):
if self.start:
elapsed = time.time() - self.start
remaining = self.total - elapsed
print(f'[{label}] Elapsed: {elapsed:.0f}s, Remaining: {remaining:.0f}s')
# Usage in real practice:
timer = InterviewTimer(15) # 15-minute easy problem
timer.begin('Two Sum')
time.sleep(1)
timer.checkpoint('Identified pattern')简单题 1：有效的括号
题目：给定一个只包含 '('、')'、'{'、'}'、'['、']' 的字符串，判断输入字符串是否有效。如果每个左括号都按照正确的顺序由相同类型的括号闭合，则该字符串有效。
信号：匹配成对、顺序很重要、最近打开的括号必须先闭合 → 栈。将左括号推入栈；遇到右括号时 pop 并验证。如果尝试 pop 时栈为空，或结束时仍有剩余元素，则字符串无效。时间 O(n)，空间 O(n)。
def is_valid(s):
stack = []
matching = {')': '(', '}': '{', ']': '['}
for char in s:
if char in '({[':
stack.append(char)
else:
if not stack or stack[-1] != matching[char]:
return False
stack.pop()
return len(stack) == 0
# Test cases
test_cases = [
('()', True),
('()[]{}' , True),
('(]', False),
('([)]', False),
('{[]}', True),
('', True), # empty string is valid
('(((', False), # unmatched opens
(')]', False), # close without open
]
for s, expected in test_cases:
result = is_valid(s)
status = 'PASS' if result == expected else 'FAIL'
print(f'{status}: is_valid({repr(s)}) = {result} (expected {expected})')简单题 2：买卖股票的最佳时机
题目：给定数组 prices，其中 prices[i] 表示第 i 天的股票价格，找出一次买入和一次卖出所能获得的最大利润（必须先买入再卖出）。如果无法获利，则返回 0。
信号：左侧必须先于右侧的最大差值 → 从左到右扫描时跟踪当前遇到的最小值。在每一天，潜在利润为 current_price - min_so_far。更新最大利润。这一方法的复杂度为 O(n)/O(1)，是 Kadane 算法的一个特例。
def max_profit(prices):
if not prices:
return 0
min_price = float('inf')
max_profit = 0
for price in prices:
if price < min_price:
min_price = price
elif price - min_price > max_profit:
max_profit = price - min_price
return max_profit
# Test cases
test_cases = [
([7, 1, 5, 3, 6, 4], 5), # buy at 1, sell at 6
([7, 6, 4, 3, 1], 0), # monotonically decreasing: no profit
([2, 4, 1], 2), # buy at 2, sell at 4
([1], 0), # single price: no transaction possible
([3, 3, 3], 0), # flat: no profit
]
for prices, expected in test_cases:
result = max_profit(prices)
status = 'PASS' if result == expected else 'FAIL'
print(f'{status}: max_profit({prices}) = {result} (expected {expected})')中等题 1：三数之和
题目：给定一个数组，找出所有和为零的不重复三元组。结果中不能包含重复的三元组。
模式：将双指针扩展到三个元素。对数组执行 sort。对于每个元素 nums[i]，使用两个指针 left = i+1 和 right = n-1，查找和为 -nums[i] 的数对。通过越过相同的值来跳过重复项。时间 O(n²)，不计输出时空间为 O(1)。sort 操作使重复项处理更加简洁。
def three_sum(nums):
nums.sort()
result = []
n = len(nums)
for i in range(n - 2):
# Skip duplicate values for the first element
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, n - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1 # skip duplicate lefts
while left < right and nums[right] == nums[right - 1]:
right -= 1 # skip duplicate rights
left += 1; right -= 1
elif total < 0:
left += 1
else:
right -= 1
return result
print(three_sum([-1, 0, 1, 2, -1, -4])) # [[-1,-1,2],[-1,0,1]]
print(three_sum([0, 0, 0, 0])) # [[0,0,0]]
print(three_sum([])) # []
print(three_sum([1, 2, -2, -1])) # []中等难度题目 2：最长不含重复字符的子串
问题：给定一个字符串，找出不含重复字符的最长子串的长度。
模式：使用集合的滑动窗口（或记录最后位置的字典）。维护一个窗口 [left, right]。通过依次纳入每个字符来向右扩展窗口。如果某个字符重复（已在窗口中），就从左侧收缩窗口，直到移除重复字符。跟踪出现过的最大窗口大小。时间复杂度 O(n)，空间复杂度 O(min(n, 字母表大小))。
def length_of_longest_substring(s):
char_index = {} # character -> last seen index
left = 0
max_len = 0
for right, char in enumerate(s):
if char in char_index and char_index[char] >= left:
left = char_index[char] + 1 # shrink window past duplicate
char_index[char] = right
max_len = max(max_len, right - left + 1)
return max_len
# Test cases
test_cases = [
('abcabcbb', 3), # 'abc'
('bbbbb', 1), # 'b'
('pwwkew', 3), # 'wke'
('', 0), # empty string
('au', 2), # full string
('dvdf', 3), # 'vdf' (skip the first d)
]
for s, expected in test_cases:
result = length_of_longest_substring(s)
status = 'PASS' if result == expected else 'FAIL'
print(f'{status}: len_longest({repr(s)}) = {result} (expected {expected})')中等难度题目 3：零钱兑换
问题：给定硬币面额和目标金额，找出凑出该金额所需的最少硬币数。如果无法凑出目标金额，则返回 -1。
模式：经典的一维 DP（无界背包变体）。dp[i] = 金额 i 所需的最少硬币数。将 dp[0] 初始化为 0，将其他值初始化为无穷大。对于从 1 到目标金额的每个金额，尝试所有硬币面额。对于每个有效硬币，使用 dp[i] = min(dp[i], dp[i - coin] + 1) 更新结果。时间复杂度 O(金额 × 硬币数量)，空间复杂度 O(金额)。
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # 0 coins to make amount 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i and dp[i - coin] + 1 < dp[i]:
dp[i] = dp[i - coin] + 1
return dp[amount] if dp[amount] != float('inf') else -1
# Test cases
test_cases = [
([1, 5, 11], 15, 3), # 11+1+1+1+1... wait: 11+1+1+1+1=5 coins? No: 5+5+5=3
([2], 3, -1), # impossible (only even coins)
([1], 0, 0), # 0 coins for amount 0
([1, 2, 5], 11, 3), # 5+5+1
([186, 419, 83, 408], 6249, 20), # stress test
]
for coins, amount, expected in test_cases:
result = coin_change(coins, amount)
status = 'PASS' if result == expected else 'FAIL'
print(f'{status}: coin_change({coins}, {amount}) = {result} (expected {expected})')时间压力下的问题解决流程
当时间所剩无几时，请按以下顺序优先处理：(1) 优先选择输出正确的可运行暴力解法，而不是未完成的最优解法；(2) 明确处理边界情况；(3) 编写整洁、易读的代码，而不是炫技式的单行代码。面试官更倾向于一个能通过所有测试用例的整洁 O(n²) 解法，而不是一个带有隐蔽错误的 O(n) 解法。
如果您意识到自己的 O(n²) 解法有误，请不要中途放弃——先完成它并进行测试，然后在时间允许的情况下提出优化方案。一个写到一半的最优解法，其所得评价不如一个完整但并非最优的解法。
# Priority order when time runs out
priority = [
('First priority', 'Correct brute-force that passes all test cases'),
('Second priority', 'Optimal solution with bugs is WORSE than suboptimal correct'),
('Third priority', 'Edge cases handled visibly (empty input, single element, negatives)'),
('Fourth priority', 'Clean variable names and readable code'),
('Fifth priority', 'Add complexity statement as a comment at the top'),
]
print('Under time pressure, prioritise:')
for priority_level, desc in priority:
print(f' {priority_level}: {desc}')
# Adding complexity as a comment
def two_sum_commented(nums, target):
# Time: O(n), Space: O(n)
seen = {}
for i, n in enumerate(nums):
complement = target - n
if complement in seen:
return [seen[complement], i]
seen[n] = i
return []检查您的解法：五个问题
在说“我完成了”之前，请问自己以下五个问题：
- 能否处理空输入？
[]、''、None、n=0 - 能否处理单个元素？ 大小为 1 的数组、只有一个节点的树
- 能否处理所有元素都相同的情况？
[5, 5, 5, 5]、'aaaa' - 能否处理最小值和最大值？ 负数、非常大的整数、0
- 是否说明了时间和空间复杂度？ 使用大 O 表示法并给出简短说明
这五项检查可以发现面试解法中的大多数错误。面试官希望候选人能够自行测试——除非您主动请求反馈，否则他们不会告诉您解法中存在错误。
# The five edge-case categories with examples
edge_cases = {
'Empty input': ['[] empty array', '"" empty string', 'None / null'],
'Single element': ['[42]', 'single node tree', 'n=1'],
'All same': ['[3,3,3,3]', '"aaaa"', 'uniform grid'],
'Extreme values': ['[-10^9, 10^9]', 'INT_MAX + 1 overflow check', '0 as input'],
'Already sorted': ['ascending + descending', 'already optimal input'],
}
for category, examples in edge_cases.items():
print(f'{category}:')
for ex in examples:
print(f' - {ex}')
print()
# Template for self-testing:
def test_my_solution(fn, test_cases):
for inputs, expected in test_cases:
result = fn(*inputs) if isinstance(inputs, tuple) else fn(inputs)
status = 'PASS' if result == expected else 'FAIL'
print(f'{status}: {inputs} => {result} (expected {expected})')处理后续问题
解决问题后，面试官通常会提出后续问题。常见类型包括：
- “能否使用 O(1) 的空间？” → 寻找原地修改或数学技巧
- “如果 n 非常大怎么办？” → 讨论流式处理、分页或采样方法
- “如果数组已经排序怎么办？” → 通常存在更简单的算法
- “能否将其并行化？” → 找出相互独立的子问题，并讨论 MapReduce 或任务并行
后续问题考察的是知识深度和应变能力。请说“请让我思考一下”，而不是立即猜测。经过思考的停顿胜过自信地说出错误答案。
# Follow-up answers for classic problems
follow_ups = [
{
'problem': 'Find duplicate in array 1..n (space O(n) solution uses set)',
'follow_up': 'Can you do it in O(1) space without modifying input?',
'answer': 'Floyd cycle detection: treat array as linked list (slow/fast pointer)',
},
{
'problem': 'Reverse a string (space O(n) with new array)',
'follow_up': 'Can you do it in-place?',
'answer': 'Two pointers from both ends, swap until they meet: O(n) time O(1) space',
},
{
'problem': 'Find max in array: O(n) single pass',
'follow_up': 'What if the array is streamed one element at a time?',
'answer': 'Same algorithm works! Running maximum handles infinite streams',
},
{
'problem': 'Merge sorted arrays O(n+m)',
'follow_up': 'What if you have K sorted arrays?',
'answer': 'Use a min-heap of (value, array_idx, element_idx): O(n log k)',
},
]
for fu in follow_ups:
print(f'Problem: {fu["problem"]}')
print(f'Follow-up: {fu["follow_up"]}')
print(f'Answer: {fu["answer"]}\n')练习题：字母异位词分组
问题：给定一个字符串数组，将字母异位词归为一组。返回一个分组列表。
模式：使用频率映射作为键。对于每个字符串，使用 sort 对其字符排序（或计算字符频率元组），将其结果作为规范键。使用以列表为值的哈希映射，根据该键将字符串分组。时间复杂度 O(n × m log m)，其中 m 是字符串的最大长度；空间复杂度 O(n × m)。不需要嵌套循环——遍历数组一次即可。
from collections import defaultdict
def group_anagrams(strs):
# Method 1: sort each string as key
groups = defaultdict(list)
for s in strs:
key = ''.join(sorted(s)) # canonical form
groups[key].append(s)
return list(groups.values())
def group_anagrams_v2(strs):
# Method 2: character count tuple as key (avoids sorting)
groups = defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
key = tuple(count) # immutable, hashable
groups[key].append(s)
return list(groups.values())
test = ['eat', 'tea', 'tan', 'ate', 'nat', 'bat']
result = [sorted(g) for g in group_anagrams(test)]
result.sort()
print('Groups:', result)
# [['ate','eat','tea'], ['bat'], ['nat','tan']]
print('V2:', [sorted(g) for g in sorted(group_anagrams_v2(test), key=len)])模拟面试后的自我评估
每次模拟面试后，请从以下维度评估自己：
- 模式识别速度：您是否在 <60 秒内识别出模式？
- 代码正确性：您的第一个解法是否通过了所有测试用例？
- 边界情况处理：您是否测试了空输入、单个元素输入和极端输入？
- 沟通表达：您是否始终解释了自己的推理过程？
- 复杂度意识：您是否说明了时间和空间复杂度？
- 应变恢复能力：遇到困难时，您是顺利调整了方向，还是僵住了？
请在每个维度上为自己评 1—5 分。下一周的练习应重点放在评分最低的维度上。大多数候选人需要提高模式识别能力或沟通表达能力，很少需要同时提高这两项。
# Self-assessment scoring template
def self_assess(pattern_speed, code_correctness, edge_cases,
communication, complexity, recovery):
scores = {
'Pattern recognition (< 60s)': pattern_speed,
'Code correctness (all tests pass)': code_correctness,
'Edge case handling': edge_cases,
'Communication (thinking aloud)': communication,
'Complexity stated correctly': complexity,
'Recovery when stuck': recovery,
}
total = sum(scores.values())
max_total = len(scores) * 5
print('Self-Assessment Results:')
print('-'*50)
for dim, score in scores.items():
bar = '#' * score + '-' * (5 - score)
print(f'{dim:45s} [{bar}] {score}/5')
print(f'\nTotal: {total}/{max_total} ({total/max_total*100:.0f}%)')
weak = min(scores, key=scores.get)
print(f'Focus area: {weak}')
self_assess(4, 3, 4, 3, 5, 2) # example scores快速检查
测试您对本课中“数据结构与算法——编码面试准备”相关概念的理解。
课程回顾
在本课中，您学到了：采用固定流程处理问题——阅读题目、在 60 秒内识别模式、说明复杂度、编码，然后用五类边界情况进行测试、时间所剩无几时，可运行的暴力解法胜过未完成的最优解法，以及每次模拟练习后，从六个维度（速度、正确性、边界情况、沟通、复杂度、恢复能力）进行自我评估，将改进重点放在正确的方面。接下来，我们将深入讲解边界情况的处理，以及面试者沟通的最佳实践。
常见问题解答
「限时模拟面试：简单与中等难度问题」课时是免费的吗？
是的 — 「限时模拟面试：简单与中等难度问题」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「限时模拟面试：简单与中等难度问题」这节课中我会学到什么？
在 45 分钟计时内解决三个问题，像真实面试中一样口述思考过程，并在之后复习最优解法。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「限时模拟面试：简单与中等难度问题」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。