Interview intelligence questions

1. Weight weighing problem

problem 1

• There are ten sets of weights , Ten in each group , The weight of each weight of nine groups is 10g, The weight of each weight in the other group is 9g, Ask for a scale that can show grams , Find this group at least a few times 9g The weight of ？

analysis

• Divide the weight into 1~10 Group , The first group takes out 1 A weight , The second group takes out 2 A weight , The third group takes out 3 A weight ,…, The last group takes out 10 A weight , Put it all on the scale , The weight shown is y, Make x=550-y, Is the first x Group is the weight of the weight x A group of .

problem 2

• There's a scale ,9 A weight , Among them is 1 One is better than the other 8 A light , Ask if you can find the light weight at least several times ？

analysis

• Divide the weight into 3 Group , Each group 3 individual , Take two of them and weigh them on the balance （ The first 1 Time ）, If it's the same weight , The light one is the remaining group , Not as heavy , You can also tell which group is light ;

• The lighter group 3 A weight , Choose two of them and weigh them on the balance （ The first 2 Time ）, If it's the same weight , Then the rest 1 One is light , Not as heavy , The light ones can also be easily found .

2. The kettle problem

problem 1

• There is now an unlimited amount of water , You have two... Capacity 5L and 3L My jar , Please weigh out 4L water . Note that you can only fill or empty the jar at a time , Or pour water from one pot to another .

analysis

• We need to solve an indefinite equation ：

$$5\times a+3\times b=4$$

• Can take $a=2,b=-2$, It means that in the end 5L My jar （ Write it down as A） Need to be filled twice ,4L My jar （ Write it down as B） It needs to be poured out twice , The specific operation is as follows ：

  • take A Fill it up with , hold A Pour the water in B in , And then B Pour out the water in , And then A Pour the remaining water in B in , here ：A：0L、B：2L;

  • take A Fill it up with , hold A Pour the water in B in , And then B Pour out the water in , here ：A：4L、B：0L;

problem 2

• There is now an unlimited amount of water , You have two... Capacity 5L and 6L My jar , Please weigh out 3L water .

analysis

• We need to solve an indefinite equation ：

$$5\times a+6\times b=3$$

• Can take $a=3,b=-2$, It means that in the end 5L My jar （ Write it down as A） It needs to be filled three times ,4L My jar （ Write it down as B） It needs to be poured out twice , The specific operation is as follows ：

  • take A Fill it up with , hold A Pour the water in B in , here ：A：0L、B：5L;

  • take A Fill it up with , hold A Pour the water in B in , here ：A：4L、B：6L;

  • hold B Pour out the water in , here ：A：4L、B：0L;

  • hold A Pour the water in B in , here ：A：0L、B：4L;

  • take A Fill it up with , hold A Pour the water in B in , here ：A：3L、B：6L;

  • hold B Pour out the water in , here ：A：3L、B：0L;

Question 3

• There is now an unlimited amount of water , You have two... Capacity x and y My jar , Please weigh out z water .

analysis

• This problem is the most general problem of the above two problems . A necessary and sufficient condition for the existence of a scheme ：z<=x+y also z aliquot gcd(x, y).

• For specific analysis, please refer to ：【 Classic algorithm problem 】 The kettle problem .

3. Stone weight sorting problem

problem

• Give you a pile of stones with the same appearance , But the weight is different , You can also use a balance without weights , Ask how to arrange these stones in ascending order ？

analysis

• The key of sorting algorithm is that it can compare the size of two numbers , It doesn't matter how much these two numbers are . Therefore, all sorts of sorting algorithms can be used .

• You can use fast platoon ： The idea is to find the location of each stone , You can put stones less than the current stone weight on the left , Put the larger ones to the right , Then solve recursively .

• You can use merge sort ： At first, it was thought that each stone was a pile , Then recursively merge two adjacent piles of stones .

• You can use heap sort , Use heapify Build a big pile , Then put the top of the heap element to the end each time , after down(1) that will do .

4. Burn the rope

problem 1

• It takes to burn a rope 1 Hours , How to use this rope to judge half an hour ？

analysis

• Start from both ends , When it's finished, it's half an hour .

problem 2

• It takes to burn a rope 1 Hours , How many ropes do you have , How to count an hour and 15 minutes with a burning rope ？

analysis

• Burn two ropes at the same time , One from one end , Burn one from both ends ; When the burning rope at both ends is finished （ Half an hour ）, Ignite the other end of the burning rope （ It has been burning for half an hour ）, When this rope burns out （ Fifteen minutes ）; Light the third rope from both ends , When finished burning （ Half an hour ） One hour and fifteen minutes .

5. COINS

problem

• Yes 10 A coin with its face up ,10 A coin with the reverse side up , Mixed in with . You need to close your eyes , At the same time, you can't feel a coin face up , Or the opposite side up . You need to put this 20 Coins are divided into two piles , Make the number of coins facing up the same in the two stacks , The number of coins with the reverse facing upwards is the same .

analysis

• It must be divided into two piles of the same number , All are 10 individual , Then turn one pile over .

• Suppose there is... In a pile x Face up , The other pile has 10-x Face up , After turning, another pile has x Face up , Meet the conditions .

6. A Poor Pig

problem 1

• Yes 1000 Bucket water , Only one bucket of water is poisonous , You can feed water to the piglets , As long as the piglets drink poisonous water , You'll die . You can only feed one round （ Every barrel of water is treated once and counted as one round ）. Ask how many piglets you need at least ？ How to determine the toxic bucket of water ？

analysis

• The number of piglets needed ：

$$\lceil lo{g}_2(1000)\rceil =10$$

