2017-05-24 10:58 已编辑字节跳动_基础架构_后台开发

关注

去哪儿网, 腾讯, 百度(5.22已拿offer)

2017年暑假实习面经: 去哪儿网(一面, 二面, HR面, Offer), 腾讯IEG(一面, GG...), 百度(一面, 二面, 三面, offer)

经过几个月的努力, 春招应该就这么结束了。总的来说这次春招结果还是比较理想(去哪儿网 offer 百度 offer)。有点遗憾是腾讯一面由于我的项目经验不足, 而把我挂了。面试之前, 在网上看了许多面经, 对我的帮助也很大, 因此, 我也就决定写点东西, 算是对前人的工作的回报, 也算是为后来者提供经验。

一. 去哪儿网(2017-4-13)

去哪儿网的面试安排在成都春熙路的亚朵轻居, 酒店的氛围还是很温馨的。到了之后, 先让我们签到排队, 等待面试官叫号。

1. 去哪儿网一面

去哪儿网的一面面试官是我遇到的最好的面试官, 没有之一。因为这是我第一次面试, 过程中出现了许多尴尬的事情, 面试官很亲切的让我别紧张。有的问题我不太了解, 他也循序诱导, 让我最后得出较为满意的结果。面完之后, 就让我去等候室等二面。
下面是一面问题的罗列：

(1) STL 相关: STL 中的内存管理(allocator)的原理, 以及如何让它线程安全。

因为我对 STL 源码比较了解, 所以就很轻松地回答了 allocator 的实现原理, 相关实现可以参考《STL 源码剖析(侯捷)》。
由于对线程安全了解的比较少, 所以直接我给面试官说我不知道。面试官也没多说。等到后面回答了线程安全的单例模式时, 面试官让我把那里线程安全的知识用在这里来。然后我就大概写了一下分配器工作的关键代码的伪代码, 然后试着去加锁。最后面试官还是觉得很满意的。

(2) 操作系统相关: 什么是进程, 什么是线程。它们之间的区别和联系。

我就随便谈了谈自己的理解: 进程管理内存资源运行过程, 线程只管理运行过程, 线程要在进程提供的资源基础上运行。 Blabla.... 操作系统书上介绍得详细, 我这里也就不多说了。

(3) 设计模式相关：单例模式及其应用

这个网上随便找一篇介绍单例模式的文章都有详细地介绍。我就从基本的单例模式到线程安全的单例模式, 用智能指针管理的单例等大概说了说。
关于应用, 我就举了《Effective C 》中的一个例子。定义在两个文件下的全局变量A, B,然后A 需要用 B 来初始化, 但是由于不知道 B 是否在 A 初始化时, 已经初始化了。因此我们可以用单例来封装一下, 从而保证了其 B 在 A 之前初始化。

(4)数据结构相关: 判断一个链表是否有环

这个也是经典问题了。一个快指针, 一个慢指针, 然后相遇就有环, 不相遇就没环。

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; 
}

证明: 假设存在环, 且环的周期(环上的节点数)为 T, 环之前有 k 个节点, 则, 第 2T k 个节点和第 T k 个节点一定是同一个节点, 否则就会走到空节点。由此可以得到该链表是否有环。

2. 去哪儿网二面

去哪儿网二面的面试官明显比一面面试官年纪大, 估计应该是管理层的。一开场就问了特别难的问题, 表示一脸懵逼。好在后面的问题回答得还算可以, 因此, 面试完之后, 面试官就让我去等 HR 面。

(1) 在公网的两台服务器, 每个服务器都有一个标准的时钟, 已知其中一个服务器时钟是准确的, 另外一个服务器的时钟快或慢了一些。请设计同步时钟的算法。

一脸懵逼... 但是我不说。 = =! 硬起头皮说了个 "多次测量在传输过程中耗费的时间求平均值, 然后让待校准的服务器将收到的标准时间加上求得的平均时间"。然后面试官不满意, 因为网络这个东西很不稳定, 这个传输时间怎么能这样算呢。我也很绝望啊! 我也没办法啊! 我还以为有巧妙的方法可以算出准确的时间, 一直在想, 结果还是没想出来。结果面试结束我在网上搜了下, 原来这个要用统计学什么的知识, 尽可能精确地估计时间。

(2) STL 源码中的 hash 表的实现

