Tester's algorithm interview question - find mode

Algorithm interview — Find the mode

Premise :
Now the interview of test engineer , More or less, I will ask about programming technology . In programming technology , Often choose a simple algorithm problem . Many students see this , Often I don't know what to do . If the consequences are light, the salary will be reduced , The most important thing is to lose this interview .

In fact, the algorithm in the interview , You can brush questions to prepare . Now share the algorithm interview questions encountered in the recent interview

subject - Find a mode in the list

Given a size of n Array of , Find the mode

* The number of : It means that the number of occurrences in the array is greater than "n/2" The elements of

Example :

Given array :list = [1,2,5,5,5,5,7]

Expected output : 5

LV1: Direct problem solving
First use the most direct way , Try to change the topic

def func(num:list): # Define a function , receive " list " data
res = [] # Define a variable to receive the result

For greater than "n/2" This demand , You can find out first n

n = len(num) # use len Function to get n
Find the mode in the array , It can be understood as : Compare circularly in the array .

On the condition that The number of occurrences of the current element (list.count() Function can get ) Greater than n/2

If you qualify , Then save it to res variable

For greater than "n/2" This demand , You can find out first n

for i in num: # Traverse num
now_time = num.count(i) # Get the number of occurrences of the current traversal item
if now_time > n/2: # If the number appears more than n/2
res.append(i) # Then add the result
Due to circulation , Each mode will be added to the result to get the following result

[5, 5, 5, 5]

So we are adding one to duplicate the data

return set(res)

result :

Lv2: simplify
In the above scheme , Strive to achieve the requirements quickly . Redundant in details , Here is a step of simplification .

def func(num:list): # Define a function , receive " list " data
# res = [] # In fact, due to the rule of mode ( Number > commonly ), There can only be one in an array . So it's good to return directly
# n = len(num) # Put this calculation directly into if In the condition
for i in num: # Traverse num
# now_time = num.count(i) # You can put this calculation directly on the condition
if num.count(i) > len(num)/2: # Can be n/2 The calculation of , Put it directly here
return i # Then add the result
The effect is as follows :

LV3 Efficiency optimization
From a functional point of view , The above scheme is feasible . But once you encounter massive data , Repeat the calculation list.count() It's very time consuming . Pictured :

This test data includes 5w+ Elements , The calculation is huge

Rethink the mode in the topic , Found several features :

① At most, there are 1 Multiple modes ( There will be no 2 More than half of the elements )

② If the array is arranged from large to small (list.sort() Function can sort ), Then the number in the middle must be mode

③ For arrays , There are also odd numbers / Even elements

If it's odd

The number of elements of the array is odd

l = [1,1,3,3,3]
print(len(l) // 2) have access to " to be divisible by " Get the midpoint

At this time, it happens to get to the midpoint of the array , Then you must get the mode

If it's even

The number of elements of the array is even

l = [1,1,3,3,3,3]
print(len(l) // 2)

The absolute midpoint is rounded back , This case is an example 4/7

At this time, the mode must also be >7/2, That is, at least 4 Time

therefore l[len(2//l)] It must be the mode

rewrite :

The number of elements of the array is even

def majorityElement(nums):
nums.sort()
return nums[len(nums) // 2]
The effect is as shown in the picture :

Conclusion : The speed is faster than the direct solution , fast 20 More than times