快手（客户端）

一面 9.27 45min
小哥哥有点帅，嘻嘻...介绍自己是做快手同城的

自我介绍
项目相关
1、介绍聊天服务器的项目，开发细节
2、怎么保证消息能送达？如果发生了奔溃等，怎么标记？
进程和线程
多线程怎么保证线程安全？
有了解过自旋锁吗？
哈希表的实现原理
不同类型的哈希函数怎么计算的？
数组和链表的区别
java里对数组扩容的优化？
不晓得啊。。。
好像有一个ArrayList的泛型类，也被叫做数组列表，具有自动调节数组容量的功能，而不需要编写另外的代码。
7层网络结构
应用，表示，会话（这两层我竟然忘了谁先谁后。。。），传输，网络，数据链路，物理
TCP/UDP/HTTP分别在哪一层
HTTP的请求方式有哪些？
TCP/UDP的区别？
HTTPS的连接过程
TCP三次握手/四次挥手

手撕：二叉树层序遍历

/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
  vector<vector<int> > levelOrder(TreeNode *root) {
      if(root==nullptr) return {};
      queue<TreeNode*> q;
      q.push(root);
      vector<vector<int>> res;
      while(!q.empty())
      {
          int sz=q.size();
          vector<int> vec;
          for(int i=0;i<sz;++i)
          {
              TreeNode* node=q.front();
              q.pop();
              vec.push_back(node->val);
              if(node->left) q.push(node->left);
              if(node->right) q.push(node->right);
          }
          res.push_back(vec);
      }
      return res;    
  }
};

写完后，可能还有时间，又让我写了一道。。。

手撕：最小栈（调用 min、push 及 pop 的时间复杂度都是 O(1)

class MinStack
{
  public:
  MinStack() {}
  void push(int x)
  {
      s1.push(x);
      if(s2.empty() || x<s2.top())
          s2.push(x);
  }
  void pop()
  {
      if(s1.top()==s2.top())
          s2.pop();
      s1.pop();
  }
  int top()
  {
      return s1.top();
  }
  int getmin()
  {
      return s2.top();
  }
  private:
  stack<int> s1,s2;
};

问我11点可以二面吗？我说11点和同学约了饭。。。现在想想当时简直太蠢了。。。蠢到窒息。。。

二面 9.27 55min

自我介绍
为什么想做程序员？（看到专业名字，必问的问题）
有学过计算机相关的课程吗？
extern "C"使用场景和作用
extern "C"的主要作用就是为了能够正确实现C++代码调用其他C语言代码。加上extern "C"后，会指示编译器这部分代码按C语言（而不是C++）的方式进行编译。由于C++支持函数重载，因此编译器编译函数的过程中会将函数的参数类型也加到编译后的代码中，而不仅仅是函数名；而C语言并不支持函数重载，因此编译C语言代码的函数时不会带上函数的参数类型，一般只包括函数名。
这个功能十分有用处，因为在C++出现以前，很多代码都是C语言写的，而且很底层的库也是C语言写的，为了更好的支持原来的C代码和已经写好的C语言库，需要在C++中尽可能的支持C，而extern "C"就是其中的一个策略。
这个功能主要用在下面的情况：C++代码调用C语言代码；在C++的头文件中使用；在多个人协同开发时，可能有的人比较擅长C语言，而有的人擅长C++，这样的情况下也会有用到。
（真是令人窒息。。。我回答的是extern。。。）
智能指针的作用？有哪些？
malloc/free/new/delete
const和宏定义的区别
多线程的同步
对称加密和非对称加密的区别/常用的加密算法
TCP三次握手/四次挥手的原因
数据库了解吗？
。。。不了解啊。。。
数据库基本的语句了解吗？
。。。不晓得啊。。。
设计模式了解吗？
。。。没有学啊。。。
以生产者模式为例，能写出框架吗？
。。。不能啊。。。
正则表达式了解过吗？
。。。。。。。。。
设计题：实现一个下载器的功能，能想到的一些技术/设计/边缘条件？
获取用户检索信息；解析检索信息，分成图片，视频，文档等几类；在存储库中寻找，传给用户；
1、怎么做存储？
哈希表，查找速度快
2、下载视频，和服务器的交互需要传输哪些数据？
3、要考虑单线程下载/多线程下载/断点虚传（下载一半，程序终止，下一次再接上）/完整性的校验
单/多线程下载：磁盘读写效率；CPU占用率；耗电量；（PC的相应限制比较小，可以多个线程同时往一个磁盘读写）。

手撕：合并有序链表
将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的。

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
  ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
      if(l1==nullptr) return l2;
      if(l2==nullptr) return l1;
      ListNode* newhead=new ListNode(0);
      ListNode* p1=l1;
      ListNode* p2=l2;
      ListNode* tail=newhead;
      while(p1 && p2)
      {
          if(p1->val < p2->val)
          {
              tail->next=p1;
              p1=p1->next;
          }
          else
          {
              tail->next=p2;
              p2=p2->next;
          }
          tail=tail->next;
      }
      if(p1) tail->next=p1;
      if(p2) tail->next=p2;
      return newhead->next;
  }
};

一开始我是另外开辟内存写的新链表。。。后来说让在原地合并。。。