# Fundamentals of test development | Python algorithm and data structure interview question series I (with answers)

⬆️ Pay attention to @ Hogwarts test institute official account, reply "interview", receive BAT big factory test interview real album.

#### 1. Time complexity

Known alias = [1, 2, 3], BSet = {1, 2, 3}
(1) Find 4 from list and BSet. Which is the worst time complexity? (2) Insert 4 from AList and BSet. Which is the worst time complexity?

1. For lookup, the worst time complexity of list and set is O(n), so it is the same.
2. The worst time complexity of list operation insertion is o(n), and the set is o(1), so Alist is large. Set is a hash table, so the operation complexity is basically o(1).

#### 2. Implement a binary search function in 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. Implementation method of Python singleton mode

There are many ways to implement singleton mode. When talking about metaclasses, we used call method to implement a singleton mode. In addition, Python module is a natural singleton mode. Here we use new
Keyword to implement a singleton pattern.

The simple singleton mode is realized through the new function.

```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')
print(id(b))
print(id(b2))
print(b.title)
print(b2.title)
```

#### 4. Implement a Fibonacci sequence using Python

Fibonacci sequence: the sequence starts from item 3, and each item is equal to the sum of the first two items.

```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. Find duplicate numbers in the list

Idea: scan from beginning to end. As long as the current element value is different from the subscript, make a judgment. If numbers[i] is equal to numbers[numbers[i]], it is considered that a duplicate element is found and returned
true； Otherwise, swap the two and continue the cycle. Until the end, no duplicate elements were found.

```# -*- 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:
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. Find a single number in the list

```def find_single(l :list):
result = 0
for v in l:
result ^= v
if result == 0:
print("No single element")
else :
print("Single element", result)

if __name__ == '__main__':
l = [1, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6]
find_single(l)
```

#### 7. Write a bubble sort

```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. Write a quick sort

```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  # Move cursor left
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. Write a topological sort

The topological sorting corresponding to the graph. Every directed acyclic graph has at least one topological ordering.

```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]:  # Find the value according to the key, that is, the child node
in_degrees[v] += 1  # Add 1 to the penetration of the obtained child nodes
# Results after the loop ends: {a ': 0,' B ': 1,' C ': 1,'d': 2, 'e': 1, 'f': 4}
Q = [u for u in graph if in_degrees[u] == 0]  # Nodes with penetration of 0
in_degrees_zero = []
while Q:
u = Q.pop()  # Remove from last by default
in_degrees_zero.append(u)  # Nodes with storage penetration of 0
for v in graph[u]:
in_degrees[v] -= 1  # Delete a node with a penetration of 0 and remove its point
if in_degrees[v] == 0:
Q.append(v)
return in_degrees_zero

if __name__ == '__main__':
# The key value of the dictionary is used to represent the relationship between the nodes of the graph, and the key is the current node. The value is the subsequent node.
graph_dict = {
'a': 'bf',  # Indicates that a points to b and f
'b': 'cdf',
'c': 'd',
'd': 'ef',
'e': 'f',
'f': ''}

t = topological_sort(graph_dict)
print(t)
```

#### 10. Python implements a binary calculation

```def binary_add(a:str, b: str):
return bin(int(a, 2) + int(b, 2))[2:]

if __name__ == '__main__':
num1 = input("Enter the first number in binary format:\n")
num2 = input("Enter the second number in binary format:\n")