一亩三分地论坛

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

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

谷歌面经,我自己可能性不大,造福后人吧

[复制链接] |试试Instant~ |关注本帖
黄豆沙君 发表于 2016-10-29 07:04:33 | 显示全部楼层 |阅读模式

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

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

x
刚刚结束的面试,估计希望不大了,造福以后要面的同学。题目不是那么难但是自己实力有限。也算是为之后面试赞赞人品吧。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
电面  https://leetcode.com/problems/valid-word-square/https://leetcode.com/problems/word-squares/  当时没刷这道题,有一个基本的用trie和search的思路,然后强行当场写差点没写完,对面是国人妹子无比感谢,再三提醒下写了个70%出来。


第一轮,https://leetcode.com/problems/flatten-nested-list-iterator/ 类似这个,只是input变成了一个iterator,没用queue做,用了个list存然后就给自己挖了大坑,然后一个个test case跑了好多遍,结果优化了好半天,花了三十来分钟(这个很伤,希望大家别这样),跟他说了用queue但是他还是执意在现在的基础上改。 然后还剩10分钟的时候问了一个题差不多就是一个加锁的过程,其实很简单楼主一开始说的是synchronized整个map,但是后来跟他说不高效可以synchronized中间一个entry就好了。当时时间紧迫一急就没想出来,其实就是每个element用一个lock就好了,被自己蠢哭。这一轮肯定跪了!诶!他的问题是问的So how can you synchronize this entry,我就被带进去了在想synchronize完全没想锁的事情。没什么时间就结束了。

第二轮 每个人有父母,查看两个人有没有血缘关系。Follow up1 是query很多怎么办。Follow up2是每一个国家有这样一个储存本国的database,有的人会移民,例如AB在China,move to USA然后生了C,这种情况下问你如何完成这个问题。Follow up2一开始没有完全理解最后磕磕绊绊答出来了。


第三轮,国人小哥,题目不难,十分感谢。一个double linked list,然后有一个Node[], 问你这个array里的联通区间有多少个,有点类似 https://leetcode.com/problems/longest-consecutive-sequence/  我用这个题的top down的方法做了一遍,他问可不可以bottom up,然后就用union find再做了一遍。最后他问你如何自己实现一个Set,然后就把hash的基本过程,各种hash方法,resize,如何实现hash function说了一下。

第四轮, 一个word例如abcd,一个字典例如[abd, cc, aaa, d],通过从abcd中删除字符找到字典中包含的最长的字符。这一题完全不会做。给了两个Brute force的解法。一个是bfs generate然后看是不是在字典里。另一个是类似bucket sort把字典根据长度放到不同的bucket,然后从最长的bucket开始查看能不能生成一个。我先写了第二种解法,然后他给了follow up说字典很大装不进内存,我说分成小块然后慢慢给了一些小优化什么的。 后来又写了另一种解法,但是都不优,这一轮估计也跪了。

希望之后的面试能够好运。也建议大家不要口头跑test case过于详细,不然真的会时间不够。主要还是自己实力太差,多线程这一块也完全没有准备。也希望以后的面试能好运吧。

评分

4

查看全部评分

本帖被以下淘专辑推荐:

jiongjiongyoush 发表于 2016-10-29 07:09:24 | 显示全部楼层
祝lz好运~
回复 支持 反对

使用道具 举报

jocelyna 发表于 2016-10-29 07:20:28 | 显示全部楼层
第四轮就是word search吧,用trie就好了
回复 支持 反对

使用道具 举报

 楼主| 黄豆沙君 发表于 2016-10-29 07:22:02 | 显示全部楼层
jocelyna 发表于 2016-10-29 07:20
第四轮就是word search吧,用trie就好了

不是的,不能用trie,因为可以不连续,例如abcde, 字典是ace, bb,dd 减掉两个返回ace
回复 支持 反对

使用道具 举报

 楼主| 黄豆沙君 发表于 2016-10-29 07:22:23 | 显示全部楼层

. From 1point 3acres bbs谢谢啦!也祝你好运!!!好后悔啊诶!!!!
回复 支持 反对

使用道具 举报

jocelyna 发表于 2016-10-29 07:24:08 | 显示全部楼层
不是啊,把字典里的word都插入到trie里,Backtracking看原来的字符串删除字符可以组成哪些,用trie剪枝,提前返回,最后返回结果里面最长的
回复 支持 反对

使用道具 举报

 楼主| 黄豆沙君 发表于 2016-10-29 07:26:20 | 显示全部楼层
jocelyna 发表于 2016-10-29 07:24
不是啊,把字典里的word都插入到trie里,Backtracking看原来的字符串删除字符可以组成哪些,用trie剪枝,提 ...

原来的可以看成一个set....都不需要建成trie直接是否contains就好了....但是你这样就是brute force的解法了...也是我做的第一种
回复 支持 反对

使用道具 举报

jocelyna 发表于 2016-10-29 07:28:41 | 显示全部楼层
那最优解是啥?
回复 支持 反对

使用道具 举报

 楼主| 黄豆沙君 发表于 2016-10-29 07:32:53 | 显示全部楼层
.1point3acres缃
所以不知道呢.....我没做出来。。。。他说很多种方法做,他说有人用dp做,但是我真的不知道dp咋做
回复 支持 反对

使用道具 举报

美女的 发表于 2016-10-29 07:37:01 | 显示全部楼层
谢谢楼主了
回复 支持 反对

使用道具 举报

huai10 发表于 2016-10-29 07:42:04 | 显示全部楼层
第四个AC-automaton?
回复 支持 反对

使用道具 举报

jocelyna 发表于 2016-10-29 07:42:35 | 显示全部楼层
是只用返回长度,不用返回是哪个string吗?那应该dp可以
回复 支持 反对

使用道具 举报

Tsien 发表于 2016-10-29 07:45:46 | 显示全部楼层
LZ今天面的?或许我们见过?
回复 支持 反对

使用道具 举报

 楼主| 黄豆沙君 发表于 2016-10-29 07:45:58 | 显示全部楼层
huai10 发表于 2016-10-29 07:42
第四个AC-automaton?

这个太难了。。。大神Orz
回复 支持 反对

使用道具 举报

 楼主| 黄豆沙君 发表于 2016-10-29 07:46:08 | 显示全部楼层
jocelyna 发表于 2016-10-29 07:42
是只用返回长度,不用返回是哪个string吗?那应该dp可以

不是,返回string...
回复 支持 反对

使用道具 举报

 楼主| 黄豆沙君 发表于 2016-10-29 08:10:13 | 显示全部楼层
Tsien 发表于 2016-10-29 07:45
LZ今天面的?或许我们见过?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
也许!不过我刚checkin然后就被面试官带走了
回复 支持 反对

使用道具 举报

shadow7429 发表于 2016-10-29 08:26:03 | 显示全部楼层
黄豆沙君 发表于 2016-10-29 07:32
所以不知道呢.....我没做出来。。。。他说很多种方法做,他说有人用dp做,但是我真的不知道dp咋做

感觉就是BFS generator。
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2016-10-30 03:08:58 | 显示全部楼层
第四题有点难, 我感觉如果返回符合条件的string 是不能用dp做的, 我就是把dict里面的单词 放到一个hashset里面, 然后再把原string 从长度短的删除 就会这种方法
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-10-30 03:38:56 | 显示全部楼层
感谢分享,问下楼主第二轮都是怎么答的?
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2016-11-4 14:29:19 | 显示全部楼层
第三轮 follow up 第一问query 很多怎么办?求如何解答
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 14:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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