一亩三分地论坛

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

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

Google Full time phone+onsite

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

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

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

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

x
拿到offer,发个面经,附上时间轴做参考,回馈地里。

11/18 电面1 白人小哥:
Prob 1: 有序数组,找出现次数大于等于n/4的数
  我当时只会O(n),后来想想,可以先截取位于四分点的数作为候补,然后二分找它的范围,看长度是否超过n/4,O(lgn).
Prob 2: n个文件(共100G),找出含某个词的文件将它们归档为一类。
  e.g. A: small cat and small dog
        B: small cat
        C: cat and dog. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    then given ['small cat', 'dog'], return [[A,B], [A,C]]
  写了个暴力后,问我怎么做更快,然而我并不知道。不知道他想用分布式还是某些算法(自动机?),胡扯一通

本来HR打电话告诉我挂了,后来又告诉我大家的response有分歧,就给了个二轮。估计这些题太奇葩了吧。

12/2 电面2 白人大叔:
Leetcode: Kth latgest element in an array
还有一些follow up, 很简单,所以就忘了。

1/5 Onsite
不知道为什么有5轮,累惨了。. more info on 1point3acres.com
-google 1point3acres
1. 华人大叔
给一些coin的面值,问凑成一定amount有几种方法。(每种面值无限取)
follow up:  每种面值有各自的限量。
解:DP+滚动数组

2. 白人大叔
  1)问log file里找重复出现的词用什么数据结构存:Trie
  2)全0矩阵:操作1:set一个数,操作2:求0,0到x,y的矩阵和
       解:二维树状数组,然而再讲为什么lowbit是x& -x时,讲不明白(或者是他听不懂= =). 1point 3acres 璁哄潧

3. 白人小哥
  1) 国象(8*8)主教从某位置移动到某位置最少需要几步:
      解:有非法位置,原地不动,1步,2步四种情况. 1point3acres.com/bbs
  2)public int increment(int val) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
         static int x;
         x += val;
         return x;
      }(好像是这样。。)
      问:这段代码有什么问题?
      我:不知道
      问:多线程时结果会多种可能
      我:。。。(谁会想到上锁啊)

4. 亚裔小哥
   N*N矩阵,W代表墙,F代表花,.为空白(输入给的是N, 以及W,F对应的的坐标数组)。在非墙位置能上下左右看,问那个位置能看到最多的花,(墙会挡视线,且脚下的看不到)
   解:我用O(n^2)解的(逐行逐列预处理),他最后说稀疏时,可以只考虑墙边的格子能更快。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
5. 白人小哥
  1) 跟树有关的题,leetcode上有。由于把它秒了,实在想不起来是哪题了。
  2)图上的点代表城市,从一个城市到另一个要花一周(瞬间移动,e.g.第3周在A,第4周在B,前提是AB有边)。
       每个城市每周会有一些假日,如果某周在某城市停留,会获得相应数量的假日。起始在某一城市,问第n周在k城市时,能获得的最多假日数量.
     解:在图上DP

1/14 过hc

1/21 offer

今年工作难找(我找的晚也是一部分原因),大公司给电面的只有G,幸好过了。
祝大家也有我的好运气!
. 鍥磋鎴戜滑@1point 3 acres

评分

8

查看全部评分

 楼主| lencle 发表于 2016-1-24 15:19:40 | 显示全部楼层
say543 发表于 2016-1-24 13:29. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
感谢Lz 想再问问段的定义
WFFFW 中间FFF是一段在墙中间的example 以横断来讲这三个FFF都左右看的sum都 ...
. from: 1point3acres.com/bbs
对W,F分别按照其横纵坐标归类来实现离散化,复杂度与n无关

至于这个例子
WFWFW
WFFFW

横段3个:
行号  起始  结束  值
1        2       2      1. From 1point 3acres bbs
1        4       4      1. From 1point 3acres bbs
2        2       4      3. visit 1point3acres.com for more.

竖段3个:
列号  起始  结束  值
2        1       2      2
3        2       2      1
4        1       2      2.鐣欏璁哄潧-涓浜-涓夊垎鍦

这样枚举是3*3的,以取第3个横段和第1个竖段为例,可确认相交坐标为(2,2),该点观测值是3+2-2=3
回复 支持 1 反对 0

使用道具 举报

say543 发表于 2016-1-23 14:04:33 | 显示全部楼层
感谢LZ分享 请问M*n矩阵如果sparse 为什么考虑墙边的格子会更快? 另外假日那题能分享如何DP吗? 多谢
回复 支持 反对

使用道具 举报

umd2011 发表于 2016-1-24 00:17:41 | 显示全部楼层
恭喜楼主! 下周我就要去MTV onsite了,希望能沾沾楼主的喜气!
回复 支持 反对

使用道具 举报

 楼主| lencle 发表于 2016-1-24 04:50:52 | 显示全部楼层
say543 发表于 2016-1-23 14:04
感谢LZ分享 请问M*n矩阵如果sparse 为什么考虑墙边的格子会更快? 另外假日那题能分享如何DP吗? 多谢

关于第4题:
    对不起,这是我表述不当造成的误解。
    稀疏矩阵会因大量的空白造成重复计算,此时可应用离散化。-google 1point3acres
    e.g.  对于某行......F..........F.......W.......F....,可变成FFWF。
    这样,从墙向左看2个,向右看有1个(当然还有边界)。我所说的“墙边的格子”,即被墙所包围的一段,显然这样的"段"最多有|W|*|F|个。最终统计时,两个循环分别枚举这样的"横段"和"竖段",时间复杂度O((WF)^2)

