面试经-白红宇

面试经

阅读量：4225 次

发布时间：2019-05-26

本文共 4265 字，大约阅读时间需要 14 分钟。

笔试

感觉笔试挺不正规的，可能是由于参加的人太多了吧，教室基本上坐满了，而且大家互相挨着，很容易就能看到别人的答案。

题型：30道不定项选择题，两道程序填空题，附加题。时间为2个小时。

不定项选择题

考的内容非常广泛，包括但不限定于以下内容：计算机体系结构（32位系统和64位系统的区别）、操作系统（内存和cache）、数据结构（由二叉树的中序和后序遍历推出前序遍历结果）、算法（快排第一遍的结果；哪些排序是稳定性排序）、编译原理（操作系统，静态数据区，程序区，堆栈区在内存中的顺序）、计算机网络（服务器收到FIN后处于什么状态）。

程序填空题

给出一个数n，其中包含1，2，3，4这4个数字，写一个函数，输出n的某个变化数（重新排列n中的数字），使它能够被7整除。

删除列表中的节点。

附加题

分C/C++，JAVA，PHP，JAVASCRIPT方向，选做，不算入总分。

C/C++方向：有N个大小为G的存储单元，用户在不断上传数据，每次上传数据的大小v是随机的，请写一个系统，把上传的数据分配给各个存储单元，使得每个存储单元的使用率和写负责相对均衡，要考虑以下两个初始状态： (1) 每个存储单元的剩余空间相同。 (2) 每个存储单元的剩余空间相差很大。

JAVA方向：1. 模拟线程间通信：线程A和B共用一块空间C[] space, 模拟一次线程间的通信：线程A生产一个C物品，并把它放入space中，线程B从space中取出该物品，并输出它的信息。 2. 现有某人A与别人的QQ聊天记录（其中不包含A自己说的话），请写一个程序，快速找出与A联系得最频繁的人B。已知B的记录占整个记录的一半以上。

PHP方向：PHP本身是没有继承的，请你自己实现继承。

一面

上午笔试，晚上就通知一面，腾讯效率还挺高的。

一面在皇冠酒店的宴会厅。参加一面的人还是挺多的，整个宴会厅摆满了四人桌，每桌上都有一个面试官，对面试者进行一对一面试。

我的面试官很nice，见面还问我吃了午饭没，简单寒暄后就开始问技术问题了。

1. shell读文件并把文件的内容输出到控制台

                 1          while read line        
      
                 2          do        
      
                 3              echo $line        
      
                 4          done < $file

2. 某文件的第二列内容为数字，请用awk求出这些数字的和

`1`	`awk` `'BEGIN{sum = 0;} {sum += $2;} END{print sum;}'` `$file`

3. 按层次遍历二叉树

要点：使用队列

                 01          void layerOrder(BTree *tree)        
      
                 02          { 
        
                 03              if (tree == NULL)        
      
                 04                  return;        
      
                 05                   
      
                 06              queue<BTree *> q;        
      
                 07              q.push(tree);        
      
                 08                       
      
                 09              BTree *p = NULL;        
      
                 10              while (!q.empty())        
      
                 11              { 
        
                 12                  p = q.front();        
      
                 13                  visit(p);        
      
                 14                           
      
                 15                  q.pop();        
      
                 16                  if (p->lchild != NULL)        
      
                 17                      q.push(p->lchild);        
      
                 18                  if (p->rchild != NULL)        
      
                 19                      q.push(p->rchild);        
      
                 20              }        
      
                 21          }

4. 统计10万个单词中出现频率最高的1000个

10万个单词完全可以内存中放下，所以可以使用hashmap，单词作为key，value为该单词的计数，对这10万个单词进行统计。统计完后，用一个最小堆找出计数最多的那1000个单词。具体可参考码农的Top K算法详细解析。

5. 求1000亿个数中的最大1000个

