骨骼 店面

上上个礼拜的股哥 店面

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

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

iiimisery 发表于 2019/05/16 17:14:29


请问能讲讲用trie该怎么做吗？没太想明白

Word trie明白吗？区别就是每个node有个hashtable存str 结尾node还要存tuple id
先把所有词存成trie 第一步Omn复杂度
然后从每个tuple的每个词开始查字典 做为起点

比如 I like coding要查三个

I like coding
Like coding
Coding
综合Omnn复杂度

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

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

遍历全部的input，建立一个hashtable, {string:set(names)}

比如
[
("A", [ "abc", "bc", "de"]),
("B", [ "abc", "de"]),
("C", [ "bc"]),
]

=> {
"abc" : (A, B)
"de" : (A, B)
"bc' : (A, C)
}

然后再遍历input, 求每个string对应名字的交集，
如果是(B, A, C), 就是结果，还要一个de-dup + combination

TC: O(n),
SC: O(n),
n is # of word

这题有什么好方法吗？ rolling hash找subarray？

这题怎么做啊 暴力解生成 n^2 个pair 然后从大的array里面找有没有小的array? 感觉复杂度蛮高的 要用类似kmp或是robin karp吗.

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

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

这个可以用tire 吧。 从第一个开始生成前缀树，然后如果后面每个词跟这个树重叠那么就把这两个树的代表字母存起来。

麦田HYMK 发表于 2019-5-12 17:21
这个可以用tire 吧。 从第一个开始生成前缀树，然后如果后面每个词跟这个树重叠那么就把这两个树的代表字母 ...

这个是怎么做的啊？没个节点存的都是什么啊？

从实际角度讲 感觉确实是word trie
全存进去之后 就挨个loop每个tuple里的每个词就好了
复杂的Omn2
m tuple数目
n 平均长度

pandami 发表于 2019/05/15 03:30:26
从实际角度讲 感觉确实是word trie
全存进去之后 就挨个loop每个tuple里的每个词就好了
复杂的Omn2
m tuple数目
n 平均长度

请问能讲讲用trie该怎么做吗？没太想明白