腾讯存储工程师二面 面经

面试是腾讯文档里直接写的，没有测试过。题目是我脑补的。刚面完，不知道过了没。大家知道有几轮面试吗？

1. Given the following linked list node structure, where “random” can point to any node of the linked list. Please write a function copyRandomList that replicates the original list and returns it.

   class Node {
   public:
    int val;
    Node* next;
    Node* random;
   
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
   };
   Node* copyRandomList(Node* head) {
    if(head == nullptr) return nullptr;
    Node* res = new Node(head->val);
    if(head->next == nullptr) {
        if(head->random == head) res->random = res;
        return res;
    }
    map<Node*, Node*> m;
    m.insert(make_pair(head, res));
    for(Node* n = head->next, p = res; n->next != nullptr; 
            n = n->next, p = p->next) {
        p->next = new Node(n->val);
        m.insert(make_pair(n, p->next));
    }
    for(Node* n = head, p = res; n->next != nullptr; 
            n = n->next, p = p->next) {
        auto iter = m.find(n);
        if(iter != m.end()) {
            p->random = iter->second;
        }
    }
    return res;
   }

2. Given a regular binary TreeNode structure, please find the longest distance of the tree. For example, in the following tree, the longest length should be 3, which is from 2 to 4.

class TreeNode {
TreeNode* left;
TreeNode* right;
int val;
} 

int maxL = 0;
int dfs(TreeNode* root) 
{
    if(root == nullptr) return 0;
    int left = dfs(root->left);
    int right = dfs(root->right);
    int h = max(left, right) + 1;
    int l = left + right + 2;
    if(l > maxL) maxL = l;
        return h;
    }

int longestPath(TreeNode* root)
{
    dfs(root);
    return maxL;
}

3. Some Concepts(中间大部分我都不知道，有点凉，后来面试官就不问概念性的了)
   short : url (like bit.ly)
   hashmap: concurrent hashmap
   compare and change (CAS)
   GAP锁
   MVVC
   事务？
   Transaction 隔离性级别
   rr 串行化
   Linux 4KB page, how to fit mysql 16KB page

4. There is a 100-storey building, and you have two eggs. You want to know at which level of the building you throw the egg, will the egg be broken. But don’t know how hard the eggs are, so you have to experiment. How many trials do you have to make to find out the result?

面试官写的：（大概就只有一个鸡蛋需要100次，如果有两个呢？）
100 层
1 个 100次
2 个
10

比较巧，我一开始说如果分成10段，一段段弄过去，最多就20次，后来面试官问最少需要多少次，列个式子，正好也是20次（大概20次，实际边界上应该不用验证）。

100 / n + n >= 20