一亩三分地论坛

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

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

Google/Youtube Onsite

[复制链接] |试试Instant~ |关注本帖
jaly50 发表于 2015-7-10 11:15:05 | 显示全部楼层 |阅读模式

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

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

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

x
签了NVA,本不该说什么.但是不开心。
今天google的hiring committee说是没有approval,但是还是可以帮我问问有没有team要我。
也不知算不算被拒了QAQ


本来早就可以去hiring committee的,但是一个面试官自己有死线,就一直不给我feeback,等了三周才收集好。
(三周我自己都忘了我自己的表现了,面试官还能记得?.1point3acres缃
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
没有给我positive的一定是他!QAQ
第四个面试官!问题简单啊,我自我感觉很好的,怎么就没有positive呢!. from: 1point3acres.com/bbs
.1point3acres缃
题目:
3. Word abbreviation,
e.g. Between=>b5n,  friend=>f4d
Follow-up: implement. Waral 鍗氬鏈夋洿澶氭枃绔,
Bool checkduplicate(string [] dict, string word)
E.g. {feed }, feed => false;  {door }, deer =>true;  {dare}, deer => false
如果dict里有word 和input word的abbreviation 一样,则return true
注意就是查的词 一定在dict里。

让我拿几个case test 一下。我就自己想了几个数据去测试,都没有问题啊。。。而且这个步骤又不费脑子,我本来超开心就这样水过。可是后来才知道feedback说我out of time...(说的真的是我吗!明明一路很顺利...最后明明是写完题,聊聊天的时候超时的!

问我复杂度:我说o(n),n是dict的长度。
然后要我降复杂度 ....我胡诌要不binary search...logn
然后问我这个method如果被访问千万遍,要怎么降复杂度? 我说 建map<Abbreaviation, List<String>>  ==> 就可以o(1)找到duplicate啦!
-google 1point3acres
感觉自己蛮机智的!而且题目很简单啊秒答啊...没有卡住也没有要hint!  为什么会不postive不明白!

要不要argue...要不要argue


5轮面试,3个postive
还有一个不如人意的,也是面完后来在网上有看到面经的...
第二轮是个阿三,感觉很吊的样子,一副大爷样地坐在那里,让我很不爽。他就问了很
简单的一道题,然后就是不停地问我如何改进。
2. Given a list of words, find two strings S & T such that:
    a. S & T have no common character
    b. S.length() * T.length() is maximized
Follow up: how to optimize and speed up your algorithm
我才发现:一直以为三哥哥说的是link,...原来是length
我还建了一个数据结构 叫
class Word{
   String word;
   int link;
}
后来看到,只能说呵呵呵了
所以当时完全没办法根据length的属性去想到优化方法啊!!!>.<
这题算自己活该吧。QAQ



本帖被以下淘专辑推荐:

dayouxia 发表于 2015-7-24 11:35:14 | 显示全部楼层
好久没见到有人把弱点概括得如此言简意赅,我笑了好一会
“感觉自己蛮机智的!而且题目很简单啊秒答啊...没有卡住也没有要hint!  为什么会不postive不明白!”
1. 好机智,很简单=我没理解题意。
2. 秒答 = 我说话不走脑子。
3. 没有要hint =不会问问题
面试官想要的答案是trie,不过答案不重要,你code写的不是bug free如果思路清晰一样能过。
不要气馁,都是从那个阶段过来的,好好刷题,没有google还有fb twitter linkedin。只不过以后不要再觉得自己好机智了xD哈哈哈哈
回复 支持 1 反对 3

使用道具 举报

iverson1122 发表于 2015-8-13 05:02:43 | 显示全部楼层
jaly50 发表于 2015-8-5 01:01
噢噢噢,明白了,感谢!自己都没有想到这样的方法。 -google 1point3acres
. visit 1point3acres.com for more.
那我说的:建map  ==> 就可以o(1)找到duplicate
...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
感觉这个map可以进一步简化吧,存成map<Abbreaviation,int>可以不,存abbreaviation出现的数目,只要索引出来大于1就return false

补充内容 (2015-8-13 09:50):
大于1的话return True。。。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

xuyirio 发表于 2015-7-24 12:48:31 | 显示全部楼层
越是自我感觉良好越容易挂。word abbreviation这题,如果真如你所说,code简单易写,test都过,想改进也“好机智”,却为什么花掉了整个session的时间?
回复 支持 0 反对 1

使用道具 举报

akiame 发表于 2015-7-25 22:34:01 | 显示全部楼层
地里戾气真是重 有些人的语气哟啧啧
回复 支持 0 反对 1

使用道具 举报

MCwong 发表于 2015-7-10 16:11:57 | 显示全部楼层
"这个method如果被访问千万遍,要怎么降复杂度?", 这里每次访问传进来的dict和word都会不一样么?
回复 支持 反对

使用道具 举报

leo524891010 发表于 2015-7-11 06:58:22 | 显示全部楼层
bless楼主,请问3个positive是怎么知道的
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2015-7-24 09:21:24 | 显示全部楼层
MCwong 发表于 2015-7-10 16:11
"这个method如果被访问千万遍,要怎么降复杂度?", 这里每次访问传进来的dict和word都会不一样么?

没细说诶
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2015-7-24 09:21:45 | 显示全部楼层
leo524891010 发表于 2015-7-11 06:58
bless楼主,请问3个positive是怎么知道的

hr很好。会跟你讲。在没过hc的时候。

被拒了。难过。
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-7-26 01:16:12 | 显示全部楼层
算了楼主, 你也不会想和这些人共事吧。
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-7-26 01:24:13 | 显示全部楼层
我当时面试的时候也感觉题目好简单,好顺利。但是面完之后是非常害怕的,因为总感觉这么顺利哪里不对。是不是理解错题了。。一直没敢声张说简单,怕没offer被打脸
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-7-26 01:52:25 | 显示全部楼层
E.g. {feed }, feed => false==》 true ????;  {door }, deer =>true;  {dare}, deer => false
如果dict里有word 和input word的abbreviation 一样,则return true
回复 支持 反对

使用道具 举报

irasit 发表于 2015-7-26 02:51:36 | 显示全部楼层
对啊,不理解为啥  {feed }, feed => false  ?
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2015-8-4 04:56:47 | 显示全部楼层
dayouxia 发表于 2015-7-24 11:35. visit 1point3acres.com for more.
好久没见到有人把弱点概括得如此言简意赅,我笑了好一会
“感觉自己蛮机智的!而且题目很简单啊秒答啊... ...

好犀利
感谢这样的评论
嗯应该是trie。。。面完之后我也才想到。. visit 1point3acres.com for more.

不过trie也没有比hashmap更优吧
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2015-8-4 04:59:28 | 显示全部楼层
xuyirio 发表于 2015-7-24 12:48
越是自我感觉良好越容易挂。word abbreviation这题,如果真如你所说,code简单易写,test都过,想改进也“ ...

让我模拟了3遍test的过程,这个花了很长的时间。
但我一直都没有发现的自己的bug,所以时间就白花没了。
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2015-8-4 04:59:51 | 显示全部楼层
hulahu 发表于 2015-7-26 01:16
算了楼主, 你也不会想和这些人共事吧。

我倒是想XD
嗯谢谢你的安慰
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2015-8-4 05:03:04 | 显示全部楼层
Linzertorte 发表于 2015-7-26 01:24
我当时面试的时候也感觉题目好简单,好顺利。但是面完之后是非常害怕的,因为总感觉这么顺利哪里不对。是不 ...

结果呢,有么?

你这样的心态是很谦虚很好的呀
.鐣欏璁哄潧-涓浜-涓夊垎鍦
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2015-8-4 05:04:50 | 显示全部楼层
hulahu 发表于 2015-7-26 01:52
E.g. {feed }, feed => false==》 true ????;  {door }, deer =>true;  {dare}, deer => false
如果 ...

面试官告诉我,dict里面是包含了所有的词。
所以如果要查feed, dict里面是肯定有feed的。

我们要问的是,dict里面有没有和那个词一样abbreviation的其他单词。 所以如果dict里只有feed,自然是false.
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2015-8-4 05:05:01 | 显示全部楼层
irasit 发表于 2015-7-26 02:51
对啊,不理解为啥  {feed }, feed => false  ?

面试官告诉我,dict里面是包含了所有的词。.1point3acres缃
所以如果要查feed, dict里面是肯定有feed的。. From 1point 3acres bbs

我们要问的是,dict里面有没有和那个词一样abbreviation的其他单词。 所以如果dict里只有feed,自然是false.
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2015-8-4 05:36:07 | 显示全部楼层
dayouxia 发表于 2015-7-24 11:35
好久没见到有人把弱点概括得如此言简意赅,我笑了好一会
“感觉自己蛮机智的!而且题目很简单啊秒答啊... ...
. 鍥磋鎴戜滑@1point 3 acres
我还想讨论和请教一下:
用trie的话,是不是有点bfs一样,层层遍历地去找,但是要height刚好等于word.length() 才去检查是否相同abbreviation.

感觉如果单词短的话,那确实复杂度能降低。
但是单词长的话,worst case岂不是要把整棵trie都遍历一遍?
. visit 1point3acres.com for more.
我的理解对不对?如果用trie的话,有什么办法利用word.length()这一提前知道的条件做什么优化吗?
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2015-8-4 05:37:54 | 显示全部楼层
akiame 发表于 2015-7-25 22:34
地里戾气真是重 有些人的语气哟啧啧

就知道妹子疼我
谢谢妹子么么哒
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 00:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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