假设内存为4G，显然不足以把这1000亿个数都存入。可以把这它们划分为落干个区间，对应地存储到若干个文件中，使得每个区间中不超过10亿个数，若超过则对该区间再进行划分。

然后对这些区间内的数进行统计，假设前N个区间中数的总数X1，且X1<1000，而前N＋1个区间中数的总数为X2，且X2>1000，则最大1000个数为前N个区间内的数加上第N＋1个区间中的前1000-X1个数。

6. gdb调试时如何找到出错的地方

7. 写一个函数void strrev(char *str)反转str

8. 自定义数据结构，并写函数删除单向链表中值为n的那个结点

9. 在两个有序数组中找出共有元素

若已知同一个数组中没有重复的元素，则可以使用归并排序，然后在排序后的结果查找重复元素。若同一数组中可能存在重复元素，则不能使用归并排序。

另一个方法是使用bitmap，先扫描数组A，把其中出现的元素在bitmap中赋值为1，然后扫描数组B，若某元素在bitmap中已为1，则输出该元素。

二面

面试官一开始针对简历问了几个问题，然后开始问技术问题。

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属于哪个区间，然后把范围缩小，直到该范围中不存在移位点。

                 01          int binSearch(int *a, int len, int n)        
      
                 02          { 
        
                 03              if ( len <= 0)        
      
                 04                  return -1;        
      
                 05                   
      
                 06              int b = 0;        
      
                 07              int e = len - 1;        
      
                 08              if (a[b] == n)        
      
                 09                  return b;        
      
                 10              else if (a[e] == n)        
      
                 11                  return e;        
      
                 12                   
      
                 13              int m = (b + e) / 2;        
      
                 14              while (b < m)        
      
                 15              { 
        
                 16                  if (a[b] >= a[e])  // be区间中存在移位点        
      
                 17                  { 
        
                 18                      if (a[m] >= a[b])        // 移位点在me区间中        
      
                 19                      { 
        
                 20                          if (n > a[m] || n < a[b])        
      
                 21                              b = m;        
      
                 22                          else if (n == a[m])        
      
                 23                              return m;        
      
                 24                          else if (n == a[b])        
      
                 25                              return b;        
      
                 26                          else        
      
                 27                              e = m;        
      
                 28                      }        
      
                 29                      else if (a[m] <= a[e])   // 移位点在bm区间中        
      
                 30                      { 
        
                 31                          if (n > a[e] || n < a[m])        
      
                 32                              e = m;        
      
                 33                          else if (n == a[m])        
      
                 34                              return m;        
      
                 35                          else if (n == a[e])        
      
                 36                              return e;        
      
                 37                          else        
      
                 38                              b = m;        
      
                 39                      }        
      
                 40                  }        
      
                 41                  else                // be区间中不存在移位点，直接用二分查找        
      
                 42                  { 
        
                 43                      if (n < a[m])        
      
                 44                          e = m;        
      
                 45                      else if (n == a[m])        
      
                 46                          return m;        
      
                 47                      else        
      
                 48                          b = m;        
      
                 49                  }        
      
                 50                   
      
                 51                  m = (b + e) / 2;        
      
                 52              }        
      
                 53                   
      
                 54              return -1;        
      
                 55          }

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

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

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

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

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

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

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

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

HR终面

HR面试就是和你聊聊天，问一些你的基本情况，感觉主要在考察你实习的意愿。我的经验是要表现出强烈的想去的欲望，而且最好事先了解一下公司的背景，另外，问能够实习多久时往长了说，反正这并不是最终确定实习长度的时候，并且能够实习更久会给你有加分。

关于腾讯你了解什么

实习的目的

为什么想去腾讯，而不是别的公司

你的缺点

同学眼中的你是什么样子的

同学有过的关于你的最负面的评价

总结

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

转载地址：http://wlzqi.baihongyu.com/

你可能感兴趣的文章

c++使用宏检测类是否包含某个函数或者变量属性