应聘总结之腾讯实习生(2)

二面

一面过后一天，接到二面的通知。二面在腾讯公司所在的银科大厦。面试官一开始针对简历问了几个问题，然后开始问技术问题。

1. 二分查找大家都很熟悉，但如果给出的数组a可能进行了循环移位，如［1 2 3 4］变成了［2 3 4 1］（是否移位，移了多少位都不知道），能否写一个程序，快速找出数组中是否存在某元素n

我最初的想法是，遍历数组，找出移位的点，然后判断n属于哪个区间，进而在那个区间中对n进行二分查找。

但是面试官提示我，原本二分查找的时间复杂度是O(lgn)，而遍历数组的时间复杂度是O(n)，时间复杂度增加太多，能不能找到一个不改变时间复杂度的算法。

思考之后我发现，查找移位点其实可以用二分查找来实现，这样整体时间复杂度就不会增加了。移位点s的特征是：在它左边的元素比在它右边的元素大。可以用以下方法找到移位点：区间的头为b，尾为e，中间点为m；若a[b]<=a[e]，那么该区间中不存在移位点。若a[b]>a[m]，则移位点在该区间的左半段；若a[m]>a[e]，则移位点在该区间的右半段。

回家后我再思考这个问题，发现上面的方法可以更简化，那就是把判断移位点和查找元素n的过程结合在一起。

对于一段区间be，中间点为m。若a[b]<a[e]，说明不存在移位点，可以直接在这段区间上用二分查找查找n；若存在移位点，则m和s把整个区间分为三段，得小心判断n属于哪个区间，然后把范围缩小，直到该范围中不存在移位点。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

int binSearch(int *a, int len, int n) { if ( len <= 0) return -1; int b = 0; int e = len - 1; if (a[b] == n) return b; else if (a[e] == n) return e; int m = (b + e) / 2; while (b < m) { if (a[b] >= a[e]) // be区间中存在移位点 { if (a[m] >= a[b]) // 移位点在me区间中 { if (n > a[m] || n < a[b]) b = m; else if (n == a[m]) return m; else if (n == a[b]) return b; else e = m; } else if (a[m] <= a[e]) // 移位点在bm区间中 { if (n > a[e] || n < a[m]) e = m; else if (n == a[m]) return m; else if (n == a[e]) return e; else b = m; } } else // be区间中不存在移位点，直接用二分查找 { if (n < a[m]) e = m; else if (n == a[m]) return m; else b = m; } m = (b + e) / 2; } return -1; }

这道题包括和面试官讨论及写出代码，总共花了快一个小时，它给我的感触是，对于陌生的算法，最好的办法是先把思路用伪代码写出来，写的时候不考虑条件怎样成立、边界处理等细节，确定了整体思路后，再写出代码并考虑细节问题。在写代码的时候，需要注意考虑特殊情况：数组为空，数组中只有一个元素，数组中只有两个元素，数组中元素都一样，要增加、删除或查找的是首尾元素等。

2. 已知一个单向键表，但不知道它的头指针，给出链表中一个节点的指针，并且已知该结点的后续节点不为空，要求删除该结点

这个题咋看之下无从入手，因为不知道头指针，就无法获得那个节点的前置节点。这时候就得打破常规的思维了，删除一个节点，其实就是让它的后续节点取代它。

1 2 3

Node *temp = p->next; memcpy(p, temp, sizeof(Node)); free(temp);

3. 怎么确定内存中栈的生长方向

考察对程序内存分配的理解。内存中栈主要用来存放局部变量、函数参数、返回值等。

我的回答是，定义两个变量a和b，打印出它们的地址，看看是增大还是减小。在这里我犯了一个错误，认为先定义的变量先分配内存，其实这是不能保证的。

正确的做法是，定义两个函数a和b，a打印出它的参数的地址并调用b，b打印出它的参数的地址，根据地址的增大或是减少来判断。

HR终面

1. 关于腾讯你了解什么
2. 实习的目的
3. 为什么想去腾讯，而不是别的公司
4. 你的缺点
5. 同学眼中的你是什么样子的
6. 同学有过的关于你的最负面的评价

总结

总的来说，笔试面试过程拖得并不久，一次笔试加三次面试在一个星期内完成。但是之后的等待过程却是很漫长，一个多星期之后才收到offer（期间我甚至怀疑是不是没通过HR面试－－。），而由于要全国统一进行，所以直到现在还在等待实习流程的继续。不过等待也没有什么不好，这次应聘给了我很多收获，也暴露出我的很多问题，这等待给了我时间去思考去总结，让我成长。

作者: 白色之夜 发表于 2011-05-27 17:21 原文链接

评论: 4　查看评论　发表评论

最新新闻：
· 花旗：HTC每部Android手机向微软支付5美元(2011-05-27 22:44)
· 花旗称微软进军平板电脑市场不晚(2011-05-27 22:35)
· Facebook称不能确定所有权诉讼中邮件真伪(2011-05-27 22:26)
· Skype故障导致部分用户无法登录(2011-05-27 21:21)
· 日本欲在月球上遍布太阳能板 或成发电基地(2011-05-27 21:05)

编辑推荐：推荐阅读：谈谈对于企业级系统架构的理解

网站导航：博客园首页  我的园子  新闻  闪存  小组  博问  知识库