一亩三分地论坛

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

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

Google onsite @NY

[复制链接] |试试Instant~ |关注本帖
sophialyj 发表于 2015-11-2 00:56:08 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 博士 全职@Google - 内推 - 技术电面 Onsite |Otherfresh grad应届毕业生

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

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

x
电面: . 1point 3acres 璁哄潧
1. Find the index in the array: a[i] = i; binary search -google 1point3acres
2. 给一个BT, 每个node有一个next,当该node没有right child时,指向inorder successor,otherwise null。 让不用stack和recursion,inorder 遍历BT。.鏈枃鍘熷垱鑷1point3acres璁哄潧
3. initialize BT with next.
. 1point3acres.com/bbs
电面是一个印度gg,迟到了15分钟,说话听不太懂,不过貌似没黑我。. 1point 3acres 璁哄潧

电面(gg的 - for intern)
第一轮, merge interval的简化版和变形,具体不太记得了,但基本和leetcode是一样的. 1point 3acres 璁哄潧
第二轮,2 sum, 3 sum, 两个包含duplicate的 array A和B,输出A-B, B-A(A中有B中没有 and B中有A中没有)
目前project match中,祈祷~~~

onsite 这周四面的,一共四轮
1. 一美国年轻gg,临时换的人,晚了15分钟,一上来问iphone屏幕解锁多少种方式? (10^4), android 划屏解锁多少种方式(每个点都能走,每个点都要遍历到)? 9!。让比较那种更加secure,也就是10^4还是9!大。
然后upgrade了android得划屏解锁constraint。
1  2  3
4  5  6
7  8  9. more info on 1point3acres.com
对于每一个节点可以走到相邻的节点,比如1可以走到2,4,5, 也可以走到 6, 8。 但是当2,4,5没有走到的时候不能直接走到3,7,9(因为会穿过2,4,5)。但是当2,4,5已经走过的时候就可以直接走到3,7,9.
问题是一共有多少种解屏方式?
貌似用起始点+到达点看符不符合条件判断可能比较好,有点像n queens的感觉。但是楼主这轮本来开始得就晚,码了10分钟,门外竟然就来了下一个面试官。最后也没有码完,也就是交流了下思路。当时面完就觉得这轮跪了,但是最后recruiter临走前问我感觉咋样,我说第一轮感觉不好,她说第一轮的feedback是positive的。不过我猜也就是刚刚positive那种

2. 一美国大叔。
a) 求所有10 digits的数中的perfect square。 perfect square的定义就是平方啦~~~ constraints: 10 digits里要包含0-9中所有的数字。 . visit 1point3acres.com for more.
我当时的answers是找 10^4.5 - 10^5 的平方,看是不是满足条件,然后估计了一下10^4.5的值。检验10 digits是否有重复,就用了个boolean[10]来判断。
b) 先画了一个BST,让写出inorder 和 preorder的遍历方式,然后问能不能通过遍历出来的序列返回原来的BST。 楼主中leetcode的已深,一直觉得要inorder和preorder一起才能给出原来的BST。 楼主顺利给出了inorder的反例,然后卡在了preorder上,觉得仅靠preorder可以给出原来的BST,然后码了一下,我觉得修改版的Binary search应该可以找到分开左子树和有子树的index,但是我当时觉得没啥时间了,直接硬找,因为毕竟preorder给出的不是ordered array。面试官也表示了满意。回来想了下leetcode上说的是BT而不是BST。

午饭: 一美国mm

3. 一美国年轻gg,来google一年,第一次面试,带了个senior的shadow,问的题目是valid UTF8.
感觉gg的水平不咋的,一上来问我知道几种表示string的方法,我说我不知道你在问啥,然后回我说就是asc啥的,我说我只知道asc。。。 然后就说你听说过UTF8吗?我表示不是很熟悉。
最后给了一下utf8的表示方式,然后让判断一个byte array是valid utf8. 当中我问了他一下byte的表示方式,我是这么问的: 是不是 0b......,他说我觉得是0x......,然后我也没咋想,就用了0x。shadow就是不说话啊不说话。我就觉得0x不是16进制吗?但我还是用了0x,回来后发现明明应该用0b。
我一开始以为是判断一个utf8字符是不是valid,结果shadow说是一串utf8. 我当时脑子短路了,竟然用了dfs去判断一串是否valid,当然能work,但是时间复杂度大大提高。美国gg啥都没说,感觉他比我还紧张,就让走了几个test case。
估计如果跪了,这一轮肯定是主要原因。

4. 中国gg,终于看到一个中国人啊。很nice,希望feedback也一样nice
先问了一下知不知道 permutation和combination,写了一下combination的公式。然后让给出所有从一个 含n个char[]里找k个char的所有方式。dfs之。题很简单,但是走了好几遍他给的test case,所以剩下的时间也不是很多了。.鐣欏璁哄潧-涓浜-涓夊垎鍦
最后问了道非常简单的sql,告诉我说本来应该先问sql的,但是怕先问了sql,前面那题会时间不够。

