传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 3021|回复: 27
收起左侧

01/27 新鲜的Google实习面经

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

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

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

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

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

第一轮
国人小哥 很nice 上来先自我介绍 然后问我做过的安卓项目 然后开始做题
游客,本帖隐藏的内容需要积分高于 133 才可浏览,您当前积分为 0。 查看如何攒积分

第二轮
白人小哥 因为知道自己已经没戏了 所以就安慰自己说下一轮就当是攒经验的 然后就没那么紧张了 也是一位很nice的小哥 上来不废话 直接贴题
游客,本帖隐藏的内容需要积分高于 155 才可浏览,您当前积分为 0。 查看如何攒积分
.鏈枃鍘熷垱鑷1point3acres璁哄潧
用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。 然后让我问了问问题就结束了. 鍥磋鎴戜滑@1point 3 acres

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

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

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


补充内容 (2016-2-2 08:46):
上周五接到电话 被拒啦. visit 1point3acres.com for more.

. visit 1point3acres.com for more.补充内容 (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, 当落在这个范围内就把该点的值压栈,不知道能不能行?请问楼主有更好的办法么
. visit 1point3acres.com for more.
MovingAverage 想请问楼主是in-Queue所有的nums么?还是只in-Queue了k个啊?

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){. from: 1point3acres.com/bbs
            minValue = Math.min(node.val,minValue);
            node=node.left;
        }else if(node.val<min) node=node.right;
        else node=node.left;
    }
    return minValue;
}. From 1point 3acres bbs

回复 支持 反对

使用道具 举报

 楼主| 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);
  }
}

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;
}



补充内容 (2016-1-28 13:07):. From 1point 3acres bbs
还有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 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
谢谢分享! 我脑子想岔了,确实如果只要一个的话栈里面剩下的元素都没用。受了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
帮楼主回答下,我觉得没那么麻烦,因为是BST,所以只需要把节点分成三种,1比范围小,2在范围内,3比范围 ...

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

使用道具 举报

lxxxxxxx 发表于 2016-1-28 13:49:27 | 显示全部楼层
atwoodwang0918 发表于 2016-1-28 12:20-google 1point3acres
用递归怎么写啊。。我实在是想不出怎么不用全局变量

不用全局变量有一个很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 ...
. visit 1point3acres.com for more.
谢谢~我后来也自己写了个递归的 没用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){
        return calsmallest(node.right,min,max);
    }
    if(node.val > max){. visit 1point3acres.com for more.
        return calsmallest(node.left,min,max);
    }else{
        return Math.min(calsmallest(node.left,min,node.val),node.val);
    }
}
.鐣欏璁哄潧-涓浜-涓夊垎鍦. visit 1point3acres.com for more.

回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-24 16:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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