一亩三分地论坛

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

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

4/12 Google Onsite (MTV) Cloud组

[复制链接] |试试Instant~ |关注本帖
Janet.Ding 发表于 2016-4-30 07:37:25 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 内推 - Onsite |Fail其他

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

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

x
这次onsite之前有两次电面,一次是写bigInt加法,还有一个是根据输入自己建N-nary Tree完了vertical printing,两个都不难。第一轮:长头发的白人小哥,上来就问题目,有点类似设计,让写一个类使得可以调用一个function来查看之前一段时间内的event数量,一段时间通常设为一个小时。用python很快实现了,但是是用list记录每个事件的timestamp,每次有新的timestamp就检查之前的timestamp,如果已经超出一个小时就把之前的都扔掉,换句话说维护一个在一个小时范围内的队列。结果白人小哥说如果事件量很大你岂不是都要记ts,问怎么优化。我想了半天就想说可以通过降低精度的方法维护一个长度为60的队列,每个元素就是在一分钟内的点击次数,而不用记录每个ts。他似乎还是比较满意这样的做法。
第二轮:看起来像老墨的白人小哥,第一题竟然跟上一轮一样,也是查看一段时间内的event数量。我跟他说上一轮是类似的,他说没关系你实现一下吧。第二题是在一个binary tree里面找相同的binary tree。这题目之前做过但是做得不熟结果临时记不起来了,只好挨个点比计较估计就没戏了。
第三轮:一个看起来特别吊的亚洲胖子,也不知道是不是中国人。上来就一道题目,给你一个string是由一个bit表示的char组成的,每8位或者4位表示一个char。如果一个char第一位是1,则这个char是8位的,如果是0则是四位的。但8位char的第5位也有可能是0或者1。问如果给定你第n个char的开头在第k位,第n-1个char的开头在哪里。最简单的方法是从头到尾扫一遍记录下每一个char开头的位置直到第k-1个,但要求是不能从头扫,只能从后面一点一点往前推。这题目我跟他一点一点往前推理了4位,还是看不到能确定的情况,总是要看之前一位是什么才行。最后没办法,他问我有没有什么确定的方法能从后面推出前面,我说我不知道。他只好让我实现了一下最简单的方法。谁要是知道方法一定要分享一下,不然我死不瞑目。. 1point3acres.com/bbs
中午一起吃饭的是个印度小哥,人还挺好的,跟我聊说在google换组很容易,因为大部分code都是对内开放的,你如果有兴趣可以看到所有项目的code,前提是你能进去才行。
第四轮:吃完饭以后回到会议室,来了一个挺帅的白人小哥,拿了张纸说题目在上面你就自己看一下吧。跟leetcode text justification比较类似,给你一个wordlist,让你把这些word按顺序放进长度为n的char array里面,中间用空格隔开,word在放进去的时候不能断开,开头和末尾不用加空格,问如果有k个这样相同的wordlist最少需要多少个这样的array,也就是说要用多少行。我写的磕磕巴巴,但还是写完了。之后他说如果每行的长度很长可以怎样优化,我说可以先算整个wordlist都转成一行的长度,然后用每行的长度除一下看剩多少,但是没有时间实现了。
第五轮:一个印度大哥,开始问了很多project experience。后面我始终都没有弄清楚他的意思,即使跟他讨论了快半个小时,大概是我实在太笨加上太累了。题目很简单,给你一个unsorted array,里面的元素都是从1到n的数且没有重复,也就是说长度是n。这时将里面其中一个数换成其中的另外一个数,比如:原数组是[2,3,4,1,5],这时把3换成2,变成[2,2,4,1,5]。问在告诉你n和改过的array之后你怎样才能知道这时里面哪个数是重复的。我感觉这有什么可做的,就是用hashmap count每个出现的次数看哪个出现了2次。他说可以但还有什么方法,因为已经知道了n,我想了各种方法可他还是不满意。最后就只好算了,不知道他到底希望是用什么特殊的方法。
感觉这次onsite没有我想象的那么难,但还是能力不行水平有限被拒了,反馈是coding没问题,但general problem solving不行,应该还是题目做得不够。. more info on 1point3acres.com

评分

1

查看全部评分

edcent 发表于 2016-4-30 11:53:59 | 显示全部楼层
感觉最后一题跟 lc 那个 first missing possitive 有点像
回复 支持 1 反对 0

使用道具 举报

yueliu2366 发表于 2016-4-30 21:12:42 | 显示全部楼层
adiggo 发表于 2016-4-30 08:06
第三轮的题 应该还是找从后往前找pattern:
我们无非就是想确定k-4, k-8位置 是不是前一个char。 如果k- ...

你好,请问一下为什么"如果k-4 位置 是 1, ok, 那么就确定了, 前一个char 在k-8 " 呢?
如果k-4 位置 是 1,前一个char在k-4不是也有可能吗?举个例子来说 "10011000",如果给定 第2个char是"1000",则k=4, 此时k-4 = 0, 在index=0的位置的字符是‘1’, 但是前一个char不就是"1001",也就是在k-4的位置吗?

补充内容 (2016-4-30 22:07):. Waral 鍗氬鏈夋洿澶氭枃绔,
还有第五题能不能详细说一下?mid value 指的是什么呢?
回复 支持 1 反对 0

使用道具 举报

