一亩三分地论坛

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

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

gg onsite 10月 fresh grad

[复制链接] |试试Instant~ |关注本帖
LumiG 发表于 2016-10-13 07:35:19 | 显示全部楼层 |阅读模式

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

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

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

x
终于来面了google,早上刚面的,题目出乎意料的容易啊……

有点不记得每轮分别问了什么了,有些题目要求还比较奇怪,大概写一下:

R1:
一个LC228,不过数组是无序的,我排序后随手写了一个,他就说ok,也没问folow up;
一个类似LC399的,输出稍微有点小要求,但没有区别;
一个标准的并查集的题目,大概就是有些点,有些边,输出一些东西
.鏈枃鍘熷垱鑷1point3acres璁哄潧
R2:. more info on 1point3acres.com
一个奇怪的warmup,花了我二十分钟=。=一直没理解他什么意思,特别伤… (可能因为这个,这轮另两题尤其简单吧…)
一个wordlist,一组characters,问哪些word可以用characters里的字符拼起来(要考虑重复的),?代表任意字符,就是hashmap数一下,python用下counter代码没几行
一个array [1,5,3,8,10] 这样,代表n堆硬币,两个人每次可以取头上的或者尾巴上的硬币,最后拿的总和最多的人获胜,求先手的最优策略。。。我只写了个递归的,面试时间到了没来得及写dp的,都怪第一题。。。

R3:
这轮也挺神奇的,面我的人临时有事,找了人替他来面,结果这个人只准备了一道题,大致是把一个矩阵里边,相邻一样的数字merge成一个点,然后有一些其他小限制。大致dfs一遍就行。
然后,这白人大哥和我说,他只准备了这一道题=。=然后他和我说,那我来看看怎么变化一下,问你点follow up吧,然后就和我讨论了半个小时各种其他情况。。有的写了代码,有的没有写,反正就是各种dfs,最后就结束了。. more info on 1point3acres.com

R4:
longest consecutive substring
LC298
一堆点[(x0,y0), (x1,y1)...] 这样,问能够组成最小的长方形。这题一开始没和他verify,以为是任意角度的长方形,我写的最优解是O(N^3)的。后来他发现了,说原意是只找和两根坐标轴平行的,就又讲了一个O(N^2)的做法,没写代码,一共半小时吧。。这轮觉得做的挺好。


攒RP求给个offer吧,给了就想去了。。。。

评分

10

查看全部评分

本帖被以下淘专辑推荐:

iwknow 发表于 2016-10-14 11:18:05 | 显示全部楼层
再贡献一个我的第四题解法。N^2复杂度
=========================
1.把所有点存入hashset中
2. 从点0到点n的所有点中选取点 i 和点 j (for each i from 0 to n-1, find j from i to n-1),i 点和 j点分别表示长方形的左下角和右上角. 做如下循环:
  2.1 假设左下和右上角是(x1, y1),(x2, y2),可以推算出左上角为(x1, y2)右下角为(x2, y1).. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  2.2 查找set中是否存在(x1, y2), (x2, y1). 若都存在,计算面积并更新最小面积
3. 输出最小面积。

评分

4

查看全部评分

回复 支持 5 反对 0

使用道具 举报

pawprinter 发表于 2016-10-23 11:31:47 | 显示全部楼层
直接onsite真好。。gg坑爹加一轮电面。。。
回复 支持 1 反对 0

使用道具 举报

magic95 发表于 2016-10-13 11:04:36 | 显示全部楼层
chestnut9919 发表于 2016-10-13 10:47
求问楼主第二轮取硬币的dp怎么写?
. From 1point 3acres bbs
代码https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/NPotGold.java
&一个讲解视频https://www.youtube.com/watch?v=WxpIHvsu1RI&list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&index=30
回复 支持 1 反对 0

使用道具 举报

chestnut9919 发表于 2016-10-13 10:47:56 | 显示全部楼层
求问楼主第二轮取硬币的dp怎么写?
回复 支持 反对

使用道具 举报

yezhangpost 发表于 2016-10-13 11:00:15 | 显示全部楼层
求能够组成最小的长方形的题的解法,谢楼主
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-10-13 11:09:09 | 显示全部楼层
第四轮是这个题? https://leetcode.com/problems/perfect-rectangle/
回复 支持 反对

使用道具 举报

 楼主| LumiG 发表于 2016-10-13 11:20:04 | 显示全部楼层
wtcupup 发表于 2016-10-13 11:09
第四轮是这个题? https://leetcode.com/problems/perfect-rectangle/

