一面

C++：

• new、malloc区别
  返回类型、分配失败返回值、分配大小、数组的处理方式、是否调用构造函数
• 多态
  编译时多态、运行时多态
• 虚函数实现
  vptr、vtable
• 重载原理
  符号表
• map
  红黑树，定义，自旋

网络：

• UDP可靠实现
  序列号、ACK、重传、定时器
• DNS细节
  不会
• Listen(2),backlog参数
  The backlog argument defines the maximum length to which the queue of pending connections for sockfd may grow.
• 浏览器输入网址到实现
  略

操作系统：

• C程序的虚拟内存空间
  stack、heap、bss、data、text
• 页机制
  换页、缺页异常、TLB
• IPC
  管道、信号、消息队列、信号量+共享内存

Linux

• 常用命令

算法题

• 最大子序和
  dp

二面

网络

• 拥塞控制
  慢启动、拥塞避免、快速重传、快速恢复
• select(2)、epoll(7)
  红黑树、边缘触发、节省用户态内核态拷贝
• 红黑树原理，与AVL的区别
  定义、自旋，rebalance频率相对低，适合大量插入删除node的场景

操作系统

• 多进程和多线程的选择
  多进程可靠性高，创建销毁切换开销大，多线程反之
• Linux下C程序的调试
  breakpoint、coredump
• 静态链接、动态链接
  libc库，避免代码庞大，节省内存，更新时不需全部重新编译，提高可维护性
• 内存泄漏
  valgrind

算法题

• n个整数，找出平均数最大且长度为k的连续子数组，输出最大平均数
  easy题，滑动窗口
• 如果长度大于等于k？
  n^2超时，面试结束看了题解，用的二分，这是个hard题

    bool check(vector<int> &nums, double mid, int k) {
        double sum = 0, prev = 0, min_sum = 0;
        for (int i = 0; i < k; ++i)
            sum += nums[i] - mid;
        if (sum >= 0)
            return true;
        for (int i = k; i < nums.size(); ++i) {
            sum += nums[i] - mid;
            prev += nums[i - k] - mid;
            min_sum = min(prev, min_sum);
            if (sum >= min_sum)
                return true;
        }
        return false;
    }
    double findMaxAverage(vector<int>& nums, int k) {
        double max_val = *max_element(nums.begin(), nums.end());
        double min_val = *min_element(nums.begin(), nums.end());
        double prev_mid = max_val, error = INT_MAX;
        while (error > 0.00001) {
            double mid = (max_val + min_val) / 2;
            if (check(nums, mid, k))
                min_val = mid;
            else
                max_val = mid;
            error = abs(prev_mid - mid);
            prev_mid = mid;
        }
        return min_val;
    }

12月28日 Offer Call 效率很高