随着行业的发展，编程能力逐渐成为软件测试从业人员的一项基本能力。因此在笔试和面试中常常会有一定量的编码题，主要考察以下几点。
除基本算法之外，笔试面试中经常会考察以下三种思想：
目录
哈希即Python中的映射类型，字典和集合，键值唯一，查找效率高，序列（列表、元祖、字符串）的元素查找时间复杂度是O(n)，而字典和集合的查找只需要O(1)。
因此哈希在列表问题中主要有两种作用：
待去重列表
lt1 = [1,3,2,3,4,5,3,5]
lt2 = list(set(lt1))lt2 = list({}.fromkeys(lt1).keys())lt2 = sorted(set(lt1),key=lt1.index)lt2 = []
[lt2.append(i) for i in lt1 if not i in lt2]
即:
lt2 = []
for i in lt1:
if i not in lt2:
lt2.append(i)func = lambda x,y:x if y in x else x + [y]
lt2 = reduce(func, [[], ] + lt1)for x in lt1:
while lt1.count(x)>1:
del lt1[lt1.index(x)]
问题：最近遇到一个小问题，需要对列表中的元素分组，保证每组元素的和尽可能平衡，最后返回每组的值和所对应的下标，这里对处理办法进行记录，方便以后查看。
解决思路：
step1: 对列表进行排序，新建输出的空列表out_list[N];
step2: 根据需要分组的个数NN，每次遍历NN个元素；
step3: 循环执行step2，前后两次交替分配；
step4: 处理最后未分配的元素，依次分配给out_list。
代码：
def listGroupBySum(arr, N):
sorted_arr = sorted(enumerate(arr), key=lambda x:x[1]) # index: x[0] value: x[1]
out_list = [[] for i in range(N)]
for i in range(len(arr) // N):
for j in range(N):
if i % 2 == 0:
out_list[j].append(sorted_arr[i*N+j])
else:
out_list[N-j-1].append(sorted_arr[i*N+j])
# the remain items of arr
for i in range(len(arr) // N * N, len(arr)):
out_list[i%N].append(sorted_arr[i])
return out_list
例子：
在大规模数据处理中，常遇到的一类问题是，在海量数据中找出出现频率最高的前K个数，或者从海量数据中找出最大的前K个数，这类问题通常称为“top K”问题，如：在搜索引擎中，统计搜索最热门的10个查询词；在歌曲库中统计下载率最高的前10首歌等等。
针对top k类问题，通常比较好的方案是【分治+trie树/hash+小顶堆】，即先将数据集按照hash方法分解成多个小数据集，然后使用trie树或者hash统计每个小数据集中的query词频，之后用小顶堆求出每个数据集中出频率最高的前K个数，最后在所有top K中求出最终的top K。
实际上，最优的解决方案应该是最符合实际设计需求的方案，在实际应用中，可能有足够大的内存，那么直接将数据扔到内存中一次性处理即可，也可能机器有多个核，这样可以采用多线程处理整个数据集。
本文针对不同的应用场景，介绍了适合相应应用场景的解决方案。
3.1 单机+单核+足够大内存
设每个查询词平均占8Byte，则10亿个查询词所需的内存大约是10^9*8=8G内存。如果你有这么大的内存，直接在内存中对查询词进行排序，顺序遍历找出10个出现频率最大的10个即可。这种方法简单快速，更加实用。当然，也可以先用HashMap求出每个词出现的频率，然后求出出现频率最大的10个词。
3.2 单机+多核+足够大内存
这时可以直接在内存中实用hash方法将数据划分成n个partition，每个partition交给一个线程处理，线程的处理逻辑是同3.1节类似，最后一个线程将结果归并。
该方法存在一个瓶颈会明显影响效率，即数据倾斜，每个线程的处理速度可能不同，快的线程需要等待慢的线程，最终的处理速度取决于慢的线程。解决方法是，将数据划分成c*n个partition（c>1），每个线程处理完当前partition后主动取下一个partition继续处理，直到所有数据处理完毕，最后由一个线程进行归并。
3.3 单机+单核+受限内存
这种情况下，需要将原数据文件切割成一个一个小文件，如，采用hash(x)%M，将原文件中的数据切割成M小文件，如果小文件仍大于内存大小，继续采用hash的方法对数据文件进行切割，直到每个小文件小于内存大小，这样，每个文件可放到内存中处理。采用3.1节的方法依次处理每个小文件。
3.4 多机+受限内存
这种情况下，为了合理利用多台机器的资源，可将数据分发到多台机器上，每台机器采用3.3节中的策略解决本地的数据。可采用hash+socket方法进行数据分发。
从实际应用的角度考虑，3.1~3.4节的方案并不可行，因为在大规模数据处理环境下，作业效率并不是首要考虑的问题，算法的扩展性和容错性才是首要考虑的。算法应该具有良好的扩展性，以便数据量进一步加大（随着业务的发展，数据量加大是必然的）时，在不修改算法框架的前提下，可达到近似的线性比；算法应该具有容错性，即当前某个文件处理失败后，能自动将其交给另外一个线程继续处理，而不是从头开始处理。
Top k问题很适合采用MapReduce框架解决，用户只需编写一个map函数和两个reduce 函数，然后提交到Hadoop（采用mapchain和reducechain）上即可解决该问题。对于map函数，采用hash算法，将hash值相同的数据交给同一个reduce task；对于第一个reduce函数，采用HashMap统计出每个词出现的频率，对于第二个reduce 函数，统计所有reduce task输出数据中的top k即可。
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
| 1 2 3 4 5 6 7 8 |
|
递归是一种循环调用自身的函数。可以用于解决以下高频问题：
递归是一种分层推导解决问题的方法，是一种非常重要的解决问题的思想。递归可快速将问题层级化，简单化，只需要考虑出口和每层的推导即可。
如阶乘，要想求n!，只需要知道前一个数的阶乘(n-1)!，然后乘以n即可，因此问题可以转为求上一个数的阶乘，依次向前，直到第一个数。
举个通俗的例子：
A欠你10万，但是他没那么多钱，B欠A 8万，C欠B 7万 C现在有钱。因此你要逐层找到C，一层一层还钱，最后你才能拿到属于你的10万。
编写递归函数有两个要点：
求n的阶乘
代码如下：
Copy
def factorial(n): if n == 1: # 出口 return 1 return factorial(n-1) * n # 自我调用求上一个结果，然后推导本层结果
也可以简写为
factorial = lambda n: 1 if n==1 else factorial(n-1) * n
【问题描述】
斐波那切数列0，1，1，2，3，5，8，13，21，34，55……从第三项起，每一项都是紧挨着的前两项的和。写出计算斐波那切数列的任意一个数据项递归程序。
【输入格式】
输入所求的项数。
【输出格式】
输出数据项的值。
【输入样例】fbi.in
10
【输出样例】fbi.out
34
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int dg(int m)
{
if(m==1)return 0;
if(m==2)return 1;
else return dg(m-1)+dg(m-2);
}
int main()
{
int m;
cin>>m;
cout<<dg(m);
return 0;
}
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
1 public class Main08 {
2
3 /*
4 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。
5 * 求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
6 */
7
8 public static void main(String[] args) {
9 // TODO Auto-generated method stub
10 int num = Main08.JumpFloor(4);
11 System.out.println(num);
12 }
13
14 public static int JumpFloor(int target) {
15 if(target == 1) {
16 return 1;
17 }
18 if(target == 2) {
19 return 2;
20 }
21
22 return JumpFloor(target-1) + JumpFloor(target-2);
23 }
24
25 }
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
1 /*
2 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求
3 * 该青蛙跳上一个n级的台阶总共有多少种跳法。
4 */
5
6 import java.util.Scanner;
7
8 public class Main09 {
9
10 public static void main(String[] args) {
11 // TODO Auto-generated method stub
12 Scanner sc = new Scanner(System.in);
13 int target = sc.nextInt();
14 int times = Main09.JumpFloorII(target);
15 System.out.println(times);
16 }
17
18 public static int JumpFloorII(int target) {
19 if(target == 0) {
20 return 0;
21 }
22 if(target == 1) {
23 return 1;
24 }
25
26 return 2*JumpFloorII(target-1);
27 }
28
29 }
这两道题目都是斐波那契数列的扩展。
跳台阶：每一次只能跳1阶或者2阶；
所以F(1) = 1;
F(2) = F(2-1) + F(2-2); ----------→ F(2-1) :青蛙第一次跳了一个台阶后的情况。 举例排列的话就是 1 x, x 为 1。 F(2-2)：青蛙第一次跳了两个台阶的情况。举例排列的话就是 2 。
F(3) = F(3-1) + F(3-2); ----------→ F(3-1)：青蛙第一次跳了一个台阶后的情况。F(3-2)：青蛙第一次跳了两个台阶的情况。 。。。。。以此类推。
F(n) = F(n-1) + F(n-2);
变态跳台阶：每一次只能跳1阶或者2阶或者3阶.......n阶。
F(1) = 1；
F(2) = F(2-1) + F(2-2); ----------→ F(2-1) :青蛙第一次跳了一个台阶后的情况。 举例排列的话就是 1 x, x 为 1。 F(2-2)：青蛙第一次跳了两个台阶的情况。举例排列的话就是 2 。
F(3) = F(3-1) + F(3-2) + F(3-3); ----------→ F(3-1)：青蛙第一次跳了一个台阶后的情况。F(3-2)：青蛙第一次跳了两个台阶的情况。 。。。。。以此类推。
............
F(n-1) = F(n-2) + F(n-3) + ......+ F(1) + F(0);
F(n) = F(n-1) + F(n-2) + ......+ F(1) + F(0);
根据F(n-1)的表达式和F(n) 的表达式 我们可以轻松的推出：F(n) = 2 * F(n-1); 这样就得到了 我们的迭代表达式。
快速排序的是想是选一个基准数（如第一个数），将大于该数和小于该数的分成两块，然后在每一块中重复执行此操作，直到该块中只有一个数，即为有序。
def quick_sort(l):
if len(l) < 2:
return l
target = l[0] # 以第一个数为基准数
low_part, eq_part, high_part = [], [target], []
for i in l[1:]:
if i < target:
low_part.append(i)
elif i == target:
eq_part.append(i)
else:
high_part.append(i)
return quick_sort(low_part) + eq_part + quick_sort(high_part)二分查找需要序列首先有序。思想是先用序列中间数和目标值对比，如果目标值小，则从前半部分（小于中间数）重复此查找，否则从后半部分重复此查找。
def bin_search(l, n):
if not l:
return None
mid = len(l) // 2
if l[mid] == n:
return mid
if l[mid] > n:
return bin_search(l[:mid])
return bin_search(l[mid+1:])二叉树是非常常考的一种数据结构。其基本结构就是一个包含数据和左右节点的一种结构，使用Python类描述如下：
class Node(object):
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right二叉树的遍历分为分层遍历（广度优先）和深度遍历（深度优先）两种，其中深度遍历又分为前序、中序、后序三种。
分层遍历由于每次处理多个节点，使用循环解决更加方便一点（也可以是使用递归解决）。
分层遍历代码如下：
class Node(object):
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right深度遍历
以前序为例：
def deep(root):
if root is none:
return
[print(root.data), deep(root.left), deep(root.right)]二叉树最大深度即其左子树深度和右子树深度中最大的一个加上1（当前节点）。由于二叉树的每一个左右节点都是一个二叉树，这种层层嵌套的结构非常适合使用递归求解。
def max_depth(root):
if not root:
return 0
return max([max_depth(root.left), max_depth(root.right)]) + 1
相等二叉树是只，一个二叉树，节点数据相同，左右子树也完全相同。由于左右子树也是一个二叉树，因此也可以使用递归求解。
def is_same_tree(p, q):
if p is None and q is None:
return True
elif p and q:
return p.data == q.data and is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)平衡二叉树是指，一个二叉树的左右子树的高度差不超过1。平衡二叉树的左右子树也应该是平衡二叉树，因此这也是一个递归问题。
注：这里需要使用以上求二叉树深度的方法
def max_depth(root):
if not root:
return 0
return max([max_depth(root.left), max_depth(root.right)]) + 1
def is_balance_tree(root):
if root is None:
return True
return abs(max_depth(root.left)-max_depth(root.right))<=1 and is_balance_tree(root.left) and is_balance_tree(root.right)str1 = 'abcdaacddceea'
set1 = set(str1)
result = [(char, str1.count(char)) for char in set1]
print(result)from collections import Counter
c = Counter('abcdaacddceea')
print(c.items())
print(c.most_common(3))'abcefg'[::-1]或
''.join(reversed('abcdefg'))
a = 'abc123efg'
l = len(a)
r = []
for i,c in enumerate(a):
r.append(c) if c.isdigit() else r.append(a[l-i-1])
print(''.join(r))这是栈使用的一个经典示例，思路为，遇到正括号则入栈，遇到反括号则和栈顶判断，如果匹配则匹配的正括号出栈（完成一对匹配），否则打印不匹配，break退出。
text = "({[({{abc}})][{1}]})2([]){({[]})}[]"
def is_closed(text)
stack = [] # 使用list模拟栈, stack.append()入栈, stack.pop()出栈并获取栈顶元素
brackets = {')':'(',']':'[','}':'{'} # 使用字典存储括号的对应关系, 使用反括号作key方便查询对应的括号
for char in text:
if char in brackets.values(): # 如果是正括号,入栈
stack.append(char)
elif char in brackets.keys(): # 如果是反括号
if brackets[char] != stack.pop(): # 如果不匹配弹出的栈顶元素
return False
return True
print(is_closed(text))常见的解法有两种：
依次出队列的逻辑为：
以下为使用Python列表模拟两个队列依次弹出的示例。
由于Python列表尾部弹出list.pop()的的操作效率O(1)，比首部弹出list.pop(0)的操作效率O(n)更高，因此我们先按从大到小排序，最后在执行一次反转。
list1 = [1,5,7,9]
list2 = [2,3,4,5, 6,8,10,12,14]
result = []
for i in range(len(list1) + len(list2)):
if list1 and not list2:
result.append(list1.pop())
elif list2 and not list1:
result.append(list2.pop())
else:
result.append(list1.pop()) if list1[-1] > list2[-1] else result.append(list2.pop()) # 弹出顶端大的数
result.reverse() # 执行反转
print(result)队列是先入先出，栈是先入后出。
使用两个队列实现栈的方式有很多种，主要分为优化入栈和优化出栈两种，以下为优化入栈的一种实现方法。
实现代码如下：
import queue
class Stack(object):
def __init__(self):
self.q1 = queue.Queue()
self.q2 = queue.Queue()
def push(self, value):
self.q1.put(value)
def pop(self):
while self.q1.qsize() > 1:
self.q2.put(self.q1.get())
value = self.q1.get()
while not self.q2.empty():
self.q1.put(self.q2.get())
return value测试代码：
s = Stack()
[s.push(i) for i in [1,2,3,4,5,6,7]]
print(s.pop())
print(s.pop())
print(s.pop())
print(s.pop())打印结果为：
7
6
5
4