10分钟前的G店面，面经

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

};

jason88628 发表于 2016-8-5 01:41
可能，题意没写清楚，这里面没有user, 你指的是例子里存a+1作为key么？
Po主当时脑残，说存个类似HashMa ...

对啊，第二题咋不用 a+1 作为key 呢。。。。value 存成pair就可以了。

blackrose 发表于 2016-8-5 05:47
对啊，第二题咋不用 a+1 作为key 呢。。。。value 存成pair就可以了。

那如果现在存了("a+100", val1) ("a+20", val2), get(a,50)怎么办？要保证String Key有序也不是很容易吧？

jason88628 发表于 2016-8-5 08:19
那如果现在存了("a+100", val1) ("a+20", val2), get(a,50)怎么办？要保证String Key有序也不是很容易吧 ...

把pair group成一个data 存这个data的linked list

补充内容 (2016-8-5 10:53):
要求一定有序吗？只是返回boolean值阿，没有这个组合，直接返回false了，有这个组合的情况下考虑链表解决冲突，也可以二次hash

blackrose 发表于 2016-8-5 10:52
把pair group成一个data 存这个data的linked list

补充内容 (2016-8-5 10:53):

sorry, 栗子举得不好，不是返回boolean.
    void put(a, val1, 1)
    void put(a, val2, 4)

    get(a, 0)-> null;
    get(a, 2)->val1;
    get(a, 4)->val2;
    get(a, 7)->val2;

jason88628 发表于 2016-8-5 11:45
sorry, 栗子举得不好，不是返回boolean.
    void put(a, val1, 1)
    void put(a, val2, 4)

问一下楼主 put 和get 都是照timestamp 出现吗? 举个栗子 put(a,val1, 1) 一定在put(a, val2,4) 之前吗? GET 也是一样的case吗? thanks

jason88628 发表于 2016-8-5 11:45
sorry, 栗子举得不好，不是返回boolean.
    void put(a, val1, 1)
    void put(a, val2, 4)

就是前面yetangzhi说的第一层hash把data按照key划分，第二层把同一个key下面不同time stamp的按照时间有序排列, 搜索的时候找lower_bound吧。具体第二层用vector还是用map看面试官说timestamp输入的时候是不是保存先后顺序的了.

say543 发表于 2016-8-5 13:55
问一下楼主 put 和get 都是照timestamp 出现吗? 举个栗子 put(a,val1, 1) 一定在put(a, val2,4) 之前吗?  ...

输入不保证顺序，昨天跟同学聊了一下，用BST存Pair, 按照timestamp, 这样put, get 都是 lgn.不知道可行不

hxtang 发表于 2016-8-5 19:57
就是前面yetangzhi说的第一层hash把data按照key划分，第二层把同一个key下面不同time stamp的按照时间有 ...

输入不保证顺序，昨天跟同学聊了一下，用BST存Pair, 按照timestamp, 这样put, get 都是 lgn.不知道可行不

jason88628 发表于 2016-8-5 22:08
输入不保证顺序，昨天跟同学聊了一下，用BST存Pair, 按照timestamp, 这样put, get 都是 lgn.不知道可行不

觉得差不多就是这个想法，要search lower_bound总得维护个sorted结构的。
不过BST还是需要balanced，不然不能保证log(n)，特别是像timestamp这种哪怕不保证顺序很可能也almost按顺序的。（其实我觉得需要讨论timestamp插入顺序是不是almost sorted，如果是也许insertion sort比BST快）。
以及还是要每个key一个BST，不然log(n)的n全局是stream进来的data总数，太不scalable了。