h***u
发帖数: 9 | 1 上百万的字符串 ， 每个小于 128 char.
设计data structure处村. 要支持 fast prefix search(return all strings with
given prefix)
coding is to implement insert method. input is a stream of strings. it needs
to be fast.
First response was a tire, but interviewer not happy with every insert start
from root of the tire tree, ask if the input can be pre-processed (like
sort), any way to speed it up.
found with the tire, even string stream was sorted, still need a O(k) k is
length of string comparison during track back. so no performance gain.
any ideas? | e**t
发帖数: 39 | 2 hash the prefixes? keep index in the hash table,
then retrieve the strings in the array based on matching index
needs
start
is
【在 h***u 的大作中提到】
: 上百万的字符串 ， 每个小于 128 char.
: 设计data structure处村. 要支持 fast prefix search(return all strings with
: given prefix)
: coding is to implement insert method. input is a stream of strings. it needs
: to be fast.
: First response was a tire, but interviewer not happy with every insert start
: from root of the tire tree, ask if the input can be pre-processed (like
: sort), any way to speed it up.
: found with the tire, even string stream was sorted, still need a O(k) k is
: length of string comparison during track back. so no performance gain.
| s*****n
发帖数: 5488 | 3 if sorted, then it is a kind of tree travesal.
like.
abc
abcd
abd
abdd
a
b
c d
d d
then it is O(number of nodes) complexity.
needs
start
is
【在 h***u 的大作中提到】
: 上百万的字符串 ， 每个小于 128 char.
: 设计data structure处村. 要支持 fast prefix search(return all strings with
: given prefix)
: coding is to implement insert method. input is a stream of strings. it needs
: to be fast.
: First response was a tire, but interviewer not happy with every insert start
: from root of the tire tree, ask if the input can be pre-processed (like
: sort), any way to speed it up.
: found with the tire, even string stream was sorted, still need a O(k) k is
: length of string comparison during track back. so no performance gain.
| h****p
发帖数: 87 | |
|
