一亩三分地论坛

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

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

Yelp Intentional Google 面经 新鲜的

[复制链接] |试试Instant~ |关注本帖
jujujuhuakai 发表于 2016-3-31 08:30:14 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 本科 全职@GoogleYelp, Intentional - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
四个面经 其实是 新鲜的
0. 2月面的Qumulo Leetcode原题 course schedule 当时没准备好 跪了.1point3acres缃

1. 周一面的yelp skype 问了resume然后开始做题  Leetcode原题 course schedule 以为我准备好了 结果回答的坑坑洼洼 跪了
面完之后我就去leetcode上写了这一题
. Waral 鍗氬鏈夋洿澶氭枃绔,
2. 周二面的intentional software 只有电话 没有别的online notepad之类的 先问tree 各种traversal 要recursion和iteration 然后问bfs的tree怎么写 然后问graph和tree区别 我一开始说graph有cycle 但是忘了说directed 后面补上了 然后问graph的bfs和dfs 最后做题 Leetcode原题 course schedule(别说 我听到我觉得日了狗)最后竟然发现 我写的时候有一部分多余了。。真的是日了狗TAT. 鍥磋鎴戜滑@1point 3 acres

3. 今天google 小哥一上来直接问题目 用google doc写的
一锅汤,有胡萝卜和汤,各50份。然后有一堆人会来接汤,有四种人
a. 接一份里面有75%的胡萝卜,25%的汤
b. 接一份里面有50%的胡萝卜,50%的汤
c. 接一份里面有25%的胡萝卜,75%的汤
. 1point 3acres 璁哄潧
d. 接一份里面有0%的胡萝卜,100%的汤

请问 当没有汤的时候,还剩下胡萝卜的这种情况的概率。. more info on 1point3acres.com

我一开始很紧张,想不到,一脸懵。然后我就先写recursion的,写出base step和recursive step。然后他说很好,没有问题,然后他就问complexity。我说因为每一种可能都要算所以是N permutation。然后他让我在doc上写。我一开始还不懂什么意思,然后我写了O(N!)。他说对,我就是想看你会不会写permutation。0_0 接着就问能不能improve。我这个时候已经想到是dp了,于是就说可以,用一个2dmatrix。最后complexity是O(胡萝卜+汤)。他很满意。然后剩下15分钟。扯问题。最后byebye。求过!

新人求大米!!!!

求好运!!! 鏉ユ簮涓浜.涓夊垎鍦拌鍧.



补充内容 (2016-4-1 05:00):
3月31 follow up: 在course schedule这跪了3次。。。。。。。

评分

3

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 45
 楼主| jujujuhuakai 发表于 2016-4-1 02:54:10 | 显示全部楼层
bobzhang2004 发表于 2016-4-1 02:30
楼主可以给一下dp公式吗?

okok 我说double太麻烦了 就把他们*4 变成整数 就是200份胡萝卜和200份汤 然后recursion是这样子写的
  1. double help(int carrots,int fluid){
  2.     if(carrots == 0 && fluid > 0){
  3.         return 0.0;
  4.     }
  5.    if(carrots > 0 && fluid == 0){
  6.         return 1.0;
  7.     }
  8.    return (help(carrot-3,fluid-1) + help(carrot-2,fluid-2)+help(carrot-1,fluid-3)+help(carrot,fluid-4))/4;. visit 1point3acres.com for more.
  9. }
复制代码
回复 支持 1 反对 0

使用道具 举报

say543 发表于 2016-3-31 13:46:43 | 显示全部楼层
有点不懂 N 是代表什么? 是人数吗? 感觉达成条件的总人数似乎会变动 这样probability 怎么算呢? 求指教
回复 支持 反对

使用道具 举报

木木 发表于 2016-3-31 13:58:32 | 显示全部楼层
Course schedule .........  这题跟楼主太有缘了
回复 支持 反对

使用道具 举报

 楼主| jujujuhuakai 发表于 2016-3-31 20:59:09 | 显示全部楼层
