Berkeley biostat应该是biostat里最非传统,最偏ml的超棒项目了!

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 4603|回复: 30
收起左侧

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

[复制链接] |试试Instant~
我的人缘0
printf_ll 发表于 2016-10-14 02:02:20 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (19)
 
 
0% (0)  踩

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

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

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

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

第一题不要求写code,要求说数据结构:
假设每天都给一个employee list,里面有id,如果有一个id存在第二天的list但不存在前一天的list,表示是新加入的,离职同理。要求找出哪些是新加入的,哪些是离职的。
楼主回答用两个hashset,前一天与后一天的比较,共有元素直接删除,最后留在前一个的表示是离职的,留在后一个的表示是新加入的。以及问了时间复杂度。
follow up:
如果list非常大,那我这个存储量很大,要怎么优化
楼主第一个idea: 如果employee id 存在一些共性的话,可以用trie tree来存储,问了时空复杂度。
楼主第二个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!)。【每题必问复杂度。。。
最后问了几个问题基本准时结束。
求人品!


补充内容 (2016-10-18 06:04):
刚刚接到电话,通知onsite了,求人品!

评分

参与人数 4大米 +128 收起 理由
jennyEternal + 5 回答的很好!
harrypotter + 3 感谢分享!
whdawn + 70
candy_shmily + 50

查看全部评分


上一篇:求netsuite onsite面经!
下一篇:求InterSystems onsite面经

本帖被以下淘专辑推荐:

我的人缘0
caocancabbage 发表于 2016-11-8 22:35:54 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (6)
 
 
0% (0)  踩
第二题的DFS代码。


  1. void helper(vector<int>& digits, int tmp, int maxNumber, vector<int> &res) {
  2.     if (tmp > maxNumber) {
  3.         return;
  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.     }
  11. }

  12. vector<int> getNumbers(vector<int>& digits, int maxNumber) {
  13.     vector<int> res;
  14.     sort(digits.begin(), digits.end()); 来源一亩.三分地论坛.
  15.     helper(digits,0, maxNumber, res);. from: 1point3acres
  16.     if (digits[0] == 0) {
  17.         res.push_back(0);
  18.     }
  19.     return res;
  20. }


  21. int main() {. 1point3acres
  22.     vector<int> nums{3, 7, 8};
  23.     vector<int> res = getNumbers(nums, 1000);.留学论坛-一亩-三分地
  24.     for (auto a : res) {
  25.         cout << a <<endl;
  26.     }
  27.     getchar();
  28. }
复制代码

补充内容 (2016-11-8 22:38):
Assume no duplicates in digits array.
回复

使用道具 举报

我的人缘0
xuzonghan66 发表于 2016-10-19 15:48:47 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (24)
 
 
0% (0)  踩
第二题:
. 一亩-三分-地,独家发布
  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>();.本文原创自1point3acres论坛
  7.                 queue.add(0);.本文原创自1point3acres论坛
  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++){. From 1point 3acres bbs
  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.                 }
    . more info on 1point3acres
  22.                
  23.                 if(digits[0] == 0) result.add(0, 0); // corner case when there is 0 in digits array.1point3acres网
  24.                 return result;. more info on 1point3acres
  25.         }
复制代码
回复

使用道具 举报

我的人缘0
wtcupup 发表于 2016-10-14 03:37:19 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  61% (348)
 
 
38% (215)  踩
应该是类似于combination sum的backtracking
回复

使用道具 举报

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

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
 楼主| printf_ll 发表于 2016-10-14 06:02:26 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (19)
 
 
0% (0)  踩
rinto 发表于 2016-10-14 03:57
谢谢楼主分享
第一题很有意思啊。我是这么想的,前一天的用一个hashset来存,第二天加两个新的hashset,一 ...
. visit 1point3acres for more.
对,这个方法我在很多关于scalability题目里都有看到,不过我当时没有想到它
回复

使用道具 举报

我的人缘0
wopani007 发表于 2016-10-14 06:34:19 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (11)
 
 
0% (0)  踩
最后又问了复杂度,一开始答O(n^2),后来觉得不对,改成了O(n!)。【每题必问复杂度

这个时间复杂度是怎么来的呢?我知道这个类似于combination sum,
但是假设平均k个数字组成1000,那么就是n^k啊
回复

