软件测试 / 测试开发丨 Python 算法与数据结构面试题

作者：测试人

2023-04-14
北京
本文字数：2622 字
阅读完需：约 9 分钟

获取更多相关知识

1. 时间复杂度问题

已知 AList = [1, 2, 3]，BSet = {1, 2, 3} (1)从 AList 和 BSet 中查找 4，最坏时间复杂度哪个大？(2)从 AList 和 BSet 中插入 4，最坏时间复杂度哪个大？

答:

对于查找，列表和集合的最坏时间复杂度都是 O(n)，所以一样的。
列表操作插入的最坏时间复杂度为 o(n), 集合为 o(1)，所以 Alist 大。set 是哈希表所以操作的复杂度基本上都是 o(1)。

2. 用 Python 实现一个二分查找的函数

答:

def binary_search(arr, target):    n = len(arr)    left = 0    right = n - 1    while left <= right :    mid = (left + right) // 2    if arr[mid] < target:        left = mid + 1    elif arr[mid] > target:        right = mid - 1    else :        print(f"index:{mid},value:{arr[mid]}")        return True    return False
if __name__ == '__main__':    l = [1, 3, 4, 5, 6, 7, 8]    binary_search(l, 8)

复制代码

3. Python 单例模式的实现方法

答:

实现单例模式的方法有多种，之前再说元类的时候用 call 方法实现了一个单例模式，另外 Python 的模块就是一个天然的单例模式，这里我们使用 new 关键字来实现一个单例模式。

通过 new 函数实现简单的单例模式。

class Book:    def __new__(cls, title):        if not hasattr(cls, "_ins"):            cls._ins = super().__new__(cls)            print('in __new__')        return cls._ins
    def __init__(self, title):        print('in __init__')        super().__init__()        self.title = title
if __name__ == '__main__':    b = Book('The Spider Book')    b2 = Book('The Flask Book')    print(id(b))    print(id(b2))    print(b.title)    print(b2.title)

复制代码

4. 使用 Python 实现一个斐波那契数列

答:

斐波那契数列:数列从第 3 项开始，每一项都等于前两项之和。

def fibonacci(num):    a, b = 0, 1    l = [a, b]    for i in range(num):        a, b = b, a + b        l.append(b)    return l
if __name__ == '__main__':    print(fibonacci(10))

复制代码

5. 找出列表中的重复数字

答:

思路：从头扫到尾，只要当前元素值与下标不同，就做一次判断，numbers[i] 与 numbers[numbers[i]] 相等就认为找到了重复元素，返回 true；否则就交换两者，继续循环。直到最后还没找到认为没找到重复元素。

# -*- coding:utf-8 -*-class Solution:    def duplicate(self, numbers):        if numbers is None or len(numbers) <= 1:            return False        use_set = set()        duplication = {}        for index, value in enumerate(numbers):            if value not in use_set:                use_set.add(value)            else:                duplication[index] = value        return duplication
if __name__ == '__main__':    s = Solution()    d = s.duplicate([1, 2, -3, 4, 4, 95, 95, 5, 2, 2, -3, 7, 7, 5])    print(d)

复制代码

6. 找出列表中的单个数字

答:

def find_single(l :list):    result = 0    for v in l:        result ^= v        if result == 0:            print("没有落单元素")        else :            print("落单元素", result)
if __name__ == '__main__':    l = [1, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6]    find_single(l)

复制代码

7. 写一个冒泡排序

答:

def bubble_sort(arr):    n = len(arr)    for i in range(n - 1):        for j in range(n - i - 1):.            if arr[j] > arr[j + 1]:                arr[j], arr[j + 1] = arr[j + 1], arr[j]
if __name__ == '__main__':    l = [1, 2, 3, 4, 5, 55, 6, 3, 4, 5, 6]    bubble_sort(l)    print(l)

复制代码

8. 写一个快速排序

答:

def quick_sort(arr, first, last):    if first >= last:    return    mid_value = arr[first]    low = first    high = last    while low < high:        while low < high and arr[high] >= mid_value:            high -= 1  # 游标左移            arr[low] = arr[high]
    while low < high and arr[low] < mid_value:        low += 1        arr[high] = arr[low]        arr[low] = mid_value
quick_sort(arr, first, low - 1)quick_sort(arr, low + 1, last)
if __name__ == '__main__':    l = [1, 2, 3, 4, 5, 55, 6, 3, 4, 5, 6]    quick_sort(l, 0, len(l) - 1)    print(l)

复制代码

9. 写一个拓扑排序

答:

对应于该图的拓扑排序。每一个有向无环图都至少存在一种拓扑排序。

import pysnooperfrom typing import Mapping
@pysnooper.snoop()def topological_sort(graph:Mapping):# in_degrees = {'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0}    in_degrees = dict((u, 0) for u in graph)    for u in graph:        for v in graph[u]:  # 根据键找出值也就是下级节点            in_degrees[v] += 1  # 对获取到的下级节点的入度加 1    # 循环结束之后的结果: {'a': 0, 'b': 1, 'c': 1, 'd': 2, 'e': 1, 'f': 4}    Q = [u for u in graph if in_degrees[u] == 0]  # 入度为 0 的节点    in_degrees_zero = []    while Q:        u = Q.pop()  # 默认从最后一个移除        in_degrees_zero.append(u)  # 存储入度为 0 的节点        for v in graph[u]:            in_degrees[v] -= 1  # 删除入度为 0 的节点，以及移除其指向            if in_degrees[v] == 0:            Q.append(v)    return in_degrees_zero
if __name__ == '__main__':# 用字典的键值表示图的节点之间的关系，键当前节点。值是后续节点。    graph_dict = {            'a': 'bf',  # 表示 a 指向 b 和 f            'b': 'cdf',            'c': 'd',            'd': 'ef',            'e': 'f',            'f': ''}
    t = topological_sort(graph_dict)    print(t)

复制代码

10. Python 实现一个二进制计算

答:

二进制加法

def binary_add(a:str, b: str):    return bin(int(a, 2) + int(b, 2))[2:]
if __name__ == '__main__':    num1 = input("输入第一个数，二进制格式:\n")    num2 = input("输入第二个数，二进制格式:\n")    print(binary_add(num1, num2))

复制代码

更多 Python 编程常见面试题，我们后续继续分享，敬请关注。

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/d6028b16dcccfb4b23226f46b】。文章转载请联系作者。

测试人

关注

专注于软件测试开发 2022-08-29 加入

霍格沃兹测试开发学社，测试人社区：https://ceshiren.com/t/topic/22284

发布

暂无评论

创作场景

软件测试 / 测试开发丨 Python 算法与数据结构面试题

获取更多相关知识

1. 时间复杂度问题

2. 用 Python 实现一个二分查找的函数

3. Python 单例模式的实现方法

4. 使用 Python 实现一个斐波那契数列

5. 找出列表中的重复数字

6. 找出列表中的单个数字

7. 写一个冒泡排序

8. 写一个快速排序

9. 写一个拓扑排序

10. Python 实现一个二进制计算

测试人

评论