【生活质量系列】评测几款用过的咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 10480|回复: 44
收起左侧

gg onsite 10月 fresh grad

[复制链接] |试试Instant~
我的人缘0
LumiG 发表于 2016-10-13 07:35:19 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (85)
 
 
2% (2)  踩

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

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

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

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

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

R1:
一个LC228,不过数组是无序的,我排序后随手写了一个,他就说ok,也没问folow up;
一个类似LC399的,输出稍微有点小要求,但没有区别;
一个标准的并查集的题目,大概就是有些点,有些边,输出一些东西

R2:
一个奇怪的warmup,花了我二十分钟=。=一直没理解他什么意思,特别伤… (可能因为这个,这轮另两题尤其简单吧…) 来源一亩.三分地论坛.
一个wordlist,一组characters,问哪些word可以用characters里的字符拼起来(要考虑重复的),?代表任意字符,就是hashmap数一下,python用下counter代码没几行
一个array [1,5,3,8,10] 这样,代表n堆硬币,两个人每次可以取头上的或者尾巴上的硬币,最后拿的总和最多的人获胜,求先手的最优策略。。。我只写了个递归的,面试时间到了没来得及写dp的,都怪第一题。。。

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

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


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

评分

参与人数 10大米 +172 收起 理由
忆梦前尘 + 10 感谢分享!
chestnut9919 + 1 感谢分享!
WhatsFLAG + 3 感谢分享!
whyvic13 + 5 谷神66666
neomiracle + 5 感谢分享!
lookbackinanger + 3 感谢分享!
william_gong + 5 欢迎来介绍你知道的情况
whdawn + 70
wcyz666 + 10 亲简单介绍下自己情况,再补加剩下的
candy_shmily + 60

查看全部评分


上一篇:IBM entry level software engineer OA 10/12
下一篇:10.12 Indeed电面

本帖被以下淘专辑推荐:

我的人缘0
iwknow 发表于 2016-10-14 11:18:05 | 显示全部楼层
本楼: 【顶】   100% (6)
 
 
0% (0)   【踩】
全局: 顶  100% (15)
 
 
0% (0)  踩
再贡献一个我的第四题解法。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大米 +18 收起 理由
gougou9903 + 5 回答的很好!
rinto + 3 赞!
LumiG + 5 Nice work!
william_gong + 5 nice solution

查看全部评分

回复

使用道具 举报

我的人缘0
pawprinter 发表于 2016-10-23 11:31:47 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  96% (73)
 
 
3% (3)  踩
直接onsite真好。。gg坑爹加一轮电面。。。
回复

使用道具 举报

我的人缘0
magic95 发表于 2016-10-13 11:04:36 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
chestnut9919 发表于 2016-10-13 10:47
求问楼主第二轮取硬币的dp怎么写?

代码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
回复

使用道具 举报

我的人缘0
chestnut9919 发表于 2016-10-13 10:47:56 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
求问楼主第二轮取硬币的dp怎么写?

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
yezhangpost 发表于 2016-10-13 11:00:15 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (16)
 
 
0% (0)  踩
求能够组成最小的长方形的题的解法,谢楼主
回复

使用道具 举报

我的人缘0
wtcupup 发表于 2016-10-13 11:09:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  61% (346)
 
 
38% (215)  踩
第四轮是这个题? https://leetcode.com/problems/perfect-rectangle/
回复

使用道具 举报

我的人缘0
 楼主| LumiG 发表于 2016-10-13 11:20:04 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (85)
 
 
2% (2)  踩
wtcupup 发表于 2016-10-13 11:09
第四轮是这个题? https://leetcode.com/problems/perfect-rectangle/

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

使用道具 举报

我的人缘0
chestnut9919 发表于 2016-10-13 11:27:15 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
magic95 发表于 2016-10-13 11:04
代码https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/NPotGold.java ...
来源一亩.三分地论坛.
你太牛逼了。。。话说Tushar是真男神
回复

使用道具 举报

我的人缘0
christwsy 发表于 2016-10-13 11:43:36 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (43)
 
 
2% (1)  踩
下周五onsite,路过蹭个rp。感觉楼主这波很稳啊
回复

使用道具 举报

我的人缘0
hjx447297354 发表于 2016-10-13 13:15:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (19)
 
 
0% (0)  踩
请问楼主是在哪面的?祝好运~

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
chestnut9919 发表于 2016-10-13 13:28:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
楼主能详细讲讲怎么做的找最小长方形吗?俩hashmap存啥啊?
回复

使用道具 举报

我的人缘0
cheeroh 发表于 2016-10-13 15:16:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
楼主R4的longest consecutive substring是什么题目?还是说是longest consecutive subsequence?LC128那个?
回复

使用道具 举报

我的人缘0
sophie729 发表于 2016-10-13 17:56:53 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (26)
 
 
7% (2)  踩
感谢分享,感觉肯定妥了 ,best luck!
回复

使用道具 举报

我的人缘0
prodigalr 发表于 2016-10-13 23:46:13 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (24)
 
 
4% (1)  踩
楼主能说下找任意角度的最小长方具体怎么做吗?谢谢~
回复

使用道具 举报

我的人缘0
william_gong 发表于 2016-10-14 01:29:25 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (104)
 
 
8% (10)  踩
第二轮就是这题吧http://articles.leetcode.com/coins-in-line/
第四轮是固定三个点以后用hashmap找第四个点做任意角度吗?-google 1point3acres

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