题目除了第一轮,都不是很难。希望能够rp爆棚! 不过看大家都做得那么好,估计第3轮那么二的一个做法足以让我跪了吧。。。。
最后求点大米吧!

.鏈枃鍘熷垱鑷1point3acres璁哄潧

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

评分

4

查看全部评分

本帖被以下淘专辑推荐:

cnsudo 发表于 2015-11-9 05:13:21 | 显示全部楼层
我在mtv onsite也遇到安卓解锁的题,不过只是问长度为k的密码有多少种。
  1. public void dfs(int remainingLength, int visited, int lastKey).鏈枃鍘熷垱鑷1point3acres璁哄潧
  2. //remainingLength剩下的长度
  3. //visited,每visit一个key,下一层dfs的时候传入visited+1<<currentKey. more info on 1point3acres.com
  4. //lastKey上一层的key
复制代码
-google 1point3acres
dfs函数里遍历currentKey从1到9,如果(visited&(1<<currentKey))!=0就跳过,否则看(lastKey+current)%2是否等于0,
如果等于0就说明会经过一个midKey,看midKey是不是visited;如果不等于0就放心进入下一层。
remainingLength==0的时候global计数加一跳出。
. 1point3acres.com/bbs
我觉得稍微改一改用Queue或Stack实现一个bfs或者dfs就能做你那题,不过这样空间复杂度好像有点高。. From 1point 3acres bbs

补充内容 (2015-11-9 17:10):
想了想,对于经过一个midkey的arc的判断条件不够充分。一个arc经过一个midkey的条件应该是
(lastKey+currentKey)%2==0&&(Math.abs(lastKey/3-currentKey/3)==2||Math.abs(lastKey%3-currentKey%3)==2)
应该就可以...

补充内容 (2015-11-9 17:15):
上面还有bug,下面这样应该可以。。
(lastKey+currentKey)%2==0&&(Math.abs((lastKey-1)/3-(currentKey-1)/3)==2||Math.abs((lastKey-1)%3-(currentKey-1)%3)==2)
回复 支持 3 反对 0

使用道具 举报

nuanuan1208 发表于 2015-11-2 01:38:20 | 显示全部楼层
bless楼长拿到offer。。。现在面试怎么都开始考SQL了。。。看来应该去复习一下。。。
回复 支持 反对

使用道具 举报

 楼主| sophialyj 发表于 2015-11-2 03:12:28 | 显示全部楼层
sql那题很简单,最基本的那种
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-2 03:30:25 | 显示全部楼层
谢lz分享,请问android划屏解锁那题,是密码必须包括所有数字并且每个数字只能出现一次吗?

补充内容 (2015-11-2 03:52):
还有请问lz(起始点+到达点看符不符合条件判断)这一步是怎么做的?是写一个function用位置来判断,还是hard code先把对应位置不符合的点放到map里?
回复 支持 反对

使用道具 举报

binomial 发表于 2015-11-2 03:47:33 | 显示全部楼层
lz,我跟你一天面的啊。。。。HR怎么就告诉你feedback了呢?我面完都没有见HR的面呀。HR有没有跟你说什么时候有消息呀?感觉你的题比我的要难。
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-11-2 03:55:52 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-2 03:30
谢lz分享,请问android划屏解锁那题,是密码必须包括所有数字并且每个数字只能出现一次吗?

