前言

隨著行業(yè)的發(fā)展，編程能力逐漸成為軟件測(cè)試從業(yè)人員的一項(xiàng)基本能力。因此在筆試和面試中常常會(huì)有一定量的編碼題，主要考察以下幾點(diǎn)。

• 基本編碼能力及思維邏輯
• 基本數(shù)據(jù)結(jié)構(gòu)（順序表、鏈表、隊(duì)列、棧、二叉樹(shù)）
• 基本算法（排序、查找、遞歸）及時(shí)間復(fù)雜度

除基本算法之外，筆試面試中經(jīng)常會(huì)考察以下三種思想：

• 哈希
  
• 遞歸
  
• 分治
  

哈希

哈希即Python中的映射類型，字典和集合，鍵值唯一，查找效率高，序列（列表、元祖、字符串）的元素查找時(shí)間復(fù)雜度是O(n)，而字典和集合的查找只需要O(1)。
因此哈希在列表問(wèn)題中主要有兩種作用：

去重

優(yōu)化查找效率

例題1：列表去重#

列表去重在不考慮順序的情況下可以直接使用set()轉(zhuǎn)換（轉(zhuǎn)換后會(huì)自動(dòng)排序），需要保持順序可以使用字典構(gòu)建的fromkeys()方法，利用字典鍵值的唯一性去重。

不考慮順序：

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

運(yùn)行結(jié)果：

[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)

運(yùn)行結(jié)果：

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

例題2：分組

一串字母數(shù)字組合的字符串，找出相同的字母或數(shù)字，并按照個(gè)數(shù)排序。

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)

這里使用哈希的鍵值不重復(fù)性。當(dāng)然也可以使用python自帶的groupby函數(shù)，代碼如下：

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：海量數(shù)據(jù)找出top K的數(shù)據(jù)#

對(duì)于小數(shù)據(jù)量可以使用排序+切片，而對(duì)于海量數(shù)據(jù)，需要考慮服務(wù)器硬件條件。即要考慮時(shí)間效率，也要考慮內(nèi)存占用，同時(shí)還要考慮數(shù)據(jù)特征。如果大量的重復(fù)數(shù)據(jù)，可以先用哈希進(jìn)行去重來(lái)降低數(shù)據(jù)量。

這里我們使用生成器生成1000萬(wàn)個(gè)隨機(jī)整數(shù)，求最大的1000個(gè)數(shù)，生成隨機(jī)數(shù)的代碼如下：

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)

不限內(nèi)存可以直接使用set()去重+排序

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

1000w個(gè)數(shù)據(jù)會(huì)全部讀入內(nèi)存，set后列表自動(dòng)為遞增順序，使用切片取-1000到最后的即為top 1000的數(shù)

使用堆排可以節(jié)省一些內(nèi)存

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

這里是用來(lái)Python自帶的堆排庫(kù)heapq。使用nlargest(k,l)可以取到l序列，最大的k個(gè)數(shù)。

較小內(nèi)存可以分治策略，使用多線程對(duì)數(shù)據(jù)進(jìn)行分組處理（略）

例題4：兩數(shù)之和#

l=[1,2,3,4,5,6,7,8] 數(shù)據(jù)不重復(fù)，target=6，快速找出數(shù)組中兩個(gè)元素之和等于target 的數(shù)組下標(biāo)。

注意，不要使用雙重循環(huán)，暴力加和來(lái)和target對(duì)比，正確的做法是單層循環(huán)，然后查找target與當(dāng)前值的差，是否存在于列表中。

但是由于列表的in查詢時(shí)間復(fù)雜度是O(n)，即隱含了一層循環(huán)，這樣效率其實(shí)和雙重循環(huán)是一樣的，都是O(n^2)。

這里就可以使用哈希來(lái)優(yōu)化查詢差值是否在列表中操作，將O(n)降為O(1)，因此總體的效率就會(huì)變成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:  # 在集合中查找,為避免重復(fù)，判斷a為較小的那個(gè)值
    result.append((list1.index(a), list1.index(b)))  # 列表index取下標(biāo)的操作為O(1) 
print(result)

遞歸問(wèn)題

遞歸是一種循環(huán)調(diào)用自身的函數(shù)?？梢杂糜诮鉀Q以下高頻問(wèn)題：

• 階乘
• 斐波那切數(shù)列
• 跳臺(tái)階、變態(tài)跳臺(tái)階
• 快速排序
• 二分查找
• 二叉樹(shù)深度遍歷（前序、中序、后序）
• 求二叉樹(shù)深度
• 平衡二叉樹(shù)判斷
• 判斷兩顆樹(shù)是否相同

遞歸是一種分層推導(dǎo)解決問(wèn)題的方法，是一種非常重要的解決問(wèn)題的思想。遞歸可快速將問(wèn)題層級(jí)化，簡(jiǎn)單化，只需要考慮出口和每層的推導(dǎo)即可。

如階乘，要想求n!，只需要知道前一個(gè)數(shù)的階乘(n-1)!，然后乘以n即可，因此問(wèn)題可以轉(zhuǎn)為求上一個(gè)數(shù)的階乘，依次向前，直到第一個(gè)數(shù)。

舉個(gè)通俗的例子：

A欠你10萬(wàn)，但是他沒(méi)那么多錢，B欠A 8萬(wàn)，C欠B 7萬(wàn) C現(xiàn)在有錢。因此你要逐層找到C，一層一層還錢，最后你才能拿到屬于你的10萬(wàn)。

到此這篇關(guān)于Python自動(dòng)化測(cè)試筆試面試題精選的文章就介紹到這了,更多相關(guān)Python自動(dòng)化測(cè)試筆試面試時(shí)常見(jiàn)的編程題內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論