50 Python Interviwe Questions and Answers
This post was written by Cameron Wilson, and was originally published at Educative.io 中文翻译由Roy在cx4首发，如需转载请注明出处。
这篇文章涵盖有关Python编程语言的50个面试问题。
基础部分
- list和tuple的区别是什么？
- 怎样转换list为tuple？
- array和list的区别是什么？
- Python是怎样进行内存管理的？
- 如何在Python中实现多线程？
- 什么是monkey patching？
- 什么是lambda函数，举例说明什么时候用匿名函数更好，什么时候不行？
- 什么是pickling和unpickling?
- 与嵌套列表相比Numpy数组有什么优势？
- 举例说明Python的继承。
- python中的多态是什么？
- 举例说明range()和xrange()的区别。
- 举例说明Flask和Django的区别。
- 什么是PYTHONATH？
- 什么是PEP8？
- 什么是Python装饰器？
- 什么是init?
- 什么是三元运算符？
- 什么是全局变量和局部变量？
- 什么是@property?
- try/except在python中是怎样使用的？
- 举例说明Python2和Python3的区别。
- 什么是join方法？
- 什么是字典理解？
- 怎样做一次深度copy？
- 怎样检查一个键是否在字典中？
- 如何在Python中实现记忆优化？
- 在Python中如何实现字典排序？
- 什么时候使用any()和all(),如何使用？
- 什么是python的文档字符串？
- 写一个python的函数并举例说明它是怎样运行的。
- 举例说明迭代器和生成器在Python中的区别。
- Python中的defaultdict是什么？
- 什么是python的库？
- 怎样转换一个list为array？
代码部分
- 反转字符串
- 检查一个字符串是否在另外一个字符串中
- 在Python中实施广度优先搜索（BFS）
- 在Python中实现深度优先搜索(DFS)
- 实现通配符
- 在Python中实施合并排序
- 在Python中实现Dijkstra算法
- 合并两个排序列表
- 寻找两个和为‘K’的数字
- 找到列表中第一个非重复整数
- 查找链接列表的中间值
- 颠倒队列中的前“k”个元素
- 查找二叉搜索树（BST）的高度
- 将最大堆转换为最小堆
- 检测链表中的循环
1. list和tuple的区别
| List | Tuple |
|---|---|
| 列表由可变对象组成。 （创建后可以更改的对象） | 元组由不可变的对象组成。 （创建后无法更改的对象） |
| 列表占用很大的内存。 | 元组占用的内存很小。 |
| 列表存储在两个内存块中（一个是固定大小的，另一个是可变大小的，用于存储数据） | 元组存储在单个内存块中。 |
| 创建列表的速度较慢，因为需要访问两个内存块。 | 创建元组比创建列表快。 |
| 列表中的元素可以删除或替换。 | 元组中的元素无法删除或替换。 |
| 列表中的数据存储在[]括号中。例如[1,2,3] | 元组的数据存储在（）括号中。例如（1,2,3） |
只要用户知道在元组中插入了什么，就应该使用元组。假设一所大学将其学生的信息存储在一个数据结构中；为了使此信息保持不变，应将其存储在元组中。由于列表为用户提供了更方便的可访问性，因此在需要存储类似类型的对象时应使用它们。例如，如果杂货店需要将所有乳制品存储在一个字段中，则应使用一个列表。
2. 您如何将列表转换为元组？
1 | |
3. 数组和列表的区别是什么？
| List | Array |
|---|---|
| Python列表非常灵活，可以保存任意数据。 | Python数组只是C数组的一个薄包装。 |
| 列表是Python语法的一部分，因此不需要首先声明它们。 | 首先需要从其他库（即numpy）中导入或声明数组。 |
| 列表还可以以省时的方式快速调整大小。这是因为Python在初始化时会初始化列表中的一些额外元素。 | 数组无法调整大小。相反，需要将一个数组的值复制到另一个更大的数组中。 |
| 列表可以保存异构数据。 | 数组只能存储同质数据。它们的值具有统一的数据类型。 |
| 数学函数不能直接应用于列表。相反，必须将它们分别应用于每个元素。 | 数组是专门为算术计算而优化的。 |
| 由于为列表分配了一些额外的元素，因此可以消耗更多的内存，从而可以更快地附加项目。 | 由于数组保持其首次初始化时的大小，因此它们是紧凑的。 |
4. 如何在Python中管理内存？
- python中的内存管理由Python专用堆空间管理。所有Python对象和数据结构都位于私有堆中。程序员无权访问此私有堆。 python解释器代替了它。
- Python对象的堆空间分配是由Python的内存管理器完成的。核心API允许访问一些工具，以便程序员进行编码。
- Python还具有一个内置的垃圾收集器，该垃圾收集器回收所有未使用的内存，并使其可用于堆空间。
5. 如何在Python中实现多线程？
- Python有一个多线程程序包，但是如果您想使用多线程来加快代码速度，那么使用它通常不是一个好主意。
- Python具有称为全局解释器锁（GIL）的构造。 GIL确保您的“线程”只能在任何一次执行。线程获取GIL，做一些工作，然后将GIL传递到下一个线程。
- 这发生得非常快，因此在人眼看来，您的线程似乎是并行执行的，但实际上它们只是使用相同的CPU内核轮流执行。
- 所有这些GIL传递都会增加执行开销。这意味着，如果您想使代码运行更快，那么使用线程包通常不是一个好主意。
6. 什么是猴子修补？
在Python中，术语“monkey patch”仅指运行时对类或模块的动态修改。7. 什么是lambda函数？举例说明什么时候有用，什么时候没用。
Lambda函数是一个小的匿名函数，它返回一个对象。
lambda返回的对象通常被分配给变量或用作其他较大函数的一部分。
lambda函数不是用于创建函数的常规def关键字，而是使用lambda关键字定义。
lambda的结构如下所示:
使用lambda的目的：
- Lambda比完整功能更具可读性，因为它可以内联编写。因此，当函数表达式较小时，最好使用lambda。
- lambda函数的优点在于它们返回函数对象。
- 当与要求函数对象作为参数的map或filter等函数一起使用时，这使它们很有用。
- 当表达式超过一行时，Lambda无效。
8. 什么是pickling和unpickling?
Pickle模块接受任何Python对象并将其转换为字符串表示形式，然后使用转储函数将其转储到文件中，此过程称为pickling。
从存储的字符串表示形式检索原始Python对象的过程称为unpickling。9. 与（嵌套）Python列表相比，NumPy数组有什么优势？
- Python的列表是有效的通用容器。
它们支持（相当）高效的插入，删除，附加和连接，并且Python的列表表达式使它们易于构造和操作。 - 它们有一定的局限性：它们不支持“向量化”操作，例如逐元素加法和乘法，并且它们可以包含不同类型的对象这一事实意味着Python必须存储每个元素的类型信息，并且在操作时必须执行类型调度代码在每个元素上。
- NumPy不仅效率更高，也更加方便。您可以免费获得许多矢量和矩阵运算，避免不必要的工作。
- NumPy数组更快，您可以使用NumPy，FFT，卷积，快速搜索，基本统计信息，线性代数，直方图等内置大量内容。
10. 举例说明Python中的继承
继承允许一个类获取另一类的所有成员（例如属性和方法）。
继承提供了代码可重用性，使创建和维护应用程序变得更加容易。
我们从中继承的类称为超类，而继承的类称为派生/子类。 - 单一继承：派生类获取超类的单个成员。
- 多级继承：从超类A继承的派生类A1，和从B类继承的B2
- 层次继承：从一个超类可以继承任意数量的子类。
- 多重继承：派生类继承自多个超类。
11. Python中的多态是什么？
多态是指采取多种形式的能力。
因此，例如，如果父类具有一个名为ABC的方法，那么子类也可以具有一个具有相同名称和参数的ABC方法。
Python允许多态。
12. 解释range（）和xrange（）之间的区别
在大多数情况下，xrange和range在功能方面完全相同。
它们都提供了一种生成整数列表供您使用的方法。
唯一的区别是range返回一个Python列表对象，而xrange返回一个xrange对象。
这意味着xrange实际上不会像range那样在运行时生成静态列表。
它通过一种称为yield的特殊技术根据需要创建值。
该技术与一种称为生成器的对象一起使用。
13. 解释Flask和Django之间的区别
Django是一个Python网络框架，提供了一个开放源代码的高级框架，“鼓励快速开发和简洁实用的设计”。
快速，安全且可扩展。Django提供了强大的社区支持和详细的文档。
该框架是一个包容性软件包，在您创建应用程序时，您将在其中获得管理面板，数据库界面和目录结构。
此外，它包括许多功能，因此您不必添加单独的库和依赖项。
它提供的一些功能包括用户身份验证，模板引擎，路由，数据库模式迁移等等。
Django框架非常灵活，您可以在其中与大型公司的MVP一起使用。
从某些角度来看，使用Django的一些最大的公司是Instagram，Dropbox，Pinterest和Spotify。
Flask被认为是一个微框架，是一个简约的Web框架。
它电量较低，这意味着它缺少Django等全栈框架提供的许多功能，例如网络模板引擎，帐户授权和身份验证。
Flask极简且轻巧，这意味着您可以在编写代码时添加所需的扩展和库，而不会被框架自动提供。
Flask背后的理念是，它仅提供构建应用程序所需的组件，因此您具有灵活性和控制力。
换句话说，它是不受限制的。
它提供的一些功能包括：一个内置int开发服务器，Restful请求分派，Http请求处理等等。
14. 什么是PYTHONPATH？
它是环境变量，在导入模块时使用。
每当导入模块时，都会查找PYTHONPATH以检查各个目录中是否存在导入的模块。
解释器使用它来确定要加载哪个模块。
15. 什么是PEP8？
PEP代表Python增强提案。
这是一组规则，用于指定如何格式化Python代码以实现最大的可读性。
16. 什么是Python装饰器？
装饰器是Python中的一种设计模式，允许用户在不修改其结构的情况下向现有对象添加新功能。
装饰器通常在要装饰的函数定义之前调用。
17. 什么是初始化init
_init__是Python中的方法或构造函数。
创建类的新对象/实例时，将自动调用此方法以分配内存。
所有类都具有init方法。
18. 什么是三元运算符？
三元运算符是用Python编写条件语句的一种方式。
顾名思义，此Python运算符由三个操作数组成。
注意：三元运算符可以看作是if-else语句的简化的单行版本，用于测试条件。
语法：
三元表达式包含三个操作式：
- 条件语句：一个布尔表达式，其值为true或false
- true_val:如果表达式的计算结果为true，则将分配一个值。
- false_val: 如果表达式的结果为false，则分配一个值。
1
var = true_val if condition else false_val
19. Python中的全局变量和局部变量是什么？
全局变量
在函数外部或全局空间中声明的变量称为全局变量。
程序中的任何函数都可以访问这些变量。
局部变量
在函数内部声明的任何变量都称为局部变量。
此变量存在于局部空间而不是全局空间中。
20. Python中的@property是什么？
@property是一个装饰器。
在Python中，装饰器使用户能够以相同的方式使用该类（而不管对其属性或方法所做的更改）。
@property装饰器允许像属性一样访问函数。
21. 在Python中如何使用try/except？
异常是程序执行时发生的错误。
发生错误时，程序将停止并生成异常，捕捉异常然后对其进行处理，以防止程序崩溃。
程序生成的异常在try块中捕获，并在except块中处理。
22. 解释Python 2和Python 3之间的区别
| Python2 | Python3 |
|---|---|
| 字符串编码Python 2将它们存储为ASCII。Unicode是ASCII的超集，因此可以编码更多字符，包括外来字符。 | 字符串编码Python 3默认将字符串存储为Unicode。 |
| Python 2除法将floor函数应用于十进制输出并返回整数。因此，将5除以2将返回floor（2.5）= 2。 | Python 3中的除法返回期望的输出，即使它是十进制的。 |
| Python 2打印不需要括号。 | Python3需要在要打印的内容周围加上括号。 |
| 许多较旧的库是专门为Python 2构建的，并不“向上兼容”。 | 一些较新的库是专门为Python 3构建的，不适用于Python 2。 |
23. python中的join方法是什么？
Python中的join方法采用可迭代数据结构的元素，并使用特定的字符串连接器值将它们连接在一起。
join是如何工作的？
Python中的join方法是一个字符串方法，它通过使用特定的字符串作为连接器来连接字符串可迭代结构的元素，该结构还包含字符串或字符（数组，列表等）。
24. 什么是字典？
字典表达式是在Python中创建字典的一种方法。
它通过合并以列表或数组形式的两组数据来创建字典。
两个列表/数组之一的数据将作为字典的键，而第二个列表/数组的数据将作为值。
每个键充当每个值的唯一标识符，因此两个列表/数组的大小应相同。
1 | |
25. 您将如何在Python中进行深层复制？
深拷贝是指克隆对象。
当使用=运算符时，我们不克隆对象；
相反，我们将变量引用到相同的对象（也称为浅表副本）。
这意味着更改一个变量的值会影响另一个变量的值，因为它们引用（或指向）同一对象。
浅表副本与深表副本之间的区别仅适用于包含其他对象的对象，例如列表和类的实例。
方法
此函数将要克隆的对象作为唯一参数，并返回克隆。
语法
此函数将要克隆的对象作为唯一参数，并返回克隆。
1 | |
1 | |
26. 如何检查Python字典中是否存在键？
一种安全的做法是在提取该键的值之前检查该键是否在字典中存在。
为此，Python提供了两个内置函数：has_key()
如果字典中有给定的键，则has_key方法返回true；否则，返回true。
否则，它返回false。if-in表达式
此方法使用if-in语句检查字典中是否存在给定键。
1 | |
27. 您将如何在Python中实现记忆化？
对于计算量比较大的代码：
1 | |
记忆化可以通过Python装饰器实现
这是完整的实现。
1 | |
28. 您将如何在Python中对字典进行排序？
我们可以通过键或值对这种类型的数据进行排序，这可以通过使用sorted（）函数来完成。
首先，我们需要知道如何从字典中检索数据以传递给该函数。
有两种从字典中获取数据的基本方法：
- Dictionary.keys（）：仅以任意顺序返回键。
- Dictionary.values（）：返回值列表。
- Dictionary.items（）：返回所有数据作为键值对列表。
Sorted（）语法
此方法采用一个强制性参数和两个可选参数：
数据（必填）：要排序的数据。
我们将使用上述方法之一传递我们检索到的数据。
键（可选）：我们要根据其对列表进行排序的功能（或条件）。
例如，条件可以是根据字符串的长度或任何其他任意函数对字符串进行排序。
此功能应用于列表的每个元素，并对结果数据进行排序。
将其保留为空将根据其原始值对列表进行排序。
反向（可选）：将第三个参数设置为true将按降序对列表进行排序。
保留此空的升序排列。keys()
1 | |
dict = {}
dict[‘1’] = ‘apple’
dict[‘3’] = ‘orange’
dict[‘2’] = ‘pango’
lst = dict.values()
#Sorted by value
print(“Sorted by value: “, sorted(lst))
1 | |
dict = {}
dict[‘1’] = ‘apple’
dict[‘3’] = ‘orange’
dict[‘2’] = ‘strawberry’
lst = dict.items()
Sorted by key
print(“Sorted by key: “, sorted(lst, key = lambda x : x[0]))
#Sorted by value
print(“Sorted by value: “, sorted(lst, key = lambda x : x[1]))
1 | |
one_truth = [True, False, False]
three_lies = [0, ‘’, None]
print(any(one_truth))
print(any(three_lies))
1 | |
all_true = [True, 1, ‘a’, object()]
one_true = [True, False, False, 0]
all_false = [None, ‘’, False, 0]
print(all(all_true))
print(all(one_true))
print(all(all_false))
1 | |
def Examplefunc(str): #function that outputs the str parameter
print(“The value is”, str)
#no return statement needed in this function
def Multiply(x,y): #function that computes the product of x and y
return x*y #returning the product of x and y
#Calling the functions
Examplefunc(9) #9 passed as the parameter)
answer = Multiply(4,2) #4 and 2 passed as the parameters
print(“The product of x and y is:”,answer)
1 | |
Function to generate all the non-negative numbers
up to the given non-negative number.
class UpTo:
# giving the parameter a default value of 0
def init(self, max = 0):
self.max = max
def iter(self):
self.n = 0
return self
def next(self):
# The next method will throw an
# exception when the termination condition is reached.
if self.n > self.max:
raise StopIteration
else:
result = self.n
self.n += 1
return result
for number in UpTo(5):
print(number)
1 | |
Function to generate all the non-negative numbers
up to the given non-negative number
def upto(n):
for i in range(n+1):
# The yield statement is what makes a function
# a generator
yield i
for number in upto(5):
print(number)
1 | |
dict_demo = dict()
print(dict_demo[3])
1 | |
from collections import defaultdict
defaultdict_demo = defaultdict(int)
print(defaultdict_demo[3])
Output: 0
1 | |
import numpy as np
my_list = [2,4,6,8,10]
my_array = np.array(my_list)
print(my_array)
print(type(my_array))
[2 4 6 8 10]
1 | |
string.find(substring)
a_string=”Python Programming”
substring1=”Programming”
substring2=”Language”
print(“Check if “+a_string+” contains “+substring1+”:”)
print(a_string.find(substring1))
print(“Check if “+a_string+” contains “+substring2+”:”)
print(a_string.find(substring2))
1 | |
graph = {
‘A’ : [‘B’,’C’],
‘B’ : [‘D’, ‘E’],
‘C’ : [‘F’],
‘D’ : [],
‘E’ : [‘F’],
‘F’ : []
}
visited = [] # List to keep track of visited nodes.
queue = [] #Initialize a queue
def bfs(visited, graph, node):
visited.append(node)
queue.append(node)
while queue:
s = queue.pop(0)
print (s, end = “ “)
for neighbour in graph[s]:
if neighbour not in visited:
visited.append(neighbour)
queue.append(neighbour)Driver Code
bfs(visited, graph, ‘A’)
Output: A B C D E
1 | |
Using a Python dictionary to act as an adjacency list
graph = {
‘A’ : [‘B’,’C’],
‘B’ : [‘D’, ‘E’],
‘C’ : [‘F’],
‘D’ : [],
‘E’ : [‘F’],
‘F’ : []
}
visited = set() # Set to keep track of visited nodes.
def dfs(visited, graph, node):
if node not in visited:
print (node)
visited.add(node)
for neighbour in graph[node]:
dfs(visited, graph, neighbour)
Driver Code
dfs(visited, graph, ‘A’)
Output: A B D E F C
1 | |
Regular expression library
import re
Add or remove the words in this list to vary the results
wordlist = [“color”, “colour”, “work”, “working”,
“fox”, “worker”, “working”]
for word in wordlist:
# The . symbol is used in place of ? symbol
if re.search(‘col.r’, word) :
print (word)
Output:color
1 | |
def mergeSort(myList):
if len(myList) > 1:
mid = len(myList) // 2
left = myList[:mid]
right = myList[mid:]
# Recursive call on each half
mergeSort(left)
mergeSort(right)
# Two iterators for traversing the two halves
i = 0
j = 0
# Iterator for the main list
k = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
# The value from the left half has been used
myList[k] = left[i]
# Move the iterator forward
i += 1
else:
myList[k] = right[j]
j += 1
# Move to the next slot
k += 1
# For all the remaining values
while i < len(left):
myList[k] = left[i]
i += 1
k += 1
while j < len(right):
myList[k]=right[j]
j += 1
k += 1myList = [54,26,93,17,77,31,44,55,20]
mergeSort(myList)
print(myList)
Output: [17, 20, 26, 31, 44, 54, 55, 77, 93]
1 | |
import sys
Function to find out which of the unvisited node
needs to be visited next
def to_be_visited():
global visited_and_distance
v = -10
Choosing the vertex with the minimum distance
for index in range(number_of_vertices):
if visited_and_distance[index][0] == 0
and (v < 0 or visited_and_distance[index][1] <=
visited_and_distance[v][1]):
v = index
return v
Creating the graph as an adjacency matrix
vertices = [[0, 1, 1, 0],
[0, 0, 1, 0],
[0, 0, 0, 1],
[0, 0, 0, 0]]
edges = [[0, 3, 4, 0],
[0, 0, 0.5, 0],
[0, 0, 0, 1],
[0, 0, 0, 0]]
number_of_vertices = len(vertices[0])
The first element of the lists inside visited_and_distance
denotes if the vertex has been visited.
The second element of the lists inside the visited_and_distance
denotes the distance from the source.
visited_and_distance = [[0, 0]]
for i in range(number_of_vertices-1):
visited_and_distance.append([0, sys.maxsize])
for vertex in range(number_of_vertices):
Finding the next vertex to be visited.
to_visit = to_be_visited()
for neighbor_index in range(number_of_vertices):
# Calculating the new distance for all unvisited neighbours
# of the chosen vertex.
if vertices[to_visit][neighbor_index] == 1 and
visited_and_distance[neighbor_index][0] == 0:
new_distance = visited_and_distance[to_visit][1]
+ edges[to_visit][neighbor_index]
# Updating the distance of the neighbor if its current distance
# is greater than the distance that has just been calculated
if visited_and_distance[neighbor_index][1] > new_distance:
visited_and_distance[neighbor_index][1] = new_distance
# Visiting the vertex found earlier
visited_and_distance[to_visit][0] = 1
i = 0
Printing out the shortest distance from the source to each vertex
for distance in visited_and_distance:
print(“The shortest distance of “,chr(ord(‘a’) + i),
“ from the source vertex a is:”,distance[1])
i = i + 1
Output:
The shortest distance of a from the source vertex a is: 0
The shortest distance of b from the source vertex a is: 3
The shortest distance of c from the source vertex a is: 3.5
The shortest distance of d from the source vertex a is: 4.5
1 | |
Merge list1 and list2 and return resulted list
def merge_lists(lst1, lst2):
index_arr1 = 0
index_arr2 = 0
index_result = 0
result = []
for i in range(len(lst1)+len(lst2)):
result.append(i)
# Traverse Both lists and insert smaller value from arr1 or arr2
# into result list and then increment that lists index.
# If a list is completely traversed, while other one is left then just
# copy all the remaining elements into result list
while (index_arr1 < len(lst1)) and (index_arr2 < len(lst2)):
if (lst1[index_arr1] < lst2[index_arr2]):
result[index_result] = lst1[index_arr1]
index_result += 1
index_arr1 += 1
else:
result[index_result] = lst2[index_arr2]
index_result += 1
index_arr2 += 1
while (index_arr1 < len(lst1)):
result[index_result] = lst1[index_arr1]
index_result += 1
index_arr1 += 1
while (index_arr2 < len(lst2)):
result[index_result] = lst2[index_arr2]
index_result += 1
index_arr2 += 1
return resultprint(merge_lists([4, 5, 6], [-2, -1, 0, 7]))
Output: [-2, -1, 0, 4, 5, 6, 7]
1 | |
def binarySearch(a, item, curr):
first = 0
last = len(a) - 1
found = False
index = -1
while first <= last and not found:
mid = (first + last) // 2
if a[mid] == item:
index = mid
found = True
else:
if item < a[mid]:
last = mid - 1
else:
first = mid + 1
if found:
return index
else:
return -1
def findSum(lst, k):
lst.sort()
for j in range(len(lst)):
# find the difference in list through binary search
# return the only if we find an index
index = binarySearch(lst, k -lst[j], j)
if index is not -1 and index is not j:
return [lst[j], k -lst[j]]
print(findSum([1, 5, 3], 2))
print(findSum([1, 2, 3, 4], 5))
Output:
None
[1,4]
1 | |
[9,2,3,2,6,6]
def findFirstUnique(lst):
counts = {} # Creating a dictionary
# Initializing dictionary with pairs like (lst[i],(count,order))
counts = counts.fromkeys(lst, (0,len(lst)))
order = 0
for ele in lst:
# counts[ele][0] += 1 # Incrementing for every repitition
# counts[ele][1] = order
counts[ele] = (counts[ele][0]+1 , order)
order += 1 # increment order
answer = None
answer_key = None
# filter non-repeating with least order
for ele in lst:
if (counts[ele][0] is 1) and (answer is None):
answer = counts[ele]
answer_key = ele
elif answer is None:
continue
elif (counts[ele][0] is 1) and (counts[ele][1] < answer[1]):
answer = counts[ele]
answer_key = ele
return answer_key
print(findFirstUnique([1, 1, 1, 2]))
Output: 2
1 | |
def minHeapify(heap, index):
left = index * 2 + 1
right = (index * 2) + 2
smallest = index
# check if left child exists and is less than smallest
if len(heap) > left and heap[smallest] > heap[left]:
smallest = left
# check if right child exists and is less than smallest
if len(heap) > right and heap[smallest] > heap[right]:
smallest = right
# check if current index is not the smallest
if smallest != index:
# swap current index value with smallest
tmp = heap[smallest]
heap[smallest] = heap[index]
heap[index] = tmp
# minHeapify the new node
minHeapify(heap, smallest)
return heap
def convertMax(maxHeap):
# iterate from middle to first element
# middle to first indices contain all parent nodes
for i in range((len(maxHeap))//2, -1, -1):
# call minHeapify on all parent nodes
maxHeap = minHeapify(maxHeap, i)
return maxHeap
maxHeap = [9, 4, 7, 1, -2, 6, 5]
print(convertMax(maxHeap))
Output: [-2, 1, 5, 9, 4, 6, 7]
```
说明
请记住，我们可以将给定的maxHeap视为元素的常规列表，并对其进行重新排序，以使其准确表示最小堆。
我们在此解决方案中正是这样做的。convertMax（）函数通过在每个父节点上调用minHeapify（）函数来从最低父节点还原所有节点上的堆属性。
时间复杂度minHeapify（）函数被调用堆中一半的节点。minHeapify（）函数花费O（log（n））时间，并被调用
50. 检测链表中的循环
说明
遍历整个链表，并将每个访问的节点添加到visit_nodes集合中。
在每个节点上，我们检查它是否已被访问。
原则上，如果重新访问节点，则存在一个循环！
时间复杂度
我们对列表进行一次迭代。
平均而言，集合中的查找需要O（1）时间。
因此，该算法的平均运行时间为O（n）。
但是，在最坏的情况下，查找可能会增加到O（n），这将导致算法在
- 本文标题：50-python-interview-questions-and-answers
- 本文作者：Roy
- 创建时间：2020-06-16 13:31:34
- 本文链接：https://www.yrzdm.com/2020/06/16/50-python-interview-questions-and-answers/
- 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！