买新车如何让dealer直接竞价?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 10336|回复: 44
收起左侧

gg onsite 10月 fresh grad

[复制链接] |试试Instant~ |关注本帖
我的人缘0
LumiG 发表于 2016-10-13 07:35:19 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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

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

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

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

R2:.1point3acres网
一个奇怪的warmup,花了我二十分钟=。=一直没理解他什么意思,特别伤… (可能因为这个,这轮另两题尤其简单吧…)
一个wordlist,一组characters,问哪些word可以用characters里的字符拼起来(要考虑重复的),?代表任意字符,就是hashmap数一下,python用下counter代码没几行
一个array [1,5,3,8,10] 这样,代表n堆硬币,两个人每次可以取头上的或者尾巴上的硬币,最后拿的总和最多的人获胜,求先手的最优策略。。。我只写了个递归的,面试时间到了没来得及写dp的,都怪第一题。。。. visit 1point3acres for more.
. 1point3acres
R3:
这轮也挺神奇的,面我的人临时有事,找了人替他来面,结果这个人只准备了一道题,大致是把一个矩阵里边,相邻一样的数字merge成一个点,然后有一些其他小限制。大致dfs一遍就行。
然后,这白人大哥和我说,他只准备了这一道题=。=然后他和我说,那我来看看怎么变化一下,问你点follow up吧,然后就和我讨论了半个小时各种其他情况。。有的写了代码,有的没有写,反正就是各种dfs,最后就结束了。

R4:
longest consecutive substring
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 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
再贡献一个我的第四题解法。N^2复杂度. from: 1point3acres
=========================.本文原创自1point3acres论坛
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

查看全部评分

回复 支持 6 反对 0

使用道具 举报

我的人缘0
pawprinter 发表于 2016-10-23 11:31:47 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
直接onsite真好。。gg坑爹加一轮电面。。。
回复 支持 1 反对 0

使用道具 举报

我的人缘0
magic95 发表于 2016-10-13 11:04:36 | 显示全部楼层
  此人我要顶:
 
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
回复 支持 1 反对 0

使用道具 举报

我的人缘0
chestnut9919 发表于 2016-10-13 10:47:56 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
求问楼主第二轮取硬币的dp怎么写?
回复 支持 反对

使用道具 举报

我的人缘0
yezhangpost 发表于 2016-10-13 11:00:15 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
求能够组成最小的长方形的题的解法,谢楼主
回复 支持 反对

使用道具 举报

我的人缘0
wtcupup 发表于 2016-10-13 11:09:09 | 显示全部楼层
  此人我要顶:
 
11% (0) 【我投】
  此人我要踩:
 
89% (9) 【我投】
第四轮是这个题? https://leetcode.com/problems/perfect-rectangle/
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| LumiG 发表于 2016-10-13 11:20:04 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
wtcupup 发表于 2016-10-13 11:09. 围观我们@1point 3 acres
第四轮是这个题? https://leetcode.com/problems/perfect-rectangle/
.1point3acres网
没有没有,比这题容易很多,就是给一堆坐标,问能够组成的最小的长方形。能旋转的找个set存下,平行的弄两个hashmap就行。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
chestnut9919 发表于 2016-10-13 11:27:15 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
magic95 发表于 2016-10-13 11:04. Waral 博客有更多文章,
代码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% (暂未有人投票) 【我投】
下周五onsite,路过蹭个rp。感觉楼主这波很稳啊
回复 支持 反对

使用道具 举报

我的人缘0
hjx447297354 发表于 2016-10-13 13:15:01 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
请问楼主是在哪面的?祝好运~
回复 支持 反对

使用道具 举报

我的人缘0
chestnut9919 发表于 2016-10-13 13:28:41 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼主能详细讲讲怎么做的找最小长方形吗?俩hashmap存啥啊?
回复 支持 反对

使用道具 举报

我的人缘0
cheeroh 发表于 2016-10-13 15:16:29 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼主R4的longest consecutive substring是什么题目?还是说是longest consecutive subsequence?LC128那个?
回复 支持 反对

