2017年暑假实习面经:|2017年暑假实习面经: 去哪儿网(一面, 二面, HR面, Offer), 腾讯IEG(一面, GG...), 百度(一面, 二面, 三面, offer)
2017年暑假实习面经: 去哪儿网(一面, 二面, HR面, Offer), 腾讯IEG(一面, GG…), 百度(一面, 二面, 三面, offer) 经过几个月的努力, 春招应该就这么结束了。总的来说这次春招结果还是比较理想(去哪儿网 offer + 百度 offer)。有点遗憾是腾讯一面由于我的项目经验不足, 而把我挂了。面试之前, 在网上看了许多面经, 对我的帮助也很大, 因此, 我也就决定写点东西, 算是对前人的工作的回报, 也算是为后来者提供经验。
一. 去哪儿网(2017-4-13) 去哪儿网的面试安排在成都春熙路的亚朵轻居, 酒店的氛围还是很温馨的。到了之后, 先让我们签到排队, 等待面试官叫号。
1. 去哪儿网一面
去哪儿网的一面面试官是我遇到的最好的面试官, 没有之一。因为这是我第一次面试, 过程中出现了许多尴尬的事情, 面试官很亲切的让我别紧张。有的问题我不太了解, 他也循序诱导, 让我最后得出较为满意的结果。面完之后, 就让我去等候室等二面。
下面是一面问题的罗列：
(1) STL 相关: STL 中的内存管理(allocator)的原理, 以及如何让它线程安全。
- 因为我对 STL 源码比较了解, 所以就很轻松地回答了 allocator 的实现原理, 相关实现可以参考《STL 源码剖析(侯捷)》。
- 由于对线程安全了解的比较少, 所以直接我给面试官说我不知道。面试官也没多说。等到后面回答了线程安全的单例模式时, 面试官让我把那里线程安全的知识用在这里来。然后我就大概写了一下分配器工作的关键代码的伪代码, 然后试着去加锁。最后面试官还是觉得很满意的。
- 我就随便谈了谈自己的理解: 进程管理内存资源+运行过程, 线程只管理运行过程, 线程要在进程提供的资源基础上运行。 Blabla…. 操作系统书上介绍得详细, 我这里也就不多说了。
- 这个网上随便找一篇介绍单例模式的文章都有详细地介绍。我就从基本的单例模式到线程安全的单例模式, 用智能指针管理的单例等大概说了说。
- 关于应用, 我就举了 《Effective C++》中的一个例子。定义在两个文件下的全局变量A, B,然后A 需要用 B 来初始化, 但是由于不知道 B 是否在 A 初始化时, 已经初始化了。因此我们可以用单例来封装一下, 从而保证了其 B 在 A 之前初始化。
- 这个也是经典问题了。一个快指针, 一个慢指针, 然后相遇就有环, 不相遇就没环。
bool hasCircle(ListNode* pHead){
ListNode* pFaster = pHead;
ListNode* pSlower = pHead;
do{
// 快指针走两步
if(pFaster->next != NULL) pFaster = pFaster->next->next;
// 慢指针走一步
pSlower = pSlower->next;
}while(pFaster != NULL && pSlower != NULL && pFaster != pSlower);
if(pFaster == NULL || pSlower == NULL) return false;
return true;
}2. 去哪儿网二面
去哪儿网二面的面试官明显比一面面试官年纪大, 估计应该是管理层的。一开场就问了特别难的问题, 表示一脸懵逼。好在后面的问题回答得还算可以, 因此, 面试完之后, 面试官就让我去等 HR 面。
(1) 在公网的两台服务器, 每个服务器都有一个标准的时钟, 已知其中一个服务器时钟是准确的, 另外一个服务器的时钟快或慢了一些。请设计同步时钟的算法。
- 一脸懵逼… 但是我不说。 = =! 硬起头皮说了个 “多次测量在传输过程中耗费的时间求平均值, 然后让待校准的服务器将收到的标准时间加上求得的平均时间”。 然后面试官不满意, 因为网络这个东西很不稳定, 这个传输时间怎么能这样算呢。我也很绝望啊! 我也没办法啊! 我还以为有巧妙的方法可以算出准确的时间, 一直在想, 结果还是没想出来。结果面试结束我在网上搜了下, 原来这个要用统计学什么的知识, 尽可能精确地估计时间。
- 将数据实际存放在与 hash 表存储单元相链接的链表中，而不是 hash 的存储单元中。 当产生冲突的时候，将两个数据都链接在同一 hash 存储单元保存的链表中。然后当插入元素的个数和表的大小一样时, 就让表的大小扩大为比最接近之前大小的两倍的质数大小。
- 面试官顺着这个就问, 怎么找质数。我就简单地说了下筛选法的思路。
HR 面就没什么好说的了。就是谈谈人生, 聊聊理想, 说说薪资。然后说我已经过了, 但是 offer 要等 5 月份, 全部人面完了之后一起发。然后 5 月初就收到了确认邮件。总的来说, 去哪儿网的面试还是很轻松的, 面试官人也都比较好。
二. 腾讯IEG(2017-4-16) 腾讯是我这次春招的痛点啊。实在是为了腾讯面试准备了太久, 但是想不到一面就没有过。面试官结束之后说了句 “基础很扎实, 就是项目经验不足”。 顿时心都寒了。为了去参加腾讯面试, 还从四川千里迢迢跑到陕西, 没想到…
1. 腾讯一面(GG…)
(1) 实现一个循环队列。
- 这个很基础, 这里就不多说。
- 大概就是载入页面之类, blabla…
- 一个底层实现是哈希表, 一个是红黑树
- 由于底层实现的不同, 所以一个是有序, 一个是无序的。
- 一个查找搜索复杂度是 O(1), 一个是O(logN).
三. 百度(2017-5-6) 参加百度校招的经历算是一波三四五…折了。先是由于自己在百度校招官网申请了实习生, 学长的内推就没成功。然后由于腾讯一面就挂了, 没什么心情参加百度笔试, 差点儿就没参加了。 笔试通过后又通知我去北京现场面试，然而我根本没时间。发邮件给 HR 改为视频面试, HR 说改了之后可能会失去机会。没办法, 只好改了。还好, 当天晚上就给我发了视频面试的邀请。
总的来说, 百度更重视基础, 不太重视项目经验。 几乎全程都在问 C++ 和 数据结构之类的问题。
1. 百度一面
由于网络原因, HR 一面面试官几乎就没有用牛客网的平台, 直接打电话给我手机 —— 视频面试变成了电话面试。 = =!
(1) 写一个 memcpy() 函数
- 由于之前浏览过源码, 大概记得起实现, 很快就完成了。
void *memcpy(void *dst, const void *src, size_t len)
{
if(NULL == dst || NULL == src){
return NULL;
}void *ret = dst;
if(dst <= src || (char *)dst >= (char *)src + len){
while(len--){
*(char *)dst = *(char *)src;
dst = (char *)dst + 1;
src = https://www.it610.com/article/(char *)src + 1;
}
}else{
src = (char *)src + len - 1;
dst = (char *)dst + len - 1;
while(len--){
*(char *)dst = *(char *)src;
dst = (char *)dst - 1;
src = (char *)src - 1;
}
}
return ret;
}(2) 写一个快排
* 这也是老生常谈的问题了。
//[beg, end)
void QuickSort(vector& datas, int beg, int end){
if(beg+1 >= end) return;
int i = beg, j = end - 1;
while(i < j){
while(i < j && datas[i] <= datas[beg]) ++i;
while(i < j && datas[j] > datas[beg]) --j;
if(i < j) swap(datas[i], datas[j]);
++i, --j;
}
swap(datas[beg], datas[j]);
QuickSort(datas, beg, j);
QuickSort(datas, j+1, end);
} (3) 进程和线程的区别
- 和前面去哪儿网的面试回答类似。
- 随便说了说。
- 先申请一定的大小的数组, 当数组填满之后,另外申请一块原数组两倍大的新数组, 然后把原数组的数据拷贝到新数组, 最后释放原数组的大小。 详情参考 《STL源码剖析(侯捷)》。
- C++ 包含 C 几乎全部功能。
- C++ 比 C 多面向对象语言部分。
- C++ 比 C 多泛型编程部分。
- C++ 比 C 多 STL 部分。
- 详情参考 《Effective C++》。
(1) 单例模式
- 和前面去哪儿网的回答类似。
这个比较多, 详细的可以自己在网上找找。
- const 关键字: 用在局部变量上, 用在类成员变量上, 用在类成员函数后面…
- static 关键字: 用在全局变量上, 用在局部变量上,用在类成员变量上, 用在类成员函数上…
class A {};: sizeof(A) = 1;class A { virtual Fun(){} };: sizeof(A) = 4(32位机器)/8(64位机器);class A { static int a; };: sizeof(A) = 1;class A { int a; };: sizeof(A) = 4;class A { static int a; int b; };: sizeof(A) = 4;
class A
{
public:
A(int x){}
}问：
A a = 1;
是否正确, 如果正确, 那么它调用了哪些函数？- 由于 A 类的构造函数没有声明为
explicit因此可以 int 类型强制转换来。因此, 该表达式正确。 - 对于没有优化过的编译器: 先将 1 转化为 A 类型(构造函数), 再将其赋值给 a 变量(拷贝赋值函数)。
- 对于优化了的编译器: 直接用 1 来构造变量 a(构造函数)。
char* str = "hello";
1)
char* p = new char[5];
2)
strcpy(p, str);
3)
cout << p << endl;
4)- 编译通过, 运行时出错。
- 2) 中的数组申请太小, 无法容纳下 “hello” 的大小。 因为字符串后面还有结束符(‘\0’)。
- 与 new 搭配的是 delete。2) 中 new 了资源没有 delete 掉。
class {} 内部实现的函数。- 一般认为: 默认构造函数, 默认析构函数, 拷贝赋值函数, (移动构造函数, 移动赋值函数)
- 《深度探索C++对象模型》中讲到, 不一定会生成这些函数, 然后blabla…(太多了, 这里不细说)
- 表示一脸懵逼, 但是还是硬起头去回答。下面罗列出我的回答, 不知道正确与否。
- C++ 是面向对象的语言, 自然有面向对象的语言的特性: 封装, 继承, 多态。
- C++ 也是泛型编程语言, 自然也有泛型编程语言的特性。
- 含有虚函数的对象内部保存有一个虚函数指针(vptr), 指向一个虚函数表(vtbl), 表内是函数指针。blabla…(详情参看 《深度探索C++对象模型)
- 重载要求相同的函数名, 不同的参数列表。仅返回值不同的函数不能重载。
- 重写要求父类是虚函数, 子类改写其函数体。要求函数签名一模一样。
百度三面比较随意。面试官也就随便问问代码, 聊聊人生。
(1)翻转一个链表
- 我首先用一个栈来实现。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
stack stk;
stk.push(nullptr);
while(pHead != nullptr){
stk.push(pHead);
pHead = pHead->next;
}
ListNode* tmp = nullptr;
while(stk.empty() == false){
if(tmp == nullptr){
pHead = tmp = stk.top();
}else{
tmp->next = stk.top();
tmp = tmp->next;
}
stk.pop();
}return pHead;
}
};
- 面试官不满意, 让我优化, 然后就用了下面的方法。遍历一遍用头插法。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
ListNode* newHead = nullptr;
while(pHead != nullptr){
ListNode* tmp = pHead->next;
pHead->next = newHead;
newHead = pHead;
pHead = tmp;
}
return newHead;
}
};
(2) 冒泡排序
void bubble_sort(int datas[], int n)
{
if (NULL == datas || 0 == n)
{
return;
}for (int i = 0;
i < n;
++i)
{
for (int j = 0;
j < n - i;
++j)
{
if (datas[j] > datas[j + 1])
{
swap(datas[j], datas[j + 1]);
}
}
}
}(3) 为什么选择百度
- 额… 这个… blabla…
5月6日面试, 5月17日收到 HR 的通知。确认信息, 问我是否有其他 offer, 选择入职时间, 实习时间。blabla…
四. 总结 总的来说, 这次春招的结果还算满意。中间可能也对自己的实力感到怀疑, 但是幸好自己没有放弃！
