一亩三分地论坛

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

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

11/04 热腾腾的狗家电面,求onsite

[复制链接] |试试Instant~ |关注本帖
duziyuanyang 发表于 2016-11-5 04:19:04 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
听说面完到地里来报个面经拿到onsite的概率会变大?面完就来分享了(之前快码完了结果不小心页面被关了,再次码完分享,只求onsite)

约的美东下午2点,准时来了LA的电话,3分钟相互寒暄之后直接上题。

1.Given a text file, remove all the duplicate lines, maintaining the order such that the first occurrences of the lines stay in the same order.
照例先问file size,能不能用extra space。小哥说take it easy你开心就好 ,于是用hashset解决,我问能不能把input简化成int[] array存hashcode,小哥先问了how to hash和conflict的问题,然后问存hashcode的话本来的出现顺序如何维护,我说加个map。小哥同意,于是1分钟码完,中间出个小bug,因为用的hashset,小哥问顺序如何维护,我说那就linkedhashset,他同意。. From 1point 3acres bbs
follow up就是常规的file size大到内存放不下怎么办,我就说split into small pieces然后sorting去重,然后external sort。本来以为他会问我怎么external sort,结果他一直在质疑我用sorting去重的方法出现顺序没法保证,我花了5分钟run case才跟他说清楚(感觉他是故意装傻),此时时间已经过去20分钟。. 1point3acres.com/bbs

2.trapping rain water,照例跟他确认了问题和输入输出后先说了个O(N^2)的解法,小哥没听懂,我又跟他run case,但这题光有图不能指说起来真的很难说清楚,35分钟的时候他终于同意我的解法,我看时间不多了想抓紧码掉。他说不急,咱们先优化下,于是我说用单调栈实现O(N), 他说O(N)的确不错,但不需要用stack, 我又赶紧翻开笔记说了个记录level的方法,小哥说也不是他想要的。最后给了hint说只需要记录leftmost和rightmost, curBar存多少水只只取决min(leftmost, rightmost), 我心想这不还是单调栈嘛。。但嘴上只能说wo, so cool!那我来实现下吧,小哥说不用了,我知道你想出来了就行,下面问我问题吧。

本来心想45分钟电面就写一个10行不到的代码,还出了个bug,第二题也没想出最优解,估计是挂了,于是随便问了个问题,what do think is the most important quality to be a great SDE in Google? 结果这小哥陷入了沉思,跟我分析了5分钟,说了balance between get something work and get something clean, 总体就是entry level先把活干了避免layoff, 升上去了或者活有余力再想优化。我一看他居然还聊hi了就赶紧follow up一下问他,所以你觉得对entry level来说ddl比quality更重要咯?他又跟我讲起了他自己的故事,中间不断跟我讲段子,有的没听懂,听懂的我就抖个机灵也跟他讲段子,一来二去时间已经到了3:15, 持续了半个小时的欢声笑语后突然出现了5秒钟的冷场,我当时心里再想:你是不是要跟我say goodbye了?但猜他在想:哥今天开心,再问再问再问。于是我就说感觉今天表现不是很好,最后一题没想出最优解(潜台词其实是,大哥我都陪您hi了这么久了,您能放我过吗),结果他还是不置可否,说大概1周出结果。大概3:20那边挂了电话。

总结下:
lz运气挺好了,遇到两个这么简单的题,比起最近G家电面的画风真是很幸运了,但是lz自身实力有限,trapping rain water的确只会那两种解法,挂了我也认了,毕竟白人小哥从头到尾套路太深,真的不知道他是想故意放水还是来个十动然拒。。接下来刷题一定要多想solution, 多想follow up。.鏈枃鍘熷垱鑷1point3acres璁哄潧

不求大米,只求好运,给个onsite吧!
.1point3acres缃


补充内容 (2016-11-10 03:56):
今天中午收到hr电话给onsite了,感谢白人小哥放水

