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