• Each barrel of water is numbered , Corresponding 0~999, You can convert numbers to binary , For a barrel of water , If a binary bit is 1, Feed this bucket of water to the corresponding piglet .

• Finally, determine which piglets are dead , Then the corresponding binary bit is 1, The binary bit corresponding to the undead pig is 0. In this way, the number of poisonous water can be determined .

problem

• The above questions remain basically unchanged , The only change is that you can feed k round . Ask how many piglets you need at least ？ How to determine the toxic bucket of water ？

analysis

• The number of piglets needed ：

$$\lceil lo{g}_{k+1}(1000)\rceil$$

• Tips ： Think of a barrel of water as a k+1 Hexadecimal number . For details, please refer to ：【 Classic algorithm problem 】 A Poor Pig .

7. The hardness of the egg

• Definition ： If the egg is in the a The first floor will not be broken , But in the a+1 The first floor fell to pieces , The hardness of the egg is a（ The egg hardness is less than or equal to the floor height ）.

Question 1

• 100 floor , Do you have 1 An egg , To test the hardness of an egg , How many times do you need to throw ？

analysis

• Because there is only one egg , In order to ensure that the hardness of the egg is tested , You must test layer by layer from the first layer , So in the worst case it needs to be tested 100 Time （ The hardness of the corresponding egg is 100） The situation of .

Question two

• 100 floor , Do you have 2 An egg , To test the hardness of an egg , How many times do you need to throw ？

analysis

• Refer to the website ： Throwing eggs .

• Two points ： The first egg starts from 50 Throw it down on the first floor , Another egg can only be left one layer at a time , At worst, we need 51 Time （ The corresponding hardness is 100）.

• Square root method ： We try every 10 Layer throw once , First time from 10 Layer throw , Second times from 20 Layer throw , The third time from 30 layer … Throw it all the way to 100 layer . The worst-case scenario is at 100 The layers are broken , The number of attempts is 10 + 9 = 19 Time .

• Mathematical approach ：

  • Suppose the optimal solution is x Time , For the first time x Throw eggs on the floor . It can't be x+1 layer 、 perhaps x-1 Layer throw , Because if the egg breaks , Then we need x+1 Attempts to 、x-1 Attempts to ;x+1>x, It's not the optimal solution ,x-1 If the conditions are met , be x It's not the optimal solution , contradiction （ In fact, there are still cases to be considered but not broken , So we can't take x-1）.

  • If it's not broken , The problem becomes two eggs from 100-x Throw it down the first floor , It is required that the number of attempts should not exceed x-1 Time , Therefore, it is necessary to x+x-1 Floor throwing .

  • So there is ：x+(x-1)+...+1>=100, Round up , You know x=14.

  • So at worst , The minimum need to throw 14 You can measure the hardness of an egg .

Question 3

• n floor ,m An egg , To test the hardness of an egg , How many times do you need to throw ？

analysis

• This is a dynamic programming problem .

• Please refer to for specific explanation ：【 Classic algorithm problem 】 The hardness of the egg .

8. Bulb switch

problem

• Yes n A light bulb , It was bright at first . Conduct n Wheel operation , The first round will be all 1 Press the multiple bulb switch once , The second time all 2 Press the multiple bulb switch once ,…, How many lights are on at last ？ What are the lights ？

analysis

• A light bulb x The last one is bright $*$ It is pressed an odd number of times $*$ Its divisors are odd .

• Therefore, all the bulbs whose approximate number is an odd number are bright , such as 5 A light bulb is pressed 5 Time ,1、4 The light bulb is on , because 1 Only 1 This is a divisor ,4 Yes 1、2、4 Three divisors .

• Next, consider the characteristics of odd data ： If a number N The prime factor can be decomposed into $p_1^{{\alpha }_1}\ast p_2^{{\alpha }_2}\ast ...\ast p_k^{{\alpha }_k}$ , be N The approximate number of is $({\alpha }_1+1)\ast ({\alpha }_2+1)\ast ...\ast ({\alpha }_k+1)$ . Must have ${\alpha }_i+1$ Must be an odd number , therefore ${\alpha }_i$ It must be an even number , therefore N It's a total square .

• It is proved that if a number N The number of divisors of is odd , Then it is a perfect square number . And vice versa （ for example $x=y^2$, Only divisor y once , The rest are in pairs ）.

• So the final answer to this question is 1~n The number of complete squares in .

9. The probability of forming a triangle

problem

• Given a length of 1 The rope of , You can select two points from which to truncate , Turn into three paragraphs , What is the probability of forming a triangle ？

analysis

• Suppose the coordinates of the two selected points are y、x（y<x）, Here's the picture ：

• You need to meet （ The sum of the two sides is greater than that of the third side ）：

$$\{\begin{array}{l}1-y>y\\ x>1-x\\ y+(1-x)>x-y\end{array}$$

• Simplification , Yes ：

$$\{\begin{array}{l}y<\frac{1}{2}\\ x>\frac{1}{2}\\ y>x-\frac{1}{2}\end{array}$$

Method 1 ： Linear programming

• The linear programming region corresponding to the above inequality is as follows ：

• Green and orange are the legal total area , Orange is the area that can form a triangle , Therefore, it should be changed to 1/4.

Method 2 ： Double integral

• The probability corresponds to the following integral ：

$$\begin{gathered} {\int }_{\frac{1}{2}}^1{\int }_{x-\frac{1}{2}}^{\frac{1}{2}}dydx/{\int }_0^1{\int }_0^{x}dydx \\ =\frac{1}{8}/\frac{1}{2}=\frac{1}{4} \end{gathered}$$

---

• explain ： Some reference websites ： Check the common intelligence questions in the interview .