一亩三分地论坛

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

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

01/27 新鲜的Google实习面经

[复制链接] |试试Instant~ |关注本帖
atwoodwang0918 发表于 2016-1-28 08:11:20 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
人生第一次面试 献给了google 其实已经很用心的准备了 从11月刷题到现在 寒假哪都没去 每天从早到晚 但是还是跪了 而且跪得是妥妥的 哎 虽然挺不甘心 但是也只能怪自己实力不够经验不足而且心理素质那是差的惨不忍睹。

第一轮
国人小哥 很nice 上来先自我介绍 然后问我做过的安卓项目 然后开始做题
给一个BST和一个range 求value在这个range里面且value最小的那个node。 拿到题第一反应还感觉蛮幸运的 感觉比其他地里的同学的面经简单多了 但是真正做起来的时候发现 自己太紧张了 集中不了注意力 智商出差 脑子一片浆糊 怎么想都感觉不对 小哥很耐心的给了我提示 但是我的脑子依然不在服务区 后来先写了一个brute force O(n)time的 小哥也很耐心说可以 写完后要我improve 然后脑子又没信号了 后来在小哥的各种 真是各种提示下写了出来 但是我之前用了个全局变量 小哥说要我不用全局变量再写写 呵呵 相信你们已经不意外了 脑子又断线了 最后时间不够了 小哥让我问了问问题就结束了 我说我太紧张了 发挥太差了 他还安慰我说没事回去多练习以后还有机会 挂了电话以后 5分钟不到做出来了 我真是。。。。想抽我自己. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第二轮
白人小哥 因为知道自己已经没戏了 所以就安慰自己说下一轮就当是攒经验的 然后就没那么紧张了 也是一位很nice的小哥 上来不废话 直接贴题
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第一题 MovingAverage.1point3acres缃
好像前几天地里有同学发过这道题 我当时没仔细看 结果理解题意理解了好久才懂-google 1point3acres
写一个 method MovingAverage(int num) 提前告诉你一个int n 每次调用这个方法 就把num加进一个队列中 然后返回最近n个数的平均值
比如 如果n是3那么
MovingAverage(1)->1/1. 1point3acres.com/bbs
MovingAverage(2)->(1+2)/2. more info on 1point3acres.com
MovingAverage(3)->(1+2+3)/3
MovingAverage(4)->(2+3+4)/3
MovingAverage(5)->(3+4+5)/3

用queue很快做出来了 然后小哥问了问时间空间复杂度 然后问我怎么improve space complexity 我有点蒙 感觉O(n)已经最小了 然后我说用bitmap 他说不用用那么高级的 用个折中一点的方法 我想了1分钟没想出来 小哥就说It's OK. Your code seems pretty good to me. let's move on.

第二题 Number of islands ii leetcode原题
我做过number of islands1 但是没做过2 听完描述以后我觉得可以用brute force 每次更新完 就调用number of islands1里那个函数算一共有多少个islands 我说我在想更好的揭发 小哥说这个就可以了 写吧 我就写了 中间有个小bug 我过test case的时候发现了 然后改正了 写完小哥也是说seems pretty good to me。 然后让我问了问问题就结束了

两个题小哥都要我自己跑test case 然后做题的时候不停的要我说自己的想法 我只要沉默10秒钟以上他就说talk to me, tell me what are u thinking.=_= 说实话我还有点不习惯这样边做边说 感觉会影响到思考。。以后多面几次可能会适应点

哎 虽然没什么希望 但是还是求个加面吧 总的来说两题都不难 我算是很幸运的了 但因为心理素质太差 本来实力就不是很强结果还没有发挥出 挺遗憾的 不过跪是不跪他妈 就当是涨经验啦 希望其他还没消息的公司能快点给我面试啊拜托!!!

. from: 1point3acres.com/bbs 最后 希望群里的大家都能拿到梦想的offer!!也希望自己的努力终会有回报!!
. 1point3acres.com/bbs


补充内容 (2016-2-2 08:46):
上周五接到电话 被拒啦.鐣欏璁哄潧-涓浜-涓夊垎鍦

补充内容 (2016-2-2 08:47):
不过也不意外哈哈

评分

6

查看全部评分

pustar 发表于 2016-9-25 08:03:53 | 显示全部楼层
第二轮第1题用滑动窗口的方法就行了吧?进窗口的时候,sum += A[end++], 出窗口的时候 sum -= A[begin++], 空间复杂度)(1)
回复 支持 1 反对 0

使用道具 举报

singku 发表于 2016-1-28 08:37:49 | 显示全部楼层
露珠加油。我昨天面的第一面 感觉也是脑子断线抽风 挂完电话分分钟做出来。不要灰心 后面还有其他的
回复 支持 反对