使用道具 举报

我的人缘0
 楼主| LumiG 发表于 2016-10-14 02:36:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (85)
 
 
2% (2)  踩
christwsy 发表于 2016-10-13 11:43
下周五onsite,路过蹭个rp。感觉楼主这波很稳啊
. visit 1point3acres for more.
别奶。。。加油加油!
回复

使用道具 举报

我的人缘0
 楼主| LumiG 发表于 2016-10-14 02:36:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (85)
 
 
2% (2)  踩
hjx447297354 发表于 2016-10-13 13:15
请问楼主是在哪面的?祝好运~

谢谢!在mtv
回复

使用道具 举报

我的人缘0
 楼主| LumiG 发表于 2016-10-14 02:36:50 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (85)
 
 
2% (2)  踩
cheeroh 发表于 2016-10-13 15:16.留学论坛-一亩-三分地
楼主R4的longest consecutive substring是什么题目?还是说是longest consecutive subsequence?LC128那个 ...

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

使用道具 举报

我的人缘0
 楼主| LumiG 发表于 2016-10-14 02:48:31 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (85)
 
 
2% (2)  踩
chestnut9919 发表于 2016-10-13 13:28
楼主能详细讲讲怎么做的找最小长方形吗?俩hashmap存啥啊?

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

使用道具 举报

我的人缘0
prodigalr 发表于 2016-10-14 07:40:11 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (24)
 
 
4% (1)  踩
LumiG 发表于 2016-10-14 02:48. 留学申请论坛-一亩三分地
分别存每行/每列有哪些点,里边我存的是所有另一个坐标的set。这样你遍历一遍所有点,每个点找和他在同一 ...

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

使用道具 举报

我的人缘0
rinto 发表于 2016-10-14 09:52:26 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
感谢楼主分享,第四题我试着用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. . From 1point 3acres bbs
  3.     [color=#808080][i]//xmap: for each x value, store the set of y values. 围观我们@1point 3 acres
  4. [/i][/color][color=#808080][i]    [/i][/color]Map<Integer, Set<Integer>> xmap = [color=#000080][b]new [/b][/color]TreeMap<>();. from: 1point3acres

  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. . 牛人云集,一亩三分地
  14.     [color=#000080][b]int [/b][/color]result = Integer.[color=#660e7a][b][i]MAX_VALUE[/i][/b][/color];
  15.     [color=#000080][b]boolean [/b][/color]found = [color=#000080][b]false[/b][/color];
  16. . Waral 博客有更多文章,
  17.     [color=#000080][b]for [/b][/color]([color=#000080][b]int [/b][/color]x : xmap.keySet()){
  18.         [color=#000080][b]for [/b][/color]([color=#000080][b]int [/b][/color]y : xmap.get(x)){
  19.             Iterator<Integer> yiter = xmap.get(x).iterator();
  20.             [color=#000080][b]int [/b][/color]yy = yiter.next();

  21.             [color=#000080][b]while [/b][/color](yy <= y && yiter.hasNext()){. Waral 博客有更多文章,
  22.                 yy = yiter.next();. 牛人云集,一亩三分地
  23.             }
  24.             [color=#000080][b]if [/b][/color](yy <= y){
  25.                 [color=#000080][b]break[/b][/color];
  26.             }. more info on 1point3acres

  27.             [color=#000080][b]boolean [/b][/color]keepSearch = [color=#000080][b]true[/b][/color];. from: 1point3acres

  28.             [color=#000080][b]while [/b][/color]([color=#000080][b]true[/b][/color]){
  29.                 Iterator<Integer> xiter = ymap.get(y).iterator();
  30.                 [color=#000080][b]int [/b][/color]xx = xiter.next();. 1point 3acres 论坛
  31.                 [color=#000080][b]while [/b][/color](xx <= x && xiter.hasNext()){
  32.                     xx = xiter.next();
  33.                 }
  34.                 [color=#000080][b]if [/b][/color](xx <= x || (yy - y) * (xx - x) >= result){. From 1point 3acres bbs
  35.                     keepSearch = [color=#000080][b]false[/b][/color];
  36.                     [color=#000080][b]break[/b][/color];
  37.                 }
  38.                 [color=#000080][b]while [/b][/color]([color=#000080][b]true[/b][/color]){
  39.                     [color=#000080][b]if [/b][/color](xmap.get(xx).contains(yy)){
  40.                         result = Math.[i]min[/i](result, (yy - y) * (xx - x));
  41.                         found = [color=#000080][b]true[/b][/color];
  42.                         [color=#000080][b]break[/b][/color];
  43.                     }

  44.                     [color=#000080][b]if [/b][/color](xiter.hasNext()){
  45.                         xx = xiter.next();
  46.                     } [color=#000080][b]else[/b][/color]{
  47.                         [color=#000080][b]break[/b][/color];
  48.                     }
  49.                 }
  50. . 1point 3acres 论坛
  51.                 [color=#000080][b]if [/b][/color](yiter.hasNext() && keepSearch){
  52.                     yy = yiter.next();
  53.                 } [color=#000080][b]else[/b][/color]{
  54.                     [color=#000080][b]break[/b][/color];
  55.                 }
  56.             }
  57.         }
  58.     }
  59.     [color=#000080][b]return [/b][/color]found ? result : -[color=#0000ff]1[/color];.留学论坛-一亩-三分地
  60. }
复制代码
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

GMT+8, 2018-9-22 09:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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