狗家新鲜面经

刚刚结束的狗家12面。回馈地里。
一面： 印度小姐姐。
只做了一道题： 给一个字典和一个关键字，要求根据这个关键字把字典里可能的单词全部print出来。 类似于输入法里输入几个字母然后弹出推荐的可能你需要的单词。
比如 word: "ca",  dict -

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

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

alse.
       E<1,3>,E<2,3>,E<7,1> -> return true.

第二题就是建一个 hashmap map 其中key是time value是count  然后遍历  map[time]++, map[time+ duration]-- 最后看map里的count是否有大于3的就行了

dimi 发表于 2018-1-17 09:10
不超过三个 意思是可以有两个同时存在

哦哦，那这个E<1,3>, E<2, 3>, E<3,3> -> return false例子中，E<1,3>占用1 2 3, E<2, 3>占用2 3 4，这两个有重叠，只能二选1加上第三个，也不超过3个event，为什么返回false呢，谢谢

ton9eric1 发表于 2018-1-18 02:30
time就是这个event的开始时间，第一个E 1-4, 第二个E 2-5, 第三个E 7-8, 开始的时候前面2个已经结束了。 ...

第一个例子就是 E 1-4, E 2-5, E 3-6, 第三个E开始的时候前面两个还没有结束。所以return false。

请问楼主，第一题用string.indexof做吗，会不会出现word = "le" 字典中有"apple"也输出的情况呢

wjw779 发表于 2018-1-17 06:05
请问楼主，第一题用string.indexof做吗，会不会出现word = "le" 字典中有"apple"也输出的情况呢

我是建了一个trie tree。从关键词指定的node往下面找符合的。

ton9eric1 发表于 2018-1-17 07:48
我是建了一个trie tree。从关键词指定的node往下面找符合的。

哦哦，请问楼主这里每个TrieNode除了boolean和children[]，还要存prefix吗，不然怎么找到返回呢

wjw779 发表于 2018-1-17 07:56
哦哦，请问楼主这里每个TrieNode除了boolean和children[]，还要存prefix吗，不然怎么找到返回呢

记录一下每次走过的node存的char。

ton9eric1 发表于 2018-1-17 08:29
记录一下每次走过的node存的char。

谢谢楼主，请问第二题      E<1,3>,E<2,3>,E<7,1> 这个例子为什么是true呢，E<1,3>,E<2,3>有交叉吧

wjw779 发表于 2018-1-17 08:52
谢谢楼主，请问第二题      E,E,E 这个例子为什么是true呢，E,E有交叉吧

不超过三个 意思是可以有两个同时存在

wjw779 发表于 2018-1-17 10:09
哦哦，那这个E, E, E -> return false例子中，E占用1 2 3, E占用2 3 4，这两个有重叠，只能二选1加上第三 ...

楼主是写的返回true

补充内容 (2018-1-17 10:59):
可能 3 重复了吧？