腾讯微信事业部后端开发暑期实习生 7面

上周三约了HR面试，闲聊了半天，和技术面的套路差别很大。因为我说我实习想在北京，所以又约了这周一（今天）下午的一次北京同事的技术面试。北京这边应该就只有一个技术面试，还有HR面试。

视频面试采用牛客网平台，分为项目、算法、数据结构、计算机基础。

算法题

逛街
小Q在周末的时候和他的小伙伴来到大城市逛街，一条步行街上有很多高楼，共有n座高楼排成一行。
小Q从第一栋一直走到了最后一栋，小Q从来都没有见到这么多的楼，所以他想知道他在每栋楼的位置处能看到多少栋楼呢？（当前面的楼的高度大于等于后面的楼时，后面的楼将被挡住）
输入描述
输入第一行将包含一个数字n，代表楼的栋数，接下来的一行将包含n个数字wi(1<=i<=n)，代表每一栋楼的高度。
1<=n<=100000;
1<=wi<=100000;
输出描述
输出一行，包含空格分割的n个数字vi，分别代表小Q在第i栋楼时能看到的楼的数量。
示例1
输入
6
5 3 8 3 2 5
输出
3 3 5 4 4 4
说明
当小Q处于位置3时，他可以向前看到位置2,1处的楼，向后看到位置4,6处的楼，加上第3栋楼，共可看到5栋楼。当小Q处于位置4时，他可以向前看到位置3处的楼，向后看到位置5,6处的楼，加上第4栋楼，共可看到4栋楼。

LeetCode medium难度，秒杀，正反使用2次单调递减栈即可。需要注意的是，看到的楼包括当前楼，所以当前楼会正反计算2次，最后需要减1。

#include <vector>
#include <stack>
#include <iostream>

using namespace  std;

int main() {
    int n;
    cin >> n;
    vector<int> height(n);
    for (int i = 0; i < n; ++i) {
        cin >> height[i];
    }
    vector<int> ans(n, 0);
    stack<int> s;
    auto process = [&](int i) -> void {
        while (!s.empty() && height[s.top()] <= height[i])  {
            int t = s.top();
            s.pop();
            ++ans[i];
        }
        s.push(i);
        ans[i] += s.size();
    };
    for (int i = 0; i < n; ++i) {
        process(i);
    }
    while (!s.empty()) {
        s.pop();
    }

    for (int i = n - 1; i >= 0; --i) {
        process(i);
    }
    for (int i = 0; i < n; ++i) {
        -- ans[i]; // delete repeated self(count twice)
        cout << ans[i] << " ";
    }
    cout << endl;

    return 0;
}

数据结构

设计一个支持序列化和反序列话的HashMap。我之前没有接触过类似问题，了解过一些序列化的知识。就设计了一个线型探查版的hashmap, 因为这样所有数据都可以存储在一个数组中，方便序列化。

为了方便实现，并没有考虑泛化和扩容，虽然提前和面试官沟通过。面试官还是抨击了线型探查对空间利用有问题，说是单个bucket中有过多元素时会有问题。对此我并不苟同，然后有讨论了半天。最后他有怼我说，没别人实现的好，insert时没有考虑扩容。因为我之前已经和他沟通过不考虑扩容和泛化以简化问题。对此，面试官不免有些为了怼而怼的嫌疑，我是并不信服的。我问他别人怎么实现，主流方法如何？他只是说没有标准答案。

struct HashMap {
    const int capity = 1 << 7;
    array<int, capity> data;
    const int NOT_EXIST = -1;
    HashMap() {
        memset(data.data(), capity * sizeof(int), -1);
    }
    void searilize(const string& file_name) {
        // 把data内容写到文件中
        std::ofstream fout (file_name, std::fstream::binary);
        auto& d = static_cast<array<char, capity*sizeof(int)>>(data)
        std::copy(d.begin(), d.end(), std::istreambuf_iterator<char>(fout));
    }
    void load(const string& file_name) {
        // 把文件内容读到data中
        std::ifstream input(file_name, std::ios::binary );
        std::copy( 
            std::istreambuf_iterator<char>(input), 
            std::istreambuf_iterator<char>( ),
            static_cast<array<char, capity*sizeof(int)>>(data).begin());
    }
    int get(int key) {
        int hashcode = hash(key);
        int bucket = hashcode & 6;
        for (int i = bucket; i < 1 << 6; ++i) {
            if (data[i] == key) {
                return data[i + (1 << 6)];
            } else if (data[i] == NOT_EXIST) {
                return NOT_EXIST;
            }
        }
        return NOT_EXIST;
    }
    void insert (int key, int value) {
        int hashcode = hash(key);
        int bucket = hashcode & 6;
        for (int i = bucket; i < 1 << 6; ++i) {
            if (data[i] == NOT_EXIST || data[i] == key) {
                data[i] = key;
                data[i + (1 << 6)] = value;
            }
        }
    }
}

计算机基础

多态。构造函数不能虚函数，析构函数可以虚函数。
并发了解。

其他

自己的优点：
我讲了基础扎实、算法好（刷题多）。
他讲了他对刷题的看法。虽然不排斥刷题，但说了很多ACM选手的问题，工程实现考虑不周。感觉他有很多怨言呀。

腾讯微信事业部 后端开发 暑期实习生 7面

算法题

数据结构

计算机基础

其他

全站热榜

腾讯微信事业部后端开发暑期实习生 7面