Written interview topic: looking for the lost pig

      Original published in ：

 

 

    Today's National Day , The Mid Autumn Festival, too , It's really rare . stay 21 Century's 100 During the year , have only 4 Year is like this . At home today , With family , Cook and eat , Do housework , Read some idle books , By the way, write something , I'll go out later , And then come back and run .

 

      The campus autumn recruitment has begun in succession , I wish the students in school get their favorite offer, I also wish the students who are recruited by the society to change jobs smoothly .

       today , Let's see A An interview question for the company ：

      Yes n Pigs , Take the car to the vegetable market , The pigs were pasted with 1~n The number of , All of a sudden , A pig jumped out of the car and ran away , Ask for the number of the pig that escaped .

 

    

      The pig is still very poor , Slip away , We also need to track down the numbers . below , Let's look at algorithms .

 

Algorithm 1： Making difference method

        Ideas ：

       Step1: To calculate the 1~n And a.

       Step2: Find the sum of the numbers of the remaining pigs b.

       Step3: a-b That's the number of the pig .

 

        The disadvantage of this algorithm is ： seek 1~n And , It might spill over .

 

Algorithm 2： Tagging

      Ideas ： Open up an array m, use m[i]=0 or 1 To record i Whether there is , For lost pigs j, There must be m[j]=0.

      The disadvantage of this algorithm is ： The space complexity is O(n)

 

Algorithm 3： Sequencing

      Ideas ： Sort the rest of the pigs , The pig that is running away j At the number of , There must be a break , So they know j The specific value of .

      The disadvantage of this algorithm is ： Let's take the example of fast track , Neither time complexity nor space complexity is optimal .

 

Algorithm 4： Exclusive or law ( The best algorithm )

        Ideas ：

       Step1:  To calculate the 1~n Exclusive or values a.

       Step2:  Find the exclusive or value of the number of the remaining pigs b.

       Step3:  seek a and b Exclusive or values , It's the number of the pig that escaped j.

 

       The principle is as follows :

        hypothesis n=5, The number of the lost pig is 3, So the number of the remaining pigs is 2, 4, 1, 5, Let's calculate ：

       j = 1^2^3^4^5^2^4^1^5

      obviously , According to the exchange law of XOR , The above operations can be simplified , as follows ：

       j = 1^1^2^2^4^4^5^5^3 = 3

      

      This gives you the number of the pig that's gone . here , The time complexity is O(n), The space complexity is O(1), This is the best algorithm . As for the procedure , It's simple , So I won't go back to .

 

 

      In the previous post , We can actually see , XOR is a special kind of “ Addition and subtraction ”, therefore , Algorithm 1 Sum algorithm 4 It's a wonderful thing to do the same . About binary XORs , You can refer to ：

       The circuit principle of computer addition and proteus Simulation