一亩三分地论坛

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

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

谷on塞 BakerySqure

[复制链接] |试试Instant~ |关注本帖
shirt 发表于 2016-11-17 05:28:32 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 本科 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
1.Leetcode course scheduleII简化版,不会有环=>一定有一个sequence。
2.(地里前几天的面经有)Guess string(jargo game?)给一个dictionary,一个Picker选一个词并返回guessed string和该词的相同char的个数(给了int makeguess(String guess)),implement Guesser的guess()  method,使得尽量少调用makeguess()方法
3.给一个target Node和sourceNode,判断两个是否相连(Kary tree),自己定义Node, follow-up:如果你可以process given data structure优化search的time complexity,先想到用hashmap,又说能不能在O(1)的空间优化。
4.Domino Game(没听说过这个游戏,规则基本靠问),Domino牌定义为一个只有两个int的array,按d(i)[0] == d(i-1)[1] && d(i)[1] == d(i+1)[0]的顺序连起来,先是很笼统的说去实现这个game的add和length,写了个add(Domino d)之后又问add first怎么办,实现了add first之后又问add中间怎么办,总之最后就是各种followup,最后还要把add变成O(1)(本来用的Collection List这样就不能用了,后来想想面试官中间说了一嘴说他不是很熟悉java,所以可能还是希望能看到自己写的数据结构吧)

这次面试前recruiter就说了只考算法和datastruture不考system design,然后题目虽然不难但是感觉沟通的磕磕绊绊的还是希望能送hc,而且感谢之前地里的面经压到了一道原题(面的时候心里千恩万谢地里的前辈),所以刚面就来汇报了,而且听说面试官其实都只考一道题(一般没跟之前的人重复就不换题),希望大家也能好运(第一次发帖不知道什么姿势能求到卧佛?)!
. 1point 3acres 璁哄潧

评分

1

查看全部评分

本帖被以下淘专辑推荐:

houqingniao 发表于 2016-11-17 05:32:43 | 显示全部楼层
bless LZ. guess 这个题能详细说下吗
回复 支持 反对

使用道具 举报

 楼主| shirt 发表于 2016-11-17 06:52:35 | 显示全部楼层
houqingniao 发表于 2016-11-17 05:32
bless LZ. guess 这个题能详细说下吗

哦哦题目给了一个5-letter word的dictionary(自己选择用什么data structure表示我用了Set),然后要最少次数的调用makeGuess方法来得到那个Picker选择的String。我最后用的HashMap存之前的String-int pair然后iterate dictionary来找,每个iteration里面跟之前的String算一下相同的char个数,和map里的value不同就略去,最后worst case 还是O(n^2),只是recruiter也没问优化了。
回复 支持 反对

使用道具 举报

xiangminxufsu 发表于 2016-11-17 15:49:44 | 显示全部楼层
shirt 发表于 2016-11-17 06:52
哦哦题目给了一个5-letter word的dictionary(自己选择用什么data structure表示我用了Set),然后要最少次 ...

感觉不是很对啊。。
如果第一次guess abcde,返回1,然后找到第二个单词axyzq,也是返回1,这种情况该怎么办呢?有可能a是属于被猜的单词的,也有可能不是啊。如果axyzq返回0的话至少能证明a一定不是被猜的单词。
回复 支持 反对

使用道具 举报

 楼主| shirt 发表于 2016-11-18 04:03:00 | 显示全部楼层
xiangminxufsu 发表于 2016-11-17 15:49
感觉不是很对啊。。
如果第一次guess abcde,返回1,然后找到第二个单词axyzq,也是返回1,这种情况该怎么办 ...

这样就调用makeguess并且把结果存在map里啊~
回复 支持 反对

使用道具 举报

dfnjy 发表于 2016-11-18 06:42:14 | 显示全部楼层
请问楼主第三题是啥意思……Kary tree里的节点为啥会不相连……不都和root连着么
follow up什么是process given data structure?是给你一个用来搜索的data structure吗?
谢谢~
回复 支持 反对

使用道具 举报

hellojay 发表于 2016-11-18 09:41:07 | 显示全部楼层
同问第三题具体的描述,多谢楼主
回复 支持 反对

使用道具 举报

 楼主| shirt 发表于 2016-11-18 11:47:02 | 显示全部楼层
hellojay 发表于 2016-11-18 09:41
同问第三题具体的描述,多谢楼主
. From 1point 3acres bbs
啊对不住描述不清,不是问两个node是否有共同parent,而是判断这两个node是否直接相连(source是否能通过向下找到target)现在想想当时好像强行把问题简化了,面试官开始只说判断两个是否connect,我问是指用从source开始找children,找到target就可以了吗,面试官说是…就…感觉悲剧了啊…以及可以@一下楼上的同学吗~
回复 支持 反对