使用道具 举报

我的人缘0
rinto 发表于 2016-10-14 07:49:47 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
printf_ll 发表于 2016-10-14 06:02
对,这个方法我在很多关于scalability题目里都有看到,不过我当时没有想到它
. from: 1point3acres
我上的dbms课要求implement hash join,当时是这么做的,所以一下子就想到了~

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

我的人缘0
 楼主| printf_ll 发表于 2016-10-14 09:18:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (19)
 
 
0% (0)  踩
wopani007 发表于 2016-10-14 06:34 来源一亩.三分地论坛.
最后又问了复杂度,一开始答O(n^2),后来觉得不对,改成了O(n!)。【每题必问复杂度

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

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

使用道具 举报

我的人缘0
黄豆沙君 发表于 2016-10-14 09:28:18 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (20)
 
 
4% (1)  踩
巨巨加油!!祝你好运!!!!
回复

使用道具 举报

我的人缘0
 楼主| printf_ll 发表于 2016-10-14 13:15:52 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (19)
 
 
0% (0)  踩
黄豆沙君 发表于 2016-10-14 09:28
巨巨加油!!祝你好运!!!!

你怎么会认出我的!

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
hezhifeng850207 发表于 2016-10-14 23:01:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
第二题只能backtracking,不能用dp或者memorization?
回复

使用道具 举报

我的人缘0
 楼主| printf_ll 发表于 2016-10-14 23:45:15 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (19)
 
 
0% (0)  踩
hezhifeng850207 发表于 2016-10-14 23:01
第二题只能backtracking,不能用dp或者memorization?

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

使用道具 举报

我的人缘0
黄豆沙君 发表于 2016-10-14 23:52:11 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (20)
 
 
4% (1)  踩
printf_ll 发表于 2016-10-14 13:15
你怎么会认出我的!
.本文原创自1point3acres论坛
因为!我聪明!
回复

使用道具 举报

我的人缘0
jennyEternal 发表于 2016-10-19 13:37:25 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  99% (122)
 
 
0% (1)  踩
第二题:
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) {. visit 1point3acres for more.
                        result.add(curResult);
                }
                return;
        }. From 1point 3acres bbs
        recursiveGetNumbers(digits, level+1, maxNumber, curResult, result);
        curResult = curResult * 10 + digits[level];.本文原创自1point3acres论坛
        recursiveGetNumbers(digits, level+1, maxNumber, curResult, result);
}-google 1point3acres

评分

参与人数 1大米 +3 收起 理由
harrypotter + 3 回答的很好!

查看全部评分

回复

使用道具 举报

我的人缘0
syjohnson 发表于 2016-10-31 09:14:30 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (55)
 
 
1% (1)  踩
请问bitmap是如何存储达到节省空间的呢
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-31 09:51:47 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
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肯定是节省空间的。.本文原创自1point3acres论坛
Crack Coding Interview 4th Ed 的Chapter 12有一些处理memory limits的题目。这个好像是个处理大数据节省内存惯用的技巧。这就相当于把一个32bit int type的值如果只看成一个1D的数比较浪费,应该看成是一个32D的0-1 vector.. visit 1point3acres for more.

补充内容 (2016-10-31 09:52):
bit[\i] = 1 or 0 ..       [\i]被自动格式化了
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-31 10:01:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
第一题:若比较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) {
  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. }
复制代码
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-31 10:39:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
第二题:这个可以想成是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!)是远远地小的
PS:这个题可以延伸到用给定的char set来组成lexicographically 不超过target string的所有strings. 如果char set可以任意多(不局限于ASCII 256),那么时间复杂度就真的是O(M^N)了。
. from: 1point3acres
  1. void dfs(set<int>& digits, int target, int cur, vector<int>& res) {. from: 1point3acres
  2.   if (cur >= target) {. more info on 1point3acres
  3.     if (cur == target) res.push_back(cur); . Waral 博客有更多文章,
  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;   
  13.   dfs(digits, target, 0, res);
  14.   return res;
  15. }
复制代码
回复

使用道具 举报

我的人缘0
syjohnson 发表于 2016-10-31 12:12:56 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (55)
 
 
1% (1)  踩
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更省空间咯
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

GMT+8, 2018-9-26 05:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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