say543 发表于 2016-3-31 13:46
有点不懂 N 是代表什么? 是人数吗? 感觉达成条件的总人数似乎会变动 这样probability 怎么算呢? 求指教

应该是萝卜+汤
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-31 21:40:40 | 显示全部楼层
还是没懂。。。汤就只有这四种可能吗?
回复 支持 反对

使用道具 举报

zatarratw 发表于 2016-3-31 22:27:37 | 显示全部楼层
感覺你的Google電面是碾壓過的,別擔心拉~
回复 支持 反对

使用道具 举报

 楼主| jujujuhuakai 发表于 2016-3-31 23:46:35 | 显示全部楼层
bobzhang2004 发表于 2016-3-31 21:40
还是没懂。。。汤就只有这四种可能吗?
. from: 1point3acres.com/bbs
可能是我没有说清楚,我再说一次题目吧。 就是这样的:
有一锅胡萝卜汤,有一队人排队来装汤,一共有四种装法(就是上面描述的)。问题就是,当这锅汤里面的汤被装完了,还剩下胡萝卜的这种情况的概率是多少。
举个🌰,
假如锅里现在有50份萝卜和50份汤,那么下一个人装,有25%的概率这个人会装0.75份的胡萝卜和0.25份的汤;有25%的概率这个人会装0.5份的胡萝卜和0.5份的汤,以此类推剩下的两种。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| jujujuhuakai 发表于 2016-3-31 23:47:01 | 显示全部楼层
zatarratw 发表于 2016-3-31 22:27
感覺你的Google電面是碾壓過的,別擔心拉~

谢谢 真心求过 已经fail了好多了
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-4-1 02:29:28 | 显示全部楼层
jujujuhuakai 发表于 2016-3-31 23:46
可能是我没有说清楚,我再说一次题目吧。 就是这样的:. visit 1point3acres.com for more.
有一锅胡萝卜汤,有一队人排队来装汤,一共有四 ...

写了下代码,时间复杂度很高啊
  1. public class CarrotAndSoup {

  2.         int total = 0;
  3.         int num = 0; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  4.         public double getCarrotAndSoupProbability() {
  5.                 double[][] pair = { { 0.75, 0.25 }, { 0.5, 0.5 }, { 0.25, 0.75 },
  6.                                 { 0.0, 1 } };
  7.                 helper(50, 50, pair);. from: 1point3acres.com/bbs
  8.                 if (total != 0) {
  9.                         return (float)num / total;. Waral 鍗氬鏈夋洿澶氭枃绔,
  10.                 } else {
  11.                         return 0;
  12.                 }
  13.         }

  14.         private void helper(double carrotNum, double soupNum, double[][] pair) {
  15.                 if (carrotNum <= 0 || soupNum <= 0) {
  16.                         total++;
  17.                         if (carrotNum > 0 && soupNum == 0) {
  18.                                 num++;
  19.                         }
  20.                         return;
  21.                 }
  22. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  23.                 for (int k = 0; k < pair.length; k++) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  24.                         if (carrotNum >= pair[k][0] && soupNum >= pair[k][1]) {
  25.                                 helper(carrotNum - pair[k][0], soupNum - pair[k][1], pair);
  26.                         }
  27.                 }
  28. . visit 1point3acres.com for more.
  29.         }
  30. . 1point 3acres 璁哄潧
  31.         public static void main(String[] args) {
  32.                 CarrotAndSoup cs = new CarrotAndSoup();
  33.                 System.out.println(cs.getCarrotAndSoupProbability());
  34.         }
  35. }. From 1point 3acres bbs
复制代码
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-4-1 02:30:23 | 显示全部楼层
楼主可以给一下dp公式吗?
回复 支持 反对

使用道具 举报

