十月份的KPI面，我也是无语，真的全部都答上了，面试官问问题的时候 总停顿十几秒 场面上真的尴尬。

不过没有游戏经验，就这样吧。

一、笔试题：

二叉树权值

有一棵二叉树，树上每个点标有权值，权值各不相同，请设计一个算法算出权值最大的叶节点到权值最小的叶节点的距离。二叉树每条边的距离为1，一个节点经过多少条边到达另一个节点为这两个节点之间的距离。 给定二叉树的根节点root，请返回所求距离。 我看大佬用的map算二进制编码，然后计算距离。 大佬们太秀了，好好学学

struct TreeNode{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};

void GetCode(map<int,string>& treeMap,TreeNode* root,string s)
{
    if(root->left==nullptr && root->right==nullptr){
        //给出01编码
        treeMap[root->val] = s;
        return;
    }
    if(root->left!=nullptr){
        GetCode(treeMap,root->left,s+'0');
    }
    if(root->right!=nullptr){
        GetCode(treeMap,root->right,s+'1');
    }
}


int getDis(TreeNode* root)
{
    if(root == nullptr)
        return 0;

    map<int,string> treeMap;

    GetCode(treeMap,root,"");
 //利用迭代器获取开头结尾的值（map会自动排序）
    auto minNum = treeMap.begin();
    string s1 = minNum->second;
    auto maxNum = (--treeMap.end());
    string s2 = maxNum->second;

 //根据编码计算距离
    int i = 0,j = 0;
    while(i<s1.size() && j<s2.size() && s1[i] == s2[j]){
        i++;j++;
    }
    return s1.size() + s2.size() - i - j;
}

分割链表

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* small = new ListNode(0);
        ListNode* smallHead = small;
        ListNode* large = new ListNode(0);
        ListNode* largeHead = large;
        while (head != nullptr) {
            if (head->val < x) {
                small->next = head;
                small = small->next;
            } else {
                large->next = head;
                large = large->next;
            }
            head = head->next;
        }
        large->next = nullptr;
        small->next = largeHead->next;
        return smallHead->next;
    }
};

最大正方形

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.size() == 0 || matrix[0].size() == 0) return 0;
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<vector<int>> dp(rows, vector<int>(cols,0));
        int maxSize = 0;
        for(int i = 0; i < rows; ++i){
            for(int j = 0; j < cols; ++j){
                if(matrix[i][j] == '1'){
                    if(i == 0 || j == 0){
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] = min(dp[i-1][j],min(dp[i-1][j-1], dp[i][j-1])) + 1;
                    }
                    maxSize = max(dp[i][j], maxSize);
                }
            }
        }
        return maxSize*maxSize;
    }
};

二、面试

1. 自我介绍
2. Web服务器简单介绍
3. epol机制
4. 红黑树
5. 相比哈希表的优势
6. 线程池机制
7. 线程认是如何被唤醒的
8. 两种事件并发模式以及区别
9. TCP、UDP区别
10. TCP分为几部分
11. TCP是如何保证可靠性的
12. RPC讲一下
13. TCP是如何进行流量控制
14. 滑动窗口机制具体讲讲
15. Redis底层通信原理 五种数据结构
16. MySQL索引功能
17. 索引的种类
18. 如何解决哈希冲突
19. 堆排序介绍一下
20. 如何实现堆排序 口述算法
21. 插入30个数字的堆排序的效率
22. C++多态
23. 迭代器失效的原因

基本都答上了 比似乎也A了 就是挂了 无语。。。

三、面试笔试题

不用递归实现二叉树的中序遍历

合并k个升序链表笔试题：

分割链表

最大正方形

面试笔试题

不用递归实现二叉树的中序遍历

合并k个升序链表