补充内容 (2016-11-10 03:58):. visit 1point3acres.com for more.
打算预约12.15左右的onsite, 如果有12月onsite狗家的同学欢迎加微信sunyu566376一起准备面经题

评分

2

查看全部评分

本帖被以下淘专辑推荐:

chaosMonkey 发表于 2016-11-11 15:41:49 | 显示全部楼层
duziyuanyang 发表于 2016-11-10 22:38
如果用unordered_set的话请问如何保证set里元素在text里的出现顺序呢
. From 1point 3acres bbs
不知道我是不是有点没太理解题意,lz说的是不是读入一个文件中所有的行,按照原有顺序输出每行数据,如果遇到重复的,保留第一次出现的数据,其他的重复元素不输出? 如果这样的话,我的意思是set用来保存读入的数据,起到去重作用,输出还是照常输出,不管是直接打印还是说写到另外的文件中,set跟输出没关系。原有的文件中的行的顺序就是遍历这个文件读入数据的顺序吧
回复 支持 1 反对 0

使用道具 举报

prodigalr 发表于 2016-11-5 04:51:19 | 显示全部楼层
请问楼主是怎么回答how to hash和conflict的问题?
回复 支持 反对

使用道具 举报

 楼主| duziyuanyang 发表于 2016-11-5 04:52:29 | 显示全部楼层
prodigalr 发表于 2016-11-5 04:51
请问楼主是怎么回答how to hash和conflict的问题?

就是讲一下hash function还有两种collision ,说下利弊
回复 支持 反对

使用道具 举报

jiongjiongyoush 发表于 2016-11-5 05:15:30 | 显示全部楼层
Lz能不能讲讲第一题具体怎么做
用map是存什么信息
回复 支持 反对

使用道具 举报

 楼主| duziyuanyang 发表于 2016-11-6 10:27:14 | 显示全部楼层
jiongjiongyoush 发表于 2016-11-5 05:15
Lz能不能讲讲第一题具体怎么做
用map是存什么信息

打个比方,本来文本里存的是google-> onsite->google-> onsite->wanted, 假设"google"的 hashcode是2, "onsite"的dashcode是"1", wanted是"0", 我们不能根据hashcode的大小来决定相对顺序,所以需要先把string-> hashcode的mapping关系先记录下来
回复 支持 反对

使用道具 举报

jiongjiongyoush 发表于 2016-11-6 10:53:22 | 显示全部楼层
duziyuanyang 发表于 2016-11-6 10:27
打个比方,本来文本里存的是google-> onsite->google-> onsite->wanted, 假设"google"的 hashcode是2, "o ...

存string和hashcode是怎么保持order呢。。。。TT没懂
hashcode是指hashvalue么,如果有collision怎么办
回复 支持 反对

使用道具 举报

freeaccount 发表于 2016-11-6 11:02:30 | 显示全部楼层
fresh grad但是是猎头找的?
回复 支持 反对

使用道具 举报

 楼主| duziyuanyang 发表于 2016-11-6 22:25:23 | 显示全部楼层
jiongjiongyoush 发表于 2016-11-6 10:53
存string和hashcode是怎么保持order呢。。。。TT没懂
hashcode是指hashvalue么,如果有collision怎么办

. from: 1point3acres.com/bbs 你可以自己强制性的把"google"的hash value map 成0, "onsite"的hashvalue-> 1, "wanted"->2这个样子,相当于做一个normalization
回复 支持 反对

使用道具 举报

 楼主| duziyuanyang 发表于 2016-11-6 22:25:45 | 显示全部楼层
freeaccount 发表于 2016-11-6 11:02
fresh grad但是是猎头找的?

hr联系的
回复 支持 反对

使用道具 举报

chaosMonkey 发表于 2016-11-6 23:02:52 | 显示全部楼层
lz说的第一题,如果用C++的话,应该直接用个unordered_set记录已经输出过的数据就可以了吧,set中没有的就输出并且记录在set中,set中有的就不输出,而且,感觉很多hash function基本都是语言的标准库提供,还需要自己设计吗
回复 支持 反对

