6

我的大学即将结束，所以我已经开始准备面试以获得工作，而我在准备面试时遇到了这个面试问题

  1. 您有一组 10000 个 ascii 字符串（从文件加载）
  2. 从标准输入输入一个字符串。
  3. 编写一个伪代码，返回（到标准输出）（1）中的字符串子集，其中包含与（2）中的输入相同的不同字符（无论顺序如何）。优化时间。
  4. 假设需要重复调​​用此函数。初始化字符串数组一次并存储在内存中是可以的。请避免需要遍历所有 10000 个字符串的解决方案。

谁能给我一个通用的伪代码/算法之类的东西如何解决这个问题？我正在挠头思考解决方案。我最熟悉Java。

4

3 回答 3

6

这是一个 O(1) 算法！

初始化：

  • 对于每个字符串，对字符进行排序，删除重复项 - 例如“trees”变为“erst”
  • 使用排序的字符将排序的单词加载到trie树中，将原始单词的引用添加到存储在遍历的每个节点的单词列表中

搜索：

  • 对输入字符串进行排序，与源字符串的初始化相同
  • 使用字符跟随源字符串 trie，在结束节点处，返回那里引用的所有单词
于 2012-11-16T22:48:36.610 回答
0

他们说优化时间，所以我想我们可以随意滥用空间。

在这种情况下，您可以对 10000 个字符串进行初始传递，并构建从 10000 中存在的每个唯一字符到它们的索引（而不是一组它们的索引）的映射。这样你就可以问映射问题，哪些集合包含字符'x'？调用这个映射 M> ( order: O(nm) 当 n 是字符串的数量并且 m 是它们的最大长度)

为了再次及时优化，您可以将 stdin 输入字符串减少为唯一字符，并将它们放入队列 Q 中。（顺序 O(p)，p 是输入字符串的长度）

开始一个新的不相交集，比如说 S。然后让 S = Q.extractNextItem。

现在您可以遍历其余的唯一字符并找到包含所有这些字符的集合。

While (Q 不为空) (循环 O(p)) {

S = S intersect Q.extractNextItem （接近 O(1) 取决于您对不相交集的实现）

}

瞧，返回 S。

总时间：O(mn + p + p*1) = O(mn + p)

（这里还是凌晨，希望时间分析是对的）

于 2012-11-16T22:54:43.757 回答
0

正如波西米亚人所说，特里树绝对是要走的路！

这听起来像是在电话上查找地址簿的方式。开始输入数字，然后根据数字表示以及该数字将代表的三个（或者实际上更多，如果使用国际字符）字母中的任何一个来过滤地址簿。

于 2012-11-16T23:09:09.467 回答