使用道具 举报

我的人缘0
sophie729 发表于 2016-10-13 17:56:53 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
感谢分享,感觉肯定妥了 ,best luck!
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

我的人缘0
 楼主| LumiG 发表于 2016-10-14 02:36:09 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
christwsy 发表于 2016-10-13 11:43
下周五onsite,路过蹭个rp。感觉楼主这波很稳啊
. more info on 1point3acres
别奶。。。加油加油!
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| LumiG 发表于 2016-10-14 02:36:20 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
hjx447297354 发表于 2016-10-13 13:15.1point3acres网
请问楼主是在哪面的?祝好运~

谢谢!在mtv
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| LumiG 发表于 2016-10-14 02:36:50 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
cheeroh 发表于 2016-10-13 15:16. 围观我们@1point 3 acres
楼主R4的longest consecutive substring是什么题目?还是说是longest consecutive subsequence?LC128那个 ...

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

使用道具 举报

我的人缘0
 楼主| LumiG 发表于 2016-10-14 02:48:31 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
chestnut9919 发表于 2016-10-13 13:28 来源一亩.三分地论坛.
楼主能详细讲讲怎么做的找最小长方形吗?俩hashmap存啥啊?

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

使用道具 举报

我的人缘0
prodigalr 发表于 2016-10-14 07:40:11 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
LumiG 发表于 2016-10-14 02:48
分别存每行/每列有哪些点,里边我存的是所有另一个坐标的set。这样你遍历一遍所有点,每个点找和他在同一 ...

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

使用道具 举报

我的人缘0
rinto 发表于 2016-10-14 09:52:26 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
感谢楼主分享,第四题我试着用treemap做了一下, 大意就是对于每个点(x,y), 往左边找到一个点(xx, y), 往下找到一个点(x,yy),然后看看(xx,yy)是不是存在。. From 1point 3acres bbs
这样平均可能是O(N^2logN)吧,如果找再存一个hashmap用来着(xx,yy),平均可能是O(N^2)。有一个好处是可以减掉一些不必要的搜索。
不知道写的对不对,我大概跑了两个test是对的
  1. . visit 1point3acres for more.
  2. [color=#000080][b]public int [/b][/color]smallestRectangle([color=#000080][b]int[/b][/color][][] points){

  3.     [color=#808080][i]//xmap: for each x value, store the set of y values
  4. [/i][/color][color=#808080][i]    [/i][/color]Map<Integer, Set<Integer>> xmap = [color=#000080][b]new [/b][/color]TreeMap<>();

  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){. more info on 1point3acres
  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];. more info on 1point3acres
  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)){
  17.             Iterator<Integer> yiter = xmap.get(x).iterator();. visit 1point3acres for more.
  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();-google 1point3acres
  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]){
  27.                 Iterator<Integer> xiter = ymap.get(y).iterator();
  28.                 [color=#000080][b]int [/b][/color]xx = xiter.next();. 围观我们@1point 3 acres
  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];. from: 1point3acres
  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.                     }

  42.                     [color=#000080][b]if [/b][/color](xiter.hasNext()){.留学论坛-一亩-三分地
  43.                         xx = xiter.next();
  44.                     } [color=#000080][b]else[/b][/color]{. more info on 1point3acres
  45.                         [color=#000080][b]break[/b][/color];
  46.                     }
  47.                 }

  48.                 [color=#000080][b]if [/b][/color](yiter.hasNext() && keepSearch){
  49.                     yy = yiter.next();
  50.                 } [color=#000080][b]else[/b][/color]{
  51.                     [color=#000080][b]break[/b][/color];
  52.                 }
  53.             }.本文原创自1point3acres论坛
  54.         }
  55.     }. Waral 博客有更多文章,
  56.     [color=#000080][b]return [/b][/color]found ? result : -[color=#0000ff]1[/color];
  57. }
复制代码
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-6-22 15:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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