Classic interview question [gem pirate]

Classic interview questions 【 Gem pirates 】

Interview question bank 【 Mice drink water 】

---

---

One 、 Common topics

Five pirates grabbed 100 A gem , Each one is the same size and priceless . They decided to divide up ： Draw lots to decide your number （1、2、3、4、5）
First , from 1 Put forward the distribution plan , Then we vote , When and only if more than half of the people agree , Distribute according to his plan , Otherwise they will be thrown into the sea to feed sharks
If 1 After she died , Again by 2 Put forward the distribution plan , And then the rest 4 People vote , When and only if more than half of the people agree , Distribute according to his plan , Otherwise, they will be thrown into the sea to feed sharks , And so on .
Conditions ： Every pirate is a very smart person , Can make a rational judgment , To make a choice .

problem ： What kind of distribution scheme did the first pirate propose to maximize his own profits ？

Two 、 Detailed ideas

1. Change your mind

From the title, we get that the known condition is ：

1. Every pirate is a very smart person , Can make a rational judgment .
2. according to 1、2、3、4、5 Put forward the allocation scheme in sequence
3. Not more than half of the people agree , Will be thrown into the sea to feed sharks

2. Detailed ideas

Because every pirate can make the most rational judgment , Then we can start from the fifth to push back what situation they can get the most gemstones , What is their most rational judgment ？

When 1、2、3、4 When feeding all sharks ,5 Number assigned by yourself ：

only 5 No. one
here 5 The number must be 100 A gem

0 0 0 0 100

When 1、2、3 When feeding all sharks ,4 Number assignment ：

because 5 After No. 1 objection ,4 No more than half will agree , According to known condition three , that 4 No. 1 must be fed to sharks .
here 5 No. 1 is still necessary 100 A gem

0 0 0 0 100

When 1、2 When feeding all sharks ,3 Number assignment ：

As we know above 4 The number is 3 No. 1 will definitely be fed to sharks after death , that 3 Any allocation scheme proposed by , According to condition one , Make the most rational choice , that 4 No. must agree 3 Plan No . here 3 No. holds two tickets ,3 + 4 ： 5 = 2 ：1 The condition of must hold ,3 Number will be assigned to yourself 100 A gem , At this time, more than half of the two votes , Conditions established , here 3 The number must be 100 A gem .

0 0 100 0 0

When 1 When feeding sharks on the th ,2 Number assignment ：

As we know above 3 The number is 2 The plan after death is 0 0 100 0 0, So at this time 4 personal 2 The number needs to be pulled to 2 ticket To ensure the establishment of their own programs . however 3 The expectation of No. 1 is 100 that 2 No. must not be able to win 3 Number , from 3 We can know the distribution scheme of number 4 and 5 Of Expectations are 0 , that 2 Number assigned to 4、5 various 1 A gem can canvass , here 3 The conditions for the implementation of the distribution plan are established , therefore 2 No. button to pull 2 Gemstone , here 2 No 98 A gem .

0 98 0 1 1

Return to the topic , When 1 Number assignment ：

As we know above 2 The number is 1 The plan after death is 0 98 0 1 1, So at this time 5 personal 1 The number also needs to be pulled 2 ticket To ensure the establishment of their own programs . however 3 The expectation of No. 1 is 98 that 1 No 2 No. will need to pay 99 Gemstone , By condition one The most rational choice , So by the 2 We can know the distribution scheme of number 3 Of Expectations are 0, and 4 and 5 Of Expectations are 1 , that 1 Number is only assigned to 3 Number 1 A gem can canvass , among 4 and 5 Any one of them 2 Gemstone , here 3 The conditions for the implementation of the distribution plan are established , therefore 1 No. button to pull 3 Gemstone , here 1 No 97 A gem .

97 0 1 2 0  or  97 0 1 0 2

At this point, we can conclude that the final plan is ：

97 0 1 2 0 or 97 0 1 0 2 Is the solution that meets the most rational conditions

---

summary

Gem pirate is a classic algorithm interview question , Maybe from 1 On the th, I began to think about the perfect plan, which is more convoluted , But sort out the ideas from the end , That is from 5 No. thinking , This will make you suddenly realize , The algorithm examines only one idea , We should learn to think in reverse .

I hope this blog will be beneficial to you . I am the light king , I represent myself. .