12月11日 中科院自动化所

牛客上投的，以前也没有投过科研院所，不知道里面有没有坑……

• 进程和线程

• 进程间通信的方式

• 线程间通信的方式

• 锁机制（我说了读写锁、互斥锁、自旋锁、RCU锁）

• 大规模读写锁的时候会遇到什么问题？（不会）

剩下的就是聊天，面试官是校友，西电本硕，以前在鹅厂和商汤干过，目测毕业很多年了。好像那边很偏科研算法的开发工作，自己也不是很感兴趣。

过了三天，offer~

12月14日 Momenta

• 设计题：手撕进程间的共享内存通信。

• 动态库和静态库之间的区别，静态库生成的过程。

• C++模板

• 创建进程的具体方法

• map底层是什么，为什么不是哈希表？

• 红黑树和哈希表比，优点？（排除rehash和内存的情况，没有回答到点子上）

• C++和C相比的优势

两小时后感谢信，再见~

12月15号 百度搜索架构部C++ 一面

• 判断有效的IP地址
  

  // 判断一个IP地址是否合法
  // IP地址格式，它的形式应该为：(1~255).(0~255).(0~255).(0~255)
  // 地址合法返回true，非法返回false
  bool isIpLegal(string ipaddr) {
  int num = 0;
  for (int i = 0; i < ipaddr.size(); i++) {
  if (ipaddr[i] == '.')
  num++;
  if (num > 3)
  return false;
  if ( ipaddr[i] != '.' &&( ipaddr[i] >= '9' || ipaddr[i] <= '0')) {
  return false;
  }
  int j = i;
  int temp = 0;
  while (ipaddr[j] != '.' && j < ipaddr.size()) {
  temp += (ipaddr[j]- '0') * pow(10, (2 - j + i));
  if (temp > 255 || temp < 0)
  return false;
  if ((j - i) > 3)
  return false;
  j++;
  }
  if (j - i == 1)
  return false;
  }
  return true;
  }
  

• 合并K个有序链表
  

  // 题目：合并K个升序链表
  // 给定一个链表数组，每个链表都已经按升序排列。
  // 请你将所有链表合并到一个升序链表中，返回合并后的链表。
  struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(NULL) {}
  };
  
  struct Status {
  int val;
  ListNode * ptr;
  bool operator < (const Status & rhs) const {
  return val > rhs.val;
  }
  }
  
  priority_queue<Status> q;
  
  ListNode* mergeKLists(vector<ListNode*>& lists) {
  for (auto elem : lists) {
  if (elem)
  q.push(elem->val, elem);
  }
  ListNode head, *tail = &head;
  while (q.empty()) {
  auto f = q.top();
  q.pop();
  tail->next = f.ptr;
  tail = tail->next;
  if (f.ptr->next)
  q.push({f.ptr->next->val, f.ptr->next});
  }
  return head.next;
  }
  

• 僵尸进程

• TCP和UDP的区别

• 保证UDP的可靠性（应用层面实现，参考TCP设计，确认位、同步位、滑动窗口、拥塞控制）

• 海量数据去重（布隆过滤器，不会；或者分层分类用hash，没有bloom好）

• 进程和线程的区别

• GDB调试

• const 和 static

面试官很客气，人很好，除了我太菜之外，一切完美。

12月17号 百度搜索架构部C++ 二面

• 算法题1，也可以排序后用二分，不会越界，但是复杂度高
  

  #include <iostream>
  #include <vector>
  #include <math.h>
  using namespace std;
  //有一个无序数列,对于特定的N,找出数列里大于N的最小值,小于N的最大值
  //[1,20,3,4,8,2]  N=6 8,4
  
  int minnum = (1<<21), maxnum = -(1<<21);
  void func(const vector<int>& v, int N) {
  for (int i = 0 ; i < v.size(); i++) {
  if (v[i] < N) {
  maxnum = max(maxnum, v[i]);
  } else if (v[i] > N) {
  minnum = min(minnum, v[i]);
  } else {  // 等于情况不考虑
  continue;
  }
  }
  }
  
  int main() {
  
  vector<int> v({1,20,3,4,8,2});
  int N = 6;
  func(v, N);
  // 防止出现找不到的情况，所以做一个判断再输出
  if (minnum != (1<<21)) {
  cout << minnum << " ";
  } else {
  cout << "no min num ";
  }
  if (maxnum != -(1<<21)) {
  cout << maxnum << endl;
  } else {
  cout << "no max num" << endl;
  }
  return 0;
  }
  

  
  

• 算法题2：两个字符串找最大公共子串 KMP or 字典树

• 算法题3：敏感词检测 AC自动机

• 死锁中争夺资源的一个设计题

• 问项目……

12月18号 百度搜索架构部C++ 三面

• Linux查找端口号

• 之前实习的项目

• 然后是一些常规的HR问题，经理面，能感觉很忙，但是很和善，很客气；给了口头offer；

int maxDepth(TreeNode* root) {
    if (root == nullptr)
         return 0;
    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

int maxDepth(TreeNode* root) {
    if (root == nullptr)
          return 0;
    queue<TreeNode*> q;
    q.push(root);
    int ans = 0;
    
    while (!q.empty()) {
        queue<TreeNode*> temp;
        while (!q.empty()) {
            if (q.front()->left) {
                temp.push(q.front()->left);
            }
            if (q.front()->right) {
                temp.push(q.front()->right);
            }
            q.pop();
        }
        ans++;
        q = temp;
    }
    return ans;
}





ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr)
        return head;
    ListNode* pre = nullptr;
    ListNode* cur = head;
    while (cur) {
        ListNode* n = cur->next;
        cur->next = pre;
        pre = cur;
        cur = n;
    }
    return pre;
}