preamble
With the development of the industry, programming ability has gradually become a basic ability of software testing practitioners. Therefore, there are often a certain amount of coding questions in written tests and interviews, mainly examining the following points.
- Basic coding skills and logical thinking
- Basic data structures (sequential tables, chained tables, queues, stacks, binary trees)
- Basic algorithms (sort, find, recursion) and time complexity
In addition to basic algorithms, the following three ideas are often examined in written interviews:
- hash (computing)
- recursive (calculation)
- partition
hash (computing)
Hash i.e. mapping type in Python, dictionaries and collections, key value is unique, lookup is efficient, time complexity of element lookup for sequences (lists, meta-ancestors, strings) is O(n), whereas lookup for dictionaries and collections takes only O(1).
Thus hashing has two main roles in the list problem:
de-emphasize
Optimize search efficiency
Example 1: List de-duplication#
List de-emphasis can be converted directly using set() without considering the order (the conversion will be automatically sorted), and the need to maintain the order can be used to de-emphasize using the dictionary constructed fromkeys() method, which takes advantage of the uniqueness of the dictionary keys and values.
No order is considered:
l = [2,1,2,3,4,5,6,6,5,4,3,2,1] result = list(set(l)) print(result)
Run results:
[1, 2, 3, 4, 5, 6]
Consider the order:
l = [2,1,2,3,4,5,6,6,5,4,3,2,1]
result = list({}.fromkeys(l).keys())
print(result)
Run results:
[2, 1, 3, 4, 5, 6]
Example 2: Grouping
A string of alphanumeric combinations, find identical letters or numbers and sort them by number.
l = [1,2,3,'a','b','c',1,2,'a','b',3,'c','d','a','b',1] set1 = set(l) result = [(item, (item)) for item in set1] (key=lambda x:x[1], reverse=True) print(result)
Here the key-value non-repeatability of the hash is used. Of course, you can also use python's own groupby function, the code is as follows:
from itertools import groupby l = [1,2,3,'a','b','c',1,2,'a','b',3,'c','d','a','b',1] (key=lambda x: str(x)) # Sorting is required before grouping result = [] for item, group in groupby(l, key=lambda x: str(x)): ((item, len(list(group)))) (key=lambda x:x[1], reverse=True) print(result)
Example 3: Finding the top K of data in a huge amount of data#
For small data volume you can use sorting + slicing, while for massive data, you need to consider the server hardware conditions. That is, it is necessary to consider the time efficiency, but also to consider the memory occupation, and also to consider the data characteristics. If a large amount of duplicate data, you can first use hash for de-duplication to reduce the amount of data.
Here we are using generator to generate 10 million random integers to find the maximum 1000 numbers, the code to generate random numbers is as follows:
import random
import time
n = 10000 * 1000
k = 1000
print(n)
def gen_num(n):
for i in range(n):
yield (0, n)
l = gen_num(n)
Unlimited memory can directly use set() to de-dupe + sort
start = () l = list(set(l)) result = l[-k:] () print(()-start)
All 1000w data will be read into memory, the list will automatically be in ascending order after the set, use slicing to take -1000 to the last that is the top 1000 numbers.
Using heap rows can save some memory
start = () result = (k, l) print(()-start)
Here is used Python's own heap scheduling library, heapq. Using nlargest(k,l) you can take a sequence of l, the largest number k.
Smaller memory allows for partitioning strategies, using multiple threads to group data (omitted)
Example 4: Sum of two numbers#
l=[1,2,3,4,5,6,7,8] The data is not duplicated and target=6, quickly find the subscript of the array where the sum of two elements in the array is equal to target.
Note that instead of using a double loop and violently summing to compare to target, the correct approach is to have a single loop and then look for the difference between target and the current value, whether or not it exists in the list.
But since the in query time complexity of lists is O(n), i.e., a layer of loops is implied, this is actually the same efficiency as a double loop, both are O(n^2).
Here it is possible to use hashing to optimize whether the query difference operates in a list, reducing O(n) to O(1), so the overall efficiency becomes O(n^2)->O(n).
l = [1,2,3,4,5,6,7,8]
set1 = set(list1) # Use of collections has facilitated searching
target = 6
result = []
for a in list1:
b = target - a
if a < b < target and b in set1: # Look up in the set, and to avoid duplication, determine a to be the smaller value.
(((a), (b))) # The operation of taking subscripts from listindex is O(1)
print(result)
recursive problem
Recursion is a function that calls itself in a loop. It can be used to solve the following high-frequency problems:
- the factorial of a number, e.g. 5! = 5.4.3.2.1 = 120
- Fibonacci sequence
- Jumping Steps, Perverted Jumping Steps
- rapid sorting
- binary search
- Binary tree depth traversal (preorder, middle order, postorder)
- Finding the depth of a binary tree
- balanced binary tree judgment
- Determine if two trees are the same
Recursion is a method of hierarchical derivation of a problem, a very important problem solving idea. Recursion can quickly cascade and simplify a problem by considering only the exit and the derivation at each level.
As in the case of factorial, to find n!, it is only necessary to know the factorial of the previous number (n-1)! , and then multiply by n. Thus the problem can be turned around to find the factorial of the previous number, in order forward, up to the first number.
To give a layman's example:
A owes you 100,000 but he doesn't have that much, B owes A 80,000, C owes B 70,000 C has money now. So you have to find C one layer at a time and pay him back one layer at a time, and finally you get your 100k.
To this article on the Python automation testing written interview questions selected article is introduced to this, more related Python automation testing written interview interviews common programming questions content please search my previous posts or continue to browse the following related articles I hope that you will support me in the future more!