测试开发基础 | Python 算法与数据结构面试题系列一(附答案)
2023-09-11 14:14:52 时间
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 实现一个二分查找的函数
答:
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 pysnooper
from 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 编程常见面试题,我们后续继续分享,敬请关注。
相关文章
- Python脚本扫描给定网段的MAC地址表(scapy或 python-nmap)
- python类的继承
- 地球引擎初级教程——Python API 语法(内涵JavaScript转python工具包介绍)
- 超全Python学习路线图+14张思维导图,让python初学者不走弯路
- 中途转行python?怎么学?没有基础的我30了自学Python转行靠谱吗?
- 人生苦短,我用Python!为什么现在越来越多的人转行python?
- 35岁了转行python可以吗?什么样的人合适学习Python?
- 每天一个python小知识——如何在Python 3中转换数据类型
- 怎样在Python中查询一个类或一个对象有哪些属性(方法(成员函数)、变量)【用函数dir()】
- 实战 | 如何用 Python 自动化监控文件夹完成服务部署
- Python中python-nmap模块的使用
- gyp ERR! stack Error: Can‘t find Python executable “python“, you can set the PYTHON env variable.
- python之模块base64
- python数字图像处理(8):对比度与亮度调整
- 基于Python实现自然语言处理(主题层次的情感分类)【100010252】
- 【赶快收藏】15道Python常见面试题及答案!
- 安装MySQL-python
- python进程绑定CPU的一些Demo
- 一道简单的python面试题-购物车
- 老男孩上海校区Python面试题
- python五十五课——calendar模块
- 【python百度智能云】:Python — 三种获取__VIEWSTATE、__VIEWSTATEGENERATOR、__EVENTVALIDATION方法。
- 【数字信号处理】——Python频谱绘制
- Python基础题
- Python入门学习笔记第九章——类~~~