百度质量部二面（我觉得我挂了）

一个算法题：从1-10000中随机去掉两个数，用最小的时间复杂度找出这个数。

 

先用公式n(n+1)/2算出1-10000的总和 ， 用公式n(n+1)(2n+1)/6算出1-10000的平方和，
然后扫描那9998个数，每扫到一个就从平方和中减去这个数的平方，扫描一个就从总和中减去这个数。 
知道两个数的和和平方和，解方程组即可得出这两个数

 

这题没想出来这个方法，只想了最龊的两遍扫描。。然后各种言词不清。。伤不起啊，最后我问大概多久能告诉我结果，对方说：如果Pass的话估计就很快了。。上次的那个MM说的是：你这样的情况最多两面，估计2-3天就会给你电话。。。

哎。。面试时候还是不够自信啊，项目方面答的还是比较正常...

 

还是按常规做个回忆吧。开始自我介绍，然后谈到项目，这次问的问题比较多也比较杂了，2个算法题，其中一个是上面这个，还有一个，给定一个整数：给出连续的整数相加的和等于这个数字的所有情况。

 

然后从项目开始问到测试，其中问到了SQL数据库的API（这么久了早忘记了） ，LINUX的命令（SHELL编程和显示进程状态的命令） 然后又提到项目的经历的问题，项目的好说，因为基本自己做的东西不会那么容易的忘记，但是，话锋一转到测试的正题了，给你个软件，怎么测试？ 好大的题目啊。。那就说你常用什么浏览器吧，我说Chrome。那就测下Chrome。。。顿时SB了。不知道从何说起。就忽悠一下子，然后又问了对测试的看法。。我很教条的说了下软件工程书上的内容。

 

整个过程很紧张，主要是被那题影响到心情了，没给出最完美的答案。。然后武汉今天好冷啊，打电话时候手背觉得都麻木了。感觉自己中了二面魔咒啊，从来没挺过二面的。。。

评论

4 楼 ZeaLoVe 2012-09-05  

shinelx 写道

ZeaLoVe 写道

liguocai2009 写道

一个算法题：从1-10000中随机去掉两个数，用最小的时间复杂度找出这个数。



先用公式n(n+1)/2算出1-10000的总和 ， 用公式n(n+1)(2n+1)/6算出1-10000的平方和，
然后扫描那9998个数，每扫到一个就从平方和中减去这个数的平方，扫描一个就从总和中减去这个数。
知道两个数的和和平方和，解方程组即可得出这两个数


直接一遍扫过去不行吗？
for(i=1->n){
  if(array[i] != i ){
  xxxxx
}
}

那样需要两遍，第一遍是输入，第二遍找结果。不是最好的方法撒

为什么要输入呢？是说输入那9998个数到数组么？但就算是用平方和的算法不是也要通过扫描数组来判断，也要输入么？

是的，第一次输入9998个数字到数组去，第二遍扫面数组找缺少的两个。如果用公示的那种就不需要开数组了，只需在扫描的时候记录和与平方和这两个数字就好了，空间复杂度低。

3 楼 shinelx 2012-09-01  

ZeaLoVe 写道

liguocai2009 写道

一个算法题：从1-10000中随机去掉两个数，用最小的时间复杂度找出这个数。



先用公式n(n+1)/2算出1-10000的总和 ， 用公式n(n+1)(2n+1)/6算出1-10000的平方和，
然后扫描那9998个数，每扫到一个就从平方和中减去这个数的平方，扫描一个就从总和中减去这个数。
知道两个数的和和平方和，解方程组即可得出这两个数


直接一遍扫过去不行吗？
for(i=1->n){
  if(array[i] != i ){
  xxxxx
}
}

那样需要两遍，第一遍是输入，第二遍找结果。不是最好的方法撒

为什么要输入呢？是说输入那9998个数到数组么？但就算是用平方和的算法不是也要通过扫描数组来判断，也要输入么？

2 楼 ZeaLoVe 2011-12-02  

liguocai2009 写道

一个算法题：从1-10000中随机去掉两个数，用最小的时间复杂度找出这个数。



先用公式n(n+1)/2算出1-10000的总和 ， 用公式n(n+1)(2n+1)/6算出1-10000的平方和，
然后扫描那9998个数，每扫到一个就从平方和中减去这个数的平方，扫描一个就从总和中减去这个数。
知道两个数的和和平方和，解方程组即可得出这两个数


直接一遍扫过去不行吗？
for(i=1->n){
  if(array[i] != i ){
  xxxxx
}
}

那样需要两遍，第一遍是输入，第二遍找结果。不是最好的方法撒

1 楼 liguocai2009 2011-12-01  

一个算法题：从1-10000中随机去掉两个数，用最小的时间复杂度找出这个数。



先用公式n(n+1)/2算出1-10000的总和 ， 用公式n(n+1)(2n+1)/6算出1-10000的平方和，
然后扫描那9998个数，每扫到一个就从平方和中减去这个数的平方，扫描一个就从总和中减去这个数。
知道两个数的和和平方和，解方程组即可得出这两个数


直接一遍扫过去不行吗？
for(i=1->n){
  if(array[i] != i ){
  xxxxx
}
}