📣 4th of July限时特惠: VIP通行证立减$68
12
返回列表 发新帖
楼主: jason88628
跳转到指定楼层
上一主题 下一主题
收起左侧

10分钟前的G店面,面经

🔗
hxtang 2016-8-5 05:02:31 | 只看该作者
全局:
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
};

回复

使用道具 举报

🔗
blackrose 2016-8-5 05:47:43 | 只看该作者
全局:
jason88628 发表于 2016-8-5 01:41
可能,题意没写清楚,这里面没有user, 你指的是例子里存a+1作为key么?
Po主当时脑残,说存个类似HashMa ...

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

使用道具 举报

🔗
 楼主| jason88628 2016-8-5 08:19:04 | 只看该作者
全局:
blackrose 发表于 2016-8-5 05:47
对啊,第二题咋不用 a+1 作为key 呢。。。。value 存成pair就可以了。

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

使用道具 举报

🔗
blackrose 2016-8-5 10:52:02 | 只看该作者
全局:
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

评分

参与人数 1大米 +1 收起 理由
twtypsj + 1 hao

查看全部评分

回复

使用道具 举报

🔗
 楼主| jason88628 2016-8-5 11:45:23 | 只看该作者
全局:
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;

回复

使用道具 举报

🔗
say543 2016-8-5 13:55:48 | 只看该作者
全局:
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
回复

使用道具 举报

🔗
hxtang 2016-8-5 19:57:22 | 只看该作者
全局:
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输入的时候是不是保存先后顺序的了.
回复

使用道具 举报

🔗
 楼主| jason88628 2016-8-5 22:08:24 | 只看该作者
全局:
say543 发表于 2016-8-5 13:55
问一下楼主 put 和get 都是照timestamp 出现吗? 举个栗子 put(a,val1, 1) 一定在put(a, val2,4) 之前吗?  ...

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

使用道具 举报

🔗
 楼主| jason88628 2016-8-5 22:08:43 | 只看该作者
全局:
hxtang 发表于 2016-8-5 19:57
就是前面yetangzhi说的第一层hash把data按照key划分,第二层把同一个key下面不同time stamp的按照时间有 ...

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

使用道具 举报

🔗
hxtang 2016-8-5 22:18:05 | 只看该作者
全局:
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了。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表