使用道具 举报

 楼主| shirt 发表于 2016-11-18 11:50:13 | 显示全部楼层
dfnjy 发表于 2016-11-18 06:42
请问楼主第三题是啥意思……Kary tree里的节点为啥会不相连……不都和root连着么
follow up什么是process  ...

嗯嗯~他的意思应该就是让我通过改一下我的node的structure来实现优化吧…最后在他的提示下我说那我直接把parentnode存在node里好了他让重新说了下找的过程就没followup了…
回复 支持 反对

使用道具 举报

waikai 发表于 2016-11-18 12:00:05 | 显示全部楼层
lz请问guess的时候可以不用dic里面的单词么?
回复 支持 反对

使用道具 举报

 楼主| shirt 发表于 2016-11-18 12:11:05 | 显示全部楼层
waikai 发表于 2016-11-18 12:00
lz请问guess的时候可以不用dic里面的单词么?

应该…可以?我大概问了下assumption就跟他说了iterate dictionary的方法,面试官说那你implement吧…
回复 支持 反对

使用道具 举报

xiangminxufsu 发表于 2016-11-18 12:26:49 | 显示全部楼层
shirt 发表于 2016-11-18 12:11
应该…可以?我大概问了下assumption就跟他说了iterate dictionary的方法,面试官说那你implement吧…
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
那可不可以先猜5个a,再来5个b,一直到z,这样就知道有几个a,几个b组成的了啊。最后排列一下。。. 1point 3acres 璁哄潧

补充内容 (2016-11-18 12:31):
最后好像不要排列,从字典里找一个由相同字母组成的单词。
回复 支持 反对

使用道具 举报

 楼主| shirt 发表于 2016-11-18 12:35:49 | 显示全部楼层
xiangminxufsu 发表于 2016-11-18 12:26. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
那可不可以先猜5个a,再来5个b,一直到z,这样就知道有几个a,几个b组成的了啊。最后排列一下。。

哈哈哈这个当然可以得到结果啊…我当时没怎么问dictionary以及单词构成的情况(啊这么一想感觉更糟糕了)然后加上开始面试官强调了两次是希望找到调用makeguess最少的方法,就没有考虑这种方法了…
回复 支持 反对

使用道具 举报

xiangminxufsu 发表于 2016-11-18 13:37:18 | 显示全部楼层
shirt 发表于 2016-11-18 12:35. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
哈哈哈这个当然可以得到结果啊…我当时没怎么问dictionary以及单词构成的情况(啊这么一想感觉更糟糕了) ...

这题有点不常规,挺开放的。楼主莫慌,说不定offer在路上呢。
回复 支持 反对

使用道具 举报

sf3 发表于 2016-12-1 15:10:27 | 显示全部楼层
不知道楼主说的面经是不是我的面经。。。希望帮到了楼主。。
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 4 天前 | 显示全部楼层
domino add first 其实只要 add的那个数组 a[0] == d[0][0]就好了
然后add中间的话, 那个int[] b[0] = b[1] == d[i-1][0] 就好了  是这么选择的吗?
回复 支持 反对

使用道具 举报

红醋栗树 发表于 3 天前 | 显示全部楼层
shirt 发表于 2016-11-18 11:50
嗯嗯~他的意思应该就是让我通过改一下我的node的structure来实现优化吧…最后在他的提示下我说那我直接 ...

请问楼主,直接把parentnode存在node里的话,就不是O(1) 的空间优化了吧?
回复 支持 反对

使用道具 举报

donnice 发表于 3 天前 | 显示全部楼层
求问地里guess这道题有人写过代码么?
回复 支持 反对

使用道具 举报

donnice 发表于 3 天前 | 显示全部楼层
关于字典那题我是这么想的,根据picker选出的word以及makecount(word),与字典里所有的词比对,与makecount(word)不相符的就去掉,然后慢慢一层层地删除,剩下的就是结果了 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

其实我觉得挺愚蠢的,既然有dictionary的话,我一个个选出来和结果比对不就得了
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 3 天前 | 显示全部楼层
其实可以建立一个 hashset 然后把字典里 makecount(word) 与原guess 里面 char相同数量的 单词找出来, 然后再从这个set 里面再找一个字出来, 再makecount, 在一步步进行loop 一直到只剩下一个 单词为止
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 19:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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