一亩三分地论坛

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

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

狗狗昂赛特跪经

[复制链接] |试试Instant~ |关注本帖
sf3 发表于 2016-11-20 02:42:18 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 校园招聘会 - Onsite |Failfresh grad应届毕业生

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

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

x
11月初去的狗狗昂塞特, 跪了,发给大家供参考:. 1point3acres.com/bbs
4轮:
1. 美国小哥。number of island 2. 这题刷过时间太久了我给忘了。。用union find做了,中间有个地方出了个bug, 我也是醉了。。。
2. 亚裔小哥。输入一个file: [A, B, 0.6], [C, D, 2].... 代表A = B* 0.6, C= D* 2.....-google 1point3acres
第二个file: [A, C,  "_"], [D, F, “_”], 要求根据第一个File, 把第二个file第三列的空格填上。规则和第一个file的一样。
DFS BFS都行。用BFS, 小哥要求不能记住当前所有路径, 要用BFS with path reconstruction。有点蒙蔽, 写出了一坨翔。
-google 1point3acres
3. 美国大叔。大叔一上来丢给我个c code,让找BUG。 楼主蒙蔽表示不会c, 大叔说没关系,看看吧。。。 看了N久终于发现了一个弱智bug: string qual 只比了开始地址。。。大叔的表情就是: 谢天谢地你终于找到了, 来来我们快来正式抠腚
题目是:有个很大的word list, 里面全是length为 5 的word。 里面有个target要我们猜。来写个猜的策略。 每次猜过以后会返回一个feedback表示在哪个位置的哪个Char猜对了。
假如word list 里是: trips, trick, treat; 目标是:trick, 你猜的是treat, 结果会返回 tr_ _ t。 .鐣欏璁哄潧-涓浜-涓夊垎鍦
我提了几个策略都被否定了, 没说到大叔心坎里。 最后草草写了一点code,也是一坨翔。。。
. 1point3acres.com/bbs
4. 印度小哥和一个shadow。flip game 2稍微变形. 我又醉了,都是刷过的忘了的题。写了个暴力Recursion, 让优化。 我提出可以减小连续+号的长度, 或者消去成对的减号。说了一下可以memorization。小哥让问问题。

中午吃饭,是个超级漂亮的国人姐姐。第二轮完了以后姐姐叫我说: 吃饭去吧~~~

自己运气确实很不错, 遇到两道简单原题。而且总的来说这四个题都不难, 但是自己没怎么准备自作孽。 大家一定好好好好好刷题····唉。真是辜负狗狗大哥和国人姐姐对我的一片好心了

最后, 为自己求个offer

评分

1

查看全部评分

本帖被以下淘专辑推荐:

 楼主| sf3 发表于 2016-11-20 05:03:20 | 显示全部楼层
catinclay 发表于 2016-11-20 03:56
小哥要求不能记住当前所有路径, 要用BFS with path reconstruction。
請問一下這個是什麼意思呀?
. from: 1point3acres.com/bbs
小哥要求我先找到最短路径再根据path求路径的总weight. 所以就是再bfs的时候存下来到每个node的previous node(最短的),然后找到target以后reconstruct path。
回复 支持 1 反对 0

使用道具 举报

catinclay 发表于 2016-11-20 03:56:38 | 显示全部楼层
小哥要求不能记住当前所有路径, 要用BFS with path reconstruction。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
請問一下這個是什麼意思呀?
回复 支持 反对

使用道具 举报

littlebearull 发表于 2016-11-20 04:43:17 | 显示全部楼层
楼主,请问第二轮的path with reconstruction 是什么意思呀?比如A/B = 0.6, B/C= 0.5, C/D = 0.1, A/D,在查看C的时候,会把当前得到的A/C 加入到hashmap中,那再遇到C/D的时候,就直接能得到A/D了,不太明白楼主说的path reconstruction是什么意思。还有第三题,目标是tricky,猜的是treat,返回的为什么是tr__t呢?不应该是tr___吗?谢谢回复哦
回复 支持 反对

使用道具 举报

 楼主| sf3 发表于 2016-11-20 05:06:04 | 显示全部楼层
littlebearull 发表于 2016-11-20 04:43
楼主,请问第二轮的path with reconstruction 是什么意思呀?比如A/B = 0.6, B/C= 0.5, C/D = 0.1, A/D,在 ...
. 1point 3acres 璁哄潧
就是再bfs找到路径以后在往回reconstruction path. 不能用queue记住所有从start到当前层的路径, 太费空间。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. Waral 鍗氬鏈夋洿澶氭枃绔,
第三题,因为treat中 t出现了两次, 只要是在target里有这个char, 结果中就会出现, 不管在target里的什么位置。
回复 支持 反对

使用道具 举报

