首页 › Python论坛 › Python自动化测试面试题-编程篇

努立钱来 發表於 2020-3-12 12:36:00

Python自动化测试面试题-编程篇

<h2 id="前言">前言</h2>
<p>随着行业的发展，编程能力逐渐成为软件测试从业人员的一项基本能力。因此在笔试和面试中常常会有一定量的编码题，主要考察以下几点。</p>
<ul>
<li>基本编码能力及思维逻辑</li>
<li>基本数据结构（顺序表、链表、队列、栈、二叉树）</li>
<li>基本算法（排序、查找、递归）及时间复杂度</li>
</ul>
<p>除基本算法之外，笔试面试中经常会考察以下三种思想：</p>
<ul>
<li>哈希</li>
<li>递归</li>
<li>分治</li>
</ul>
<h2 id="哈希">哈希</h2>
<p>哈希即Python中的映射类型，字典和集合，键值唯一，查找效率高，序列（列表、元祖、字符串）的元素查找时间复杂度是O(n)，而字典和集合的查找只需要O(1)。<br>
因此哈希在列表问题中主要有两种作用：</p>
<ol>
<li>去重</li>
<li>优化查找效率</li>
</ol>
<h3 id="列表去重">列表去重</h3>
<p>列表去重在不考虑顺序的情况下可以直接使用set()转换（转换后会自动排序），需要保持顺序可以使用字典构建的fromkeys()方法，利用字典键值的唯一性去重。<br>
不考虑顺序：</p>
<pre><code class="language-python">l =
result = list(set(l))
print(result)
</code></pre>
<p>运行结果：</p>
<pre><code>
</code></pre>
<p>考虑顺序：</p>
<pre><code class="language-python">l =
s = set()
result = []
for i in l:
    if i in s:
      continue
    s.add(i)
    result.append(i)
print(result)
</code></pre>
<p>注意，这里如果使用：</p>
<pre><code class="language-python">if not i in result:
    result.append(i)
</code></pre>
<p>虽然看起来代码简单，但是列表in查找的的时间复杂度为O(n)，not in的效率比in要差，每次都要进行n次比对。<br>
上例中，使用了一个集合变量s来优化in查找，同时使用in代替not in。</p>
<p>Python3.6后字典按键值插入顺序，如果使用Python3.6，也可以利用字典的有序性来去重，示例如下：</p>
<pre><code class="language-python">l =
result = list({}.fromkeys(l).keys())
print(result)
</code></pre>
<p>运行结果：</p>
<pre><code>
</code></pre>
<h3 id="列表分组">列表分组</h3>
<p>一串字母数字组合的字符串，找出相同的字母或数字，并按照个数排序。</p>
<pre><code class="language-python">l =
set1 = set(l)
result = [(item, l.count(item)) for item in set1]
result.sort(key=lambda x:x, reverse=True)
print(result)
</code></pre>
<p>这里使用哈希的键值不重复性。当然也可以使用python自带的groupby函数，代码如下：</p>
<pre><code class="language-python">from itertools import groupby

l =
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, reverse=True)
print(result)
</code></pre>
<h3 id="海量数据top--k">海量数据topK</h3>
<p>对于小数据量可以使用排序+切片，而对于海量数据，需要考虑服务器硬件条件。即要考虑时间效率，也要考虑内存占用，同时还要考虑数据特征。如果大量的重复数据，可以先用哈希进行去重来降低数据量。<br>
这里我们使用生成器生成1000万个随机整数，求最大的1000个数，生成随机数的代码如下：</p>
<pre><code class="language-python">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)
</code></pre>
<ul>
<li>不限内存可以直接使用set()去重+排序</li>
</ul>
<pre><code class="language-python">start = time.time()
l = list(set(l))
result = l[-k:]
result.reverse()
print(time.time()-start)
</code></pre>
<p>1000w个数据会全部读入内存，set后列表自动为递增顺序，使用切片取-1000到最后的即为top 1000的数</p>
<ul>
<li>使用堆排可以节省一些内存</li>
</ul>
<pre><code class="language-python">start = time.time()
result = heapq.nlargest(k, l)
print(time.time()-start)
</code></pre>
<p>这里是用来Python自带的堆排库heapq。使用nlargest(k,l)可以取到l序列，最大的k个数。</p>
<ul>
<li>较小内存可以分治策略，使用多线程对数据进行分组处理（略）</li>
</ul>
<h3 id="两数之和">两数之和</h3>
<p>l= 数据不重复，target=6，快速找出数组中两个元素之和等于target 的数组下标。<br>
注意，不要使用双重循环，暴力加和来和target对比，正确的做法是单层循环，然后查找target与当前值的差，是否存在于列表中。<br>
但是由于列表的in查询时间复杂度是O(n)，即隐含了一层循环，这样效率其实和双重循环是一样的，都是O(n^2)。<br>
这里就可以使用哈希来优化查询差值是否在列表中操作，将O(n)降为O(1)，因此总体的效率就会变成O(n^2)-&gt;O(n)。</p>
<pre><code class="language-python">l =
set1 = set(list1)   # 使用集合已方便查找
target = 6

