一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2023|回复: 18
收起左侧

10分钟前的G店面,面经

[复制链接] |试试Instant~ |关注本帖
jason88628 发表于 2016-8-4 00:21:33 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Other在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
大龄男码农第一次面G, 印度大叔:, 但感觉没有要刁难的意思,迟到五分钟没寒暄直接做题。1. LC 303, follow up 307 (就是说如果要update, 如何改进,讨论复杂度, 用了BIS, 要求解释BIS。。。。,不画图真的不太好说其实(也是水平太差),口音也略晕,我还忘了好多数学的说法,简直了,真不是抄的,希望他相信我。) 2. 本质就是实现一个带time stamp 的 hash.

    void put(a, good, 1)
    void put(a, bad, 4)

    get(a, 0)-> null;
    get(a, 2)->good;
    get(a, 4)->bad;
    get(a, 7)->bad;

讨论复杂度,小伙伴们想想怎么存吗,我滚去吃饭啦。
.1point3acres缃

补充内容 (2016-8-4 02:37):
Sorry 第一题用的Binary Indexed Tree, 缩写错了。第二题timestamp整数
. 1point 3acres 璁哄潧
补充内容 (2016-8-5 22:09):
感谢三哥高抬贵手,又加了一个电面。G这么磨人对骑驴找马的人真是折磨

评分

1

查看全部评分

yetangzhi 发表于 2016-8-4 18:46:58 | 显示全部楼层
第二题就是hash + binary serach, 用unordered_map<string,vector<pair<int,string>>> 来存,每次通过hash找历史记录,在历史记录上binary search lower_bound就行
回复 支持 2 反对 0

使用道具 举报

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];
    }
. From 1point 3acres bbs
    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
};

回复 支持 1 反对 0

使用道具 举报

blackrose 发表于 2016-8-4 01:23:49 | 显示全部楼层
存个user + timestamp 的string?
回复 支持 反对

使用道具 举报

flex 发表于 2016-8-4 02:13:34 | 显示全部楼层
第二题是假设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)。我再想想能不能优化
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-8-4 13:06:12 | 显示全部楼层
flex 发表于 2016-8-4 02:13
第二题是假设timestamp都是整数吗?如果是的话,用unordered_map来存储,第一个string是例子中的'a',后面 ...

可以用order map吗
回复 支持 反对

使用道具 举报

say543 发表于 2016-8-4 13:56:41 | 显示全部楼层
也是想到user + timestamp 的string . 楼主能说说吗?
回复 支持 反对

使用道具 举报

zhihaosun 发表于 2016-8-4 19:53:55 | 显示全部楼层
BIT挺难解释清楚的,相比之下segment tree虽然写得多,占内存也多,但好说啊
回复 支持 反对

使用道具 举报

 楼主| jason88628 发表于 2016-8-5 01:41:49 | 显示全部楼层
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这样。
回复 支持 反对

使用道具 举报

 楼主| jason88628 发表于 2016-8-5 01:45:24 | 显示全部楼层
zhihaosun 发表于 2016-8-4 19:53
BIT挺难解释清楚的,相比之下segment tree虽然写得多,占内存也多,但好说啊

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

使用道具 举报

blackrose 发表于 2016-8-5 05:47:43 | 显示全部楼层
jason88628 发表于 2016-8-5 01:41
可能,题意没写清楚,这里面没有user, 你指的是例子里存a+1作为key么?. From 1point 3acres bbs
Po主当时脑残,说存个类似HashMa ...
. 1point 3acres 璁哄潧
对啊,第二题咋不用 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有序也不是很容易吧 ...
. more info on 1point3acres.com
把pair group成一个data 存这个data的linked list

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

使用道具 举报

 楼主| 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. . visit 1point3acres.com for more.
    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快)。. From 1point 3acres bbs
以及还是要每个key一个BST,不然log(n)的n全局是stream进来的data总数,太不scalable了。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 06:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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