mzli1989 发表于 2016-4-30 07:58:28 | 显示全部楼层
谢谢分享,楼主加油继续面其他家,祝早日拿offer!!
楼主是在hc被拒的还是?
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-4-30 08:06:35 | 显示全部楼层
第三轮的题 应该还是找从后往前找pattern:
我们无非就是想确定k-4, k-8位置 是不是前一个char。 如果k-4 位置 是 1, ok, 那么就确定了, 前一个char 在k-8 。 如果k-4 的bit是 0, 那么暂时无法确定。  那么就去k-8 check, 如果是0, 前一个char的起始位置必然在-4. 如果是1, 那么我们就得继续往回探索。 . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
所以就是 0***1***1***0*** 这样的pattern, 我们的目的无非就是找到1之前的0出现的位置, 这样就能确定前一个char的位置了。

第五轮 应该是 sum(1 to n)减去 改变后的array 之和  , 就可以知道哪个数了。 比如(1,2,3) 变成 (1,2,2)。  diff = 1, 那么mid value + diff 就是那个改变的数
回复 支持 反对

使用道具 举报

missing 发表于 2016-4-30 12:16:27 | 显示全部楼层
楼主最后一轮的题目和我上次NYC onsite的中间一轮的一题是同一题。这题需要in-place操作,就是不停的num[i]换到num[num[i]-1],保证换完之后的数组是[1, 2, 3, ...n]这样。换的途中发现loop了或者超过一定次数了还没换完,loop开始的那个数就是duplicate。这题leetcode上有类似的。。我上次也是跪的这题
回复 支持 反对

使用道具 举报

edcent 发表于 2016-4-30 12:30:24 | 显示全部楼层
第三轮那个题我在别的公司被面到过,这题真的挺难现场不经提示想出答案的。. 1point3acres.com/bbs
跟二楼说的思路一样,就是看前一个是不是0开头,如果是,就再往前找0,因为这个0代表着这个 char 的结束,这个0后面的一定是下一个 char 的开始。所以找到0的时候,两个0中间夹着的都是1.
例如找到0***1***1***1***0***要判断返回哪一个 char,就数一下两个0中间的1开头的有多少个就可以。奇数个1就是返回8bit 的 char,偶数个1就是返回4bit 的 char。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-4-30 12:40:33 | 显示全部楼层
第五题XOR下就好了吧= =
回复 支持 反对

使用道具 举报

bbsbbstry 发表于 2016-4-30 13:54:26 | 显示全部楼层
hidden_track 发表于 2016-4-30 12:40
第五题XOR下就好了吧= =

细说下?
回复 支持 反对

使用道具 举报

 楼主| Janet.Ding 发表于 2016-4-30 18:43:46 | 显示全部楼层
missing 发表于 2016-4-30 12:16
楼主最后一轮的题目和我上次NYC onsite的中间一轮的一题是同一题。这题需要in-place操作,就是不停的num换 ...

他似乎提示我的就是这个方法,我最后也写出来了,但自己心里总是不确定行不行所以说的不是很好
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-4-30 22:57:11 | 显示全部楼层

XOR扫两遍,只有重复的那个会被留下
. From 1point 3acres bbs
补充内容 (2016-4-30 22:57):
第一遍扫没有重复的数组,第二遍扫有重复的
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-4-30 23:06:29 | 显示全部楼层
hidden_track 发表于 2016-4-30 22:57
XOR扫两遍,只有重复的那个会被留下
. more info on 1point3acres.com
补充内容 (2016-4-30 22:57):

好像只给了n和改过的数组,并没有给原来没改过的数组吧?还是我题意理解错了?
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-4-30 23:07:26 | 显示全部楼层
yueliu2366 发表于 2016-4-30 23:06
好像只给了n和改过的数组,并没有给原来没改过的数组吧?还是我题意理解错了?

不是给N了吗= = 1到N个数没有重复
回复 支持 反对

使用道具 举报

tcomein2009 发表于 2016-5-1 01:40:06 | 显示全部楼层
adiggo 发表于 2016-4-30 08:06
第三轮的题 应该还是找从后往前找pattern:
我们无非就是想确定k-4, k-8位置 是不是前一个char。 如果k- ...

对 好方法
或者swap到对应的index,对吧
回复 支持 反对

使用道具 举报

tcomein2009 发表于 2016-5-1 01:45:25 | 显示全部楼层
第二题是 serialize tree 然后再建suffix tree 或者 DP吧?
回复 支持 反对

使用道具 举报

tcomein2009 发表于 2016-5-1 01:45:54 | 显示全部楼层
请问楼主店面里nary tree vertical 打印是怎么回事?谢谢啊
回复 支持 反对

使用道具 举报

tcomein2009 发表于 2016-5-1 01:47:47 | 显示全部楼层
请问大家wordlist justification那道,如果line 很长, 除以wordlist长度不太对吧?比如某个词正好横跨两个line. from: 1point3acres.com/bbs
有什么优化方法呢?
回复 支持 反对

使用道具 举报

pika 发表于 2016-5-1 02:15:04 | 显示全部楼层
弱问,查看一段时间内的event数量, 这种问题有啥标准解法么?
回复 支持 反对

使用道具 举报

bbsbbstry 发表于 2016-5-1 02:27:17 | 显示全部楼层
hidden_track 发表于 2016-4-30 22:57
XOR扫两遍,只有重复的那个会被留下

补充内容 (2016-4-30 22:57):

可是这么扫两遍得到的结果应该是 重复的那个数和原数的xor吧?你怎么根据这个数得到重复的那个数?
回复 支持 反对

使用道具 举报

 楼主| Janet.Ding 发表于 2016-5-1 02:33:12 | 显示全部楼层
tcomein2009 发表于 2016-5-1 01:45 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
请问楼主店面里nary tree vertical 打印是怎么回事?谢谢啊

就是leetcode 314 Binary Tree Vertical Order Traversal,不同的是要打印的树是N-nary.
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 06:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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