狗也上树了# pets - 心有所宠
h*u
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?
设计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?
