⬆️ 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?

Answer:

- For lookup, the worst time complexity of list and set is O(n), so it is the same.
- 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

Answer:

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

Answer:

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') b2 = Book('The Flask Book') print(id(b)) print(id(b2)) print(b.title) print(b2.title)

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

Answer:

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

Answer:

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

Answer:

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

Answer:

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

Answer:

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

Answer:

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

Answer:

Binary addition

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") print(binary_add(num1, num2))

For more common interview questions about Python programming, we will continue to share them later. Please pay attention.

In addition, contributions are welcome

"Golden feather" prize essay solicitation activity

, share your test and development technology learning, career growth stories and other wonderful topics in 2020.

Come to Hogwarts test and development society to learn more advanced technologies of software testing and test development. The knowledge points include web automated testing, app automated testing, interface automated testing, test framework, performance testing, security testing, continuous integration / continuous delivery / DevOps, test left, test right, precision testing, test platform development, test management, etc, The course technology covers bash, pytest, junit, selenium, appium, postman, requests, httprunner, jmeter, jenkins, docker, k8s, elk, sonarqube, Jacobo, JVM sandbox and other related technologies, so as to comprehensively improve the technical strength of test and development engineers