result = []
for a in set1:
    b = target - a
    if a &lt; b &lt; target and b in set1:   # 在集合中查找,为避免重复，判断a为较小的那个值
      result.append((list1.index(a), list1.index(b)))   # 列表index取下标的操作为O(1)
print(result)
</code></pre>
<h2 id="递归问题">递归问题</h2>
<p>递归是一种循环调用自身的函数。可以用于解决以下高频问题：</p>
<ul>
<li>阶乘</li>
<li>斐波那切数列</li>
<li>跳台阶、变态跳台阶</li>
<li>快速排序</li>
<li>二分查找</li>
<li>二叉树深度遍历（前序、中序、后序）</li>
<li>求二叉树深度</li>
<li>平衡二叉树判断</li>
<li>判断两颗树是否相同</li>
</ul>
<p>递归是一种分层推导解决问题的方法，是一种非常重要的解决问题的思想。递归可快速将问题层级化，简单化，只需要考虑出口和每层的推导即可。<br>
如阶乘，要想求n!，只需要知道前一个数的阶乘(n-1)!，然后乘以n即可，因此问题可以转为求上一个数的阶乘，依次向前，直到第一个数。<br>
举个通俗的例子：<br>
A欠你10万，但是他没那么多钱，B欠A 8万，C欠B 7万 C现在有钱。因此你要逐层找到C，一层一层还钱，最后你才能拿到属于你的10万。</p>
<p>编写递归函数有两个要点：</p>
<ol>
<li>出口条件，可以不止一个</li>
<li>推导方法（已知上一个结果怎么推导当前结果）</li>
</ol>
<h3 id="阶乘">阶乘</h3>
<p>求n的阶乘</p>
<ul>
<li>出口：n = 1 时，返回1</li>
<li>推导：(n-1)层的结果 * n</li>
</ul>
<p>代码如下：</p>
<pre><code class="language-python">def factorial(n):
    if n == 1:# 出口
      return 1
    return factorial(n-1) * n   # 自我调用求上一个结果，然后推导本层结果
</code></pre>
<blockquote>
<p>也可以简写为 <code>factorial = lambda n: 1 if n==1 else factorial(n-1) * n</code></p>
</blockquote>
<h3 id="斐波那切数列">斐波那切数列</h3>
<p>斐波那切数列是 1 1 2 3 5 8 ...这样的序列。前两个数为1，后面的数为前两个数之和。</p>
<ul>
<li>出口：n &lt;= 2，返回1</li>
<li>推导：(n-1)层的结果 + (n-2)层的结果</li>
</ul>
<p>代码如下：</p>
<pre><code class="language-python">def fib(n):
    if n&lt;=2:
      return 1
    return fib(n-2) + fib(n-1)
</code></pre>
<p>递归是一种分层简化问题的解法，但不一定是效率最高的解法，比如斐波那切数列中，在求fib(n-2) 和 fib(n-1)时实际上反复求解了两次fib(n-2)。<br>
可以通过缓存来优化效率，代码如下。</p>
<pre><code class="language-python">from functools import lru_cache

@lru_cache()
def fib(n):
    if n&lt;=2:
      return 1
    return fib(n-2) + fib(n-1)