没有没有,比这题容易很多,就是给一堆坐标,问能够组成的最小的长方形。能旋转的找个set存下,平行的弄两个hashmap就行。
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-10-13 11:27:15 | 显示全部楼层
magic95 发表于 2016-10-13 11:04. 1point3acres.com/bbs
代码https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/NPotGold.java ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
你太牛逼了。。。话说Tushar是真男神
回复 支持 反对

使用道具 举报

christwsy 发表于 2016-10-13 11:43:36 | 显示全部楼层
下周五onsite,路过蹭个rp。感觉楼主这波很稳啊
回复 支持 反对

使用道具 举报

hjx447297354 发表于 2016-10-13 13:15:01 | 显示全部楼层
请问楼主是在哪面的?祝好运~
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-10-13 13:28:41 | 显示全部楼层
楼主能详细讲讲怎么做的找最小长方形吗?俩hashmap存啥啊?
回复 支持 反对

使用道具 举报

cheeroh 发表于 2016-10-13 15:16:29 | 显示全部楼层
楼主R4的longest consecutive substring是什么题目?还是说是longest consecutive subsequence?LC128那个?
回复 支持 反对

使用道具 举报

sophie729 发表于 2016-10-13 17:56:53 | 显示全部楼层
感谢分享,感觉肯定妥了 ,best luck!
回复 支持 反对

使用道具 举报

prodigalr 发表于 2016-10-13 23:46:13 | 显示全部楼层
楼主能说下找任意角度的最小长方具体怎么做吗?谢谢~
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-10-14 01:29:25 | 显示全部楼层
第二轮就是这题吧http://articles.leetcode.com/coins-in-line/
第四轮是固定三个点以后用hashmap找第四个点做任意角度吗?

补充内容 (2016-10-14 01:37):
第四轮平行于坐标轴的二次方做法是怎样的呢?
回复 支持 反对

使用道具 举报

 楼主| LumiG 发表于 2016-10-14 02:36:09 | 显示全部楼层
christwsy 发表于 2016-10-13 11:43.鏈枃鍘熷垱鑷1point3acres璁哄潧
下周五onsite,路过蹭个rp。感觉楼主这波很稳啊

别奶。。。加油加油!
回复 支持 反对

使用道具 举报

 楼主| LumiG 发表于 2016-10-14 02:36:20 | 显示全部楼层
hjx447297354 发表于 2016-10-13 13:15
请问楼主是在哪面的?祝好运~

谢谢!在mtv
回复 支持 反对

使用道具 举报

 楼主| LumiG 发表于 2016-10-14 02:36:50 | 显示全部楼层
cheeroh 发表于 2016-10-13 15:16
楼主R4的longest consecutive substring是什么题目?还是说是longest consecutive subsequence?LC128那个 ...

就是128,但是要求都是连续的,所以是个很容易的题
回复 支持 反对

使用道具 举报

 楼主| LumiG 发表于 2016-10-14 02:48:31 | 显示全部楼层
chestnut9919 发表于 2016-10-13 13:28. from: 1point3acres.com/bbs
楼主能详细讲讲怎么做的找最小长方形吗?俩hashmap存啥啊?

分别存每行/每列有哪些点,里边我存的是所有另一个坐标的set。这样你遍历一遍所有点,每个点找和他在同一列的,两个set取个交,交集就是另一条边可以在的横坐标……算个面积就行了。。  现在想想取交严格来说应该算作O(N),真的算起来最差情况还是有可能是n^3哎,不过反正当时他认可了。。
回复 支持 反对

使用道具 举报

prodigalr 发表于 2016-10-14 07:40:11 | 显示全部楼层
LumiG 发表于 2016-10-14 02:48
分别存每行/每列有哪些点,里边我存的是所有另一个坐标的set。这样你遍历一遍所有点,每个点找和他在同一 ...

楼主那求任意角度最小长方形怎么做啊
回复 支持 反对

使用道具 举报