关于第5题:
    dp[week][city]表示第week周在city时获得的最多假日
    初始:dp[0][initial_city] = 0, 其余为-1
    状态转移: dp[week][city_to] = max{dp[week-1][city_from]} + holiday[week][city_to]
                                                  (if dp[week-1][city_from] != -1)
                     其中city_from和city_to有边(或者是city_to本身,表示不移动)
回复 支持 反对

使用道具 举报

 楼主| lencle 发表于 2016-1-24 04:54:06 | 显示全部楼层
umd2011 发表于 2016-1-24 00:17.鏈枃鍘熷垱鑷1point3acres璁哄潧
恭喜楼主! 下周我就要去MTV onsite了,希望能沾沾楼主的喜气!

加油!祝好运!
回复 支持 反对

使用道具 举报

wildchild 发表于 2016-1-24 07:26:58 | 显示全部楼层
全0矩阵:操作1:set一个数,操作2:求0,0到x,y的矩阵和
       解:二维树状数组,然而再讲为什么lowbit是x& -x时,讲不明白(或者是他听不懂= =). more info on 1point3acres.com


lz这个题目没有看的很明白……可以多解释一点点为什么用bit么?
回复 支持 反对

使用道具 举报

 楼主| lencle 发表于 2016-1-24 10:15:57 | 显示全部楼层
wildchild 发表于 2016-1-24 07:26
全0矩阵:操作1:set一个数,操作2:求0,0到x,y的矩阵和
       解:二维树状数组,然而再讲为什么lowbit是 ...
. 1point 3acres 璁哄潧
请参考leetcode 308 Range Sum Query 2D,几乎一样。
lowbit是树状数组中用到的函数,返回参数转为二进制后,最后一个1的位置所代表的数值。
回复 支持 反对

使用道具 举报

say543 发表于 2016-1-24 13:29:53 | 显示全部楼层
lencle 发表于 2016-1-24 04:50
关于第4题:
    对不起,这是我表述不当造成的误解。
    稀疏矩阵会因大量的空白造成重复计算,此时 ...


感谢Lz 想再问问段的定义
WFFFW 中间FFF是一段在墙中间的example 以横断来讲这三个FFF都左右看的sum都依样但是竖段却可能有所不同即使是preprocess 似乎都需要n*n来做才能把sparse matrix reduce成只有W和F的矩阵? 能以belowexample 说说怎么加速吗?
ex:
. 鍥磋鎴戜滑@1point 3 acres
WFWFW
WFFFW
回复 支持 反对

使用道具 举报

say543 发表于 2016-1-24 14:05:22 | 显示全部楼层
lencle 发表于 2016-1-24 04:50
关于第4题:
    对不起,这是我表述不当造成的误解。
    稀疏矩阵会因大量的空白造成重复计算,此时 ...

多谢所以第五题时间复杂度是o(numofweek *numberof city*numberof city ) worst case?
回复 支持 反对

使用道具 举报

 楼主| lencle 发表于 2016-1-24 15:20:18 | 显示全部楼层
say543 发表于 2016-1-24 14:05
多谢所以第五题时间复杂度是o(numofweek *numberof city*numberof city ) worst case?

应该是O(week*边数)
回复 支持 反对

使用道具 举报

hylldxm 发表于 2016-1-24 15:36:07 | 显示全部楼层
恭喜楼主一步到位,楼主是找人内退的吗?
回复 支持 反对

使用道具 举报

lancelot981 发表于 2016-1-25 05:28:40 | 显示全部楼层
lencle 发表于 2016-1-24 10:15
请参考leetcode 308 Range Sum Query 2D,几乎一样。
lowbit是树状数组中用到的函数,返回参数转为二进 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
谢谢楼主的分享!我觉得用 x & -x 挑最后一个1 bit不太直观,我个人比较喜欢 x-(x & (x-1)),比如:
x = 00110101000, x-1 = 00110100111(lowbit 以后的都反过来了),所以x&(x-1)就拿到所有其他bit。不过当然是楼主那个比较快
回复 支持 反对

使用道具 举报

yueyub 发表于 2016-1-25 14:16:57 | 显示全部楼层
楼主,想请教你一个问题:. visit 1point3acres.com for more.
给一些coin的面值,问凑成一定amount有几种方法。(每种面值无限取)
follow up:  每种面值有各自的限量。

原题是unbounded knapsack problem,但这个follow up,每种coin个数限量,该怎么做?这个是bounded knapsack problem,要转换成0/1 knapsack problem似乎有些复杂啊。
回复 支持 反对

使用道具 举报

eric0417 发表于 2016-1-26 07:51:08 | 显示全部楼层
恭喜楼主 沾沾喜气^_^
回复 支持 反对

使用道具 举报

ninacc 发表于 2016-2-19 19:52:57 | 显示全部楼层
请问楼主Onsite第一题coins用dp怎么求啊?想了好久不会,多谢!
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-6 04:41:32 | 显示全部楼层
有大神可以详细说说“图上的点代表城市,从一个城市到另一个要花一周”这个题吗?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-6 04:42:29 | 显示全部楼层
楼主 ”n个文件(共100G),找出含某个词的文件将它们归档为一类。“这个题的暴力解法,是拿每个string, 去file中找吗?方法是strstr?. from: 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-6 04:44:39 | 显示全部楼层
请问”国象(8*8)主教“是指什么?国际象棋的一个子?
回复 支持 反对

使用道具 举报

huangheqing 发表于 2016-3-6 07:19:46 | 显示全部楼层
这些题目真的很好!值得学习思考!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 09:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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