10分钟前的G店面，面经

大龄男码农第一次面G, 印度大叔:, 但感觉没有要刁难的意思，迟到五分钟没寒暄直接做题。1. LC 303,

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

缩写错了。第二题timestamp整数

补充内容 (2016-8-5 22:09):
感谢三哥高抬贵手，又加了一个电面。G这么磨人对骑驴找马的人真是折磨

第二题就是hash + binary serach, 用unordered_map<string,vector<pair<int,string>>> 来存，每次通过hash找历史记录，在历史记录上binary search lower_bound就行

jason88628 发表于 2016-8-5 01:45
有道理。。。我两周前才系统的学了一下BIT，follow up被问到觉得运气真是好炸了，BIT代码简洁，写起来非 ...

其实segment tree可以借鉴BIT的表达，代码也可以很简洁的，用的空间也和BIT差不多（假定BIT还是需要另存一份data的话）。贴一个我刷leetcode的时候写的。

inline unsigned int next_power_of_two(unsigned int v) {

    --v;

    v |= (v >> 1);

    v |= (v >> 2);

    v |= (v >> 4);

    v |= (v >> 8);

    v |= (v >> 16);

    return v+1;

}

class NumArray {

public:

    NumArray(vector<int> &nums) : M(next_power_of_two(nums.size()+2)) {

        tree.resize(M<<1, 0);

        copy(nums.begin(), nums.end(), tree.begin()+M+1);

        for (int k = M-1; k>0; k--) tree[k] = tree[k<<1] + tree[k<<1|1];

    }

    void update(int i, int val) {

        i++; //number is 1 based

        int diff = val - tree[M+i];

        for (int key = M+i; key > 0; key >>= 1) tree[key] += diff;

    }

    int sumRange(int i, int j) {

        int sum = 0;

        for (i += M, j += M+2; i ^ j ^ 1; i >>= 1, j >>= 1) {

            if (!(i&1)) sum += tree[i^1];

            if (j&1) sum += tree[j^1];

        }

        return sum;

    }

private:

    vector<int> tree;  //tree stored in array, size is M*2

    int M; //smallest power of 2 greater or equal than nums.size()+2

};

存个user + timestamp 的string？

第二题是假设timestamp都是整数吗？如果是的话，用unordered_map<string, unordered_map<int, string>>来存储，第一个string是例子中的'a'，后面一个int里是timestamp，最后的string是例子中'bad', 'good'。存储是O(1)，查询a 的 timestamp n, 就要先从unordered_map里得到a对应的unordered_map<int,string>，然后把n一直递减到0，看unordered_map<int,string>有没有值，找到第一个值就返回，平均查询复杂度O(n)。我再想想能不能优化

flex 发表于 2016-8-4 02:13
第二题是假设timestamp都是整数吗？如果是的话，用unordered_map来存储，第一个string是例子中的'a'，后面 ...

可以用order map吗

也是想到user + timestamp 的string . 楼主能说说吗?

BIT挺难解释清楚的，相比之下segment tree虽然写得多，占内存也多，但好说啊

say543 发表于 2016-8-4 13:56
也是想到user + timestamp 的string . 楼主能说说吗?

可能，题意没写清楚，这里面没有user, 你指的是例子里存a+1作为key么？
Po主当时脑残，说存个类似HashMap<key, Heap<Pair>>()。Pair是{timestamp, val}然后就接着写了，他又问了你如果Pair就存一个最普通的List呢，复杂度是怎样。（发现如果用heap， 反而更差。T_T）put的顺序不一定是按照1.2,3,4这样，有可能是先放4，在放1, put get也可以进行。Po主还提了一下如果timestampe range不大，用bucket最快。总之说了一些方法，三哥也表示这个好还是不好，就是问为什么，复杂度，有没有什么limit这样。

zhihaosun 发表于 2016-8-4 19:53
BIT挺难解释清楚的，相比之下segment tree虽然写得多，占内存也多，但好说啊

有道理。。。我两周前才系统的学了一下BIT，follow up被问到觉得运气真是好炸了，BIT代码简洁，写起来非常快，没想到会被要求解释。。。