首页 > 腾讯微信事业部 后端开发 暑期实习生 7面
头像
HailHYDRA00
编辑于 2020-03-31 19:22
+ 关注

腾讯微信事业部 后端开发 暑期实习生 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选手的问题,工程实现考虑不周。感觉他有很多怨言呀。

他还问了为什么本科时成绩好,研究生时不那么好?
我如实说了,研究生成绩不重要。

面试官小哥哥早年也在北航读过书,最后我还聊了一下我实验室的现状。

更多模拟面试

全部评论

(4) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