xuqicx23 发表于 2016-11-20 06:01:14 | 显示全部楼层
求问一下楼主第二道题目是不是跟graph比较类似啊?就是第三个值得大小表示weight。感觉有点像leetcode里面的那个division evaluation。还有就是求问一下第三题楼主是怎么个想法跟思路呢?谢谢啦
回复 支持 反对

使用道具 举报

 楼主| sf3 发表于 2016-11-20 09:56:27 | 显示全部楼层
xuqicx23 发表于 2016-11-20 06:01. visit 1point3acres.com for more.
求问一下楼主第二道题目是不是跟graph比较类似啊?就是第三个值得大小表示weight。感觉有点像leetcode里面 ...

对这就是个directed graph. 因为assume不会出现invalid的情况,也就是不管什么路径,找到的accumulative weights 一定是一样的,所以dfs bfs都可以。. more info on 1point3acres.com
. Waral 鍗氬鏈夋洿澶氭枃绔,
第三题我说先看一遍List, 统计一下每个char的出现次数,然后根据这个来找一个含有最多char出现次数的word, 也就是争取在每次guess的时候eliminate 最多的错误Word。然而说了半天感觉他并不赞同。大家要是有idea给我说下哈, 我也想学学应该咋做
回复 支持 反对

使用道具 举报

xuqicx23 发表于 2016-11-20 10:21:38 | 显示全部楼层
sf3 发表于 2016-11-20 09:56
对这就是个directed graph. 因为assume不会出现invalid的情况,也就是不管什么路径,找到的accumulative  ...

我的意见是如果我上次guess的词跟答案对的某几个char那么我在我当前的word里面每一个跟上次猜的词比较。如果对的char跟答案与猜词对的char不一样的一定不会是答案就从words里面删除。一直到最后只剩下一个词可以猜。。。
回复 支持 反对

使用道具 举报

xiangminxufsu 发表于 2016-11-20 17:43:23 | 显示全部楼层
sf3 发表于 2016-11-20 05:06
就是再bfs找到路径以后在往回reconstruction path. 不能用queue记住所有从start到当前层的路径, 太费空 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
那如果我的target 是 "ttttt",岂不是trick, treat, trip,或者ttttt都返回 "ttttt“。这样就找不到target了。
回复 支持 反对

使用道具 举报

 楼主| sf3 发表于 2016-11-20 23:19:13 | 显示全部楼层
xiangminxufsu 发表于 2016-11-20 17:43
那如果我的target 是 "ttttt",岂不是trick, treat, trip,或者ttttt都返回 "ttttt“。这样就找不到target ...

没错,如果你的词是ttttt就是会这样。但是需要注意的是你知道Word list, 所以你也不会猜不在list里的词。
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-21 01:58:38 | 显示全部楼层
應該是找出現次數最接近n/2的字...但多數情況會跟出現次數最多的字一樣, 想不到什麼反例
回复 支持 反对

使用道具 举报

stellari 发表于 2016-11-21 05:15:15 | 显示全部楼层
感谢楼主分享,关于第3题,如果input是这个样子的: target=ababa, list=[abbab, abaab, aabbb, ababa]. 那么因为feedback不关心字母的位置,所以对于任意的猜测词list [ i ],feedback都是list[ i ]本身,这样的话,不就无法解了么?还是说1.假设不会出现这种情况,2. 出现这种情况返回null?
回复 支持 反对

使用道具 举报

stellari 发表于 2016-11-21 05:34:40 | 显示全部楼层
sf3 发表于 2016-11-20 05:06
就是再bfs找到路径以后在往回reconstruction path. 不能用queue记住所有从start到当前层的路径, 太费空 ...

还有就是,如果feedback完全不考虑顺序的话,那我岂不是可以总是这样猜: {abcde, fghij, klmno, pqrst, uvwxy, zabcd}。比如得到feedback序列{a____e, _____, _____, __r_t, _a___}, 这样我就知道target中肯定有且仅有t, r, e, a四个字母。然后再扫一遍原word list,找到符合条件的词即可。无论word list多长,只需要最多猜测6次,在原word list中并未出现字母表中所有字母的情况下,猜测次数可以进一步减少。
回复 支持 反对

使用道具 举报

 楼主| sf3 发表于 2016-11-21 06:42:45 | 显示全部楼层
stellari 发表于 2016-11-21 05:34
还有就是,如果feedback完全不考虑顺序的话,那我岂不是可以总是这样猜: {abcde, fghij, klmno, pqrst, u ...

对,我感觉这个题的目的是根据word list的char出现的情况来决定每一次猜测的最优策略。. more info on 1point3acres.com
还有你说的哪个例子,我也蒙蔽了。确实是。我当时都没反应过来这个情况。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 06:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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