使用道具 举报

zxl9171 发表于 2016-1-28 09:04:07 | 显示全部楼层
island2还是挺难的。。。准备赶紧去看一下
回复 支持 反对

使用道具 举报

 楼主| atwoodwang0918 发表于 2016-1-28 10:07:49 | 显示全部楼层
singku 发表于 2016-1-28 08:37
露珠加油。我昨天面的第一面 感觉也是脑子断线抽风 挂完电话分分钟做出来。不要灰心 后面还有其他的

谢谢!!你也加油哦!!~
回复 支持 反对

使用道具 举报

lxxxxxxx 发表于 2016-1-28 10:54:29 | 显示全部楼层
请教楼主,第一题我想的是,额外拿一个栈,假如range是 [low, high],就curNode.val < low时下一次找右节点,否则curNode = curNode.right, 当落在这个范围内就把该点的值压栈,不知道能不能行?请问楼主有更好的办法么

MovingAverage 想请问楼主是in-Queue所有的nums么?还是只in-Queue了k个啊?. 鍥磋鎴戜滑@1point 3 acres

Number of islands ii  确实好难....
回复 支持 反对

使用道具 举报

zxl9171 发表于 2016-1-28 11:14:04 | 显示全部楼层
lxxxxxxx 发表于 2016-1-28 10:54
请教楼主,第一题我想的是,额外拿一个栈,假如range是 [low, high],就curNode.val < low时下一次找右节点 ...

帮楼主回答下,我觉得没那么麻烦,因为是BST,所以只需要把节点分成三种,1比范围小,2在范围内,3比范围大,如果1,那找右儿子,如果2,找左儿子,3找左儿子,直到叶子节点,路上比较一下,记录在范围内且最小的就行了。
回复 支持 反对

使用道具 举报

stellari 发表于 2016-1-28 11:16:31 | 显示全部楼层
lxxxxxxx 发表于 2016-1-28 10:54
请教楼主,第一题我想的是,额外拿一个栈,假如range是 [low, high],就curNode.val < low时下一次找右节点 ...

其实不用栈。如果root->val比high大,那么要找的点肯定在左边:root=root->left;如果root->val比low小,那么同理root=root->right; 否则更新一个变量(如果是递归实现的话,这个就需要是一个全局变量,可能就是lz说的那个全局变量)minVal=min(minVal, root->val),root=root->left。



回复 支持 反对

使用道具 举报

stellari 发表于 2016-1-28 11:16:57 | 显示全部楼层
不让用全局变量的话,取巧的方法是一开始就写一个类,把getMinValInRange()包在里面,minVal作为类的private成员变量就行了:全局变量是不好,但是我用个private成员变量没关系吧?
回复 支持 反对

使用道具 举报

 楼主| atwoodwang0918 发表于 2016-1-28 12:18:28 | 显示全部楼层
lxxxxxxx 发表于 2016-1-28 10:54
请教楼主,第一题我想的是,额外拿一个栈,假如range是 [low, high],就curNode.val < low时下一次找右节点 ...