将数据实际存放在与 hash 表存储单元相链接的链表中，而不是 hash 的存储单元中。当产生冲突的时候，将两个数据都链接在同一 hash 存储单元保存的链表中。然后当插入元素的个数和表的大小一样时, 就让表的大小扩大为比最接近之前大小的两倍的质数大小。
面试官顺着这个就问, 怎么找质数。我就简单地说了下筛选法的思路。

3. 去哪儿网三面(HR面)

HR 面就没什么好说的了。就是谈谈人生, 聊聊理想, 说说薪资。然后说我已经过了, 但是 offer 要等 5 月份, 全部人面完了之后一起发。然后 5 月初就收到了确认邮件。总的来说, 去哪儿网的面试还是很轻松的, 面试官人也都比较好。

二. 腾讯IEG(2017-4-16)

腾讯是我这次春招的痛点啊。实在是为了腾讯面试准备了太久, 但是想不到一面就没有过。面试官结束之后说了句 "基础很扎实, 就是项目经验不足"。顿时心都寒了。为了去参加腾讯面试, 还从四川千里迢迢跑到陕西, 没想到...

1. 腾讯一面(GG...)

(1) 实现一个循环队列。

这个很基础, 这里就不多说。

(2) 一个程序从开始运行到结束的完整过程。

大概就是载入页面之类, blabla...

(3) STL 的 unordered_map 和 map 的区别

一个底层实现是哈希表, 一个是红黑树
由于底层实现的不同, 所以一个是有序, 一个是无序的。
一个查找搜索复杂度是 O(1), 一个是O(logN).

(4) ... (记不住了..., 对于不收我的公司, 连面试题目我也记不住。呵呵...)

三. 百度(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 = (char *)src   len){  
    while(len--){  
    *(char *)dst = *(char *)src;  
    dst = (char *)dst   1;  
    src = (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  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) 进程和线程的区别

和前面去哪儿网的面试回答类似。

(4) 介绍一下 STL 源码的内容。

随便说了说。

(5) vector 的实现

先申请一定的大小的数组, 当数组填满之后,另外申请一块原数组两倍大的新数组, 然后把原数组的数据拷贝到新数组, 最后释放原数组的大小。详情参考《STL源码剖析(侯捷)》。

(6) C 与 C 的区别。

首先 C 包含 C 几乎全部功能。
C 比 C 多面向对象语言部分。
C 比 C 多泛型编程部分。
C 比 C 多 STL 部分。
详情参考《Effective C 》。

2. 百度二面

(1) 单例模式

和前面去哪儿网的回答类似。

(2) 在C 中的 const 和 static 用法。
这个比较多, 详细的可以自己在网上找找。

const 关键字: 用在局部变量上, 用在类成员变量上, 用在类成员函数后面...
static 关键字: 用在全局变量上, 用在局部变量上,用在类成员变量上, 用在类成员函数上...

(3) 计算下面几个类的大小

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;

(4) 已知某类:

class A 
   {
   public:
     A(int x){}
   }

问：A a = 1;是否正确, 如果正确, 那么它调用了哪些函数？

由于 A 类的构造函数没有声明为explicit因此可以 int 类型强制转换来。因此, 该表达式正确。
对于没有优化过的编译器: 先将 1 转化为 A 类型(构造函数), 再将其赋值给 a 变量(拷贝赋值函数)。
对于优化了的编译器: 直接用 1 来构造变量 a(构造函数)。

(5) 代码找错:

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 掉。

(6)class {}内部实现的函数。

一般认为: 默认构造函数, 默认析构函数, 拷贝赋值函数, (移动构造函数, 移动赋值函数)
《深度探索C 对象模型》中讲到, 不一定会生成这些函数, 然后blabla...(太多了, 这里不细说)

(7) C 语言的特性

表示一脸懵逼, 但是还是硬起头去回答。下面罗列出我的回答, 不知道正确与否。
C 是面向对象的语言, 自然有面向对象的语言的特性: 封装, 继承, 多态。
C 也是泛型编程语言, 自然也有泛型编程语言的特性。

(8) C 语言的虚函数相关

含有虚函数的对象内部保存有一个虚函数指针(vptr), 指向一个虚函数表(vtbl), 表内是函数指针。blabla...(详情参看《深度探索C 对象模型)

(9) 重载和重写的区别

重载要求相同的函数名, 不同的参数列表。仅返回值不同的函数不能重载。
重写要求父类是虚函数, 子类改写其函数体。要求函数签名一模一样。

3. 百度三面

百度三面比较随意。面试官也就随便问问代码, 聊聊人生。

(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) 为什么选择百度