一亩三分地论坛

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

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

狗狗加面面经【2016-10-13】

[复制链接] |试试Instant~ |关注本帖
printf_ll 发表于 2016-10-14 02:02:20 | 显示全部楼层 |阅读模式

2017(4-6月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚面完来发面经
--------------------
十月初一面. Waral 鍗氬鏈夋洿澶氭枃绔,
面得挺不好的,第一题只记得是个BFS/DFS给地图找路径的题,后来加了什么条件也没听懂,直接跳到第二题,当时还没出的LC399,在他的提示下只来得及说一下数据结构
两周后接到电话加面一轮
--------------------
刚刚二面

第一题不要求写code,要求说数据结构:
假设每天都给一个employee list,里面有id,如果有一个id存在第二天的list但不存在前一天的list,表示是新加入的,离职同理。要求找出哪些是新加入的,哪些是离职的。
楼主回答用两个hashset,前一天与后一天的比较,共有元素直接删除,最后留在前一个的表示是离职的,留在后一个的表示是新加入的。以及问了时间复杂度。
follow up:-google 1point3acres
如果list非常大,那我这个存储量很大,要怎么优化
楼主第一个idea: 如果employee id 存在一些共性的话,可以用trie tree来存储,问了时空复杂度。.鏈枃鍘熷垱鑷1point3acres璁哄潧
楼主第二个idea: 如果employee id是数字,且有range的话,可以用bitmap来存储,后来补充了如果不是数字的话,可以用hash function计算出hash code再用bitmap,问了时空复杂度。大概到这里用了二十分钟吧。

第二题有面经里有看到过
给一个list的digit,给一个maximum number,要求返回所有由这些digit组成的且不超过max的数字,一个digit可以重复使用
比如{3,7,8}, max=1000, 返回{3,33,333,37,38...7,738,...}
突然想到我明明问了她0不能放在第一位的,结果写的时候给忘了...orz
然后写完跑了几个test case,并且跑完她问我有没有可以优化的,我说可以对list排序一下,这样遇到大于max的可以直接返回,不用考虑后序结果
写的时候也忘记考虑有重复数字了。。。orz
最后又问了复杂度,一开始答O(n^2),后来觉得不对,改成了O(n!)。【每题必问复杂度。。。
最后问了几个问题基本准时结束。
求人品!
. 鍥磋鎴戜滑@1point 3 acres

补充内容 (2016-10-18 06:04):. From 1point 3acres bbs
刚刚接到电话,通知onsite了,求人品!

评分

4

查看全部评分

本帖被以下淘专辑推荐:

xuzonghan66 发表于 2016-10-19 15:48:47 | 显示全部楼层
第二题:

  1. public List<Integer> getNumbers(int[] digits, int maxNumber) {
  2.                 List<Integer> result = new ArrayList<Integer>();
  3.                 if(digits.length == 0) return result;
  4.                
  5.                 Arrays.sort(digits);
  6.                 Queue<Integer> queue = new LinkedList<Integer>();
  7.                 queue.add(0);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  8.                
  9.                 while(!queue.isEmpty()){
  10.                         int size = queue.size();
  11.                         for(int i = 0; i < size; i++){
  12.                                 int previous = queue.poll();
  13.                                 for(int j = 0; j < digits.length; j++){
  14.                                         int current = previous * 10 + digits[j]; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  15.                                         if(current <= maxNumber && current != 0){
  16.                                                 queue.add(current); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  17.                                                 result.add(current);
  18.                                         }
  19.                                 }
  20.                         }
  21.                 }
  22.                
  23.                 if(digits[0] == 0) result.add(0, 0); // corner case when there is 0 in digits array
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  24.                 return result;
  25.         }
复制代码
回复 支持 1 反对 0

使用道具 举报

caocancabbage 发表于 2016-11-8 22:35:54 | 显示全部楼层
第二题的DFS代码。.1point3acres缃
. Waral 鍗氬鏈夋洿澶氭枃绔,

  1. void helper(vector<int>& digits, int tmp, int maxNumber, vector<int> &res) {
  2.     if (tmp > maxNumber) {
  3.         return;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  4.     }
  5.     if (tmp != 0) {
  6.         res.push_back(tmp);
  7.     }
  8.     for (int i = 0; i < digits.size(); i++) {
  9.         helper(digits, tmp * 10 + digits[i], maxNumber, res);
  10.     }. from: 1point3acres.com/bbs
  11. }. more info on 1point3acres.com
  12. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  13. vector<int> getNumbers(vector<int>& digits, int maxNumber) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  14.     vector<int> res;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  15.     sort(digits.begin(), digits.end());. from: 1point3acres.com/bbs
  16.     helper(digits,0, maxNumber, res);
  17.     if (digits[0] == 0) {. 鍥磋鎴戜滑@1point 3 acres
  18.         res.push_back(0);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  19.     }
  20.     return res;
  21. }
  22. . 1point 3acres 璁哄潧
  23. . 1point 3acres 璁哄潧
  24. int main() {
  25.     vector<int> nums{3, 7, 8};
  26.     vector<int> res = getNumbers(nums, 1000);
  27.     for (auto a : res) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  28.         cout << a <<endl;
  29.     }
  30.     getchar();
  31. }