补充内容 (201 ...

可以用一个pair来存,我写的比较繁杂。。。
https://github.com/hejian2356/-A ... r/LockSequence.java
回复 支持 反对

使用道具 举报

 楼主| sophialyj 发表于 2015-11-2 04:06:43 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-2 03:30-google 1point3acres
谢lz分享,请问android划屏解锁那题,是密码必须包括所有数字并且每个数字只能出现一次吗?

补充内容 (201 ...

可以这么理解。其实这道题目里面是没有数字的,我只是为了方便解释,这么说的,我其实就是用了个boolean[3][3]的array去表示是不是visit过和数方法数
isNext(int i1, int j1, int i2, int j2)去判断(i1, j1)是不是能走到i2, j2。
回复 支持 反对

使用道具 举报

 楼主| sophialyj 发表于 2015-11-2 04:09:58 | 显示全部楼层
binomial 发表于 2015-11-2 03:47
lz,我跟你一天面的啊。。。。HR怎么就告诉你feedback了呢?我面完都没有见HR的面呀。HR有没有跟你说什么时 ...
. from: 1point3acres.com/bbs
我的hr人超级好啊,一直很负责,我面试前一天还打电话发email提醒我。最后还来送我去电梯,给了我一个google的小袋子,里面有google的水壶和一堆小零食和google play的5刀gift card。feedback的话,其实是当时我在擦我写的白板,她就问问我感觉怎么样,然后她就透露给了我第一轮的feedback还好,非常informal的,估计正式的得至少等到下一周了。
回复 支持 反对

使用道具 举报

 楼主| sophialyj 发表于 2015-11-2 04:14:26 | 显示全部楼层
hj867955629 发表于 2015-11-2 03:55
可以用一个pair来存,我写的比较繁杂。。。
https://github.com/hejian2356/-Algorithms/blob/master/Lo ...

我觉得你写的有点复杂,感觉他希望我写出一个比较general的方法,我是没写出来特别好的。。。
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-11-2 04:24:21 | 显示全部楼层
多谢分享! 这位中国GG业界良心啊!
回复 支持 反对

使用道具 举报

binomial 发表于 2015-11-2 05:02:03 | 显示全部楼层
sophialyj 发表于 2015-11-2 04:09
我的hr人超级好啊,一直很负责,我面试前一天还打电话发email提醒我。最后还来送我去电梯,给了我一个goo ...

那你真的是很幸运啊~我都怀疑我在四楼等HR来接我的时候是不是看到过楼主。呵呵。当时还有一个中国女生在等~~
回复 支持 反对

使用道具 举报

 楼主| sophialyj 发表于 2015-11-2 05:43:40 | 显示全部楼层
binomial 发表于 2015-11-2 05:02
那你真的是很幸运啊~我都怀疑我在四楼等HR来接我的时候是不是看到过楼主。呵呵。当时还有一个中国女生在 ...
. more info on 1point3acres.com
估计就是了哈~~~  不过hr好不是关键呀,关键是面试得咋样啊,bless us!!!
回复 支持 反对

使用道具 举报

binomial 发表于 2015-11-2 06:48:47 | 显示全部楼层
sophialyj 发表于 2015-11-2 05:43. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
估计就是了哈~~~  不过hr好不是关键呀,关键是面试得咋样啊,bless us!!!

哈哈,真有缘呀。感觉mm面的挺好的啊!题目都答上了了。而且都挺难的。有消息通知一下 :) 好运~
回复 支持 反对

使用道具 举报

 楼主| sophialyj 发表于 2015-11-2 07:24:04 | 显示全部楼层
binomial 发表于 2015-11-2 06:48
哈哈,真有缘呀。感觉mm面的挺好的啊!题目都答上了了。而且都挺难的。有消息通知一下 :) 好运~
. Waral 鍗氬鏈夋洿澶氭枃绔,
本来我也觉得还凑合,后来越想越觉得自己第三轮太二了。。。 你有啥消息也告诉我一下哦~~~
回复 支持 反对

使用道具 举报

binomial 发表于 2015-11-2 07:59:07 | 显示全部楼层
sophialyj 发表于 2015-11-2 07:24
本来我也觉得还凑合,后来越想越觉得自己第三轮太二了。。。 你有啥消息也告诉我一下哦~~~

好呀。我这几天也是老琢磨老琢磨的,刚面完自我感觉良好,现在越想越心虚了。。。。. visit 1point3acres.com for more.
希望我们都好运吧~
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2015-11-2 10:08:35 | 显示全部楼层
觉得仅靠preorder可以给出原来的BST,不是只能靠inorder 和preorder才能搞出bst的妈?leetcode 有原题
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-2 10:20:00 | 显示全部楼层
qiuxuxing007 发表于 2015-11-2 10:08
觉得仅靠preorder可以给出原来的BST,不是只能靠inorder 和preorder才能搞出bst的妈?leetcode 有原题

leetcode是恢复一个binary tree而不是一个BST,所以要用inorder+preorder。。。如果是BST是可以只用preorder就恢复出来的
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2015-11-2 10:37:21 | 显示全部楼层
是的,我知道了,多谢指点,其实本质上还是建一个treenode,因为left tree 比他小,right tree比他大,所以直接可以分割建树了.
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2015-11-2 11:09:53 | 显示全部楼层
android这道题目密码生成是不是就是,假设有四位的密码,1后面只能跟2,4,5然后假设取了5,5后面可以跟9,6,8只要没被visited的都可以?是这个意思?
回复 支持 反对

使用道具 举报

 楼主| sophialyj 发表于 2015-11-2 11:43:15 | 显示全部楼层
qiuxuxing007 发表于 2015-11-2 11:09. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
android这道题目密码生成是不是就是,假设有四位的密码,1后面只能跟2,4,5然后假设取了5,5后面可以跟9,6,8只 ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
就是划屏解锁,可以想成9位密码,如果从1开始,接下去可以走的是2,4,5,6,8。例如123就是可以的,但是132不行。如果从2开始,24315就可以,因为2已经走过了,不知道解释清楚了没有。

补充内容 (2015-11-2 11:44):
后面那个例子说错了,是25413
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
补充内容 (2015-11-2 11:44):
后面那个例子说错了,是25413

补充内容 (2015-11-2 11:44):
后面那个例子说错了,是25413
-google 1point3acres
补充内容 (2015-11-2 11:44):
后面那个例子说错了,是25413
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 10:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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