狗家onsite面经

zec 发表于 2018-4-8 01:08
第五题我有一个很骚的做法，依次传入26个字符，这样你知道要你猜的单词由哪几个字母组成，然后遍历一遍字典 ...

关键是猜的单词一定要是字典里的，所以不能依次输入26个字符。。。

idatascience 发表于 2018-4-8 00:27
不太理解楼主这里说的iterate over每个单词W，那这样每个W都跟S算距离，最后不是会调用guess function很 ...

这里你不用调用那个guess的api，因为你是比较W于其它的单词，都是已知的。那个api是因为你不知道secret word。

rhwfyf 发表于 2018-4-8 00:24
这里应该是有多支股票吧？

只有一支股票而已，只是会有不同的timestamp和price。

actionlee 发表于 2018-4-8 02:00
这里你不用调用那个guess的api，因为你是比较W于其它的单词，都是已知的。那个api是因为你不知道secret w ...

不知道我这里是不是没有理解对，你是说选一个W，然后可以调用guess函数一次，算出S和W的距离，假设是3，然后自己可以算W和其他单词的距离（不用调函数），然后取出跟W距离都是3的那组单词，然后再选另一个word跟S比？这样算是类似二分？但是你之后说了一个优化，就是怎么选W（避免跟W距离都是3的那个组里单词太多），这步我没太理解，求指教。

idatascience 发表于 2018-4-8 02:18
不知道我这里是不是没有理解对，你是说选一个W，然后可以调用guess函数一次，算出S和W的距离，假设是3， ...

选W的话，我们对每个单词都做一次基于字典单词的分组，把跟它是0，1，2，3，4的组都求出来，然后把最大的那个组的个数记下来，这里你是不用调用api的。由于每个单词都有一个最大组数，我们在这里选出一个最小的作为我们要选的W。原因就是因为这可以保证最坏情况下，下一步guess的时候的候选个数是最小的。

jpm603 发表于 2018-4-8 03:33
楼主请问当是用2维hash map的话为什么query会很慢呢，hashmap的query不是O（1）吗

因为你的hash表没有顺序的，但是我们要找到那些在某个区间里的元素。所以用map可以很好的找到起点。

lznb, 给你多加点分

actionlee 发表于 2018-4-8 02:58
选W的话，我们对每个单词都做一次基于字典单词的分组，把跟它是0，1，2，3，4的组都求出来，然后把最大的 ...

哇，这个做法很聪明！这样就强制了可以选择一个最优的“最坏”情况的word！赞！

楼主不好意思啊，我等级太低了，每次只能加3升，只好给你两篇帖子分别加分了。厚着脸皮再问一下：可不可以讲一下具体这个balanced binary tree是怎么构建的？针对sparse matrix这道题。