Python自动化测试面试核心：哈希与递归算法实战解析

追风的人

发布时间：2026-10-13| 3人浏览过

原创

本文深入解析Python自动化测试面试中的高频编程题。重点讲解如何利用哈希结构（字典、集合）实现高效去重与查找优化，针对海量数据Top K问题对比内存与时间复杂度策略，并剖析递归在阶乘、二叉树遍历等场景中的分层推导逻辑，助力测试人员提升编码能力。

Python自动化测试面试核心：哈希与递归算法实战解析

前言

随着行业技术的演进，编程能力已逐渐成为软件测试工程师的核心素养之一。因此，在各类笔试与面试环节中，编码题目已成为常规考察内容，主要旨在评估候选人的以下关键能力。

基础编码能力及逻辑思维
对基本数据结构（如顺序表、链表、队列、栈、二叉树）的掌握程度
基本算法（排序、查找、递归）及其时间复杂度的分析能力

面试高频算法思想：哈希、递归与分治

除了上述基础算法外，笔试与面试中高频考察以下三种核心算法思想：

哈希
递归
分治

哈希算法实战：去重与效率优化

哈希

在Python中，哈希对应映射类型，主要包括字典和集合。其核心特征是键值唯一且查找效率极高。对于序列（列表、元组、字符串），元素查找的时间复杂度为O(n)；而利用字典和集合进行查找，时间复杂度可降至O(1)。因此，哈希在处理列表问题时主要发挥两种作用：

数据去重

优化查找效率

例题1：列表去重#

若对去重后的顺序无要求，可直接使用set()进行转换（转换后列表会自动排序）；若需保持原有顺序，可利用字典的fromkeys()方法，借助字典键值的唯一性来实现去重。

不考虑顺序的情况：


l = [2,1,2,3,4,5,6,6,5,4,3,2,1]
result = list(set(l))
print(result)

运行结果：

[1, 2, 3, 4, 5, 6]

考虑顺序的情况：


l = [2,1,2,3,4,5,6,6,5,4,3,2,1]
result = list({}.fromkeys(l).keys())
print(result)

运行结果：

[2, 1, 3, 4, 5, 6]

例题2：分组

针对包含字母和数字的字符串，需找出相同字符或数字，并按出现次数进行排序。


l = [1,2,3,'a','b','c',1,2,'a','b',3,'c','d','a','b',1]
set1 = set(l)
result = [(item, l.count(item)) for item in set1]
result.sort(key=lambda x:x[1], reverse=True)
print(result)

此处利用哈希键值不重复的特性。此外，也可使用Python内置的groupby函数，具体代码如下：


from itertools import groupby

l = [1,2,3,'a','b','c',1,2,'a','b',3,'c','d','a','b',1]
l.sort(key=lambda x: str(x)) # 分组前需要先排序
result = []
for item, group in groupby(l, key=lambda x: str(x)):
  result.append((item, len(list(group))))
result.sort(key=lambda x:x[1], reverse=True)
print(result)

例题3：海量数据找出Top K的数据#

对于小数据量，可直接采用排序加切片的方式；而对于海量数据，必须综合考量服务器硬件限制，即在时间效率、内存占用及数据特征之间取得平衡。若存在大量重复数据，可先通过哈希去重以降低处理量。

此处演示使用生成器生成1000万个随机整数，并求解其中最大的1000个数。生成随机数的代码如下：


import random
import time
n = 10000 * 1000
k = 1000
print(n)
def gen_num(n):
  for i in range(n):
    yield random.randint(0, n)
l = gen_num(n)

若内存不受限制，可直接使用set()去重后排序。


start = time.time()
l = list(set(l))
result = l[-k:]
result.reverse()
print(time.time()-start)

1000w个数据全部载入内存，经set处理后列表自动呈递增顺序，通过切片取最后1000个元素即可得到Top 1000的数值。

使用堆排序可进一步节省内存空间。


start = time.time()
result = heapq.nlargest(k, l)
print(time.time()-start)

此处调用Python内置的堆排序库heapq。使用nlargest(k, l)函数可直接获取序列l中最大的k个数。

若内存较小，可采用分治策略，利用多线程对数据进行分组处理（此处略）。

例题4：两数之和#

给定列表l=[1,2,3,4,5,6,7,8]（数据无重复），目标值target=6，需快速找出数组中两个元素之和等于target的元素下标。

注意，应避免使用双重循环暴力比对target的做法。正确的思路是单层循环，计算target与当前值的差值，并判断该差值是否存在于列表中。

然而，若直接在列表中执行in查询，其时间复杂度为O(n)，这隐含了一层循环，导致整体效率仍为O(n^2)，与双重循环无异。

此时引入哈希优化差值查询操作，将单次查询复杂度从O(n)降至O(1)，从而使总体效率由O(n^2)优化为O(n)。


l = [1,2,3,4,5,6,7,8]
set1 = set(list1)  # 使用集合已方便查找
target = 6

result = []
for a in list1:
  b = target - a
  if a < b < target and b in set1:  # 在集合中查找,为避免重复，判断a为较小的那个值
    result.append((list1.index(a), list1.index(b)))  # 列表index取下标的操作为O(1) 
print(result)