《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 2964|回复: 18
收起左侧

10分钟前的G店面,面经

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

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

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

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

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

    void put(a, good, 1). 1point3acres.com/bbs
    void put(a, bad, 4)

    get(a, 0)-> null;
    get(a, 2)->good;. 1point 3acres 璁哄潧
    get(a, 4)->bad;
    get(a, 7)->bad;

讨论复杂度,小伙伴们想想怎么存吗,我滚去吃饭啦。. Waral 鍗氬鏈夋洿澶氭枃绔,


补充内容 (2016-8-4 02:37):
Sorry 第一题用的Binary Indexed Tree, 缩写错了。第二题timestamp整数. 1point3acres.com/bbs

补充内容 (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;
}
. Waral 鍗氬鏈夋洿澶氭枃绔,
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
};
. more info on 1point3acres.com
回复 支持 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. 1point3acres.com/bbs
第二题是假设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 . 楼主能说说吗?
. From 1point 3acres bbs
可能,题意没写清楚,这里面没有user, 你指的是例子里存a+1作为key么?. visit 1point3acres.com for more.
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么?
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
. From 1point 3acres bbs
补充内容 (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. . Waral 鍗氬鏈夋洿澶氭枃绔,
    void put(a, val1, 1).鏈枃鍘熷垱鑷1point3acres璁哄潧
    void put(a, val2, 4). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
-google 1point3acres
    get(a, 0)-> null;
    get(a, 2)->val1;
    get(a, 4)->val2;. From 1point 3acres bbs
    get(a, 7)->val2;

回复 支持 反对

使用道具 举报

say543 发表于 2016-8-5 13:55:48 | 显示全部楼层
jason88628 发表于 2016-8-5 11:45. 1point 3acres 璁哄潧
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结构的。. 1point3acres.com/bbs
不过BST还是需要balanced,不然不能保证log(n),特别是像timestamp这种哪怕不保证顺序很可能也almost按顺序的。(其实我觉得需要讨论timestamp插入顺序是不是almost sorted,如果是也许insertion sort比BST快)。
以及还是要每个key一个BST,不然log(n)的n全局是stream进来的data总数,太不scalable了。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-23 21:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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