对的 楼下的同学已经解释的很清楚了 就是分3种情况处理就行了 我当时就是太紧张了 被绕进去了 哎 我写了写代码 你可以用做参考
  1. <blockquote>public int calsmallest(TreeNode node,int min,int max){
复制代码
回复 支持 反对

使用道具 举报

 楼主| atwoodwang0918 发表于 2016-1-28 12:19:37 | 显示全部楼层
public int calsmallest(TreeNode node,int min,int max){
    int minValue = Integer.MAX_VALUE;
    while(node!=null){
        if(node.val>=min&&node.val<=max){
            minValue = Math.min(node.val,minValue);
            node=node.left;
        }else if(node.val<min) node=node.right;
        else node=node.left;
    }
    return minValue;. more info on 1point3acres.com
}

.鏈枃鍘熷垱鑷1point3acres璁哄潧
回复 支持 反对

使用道具 举报

 楼主| atwoodwang0918 发表于 2016-1-28 12:20:18 | 显示全部楼层
stellari 发表于 2016-1-28 11:16
其实不用栈。如果root->val比high大,那么要找的点肯定在左边:root=root->left;如果root->val比low小, ...

用递归怎么写啊。。我实在是想不出怎么不用全局变量
回复 支持 反对

使用道具 举报

iwofr 发表于 2016-1-28 12:51:27 | 显示全部楼层
atwoodwang0918 发表于 2016-1-28 12:20. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
用递归怎么写啊。。我实在是想不出怎么不用全局变量

写一个helper啊,然后把return的variable的地址当成参数传进去,helper里直接就改就好了
回复 支持 反对

使用道具 举报

iwofr 发表于 2016-1-28 13:06:18 | 显示全部楼层
iwofr 发表于 2016-1-28 12:51
写一个helper啊,然后把return的variable的地址当成参数传进去,helper里直接就改就好了
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
大概这样
void calSmallest(TreeNode *root, int min, int max, int &ret) {
  if (!root) return;
  if (root->val > max) {
    calSmallest(root->left, min, max, ret);
  } else if (root->val < min) {
    calSmallest(root->right, min, max, ret);
  } else { // root->val < max && root->val > min                                                                                                                                                                     
    ret = root->val;
    if (root->val == min) return; // find min possible                                                                                                                                                               
    else calSmallest(root->left, min, max, ret);
  }
}
.1point3acres缃
int calSmallest(TreeNode *root, int min, int max) {
  int ret = INT_MAX; // return INT_MAX if no root->val in [min, max]                                                                                                                                                
  calSmallest(root, min, max, ret);
  return ret;
}

. Waral 鍗氬鏈夋洿澶氭枃绔,

补充内容 (2016-1-28 13:07):.鐣欏璁哄潧-涓浜-涓夊垎鍦
还有lz紧张挺正常的,我之前面试也是总紧张,有一次让写reverse linked list我都没写出来。。。
回复 支持 反对

使用道具 举报

lxxxxxxx 发表于 2016-1-28 13:46:11 | 显示全部楼层
atwoodwang0918 发表于 2016-1-28 12:19
public int calsmallest(TreeNode node,int min,int max){
    int minValue = Integer.MAX_VALUE;
    w ...

谢谢分享! 我脑子想岔了,确实如果只要一个的话栈里面剩下的元素都没用。受了leetcode那道类似题的影响...如果followup估计就是问k个了,就需要用两个栈倒来倒去了....
回复 支持 反对

使用道具 举报

lxxxxxxx 发表于 2016-1-28 13:46:48 | 显示全部楼层
stellari 发表于 2016-1-28 11:16
其实不用栈。如果root->val比high大,那么要找的点肯定在左边:root=root->left;如果root->val比low小, ...

对对,有道理,我没太想清楚,也只有栈顶元素有用。谢谢分享~
回复 支持 反对

使用道具 举报

lxxxxxxx 发表于 2016-1-28 13:47:41 | 显示全部楼层
zxl9171 发表于 2016-1-28 11:14-google 1point3acres
帮楼主回答下,我觉得没那么麻烦,因为是BST,所以只需要把节点分成三种,1比范围小,2在范围内,3比范围 ...

有道理!受教了,感谢分享
回复 支持 反对

使用道具 举报

lxxxxxxx 发表于 2016-1-28 13:49:27 | 显示全部楼层
atwoodwang0918 发表于 2016-1-28 12:20
用递归怎么写啊。。我实在是想不出怎么不用全局变量
. from: 1point3acres.com/bbs
不用全局变量有一个很tricky的做法就是传一个数组,但是数组里面只有一个元素当做max,这样在函数间调来调去就不会是值传递了
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-1-28 14:52:20 | 显示全部楼层
请问moving average 怎么优化空间? 可能可以用trie 把bits看成字符串。不知道对不对?
回复 支持 反对

使用道具 举报

 楼主| atwoodwang0918 发表于 2016-1-28 22:30:14 | 显示全部楼层
iwofr 发表于 2016-1-28 13:06
大概这样void calSmallest(TreeNode *root, int min, int max, int &ret) {  if (!root) return;  if (ro ...

谢谢~我后来也自己写了个递归的 没用helper fuction 但是不知道对不对 因为在没有范围内的值得时候我返回的是Integer.MAX_VALUE;public int calsmallest(TreeNode node,int min,int max){
    if(node==null) return Integer.MAX_VALUE;
    if(node.val < min){. visit 1point3acres.com for more.
        return calsmallest(node.right,min,max);
    }
    if(node.val > max){
        return calsmallest(node.left,min,max);
    }else{
        return Math.min(calsmallest(node.left,min,node.val),node.val);
    }
}


鏉ユ簮涓浜.涓夊垎鍦拌鍧.
回复 支持 反对

使用道具 举报

 楼主| atwoodwang0918 发表于 2016-1-28 22:31:00 | 显示全部楼层
kinggarden2001 发表于 2016-1-28 14:52
请问moving average 怎么优化空间? 可能可以用trie 把bits看成字符串。不知道对不对?

我不知道哎。。我没有想出来 用trie怎么做呢??
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 15:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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