当前位置:网站首页>Written interview topic: looking for the lost pig
Written interview topic: looking for the lost pig
2020-11-08 10:30:00 【Oc ccy4urvn】
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
版权声明
本文为[Oc ccy4urvn]所创,转载请带上原文链接,感谢
边栏推荐
- 渤海银行百万级罚单不断:李伏安却称治理完善,增速呈下滑趋势
- 解析Istio访问控制
- Julia 是如何风靡起来的?
- Cloud alibabab notes come out, the whole network detailed explanation only this one hand is slow
- 我们采访了阿里云云数据库SQL Server的产品经理,他说了解这四个问题就可以了...
- PCIe enumeration process
- 搜索引擎的日常挑战_4_外部异构资源 - 知乎
- 架构师(2020年11月)
- Adobe Prelude / PL 2020 software installation package (with installation tutorial)
- python学习 day1——基础学习
猜你喜欢
Seven features of Python 3.9
攻防世界之web新手题
python学习 day1——基础学习
5g + Ar out of the circle, China Mobile Migu becomes the whole process strategic partner of the 33rd China Film Golden Rooster Award
Istio流量管理--Ingress Gateway
Web novice problem of attacking and defending the world
软件测试就是这么回事?!
SQL Server 2008R2 18456错误解决方案
为 Docsify 自动生成 RSS 订阅
i5 1135g7和i5 1035g1参数对比区别大吗? 哪个好
随机推荐
i5 1135g7和i5 1035g1参数对比区别大吗? 哪个好
Which is more worth starting with the difference between vivos7e and vivos7
计算机网络基本概念(五)局域网基本原理
Game mathematical derivation AC code (high precision and low precision multiplication and division comparison) + 60 code (long long) + 20 point code (Full Permutation + deep search DFS)
Function periodic table filter value selectedvalue
笔试面试题目:求丢失的猪
阅读心得:FGAGT: Flow-Guided Adaptive Graph Tracking
laravel8更新之速率限制改进
Basic concepts of computer network (5) basic principles of local area network
PX4添加新的应用
python_ scrapy_ Fang Tianxia
ASP.NET MVC下基于异常处理的完整解决方案
如何将 PyTorch Lightning 模型部署到生产中
临近双11,恶补了两个月成功拿下大厂offer,跳槽到阿里巴巴
Flink's sink: a preliminary study
蓝牙2.4G产品日本MIC认证的测试要求
维图PDMS切图软件
SQL Server 2008R2 18456错误解决方案
新的目标市场在哪里?锚定的产品是什么?| 十问2021中国企业服务
PDMS cutting software