</code></pre>
<h3 id="跳台阶变态跳台阶">跳台阶、变态跳台阶</h3>
<ul>
<li>跳台阶：一只青蛙，一次可以跳上1阶，也可以跳上2阶，问跳上n阶有多少种跳法。</li>
<li>变态跳台阶：一只青蛙，一次可以跳上1阶，可以一次跳上n阶，为跳上n阶有多少种跳法。</li>
</ul>
<p>这个问题关键是逻辑分析每层的推导过程。<br>
跳台阶实际上就是一个从第二位开始的斐波那切数列：1 2 3 5 8 13 ...</p>
<ul>
<li>出口：n &lt;= 2，返回n（即1时返回1，2时返回2）</li>
<li>推导：(n-1)层的结果 + (n-2)层的结果</li>
</ul>
<p>代码如下：</p>
<pre><code class="language-python">jump1 = lambda n: n if n&lt;=2 else jump1(n-2) + jump1(n-1)
</code></pre>
<p>变态跳台阶只是推导方式不同，每一层的结果是上一层跳法的2倍。</p>
<ul>
<li>出口：n &lt;= 2，返回n</li>
<li>推导：(n-1)层的结果 * 2</li>
</ul>
<p>代码如下：</p>
<pre><code class="language-python">jump2 = lambda n: n if n&lt;=2 else jump2(n-1)* 2
</code></pre>
<h3 id="快速排序">快速排序</h3>
<p>快速排序的是想是选一个基准数（如第一个数），将大于该数和小于该数的分成两块，然后在每一块中重复执行此操作，直到该块中只有一个数，即为有序。</p>
<ul>
<li>出口：列表长度为1（&lt;2）时，返回列表</li>
<li>选择一个数，（将小于该数的序列）排序结果+基准数 + （大于该数的序列）排序结果</li>
</ul>
<pre><code class="language-python">def quick_sort(l):
    iflen(l) &lt; 2:
         return l
    target = l# 以第一个数为基准数
    low_part, eq_part, high_part = [], , []
    for i in l:
      if i &lt; 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)
</code></pre>
<blockquote>
<p>注：eq_part中应包含基准数target。</p>
</blockquote>
<h3 id="二分查找">二分查找</h3>
<p>二分查找需要序列首先有序。思想是先用序列中间数和目标值对比，如果目标值小，则从前半部分（小于中间数）重复此查找，否则从后半部分重复此查找。</p>
<ul>
<li>出口1：中间数和目标数相同，返回中间数下标</li>
<li>出口2：列表为空，返回未找到</li>
<li>推导：</li>
</ul>
<pre><code class="language-python">def bin_search(l, n):
    if not l:
      return None
    mid = len(l) // 2
    if l == n:
      return mid
    if l &gt; n:
       return bin_search(l[:mid])
    returnbin_search(l)
</code></pre>
<h3 id="二叉树遍历">二叉树遍历</h3>
<p>二叉树是非常常考的一种数据结构。其基本结构就是一个包含数据和左右节点的一种结构，使用Python类描述如下：</p>
<pre><code class="language-python">class Node(object):
    def __init__(self, data, left=None, right=None):
      self.data = data
      self.left = left
      self.right = right
</code></pre>
<p>二叉树的遍历分为分层遍历（广度优先）和深度遍历（深度优先）两种，其中深度遍历又分为前序、中序、后序三种。</p>
<p>分层遍历由于每次处理多个节点，使用循环解决更加方便一点（也可以是使用递归解决）。<br>
分层遍历代码如下：</p>
<pre><code class="language-python">def lookup(root):
    row =
    while(row):
      print(row)
      row =
</code></pre>
<p>深度遍历</p>
<ul>
<li>出口：节点为None</li>
<li>推导：
<ul>
<li>前序：打印当前节点-》遍历左子树 -》遍历右子树</li>
<li>中序：遍历左子树 -》打印当前节点-》遍历右子树</li>
<li>后序：遍历左子树 -》遍历右子树-》打印当前节点</li>
</ul>
</li>
</ul>
<p>以前序为例：</p>
<pre><code class="language-python">def deep(root):
    if root is none:
      return
   
</code></pre>
<h3 id="二叉树最大深度">二叉树最大深度</h3>
<p>二叉树最大深度即其左子树深度和右子树深度中最大的一个加上1（当前节点）。由于二叉树的每一个左右节点都是一个二叉树，这种层层嵌套的结构非常适合使用递归求解。</p>
<ul>
<li>出口：节点为空，深度返回0</li>
<li>推导：左子树深度和右子树深度中最大的一个 + 1</li>
</ul>
<pre><code class="language-python">def max_depth(root):
    if not root:
      return 0
    return max() + 1
</code></pre>
<h3 id="相等二叉树判断">相等二叉树判断</h3>
<p>相等二叉树是只，一个二叉树，节点数据相同，左右子树也完全相同。由于左右子树也是一个二叉树，因此也可以使用递归求解。</p>
<ul>
<li>出口：最后的节点都为None时，两个相等，返回True</li>
<li>推导：判断两个节点数据是否相等，左子树是否相等（递归），右子树是否相等（递归）</li>
</ul>
<pre><code class="language-python">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)
</code></pre>
<h3 id="平衡二叉树判断">平衡二叉树判断</h3>
<p>平衡二叉树是指，一个二叉树的左右子树的高度差不超过1。平衡二叉树的左右子树也应该是平衡二叉树，因此这也是一个递归问题。</p>
<ul>
<li>出口：两个节点都为None时，返回True（平衡）</li>
<li>判断左子树和右子树深度的差&lt;=1，并且左右子树都是平衡二叉树（递归）</li>
</ul>
<blockquote>
<p>注：这里需要使用以上求二叉树深度的方法</p>
</blockquote>
<pre><code class="language-python">def max_depth(root):
    if not root:
      return 0
    return max() + 1