jialegavin 发表于 2016-4-1 03:06:53 | 显示全部楼层
dp的话,楼主是怎么做的呢?我的想法是设一个M[200][200],相应的pair变成(1,3),(2,2),(3,1),(4,0),然后从M[200][200]=0开始往前推,推的公式就是M[i][j] = M[i+1][j+3] + M[i+2][j+2]+M[i+3][j+1]+M[i+4][j]?是这样么?
之后把M[0][j]和M[i][0]以及M[0][0]全加起来就是total?
求大神指点一下
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-4-1 03:14:05 | 显示全部楼层
jujujuhuakai 发表于 2016-4-1 02:54
okok 我说double太麻烦了 就把他们*4 变成整数 就是200份胡萝卜和200份汤 然后recursion是这样子写的

这是算的可行的个数吧,题目不是问概率吗?那应该还得需要是总的个数吧. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

补充内容 (2016-4-1 03:20):
没看到除以4,应该是对的
回复 支持 反对

使用道具 举报

 楼主| jujujuhuakai 发表于 2016-4-1 03:31:37 | 显示全部楼层
jialegavin 发表于 2016-4-1 03:06
dp的话,楼主是怎么做的呢?我的想法是设一个M[200][200],相应的pair变成(1,3),(2,2),(3,1),(4 ...

我后来写iterative的时候就是建一个M[201][201] 然后initialize各种情况 然后从carrot = 3 和fluid =4 开始往carrot = 200 和fluid = 200那里加。
回复 支持 反对

使用道具 举报

 楼主| jujujuhuakai 发表于 2016-4-1 03:32:02 | 显示全部楼层
bobzhang2004 发表于 2016-4-1 03:14
这是算的可行的个数吧,题目不是问概率吗?那应该还得需要是总的个数吧
. 1point3acres.com/bbs
补充内容 (2016-4-1 03:20):
. 1point3acres.com/bbs
恩恩 一开始我也是这么想写求总数 但是他提醒了我一下可以直接写成概率
回复 支持 反对

使用道具 举报

say543 发表于 2016-4-1 12:11:23 | 显示全部楼层
jujujuhuakai 发表于 2016-4-1 02:54
okok 我说double太麻烦了 就把他们*4 变成整数 就是200份胡萝卜和200份汤 然后recursion是这样子写的

受教了 不过termination condition 是不是因该是没有人可以拿就return 0 然后剩redish no soup 就return 0 ? nitpicking 一下...
回复 支持 反对

使用道具 举报

 楼主| jujujuhuakai 发表于 2016-4-1 21:06:09 | 显示全部楼层
say543 发表于 2016-4-1 12:11-google 1point3acres
受教了 不过termination condition 是不是因该是没有人可以拿就return 0 然后剩redish no soup 就return  ...
.1point3acres缃
应该是可以这样子的
回复 支持 反对

使用道具 举报

lowatt 发表于 2016-4-1 21:30:53 | 显示全部楼层
请问LZ这是本科的职位还是研究生的?
回复 支持 反对

使用道具 举报

 楼主| jujujuhuakai 发表于 2016-4-1 21:44:40 | 显示全部楼层
lowatt 发表于 2016-4-1 21:30
请问LZ这是本科的职位还是研究生的?

本科。。。。这字数限制
回复 支持 反对

使用道具 举报

hayreddinluo 发表于 2016-4-2 13:10:49 | 显示全部楼层
感谢楼主分享的面经!!!
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
楼主,胡萝卜汤的题可不可以这样。total是所有的情况,num是没汤还剩胡萝卜的情况。 用一个QUEUE存int[] 每个int[]就俩数字是胡萝卜数和汤数,然后把[200,200]放进去,每次去减[3,1],[2,2],[1,3],[0,4]减出来的结果加到queue里, 减出来的结果:若有负数就不要,胡萝卜大于0汤等于0 num和total都++. 胡萝卜0汤大于等于0就只total++。 返回num/total。 这样可以么?  感觉矩阵dp的话有好些点事不可能取到的,比如剩199个汤200个胡萝卜啥的。

补充内容 (2016-4-2 13:23):-google 1point3acres
负数应该也算进去。。。  而且好像和DFS时间一样的。。。但是时间应该是4 ^100,不是4叉树最多100层么?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 23:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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