使用道具 举报

zzwcsong 发表于 2016-11-10 13:20:17 | 显示全部楼层
LZ能在细说下第一题Follow up的Sorting去重吗?是sort什么呢?是之前hashcode对应的mapping吗?
回复 支持 反对

使用道具 举报

 楼主| duziyuanyang 发表于 2016-11-10 22:38:48 | 显示全部楼层
chaosMonkey 发表于 2016-11-6 23:02
lz说的第一题,如果用C++的话,应该直接用个unordered_set记录已经输出过的数据就可以了吧,set中没有的就 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
如果用unordered_set的话请问如何保证set里元素在text里的出现顺序呢
回复 支持 反对

使用道具 举报

 楼主| duziyuanyang 发表于 2016-11-10 22:39:18 | 显示全部楼层
zzwcsong 发表于 2016-11-10 13:20
LZ能在细说下第一题Follow up的Sorting去重吗?是sort什么呢?是之前hashcode对应的mapping吗?

我是这么做的,其实方法就很多啦,而且感觉这个并不是重点
回复 支持 反对

使用道具 举报

 楼主| duziyuanyang 发表于 2016-11-10 22:39:25 | 显示全部楼层
zzwcsong 发表于 2016-11-10 13:20
LZ能在细说下第一题Follow up的Sorting去重吗?是sort什么呢?是之前hashcode对应的mapping吗?

我是这么做的,其实方法就很多啦,而且感觉这个并不是重点
回复 支持 反对

使用道具 举报

 楼主| duziyuanyang 发表于 2016-11-10 22:39:32 | 显示全部楼层
zzwcsong 发表于 2016-11-10 13:20. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
LZ能在细说下第一题Follow up的Sorting去重吗?是sort什么呢?是之前hashcode对应的mapping吗?

. Waral 鍗氬鏈夋洿澶氭枃绔,我是这么做的,其实方法就很多啦,而且感觉这个并不是重点
回复 支持 反对

使用道具 举报

 楼主| duziyuanyang 发表于 2016-11-11 23:32:40 | 显示全部楼层
chaosMonkey 发表于 2016-11-11 15:41
不知道我是不是有点没太理解题意,lz说的是不是读入一个文件中所有的行,按照原有顺序输出每行数据,如果 ...

比如原来是[1,1,2,2,2,3,3], hashset里是[3,2,1]或者是[3,1,2], 请问你的方法如何返回[1,2,3]
回复 支持 反对

使用道具 举报

chaosMonkey 发表于 2016-11-14 16:56:23 | 显示全部楼层
duziyuanyang 发表于 2016-11-11 23:32. 1point 3acres 璁哄潧
比如原来是[1,1,2,2,2,3,3], hashset里是[3,2,1]或者是[3,1,2], 请问你的方法如何返回[1,2,3]
  1. vector<int> output;
  2. set<int> st;
  3. for(auto a : input){
  4.         if(st.count(a) > 0)
  5.                 continue;. 鍥磋鎴戜滑@1point 3 acres
  6.         else{
  7.                 output.push_back(a);
  8.                 st.insert(a);
  9.         }
  10. }
  11. return output;
复制代码
回复 支持 反对

使用道具 举报

stellari 发表于 2016-11-14 17:28:24 | 显示全部楼层

这方法其实和lz说的LinkedHashSet基本是一个意思,vector(list也可)+unordered_set就等于自己提供了一个简单的LinkedHashSet实现。而且这个vector,其实完全就是lz所说的“你可以自己强制性的把"google"的hash value map 成0, "onsite"的hashvalue-> 1, "wanted"->2这个样子,相当于做一个normalization”这样的mapping。只是lz的表述有些绕弯了。

回复 支持 反对

使用道具 举报

 楼主| duziyuanyang 发表于 2016-11-14 23:55:19 | 显示全部楼层
嗯,有道理!可能怪我表述不清
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 19:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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