def is_balance_tree(root):
    if root is None:
      return True
    return abs(max_depth(root.left)-max_depth(root.right))&lt;=1 and is_balance_tree(root.left) and is_balance_tree(root.right)
</code></pre>
<h2 id="其他">其他</h2>
<h3 id="字符串统计">字符串统计</h3>
<pre><code>str1 = 'abcdaacddceea'
set1 = set(str1)
result = [(char, str1.count(char)) for char in set1]
print(result)
</code></pre>
<h3 id="统计重复最多的n个字符">统计重复最多的n个字符</h3>
<pre><code class="language-python">from collections import Counter
c = Counter('abcdaacddceea')
print(c.items())
print(c.most_common(3))
</code></pre>
<h3 id="字符串反转">字符串反转</h3>
<ul>
<li>简单字符串反转<br>
Python中字符串反转方式非常多，而且比较高效，可以使用反向切片或者reverse实现。</li>
</ul>
<pre><code class="language-python">'abcefg'[::-1]
</code></pre>
<p>或</p>
<pre><code class="language-python">''.join(reversed('abcdefg'))
</code></pre>
<ul>
<li>包含数字字母的字符串，仅反转字母<br>
可以通过遍历判断，如果是字母则取其对应反转索引位置的字母，如果是数字则取当前数字。</li>
</ul>
<pre><code class="language-python">a = 'abc123efg'
l = len(a)
r = []
for i,c in enumerate(a):
    r.append(c) if c.isdigit() else r.append(a)   
print(''.join(r))
</code></pre>
<h3 id="判断括号是否闭合">判断括号是否闭合</h3>
<p>这是栈使用的一个经典示例，思路为，遇到正括号则入栈，遇到反括号则和栈顶判断，如果匹配则匹配的正括号出栈（完成一对匹配），否则打印不匹配，break退出。</p>
<pre><code class="language-python">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 != stack.pop():# 如果不匹配弹出的栈顶元素
                return False
    return True

print(is_closed(text))
</code></pre>
<h3 id="合并两个有序列表并保持有序">合并两个有序列表，并保持有序</h3>
<p>常见的解法有两种：</p>
<ul>
<li>连接 + 排序，时间复杂度度为O((m+n)log2(m+n))</li>
<li>两个队列根据大小依次弹出，时间复杂度度约为O(m+n)</li>
</ul>
<p>依次出队列的逻辑为：</p>
<ul>
<li>队列1为空，队列2不为空，从队列2弹出一个数据</li>
<li>队列2为空，队列1不为空，从队列1弹出一个数据</li>
<li>两个都不为空，判断两个对队列顶端哪个小，从哪个列表弹出一个数据</li>
</ul>
<p>以下为使用Python列表模拟两个队列依次弹出的示例。<br>
由于Python列表尾部弹出list.pop()的的操作效率O(1)，比首部弹出list.pop(0)的操作效率O(n)更高，因此我们先按从大到小排序，最后在执行一次反转。</p>
<pre><code class="language-python">list1 =
list2 =
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] &gt; list2[-1] else result.append(list2.pop())# 弹出顶端大的数
result.reverse()# 执行反转
print(result)
</code></pre>
<h3 id="两个队列实现一个栈">两个队列实现一个栈</h3>
<p>队列是先入先出，栈是先入后出。<br>
使用两个队列实现栈的方式有很多种，主要分为优化入栈和优化出栈两种，以下为优化入栈的一种实现方法。</p>
<ul>
<li>入栈时直接存入队列q1</li>
<li>出栈时，将q1中元素依次放入q2, 直到最后一个元素，弹出元素，然后将q2中元素重新依次放回q1</li>
</ul>
<p>实现代码如下：</p>
<pre><code class="language-python">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() &gt; 1:
            self.q2.put(self.q1.get())
      value = self.q1.get()
      while not self.q2.empty():
            self.q1.put(self.q2.get())
      return value
</code></pre>
<p>测试代码：</p>
<pre><code class="language-python">s = Stack()
]
print(s.pop())
print(s.pop())
print(s.pop())
print(s.pop())
</code></pre>
<p>打印结果为：</p>
<pre><code>7
6
5
4
</code></pre><br><br>
来源：https://www.cnblogs.com/superhin/p/12468410.html

查看完整版本: Python自动化测试面试题-编程篇