Shulou(Shulou.com)06/02 Report--

This article introduces the relevant knowledge of "what are the interview questions of Python algorithm?". In the operation of actual cases, many people will encounter such a dilemma. Then let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

1, 25 horses, there is a track that can only race five horses, we can not time, we can only see the ranking of horses, how to find the fastest five horses in the shortest number of times?

The best case of this question is 7 times, and the worst case is 10 times. Let's first set up a table and divide 25 horses into the following five groups:

Each group competes, assuming that the first group is in the order of A1, A2, A3, A4 and A5, and so on in the second group. Then the first of each group is A1, B1, C1, D1, E1.

In the best case, first let A1, B1, C1, D1, E1 race, get the first place, suppose A1 is the first place, and the order is A1 > B1 > C1 > D1 > E1; then let A2 join the competition, if the result is B1 > C1 > D1 > A2. Then the top five are A1, B1, C1, D1 and E1, with a total of 7 competitions. So in the worst case, each time you add a new candidate and get a new ranking, you need a total of 10 races.

This question is more often asked how to find the three fastest horses in the shortest number of times, which is not quite the same as finding five horses. If you find three horses, you only need to race seven times. For the first six times, it is assumed that A1 is the fastest horse, and the rest is B1 > C1 > D1 > E1. At this time, it is not for A2, B1, C1, D1, E1 to compete, first carefully analyze, the second place must appear in B1 and A2, if B1 > A2, then the third place appears in A2, B2, C1, if A2 > B1, then the third place appears in A3, B1. Therefore, the seventh race only needs to let A2, A3, B1, B2, C1 five horses race, get the top two. So it only takes seven races to get the three fastest horses.

2. In an infinitely long straight line, there are two robots, and two robots execute the same code. There are only a few sentences in this code: right stands for going right, left stands for going left, and if arrived else represents whether another robot has passed through this place. Goto stands for the jump of the code, please write a piece of code to ensure that the two robots can meet.

The pseudo code is as follows:

Start:if arrived: right rightelse: rightgoto start

To explain briefly, suppose that both robots An and B go to the right, and B is in front of A, and at the beginning they both move at the same speed. When A reaches the point where B has passed, it is found that the subsequent road is what B has passed before. So A starts to speed up twice, and B keeps the same speed. In that case, A will definitely catch up with B.

3. How to find the median of massive data? Data can not be put into memory, only need to consider space complexity, do not need to consider time complexity.

Assuming that our data are unsigned 32-bit integers, since we do not take into account the time complexity, we can solve the problem by binary, judging from high to low, first traversing all the data, and recording the number of the highest bits 0 and 1 (the highest bit 0 must be less than the highest bit 1) as N0 and N1.

Then according to the size of N0 and N1, you can know whether the highest bit of the median is 0 or 1.

If N0 > N1, then calculate N00 and N01, if N00 > (N01+N1) (it must be noted here that N00 is greater than the sum of N01 and N1, not N00 is greater than N01), then the highest two digits of the median is 00, then calculate N000 and N001. The median can be found by calculating in turn.

4. information flow sampling, there are n pieces of data, but the length of n is not known. Design a sampling algorithm so that the probability of each copy being selected is the same.

This problem actually examines the sampling method of the reservoir, here we briefly introduce the idea of the reservoir algorithm.

At the beginning, the first data is selected as the candidate data, the current candidate is replaced by the second data with the probability of 1amp 2, the current candidate is replaced with three data with the choice of 1amp 3, and so on.

Thus, the probability that the x-th data is the final selected data = the probability that x is selected * (the probability that x is not selected) * (the probability that x is not selected). (the probability that n is not selected)

For example, the probability that the second brother's data will be selected is 1 * 2 * (2 * 3 * 3 * 4 * 4 * 5). N Mei 1Pao) = 1Pao

5. N [0Jing n] numbers to calculate the number of occurrences of each number (no extra space can be opened up)

The key here is to see clearly the meaning of the question, n numbers, and then the left closed and right open interval, that is to say, each number will not be greater than or equal to n, then there are mainly the following two points:

1) if we add no matter how many n to the number under an index, then if we take the remainder of the number to n, we will know what the number is.

2) on the other hand, if a number appears once, we add n to the number under the corresponding index position, then each number corresponds to the number pair n at the index position, which is the number of times this number occurs. In this way, there is no extra space.

The code is as follows:

Public class timeDemo {public static void main (String [] args) {int [] arr = {0 int I = 0 int I = 0 Ting I

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.