米哈游 服务器开发 三面

一面
二面

语言基础

实现智能指针shared_ptr的构造、析构函数。
问：为什么count要用指针？

typename<T>
class shared_ptr {
    T* data = nullptr;
    uint32_t* count = 0;
    shared_ptr(const shared_ptr& a) {
        data = a->data;
        count = a->count;
        ++(*count);
    }
    shared_ptr(T* t) {
        data = t;
        if (t) {
            count = new uint32_t();
            count = 0;
        }
    }
    shared_ptr operator = (const shared_ptr& a) {
        if (a == this) ;
        else {
            if (this != nullptr) {
                --(*count);
                if (*count == 0) {
                    delete data;
                    delete count;
                }
            }
            data = a->data;
            count = a->count;
            ++(*count);
        }
    }
    ~shared_ptr() {
        if (data) {
            if (*count > 0) {
                --(*count);
            } else {
                delete data;
                delete count;
            }
        }
    }
};

typename<T>
shared_ptr<T> make_shared() {
    return ret(new T());
}

算法

1，7，10 三种面值硬币。
给定一个n，最少硬币凑出这个值。

我刚开始想要贪心，但面试官很快给出反例。

15

之后给出一个DP的O(N)的解法，面试官再提示N很大时，有何优化的思路。进而提出先mod最大公倍数，再对余数DP的O(1)解法。

dp(n) = min(
    dp(n - 1) + 1,
    dp(n - 7) + 1,
    dp(n - 10) + 1,
); if n >= 10;
1 * 7 * 10 = 70
O (7 + 1) = O(1)

数据结构设计

设计一个百万量级排行榜 ，支持插入，按uid查找分数，按uid查找名次，按名次查找uid.
follow up: 分数相同时，按照上榜时间排序。

order statisc tree

int getSize(TreeNode* node) {}


set
multiset

order_statisc_tree<pair<分数, 时间>，uid>：按名次查uid log N
hashmap<uid, pair<分数,时间>>: 按uid查分数 O(1)
按uid查排名 O(log N)
insert: O(1 + log N)

计算机基础

Linux熟不
排查线上某进程CPU为100%。

其他

游戏公司的特别之处。
玩过我们公司的游戏吗？（否）那平时玩什么游戏。

最后面试官问我能不能毕业前提前来实习。我说不能，没发去上海。

问题：贵司服务器开发内部分组情况。不同产品的后端共用情况。