一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 2268|回复: 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 当时没准备好 跪了.鐣欏璁哄潧-涓浜-涓夊垎鍦

1. 周一面的yelp skype 问了resume然后开始做题  Leetcode原题 course schedule 以为我准备好了 结果回答的坑坑洼洼 跪了
面完之后我就去leetcode上写了这一题

2. 周二面的intentional software 只有电话 没有别的online notepad之类的 先问tree 各种traversal 要recursion和iteration 然后问bfs的tree怎么写 然后问graph和tree区别 我一开始说graph有cycle 但是忘了说directed 后面补上了 然后问graph的bfs和dfs 最后做题 Leetcode原题 course schedule(别说 我听到我觉得日了狗)最后竟然发现 我写的时候有一部分多余了。。真的是日了狗TAT
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
3. 今天google 小哥一上来直接问题目 用google doc写的
一锅汤,有胡萝卜和汤,各50份。然后有一堆人会来接汤,有四种人
a. 接一份里面有75%的胡萝卜,25%的汤
b. 接一份里面有50%的胡萝卜,50%的汤
c. 接一份里面有25%的胡萝卜,75%的汤

d. 接一份里面有0%的胡萝卜,100%的汤
.鏈枃鍘熷垱鑷1point3acres璁哄潧
请问 当没有汤的时候,还剩下胡萝卜的这种情况的概率。
. visit 1point3acres.com for more.
我一开始很紧张,想不到,一脸懵。然后我就先写recursion的,写出base step和recursive step。然后他说很好,没有问题,然后他就问complexity。我说因为每一种可能都要算所以是N permutation。然后他让我在doc上写。我一开始还不懂什么意思,然后我写了O(N!)。他说对,我就是想看你会不会写permutation。0_0 接着就问能不能improve。我这个时候已经想到是dp了,于是就说可以,用一个2dmatrix。最后complexity是O(胡萝卜+汤)。他很满意。然后剩下15分钟。扯问题。最后byebye。求过!

新人求大米!!!!

求好运!!!
. Waral 鍗氬鏈夋洿澶氭枃绔,


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

评分

3

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 45
 楼主| jujujuhuakai 发表于 2016-4-1 02:54:10 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
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;. 鍥磋鎴戜滑@1point 3 acres
  4.     }
  5.    if(carrots > 0 && fluid == 0){. From 1point 3acres bbs
  6.         return 1.0;
  7.     }. Waral 鍗氬鏈夋洿澶氭枃绔,
  8.    return (help(carrot-3,fluid-1) + help(carrot-2,fluid-2)+help(carrot-1,fluid-3)+help(carrot,fluid-4))/4;
  9. }
复制代码
回复 支持 1 反对 0

使用道具 举报

say543 发表于 2016-3-31 13:46:43 | 显示全部楼层
关注一亩三分地微博:
Warald
有点不懂 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 怎么算呢? 求指教

应该是萝卜+汤
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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
还是没懂。。。汤就只有这四种可能吗?
. 1point 3acres 璁哄潧
可能是我没有说清楚,我再说一次题目吧。 就是这样的:
有一锅胡萝卜汤,有一队人排队来装汤,一共有四种装法(就是上面描述的)。问题就是,当这锅汤里面的汤被装完了,还剩下胡萝卜的这种情况的概率是多少。
举个🌰,
假如锅里现在有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
可能是我没有说清楚,我再说一次题目吧。 就是这样的:
有一锅胡萝卜汤,有一队人排队来装汤,一共有四 ...

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

  2.         int total = 0;
  3.         int num = 0;.1point3acres缃
  4.         public double getCarrotAndSoupProbability() {
  5.                 double[][] pair = { { 0.75, 0.25 }, { 0.5, 0.5 }, { 0.25, 0.75 },. 1point 3acres 璁哄潧
  6.                                 { 0.0, 1 } };
  7.                 helper(50, 50, pair);
  8.                 if (total != 0) {
  9.                         return (float)num / total;
  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.                 for (int k = 0; k < pair.length; k++) {-google 1point3acres
  23.                         if (carrotNum >= pair[k][0] && soupNum >= pair[k][1]) {
  24.                                 helper(carrotNum - pair[k][0], soupNum - pair[k][1], pair);
  25.                         }
  26.                 }

  27.         }

  28.         public static void main(String[] args) {
  29.                 CarrotAndSoup cs = new CarrotAndSoup();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  30.                 System.out.println(cs.getCarrotAndSoupProbability());.鏈枃鍘熷垱鑷1point3acres璁哄潧
  31.         }
  32. }
复制代码
回复 支持 反对

使用道具 举报

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是这样子写的

这是算的可行的个数吧,题目不是问概率吗?那应该还得需要是总的个数吧
. 1point3acres.com/bbs
补充内容 (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. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这是算的可行的个数吧,题目不是问概率吗?那应该还得需要是总的个数吧

补充内容 (2016-4-1 03:20):

恩恩 一开始我也是这么想写求总数 但是他提醒了我一下可以直接写成概率
回复 支持 反对

使用道具 举报

say543 发表于 2016-4-1 12:11:23 | 显示全部楼层
jujujuhuakai 发表于 2016-4-1 02:54
okok 我说double太麻烦了 就把他们*4 变成整数 就是200份胡萝卜和200份汤 然后recursion是这样子写的
. 鍥磋鎴戜滑@1point 3 acres
受教了 不过termination condition 是不是因该是没有人可以拿就return 0 然后剩redish no soup 就return 0 ? nitpicking 一下...
回复 支持 反对

使用道具 举报

 楼主| jujujuhuakai 发表于 2016-4-1 21:06:09 | 显示全部楼层
say543 发表于 2016-4-1 12:11. visit 1point3acres.com for more.
受教了 不过termination condition 是不是因该是没有人可以拿就return 0 然后剩redish no soup 就return  ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
应该是可以这样子的
回复 支持 反对

使用道具 举报

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, 2017-2-26 19:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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