rinto 发表于 2016-10-14 09:52:26 | 显示全部楼层
感谢楼主分享,第四题我试着用treemap做了一下, 大意就是对于每个点(x,y), 往左边找到一个点(xx, y), 往下找到一个点(x,yy),然后看看(xx,yy)是不是存在。
这样平均可能是O(N^2logN)吧,如果找再存一个hashmap用来着(xx,yy),平均可能是O(N^2)。有一个好处是可以减掉一些不必要的搜索。
不知道写的对不对,我大概跑了两个test是对的

  1. [color=#000080][b]public int [/b][/color]smallestRectangle([color=#000080][b]int[/b][/color][][] points){

  2.     [color=#808080][i]//xmap: for each x value, store the set of y values. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  3. [/i][/color][color=#808080][i]    [/i][/color]Map<Integer, Set<Integer>> xmap = [color=#000080][b]new [/b][/color]TreeMap<>();
  4. . 鍥磋鎴戜滑@1point 3 acres
  5.     [color=#808080][i]//ymap: for each y value, store the set of x values
  6. [/i][/color][color=#808080][i]    [/i][/color]Map<Integer, Set<Integer>> ymap = [color=#000080][b]new [/b][/color]TreeMap<>();

  7.     [color=#000080][b]for [/b][/color]([color=#000080][b]int[/b][/color][] point : points){
  8.         xmap.putIfAbsent(point[[color=#0000ff]0[/color]], [color=#000080][b]new [/b][/color]TreeSet<>());
  9.         xmap.get(point[[color=#0000ff]0[/color]]).add(point[[color=#0000ff]1[/color]]);

  10.         ymap.putIfAbsent(point[[color=#0000ff]1[/color]], [color=#000080][b]new [/b][/color]TreeSet<>());
  11.         ymap.get(point[[color=#0000ff]1[/color]]).add(point[[color=#0000ff]0[/color]]);
  12.     }

  13.     [color=#000080][b]int [/b][/color]result = Integer.[color=#660e7a][b][i]MAX_VALUE[/i][/b][/color];
  14.     [color=#000080][b]boolean [/b][/color]found = [color=#000080][b]false[/b][/color];

  15.     [color=#000080][b]for [/b][/color]([color=#000080][b]int [/b][/color]x : xmap.keySet()){
  16.         [color=#000080][b]for [/b][/color]([color=#000080][b]int [/b][/color]y : xmap.get(x)){. 鍥磋鎴戜滑@1point 3 acres
  17.             Iterator<Integer> yiter = xmap.get(x).iterator();
  18.             [color=#000080][b]int [/b][/color]yy = yiter.next();

  19.             [color=#000080][b]while [/b][/color](yy <= y && yiter.hasNext()){
  20.                 yy = yiter.next();
  21.             }
  22.             [color=#000080][b]if [/b][/color](yy <= y){
  23.                 [color=#000080][b]break[/b][/color];
  24.             }

  25.             [color=#000080][b]boolean [/b][/color]keepSearch = [color=#000080][b]true[/b][/color];

  26.             [color=#000080][b]while [/b][/color]([color=#000080][b]true[/b][/color]){. more info on 1point3acres.com
  27.                 Iterator<Integer> xiter = ymap.get(y).iterator();
  28.                 [color=#000080][b]int [/b][/color]xx = xiter.next();
  29.                 [color=#000080][b]while [/b][/color](xx <= x && xiter.hasNext()){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  30.                     xx = xiter.next();
  31.                 }
  32.                 [color=#000080][b]if [/b][/color](xx <= x || (yy - y) * (xx - x) >= result){
  33.                     keepSearch = [color=#000080][b]false[/b][/color];
  34.                     [color=#000080][b]break[/b][/color];
  35.                 }
  36.                 [color=#000080][b]while [/b][/color]([color=#000080][b]true[/b][/color]){
  37.                     [color=#000080][b]if [/b][/color](xmap.get(xx).contains(yy)){
  38.                         result = Math.[i]min[/i](result, (yy - y) * (xx - x));
  39.                         found = [color=#000080][b]true[/b][/color];
  40.                         [color=#000080][b]break[/b][/color];
  41.                     }. From 1point 3acres bbs

  42. . 1point3acres.com/bbs
  43.                     [color=#000080][b]if [/b][/color](xiter.hasNext()){
  44.                         xx = xiter.next();.鐣欏璁哄潧-涓浜-涓夊垎鍦
  45.                     } [color=#000080][b]else[/b][/color]{
  46.                         [color=#000080][b]break[/b][/color];
  47.                     }
  48.                 }
  49. -google 1point3acres
  50.                 [color=#000080][b]if [/b][/color](yiter.hasNext() && keepSearch){
  51.                     yy = yiter.next();
  52.                 } [color=#000080][b]else[/b][/color]{
  53.                     [color=#000080][b]break[/b][/color];
  54.                 }
  55.             }
  56.         }
  57.     }
  58.     [color=#000080][b]return [/b][/color]found ? result : -[color=#0000ff]1[/color];
  59. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 03:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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