复制代码

补充内容 (2016-11-8 22:38):
Assume no duplicates in digits array.
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-10-14 03:37:19 | 显示全部楼层
应该是类似于combination sum的backtracking
回复 支持 反对

使用道具 举报

rinto 发表于 2016-10-14 03:57:23 | 显示全部楼层
谢谢楼主分享
第一题很有意思啊。我是这么想的,前一天的用一个hashset来存,第二天加两个新的hashset,一个存新人,一个存和前一天重复的(从前一天的里面删掉),算完以后没删掉的是离职的,再把两个新的hashset合并用于下一天计算。
如果list很长的话可以分成多个hashset, 比方讲分10个,那就是hashvalue %10来决定存在第几个hashset里面
回复 支持 反对

使用道具 举报

 楼主| printf_ll 发表于 2016-10-14 06:02:26 | 显示全部楼层
rinto 发表于 2016-10-14 03:57
谢谢楼主分享
. 1point3acres.com/bbs第一题很有意思啊。我是这么想的,前一天的用一个hashset来存,第二天加两个新的hashset,一 ...

对,这个方法我在很多关于scalability题目里都有看到,不过我当时没有想到它
回复 支持 反对

使用道具 举报

wopani007 发表于 2016-10-14 06:34:19 | 显示全部楼层
最后又问了复杂度,一开始答O(n^2),后来觉得不对,改成了O(n!)。【每题必问复杂度
.鏈枃鍘熷垱鑷1point3acres璁哄潧
这个时间复杂度是怎么来的呢?我知道这个类似于combination sum,
但是假设平均k个数字组成1000,那么就是n^k啊
回复 支持 反对

使用道具 举报

rinto 发表于 2016-10-14 07:49:47 | 显示全部楼层
printf_ll 发表于 2016-10-14 06:02
对,这个方法我在很多关于scalability题目里都有看到,不过我当时没有想到它

我上的dbms课要求implement hash join,当时是这么做的,所以一下子就想到了~
回复 支持 反对

使用道具 举报

 楼主| printf_ll 发表于 2016-10-14 09:18:34 | 显示全部楼层
wopani007 发表于 2016-10-14 06:34
最后又问了复杂度,一开始答O(n^2),后来觉得不对,改成了O(n!)。【每题必问复杂度

这个时间复杂度是怎 ...

其实我也不太清楚,之前也没有考虑过这个,然后就说了一个n!,不一定是对的
回复 支持 反对

使用道具 举报

黄豆沙君 发表于 2016-10-14 09:28:18 | 显示全部楼层
巨巨加油!!祝你好运!!!!
回复 支持 反对

使用道具 举报

 楼主| printf_ll 发表于 2016-10-14 13:15:52 | 显示全部楼层
黄豆沙君 发表于 2016-10-14 09:28
巨巨加油!!祝你好运!!!!
.鐣欏璁哄潧-涓浜-涓夊垎鍦
你怎么会认出我的!
回复 支持 反对

使用道具 举报

hezhifeng850207 发表于 2016-10-14 23:01:34 | 显示全部楼层
第二题只能backtracking,不能用dp或者memorization?
回复 支持 反对

使用道具 举报

 楼主| printf_ll 发表于 2016-10-14 23:45:15 | 显示全部楼层
hezhifeng850207 发表于 2016-10-14 23:01
第二题只能backtracking,不能用dp或者memorization?

它只要考虑到所有排列的情况就可以了吧,dp要存储什么呢?
回复 支持 反对

使用道具 举报

黄豆沙君 发表于 2016-10-14 23:52:11 | 显示全部楼层
printf_ll 发表于 2016-10-14 13:15. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
你怎么会认出我的!

因为!我聪明!
回复 支持 反对

使用道具 举报

jennyEternal 发表于 2016-10-19 13:37:25 | 显示全部楼层
第二题:
public List<String> getNumbers(List<int> digits, int maxNumber) {
        LinkedList<int> result = new LinkedList();
        recursiveGetNumbers(digits, 0, maxNumber, 0, result);
        return result;
}
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
public void recursiveGetNumbers(List<int> digits, int level, int maxNumber, int curResult, List<int> result) {
        if (level == digits.length) {
                if (curResult <= maxNumber) {
                        result.add(curResult);
                }
                return;
        }
        recursiveGetNumbers(digits, level+1, maxNumber, curResult, result);
        curResult = curResult * 10 + digits[level];
        recursiveGetNumbers(digits, level+1, maxNumber, curResult, result);
} 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

