狗狗合同工寒out

狗狗residency program～一轮hanout面经

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

求大米，求过

sw304 发表于 2019-1-21 02:45
所以应该怎么样取第一次猜的词呀。。

我不知道是不是正确答案，我说统计所有letter出现的概率，然后加总求出每个单词的概率，然后取最高的概率，面试官表示可以，然后就让写了

z130640637 发表于 2019-1-22 10:39
我们第一次猜词的目标是match尽量多字母，如何找到这个词，如果没有从list选词的限制的话，出现频率最高 ...

我觉得这样做没什么问题
我一开始的思路其实和你这个不太一样，首先选定一个单词，然后生成这个单词和其它所有词的比较结果，对所有可能的结果计数，比如[p,0]出现了1次，而[a,0]出现了2次，[z,0]出现了5次(这里纯粹举例子，和楼上的例子对不起来)
那么我拿这个单词去猜最差的结果是什么呢，是[z,0]，也就是说可能的secret word有5个，最好的是[p,0]，secret word直接确定了
剩下就是策略问题了，我认为需要保证每次猜词的最差结果不要太差，所以要选计数最大值最小的那个，也就是minimize the maximum
当然我觉得我这个思路复杂度比你的高，实际可能还是你的好一些

bdhmwzfa 发表于 2019-1-22 10:45
我觉得这样做没什么问题
我一开始的思路其实和你这个不太一样，首先选定一个单词，然后生成这个单词和其 ...

所以我也很心慌，面试官出完题，我说这个方法，他也提出了一些疑问，比如说一个单词里面有相同的字母算几次，如果相同的概率的单词选哪个，聊了一会，就让写代码了，而且第二问也没有让写代码就讨论了，通过第一次的结果，怎么narrow down第二次猜词的范围，求过求过，就怕烙印笑面虎，背后来一刀

所以应该怎么样取第一次猜的词呀。。

apple 返回(p, 0)的意思是 apple和photo有一个字母相同，p在photo的position 0是吗

penpineapple 发表于 2019-1-21 03:06
apple 返回(p, 0)的意思是 apple和photo有一个字母相同，p在photo的position 0是吗

是的 zszszs

『photo，apple，pears，pairs』
长度是5，
a 可能出现在3个不同的位置上， p 可能出现在 3个不同的位置上， e 可能出现在 1个不同的位置上， s可能出现在一个不同的位置上

统计完之后对每个词记一下对应char次数的和（同一个只记一次），选和最大的。

求批。。

penpineapple 发表于 2019-1-21 06:12
『photo，apple，pears，pairs』
长度是5，
a 可能出现在3个不同的位置上， p 可能出现在 3个不同的位置 ...

如果list很长那5个位置上都出现的概率其实挺大的，这个方法似乎就不适用了

z130640637 发表于 2019-1-21 03:33
我不知道是不是正确答案，我说统计所有letter出现的概率，然后加总求出每个单词的概率，然后取最高的概率 ...

你说的“加总“是指相乘吗？比如list是【aa, ab】, a = 3/4, b = 1/4, 那么aa = 9/16， ab = 3/16 ?

坨坨 发表于 2019-1-22 09:54
你说的“加总“是指相乘吗？比如list是【aa, ab】, a = 3/4, b = 1/4, 那么aa = 9/16， ab = 3/16 ?

abbcd，和abcde哪个优先度高，如果用乘法的话就不对了

z130640637 发表于 2019-1-21 03:33
我不知道是不是正确答案，我说统计所有letter出现的概率，然后加总求出每个单词的概率，然后取最高的概率 ...

我其实不太明白，楼主这么解的根据是什么？
或者说为什么这个算出来的概率最高的词，是最佳的选择？

补充内容 (2019-1-22 10:31):
我大概明白了，这个概率和其实类似一种期望，是当前单词和选定的secret word相同字符数的期望，这个期望越大越好。但是严谨的证明可能还需要费点力气

补充内容 (2019-1-22 10:31):
我大概明白了，这个概率和其实类似一种期望，是当前单词和选定的secret word相同字符数的期望，这个期望越大越好。但是严谨的证明可能还需要费点力气

补充内容 (2019-1-22 10:31):
我大概明白了，这个概率和其实类似一种期望，是当前单词和选定的secret word相同字符数的期望，这个期望越大越好。但是严谨的证明可能还需要费点力气

补充内容 (2019-1-22 10:31):
我大概明白了，这个概率和其实类似一种期望，是当前单词和选定的secret word相同字符数的期望，这个期望越大越好。但是严谨的证明可能还需要费点力气

补充内容 (2019-1-22 10:32):
sorry，网络错误刷了这么多。。。