syjohnson 发表于 2016-10-31 09:14:30 | 显示全部楼层
请问bitmap是如何存储达到节省空间的呢
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-31 09:51:47 | 显示全部楼层
syjohnson 发表于 2016-10-31 09:14
请问bitmap是如何存储达到节省空间的呢

bitmap就是用一个“bit [] barr”来代替一个"hashset<int> harr",其中若一个int x在harr中,那么定义barr = 1,否则barr = 0. 这样对于一个长度为N的harr,本来占用内存=N*sizeof(int) = 4*N bytes = 32*N bits. 但如果数组值的范围比较小跨越0~M个int的化,那么就可以把barr的长度定为M+1,这样barr占用内存=(M+1)*1 bit = (M+1) bit. 这样对于数组长度远远超过int的个数的情况下bitmap肯定是节省空间的。
Crack Coding Interview 4th Ed 的Chapter 12有一些处理memory limits的题目。这个好像是个处理大数据节省内存惯用的技巧。这就相当于把一个32bit int type的值如果只看成一个1D的数比较浪费,应该看成是一个32D的0-1 vector.

补充内容 (2016-10-31 09:52):. Waral 鍗氬鏈夋洿澶氭枃绔,
bit[\i] = 1 or 0 ..       [\i]被自动格式化了
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-31 10:01:20 | 显示全部楼层
第一题:若比较2个hashset是否时间复杂度就成了O(N1*N2)了?我是直接在一个hashset中看每个id是否在另外一个hashset中, O(N1+N2)
  1. vector<unordered_set<int>> getLeavingAndNew(unordered_set<int>& day1, unordered_set<int>& day2) {
    . 1point3acres.com/bbs
  2.   vector<unordered_set<int>> res(2); // 0-index list for leaving employee
  3.                                      // 1-index list for new employee
  4.   for (int id : day1) if (!day2.count(id)) res[0].insert(id); // O(N1)
  5.   for (int id : day2) if (!day1.count(id)) res[1].insert(id); // O(N2)
  6.   return res;
  7. }
复制代码
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-31 10:39:55 | 显示全部楼层
第二题:这个可以想成是Trie,每个node都是给定的digits中的一个digit,其子child nodes是所有给定的digits,然后直接做DFS,每个node都累计成一个多位数,若超过maxValue就换个branch继续搜索。注意"0"不能是root的child node。如果将给定的digits排为sorted,那么dfs给出的还是lexicographical ascending的结果。
假设给定的digits有M个,maxValue是一个N位数,那么dfs搜索至多到level N,第k level有M^k个nodes, 所以总时间为O(1+M+M^2+...+M^N) = O((M^(N+1)-1)/(M-1)) = O(M^N) (if M>1; otherwise O(N)).
而显然M<=10为有界的,所以时间就是指数增长的,这个比O(N!)是远远地小的-google 1point3acres
PS:这个题可以延伸到用给定的char set来组成lexicographically 不超过target string的所有strings. 如果char set可以任意多(不局限于ASCII 256),那么时间复杂度就真的是O(M^N)了。
  1. void dfs(set<int>& digits, int target, int cur, vector<int>& res) {
  2.   if (cur >= target) {
  3.     if (cur == target) res.push_back(cur);
  4.     return;
  5.   }
  6.   for (auto it = digits.begin(); it != digits.end(); it++) {
  7.     if (cur == 0 && *it == 0) continue; // leading 0 not allowed
  8.     dfs(digits, target, 10*cur+(*it), res);
  9.   }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  10. }

  11. vector<int> getNumbers(set<int>& digits, int target) {
  12.   vector<int> res;    . From 1point 3acres bbs
  13.   dfs(digits, target, 0, res);
  14.   return res;
    . from: 1point3acres.com/bbs
  15. }
复制代码
回复 支持 反对

使用道具 举报

syjohnson 发表于 2016-10-31 12:12:56 | 显示全部楼层
zzgzzm 发表于 2016-10-31 09:51
bitmap就是用一个“bit [] barr”来代替一个"hashset harr",其中若一个int x在harr中,那么定义barr = 1 ...

多谢答复!所以bit[] barr和int[] iarr的区别只在于barr里只能存0或者1是吧?这样说起来只要hashset里range(min, max) /32 < range(0,max)的话, 那就是bitmap更省空间咯
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 20:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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