0

我最近被问到一个理论上的 C 问题，我想知道解决它的最佳方法是什么：

如果我有一份包含 10 个单词的文档，那么确定是否有重复单词以及是否有重复单词的最佳方法是什么？我将如何跟踪有多少单词？

任何有关如何处理此问题的见解都会很棒。

4

5 回答 5

5

关键字是“十”：这意味着使用两个嵌套循环检查其前面的每个单词的最简单方法就可以了。例如，如果这个数字是 10000000，则需要使用哈希表、堆或排序数组的方法。然而，只有十个单词，您不需要构建任何复杂的东西 - 只需要基本的 C 字符串读取/比较知识。

于 2012-06-07T21:02:34.590 回答
2

像这样的理论面试问题总是很少处理（比如 10 个字）。然而，这个数字没有任何意义。它的存在是为了将那些真正能够以一般形式思考问题的候选人与那些简单地重复他们在互联网上找到的固定面试问题的固定答案的候选人区分开来。

最好的软件公司只会偏爱可扩展的解决方案。因此，如果你的答案很简单，你将在面试中获得最高分，但也可以扩展到任何规模的问题（或者，在这种情况下，文档）。因此，排序，循环内循环，O(n^2) 复杂度，都忘记了。如果你在面试时向一家领先的软件公司提出任何类似的解决方案，你就会失败。

您的特定问题是检查您是否了解Hash Tables。这个问题最有效的解决方案可以写成伪代码如下： 

1. Initialise a new hash table.
   For each word in the document...
2.     Generate a hash key for the word.
3.     Lookup the word in the hash table using the key. If it is found,
4.         Increment the count for the word.
       Otherwise,
5.         Store the new word in table and set its count to one.


上述解决方案最重要的好处是只需要对文档进行一次扫描。没有将单词读入内存然后进行处理（两次扫描），没有循环中的循环（多次扫描），没有排序（甚至更多遍）。恰好在文档通过一次之后，如果您读出哈希表中的键，则每个单词的计数会告诉您每个单词在文档中出现的确切次数。任何计数大于 1 的单词都是重复的。

该解决方案的秘诀在于它使用了哈希表。散列密钥的生成（步骤 2）、密钥查找（步骤 3）和密钥存储（步骤 5）可以实现为接近恒定时间的操作。这意味着这些步骤所花费的时间几乎不会随着输入集的大小（即字数）的增长而改变。这意味着无论是文档中的第 10 个单词，还是第 1000 万个单词，将该单词插入哈希表（或查找它）将花费大致相同的非常短的时间。在这种情况下，我们在第 5 步中额外记录了每个单词的频率。众所周知，增加一个值是一种非常有效的固定时间操作。

此问题的任何解决方案都必须至少扫描文档中的所有单词一次。由于我们的解决方案只处理每个单词一次，并且所有单词的处理时间都差不多，因此我们说我们的解决方案性能最佳并线性扩展，产生O(n) 性能（简单地说，处理 1,000,000 个单词大约需要 1000比处理 1000 个单词要长几倍）。总而言之，该问题的可扩展且有效的解决方案

于 2012-06-13T09:41:42.800 回答
0
  1. 使用 scanf 将单词读入字符串数组
  2. 对于每个单词，使用 strncmp 与列表后面的其他单词进行比较

有速度和空间优化，但我（通常）为了简单而优化。

于 2012-06-07T21:02:18.083 回答
0

对于更大的实现，您可以使用哈希表并检查冲突

对于较小的 n（例如 n = 10），我们可以遍历元素并将它们添加到数组中。对于每个元素，检查数组以查看它是否重复。

检查数组在 O(n) 中，遍历 10 个元素中的每一个在 O(n) 中。由于我们可以简单地使用嵌套循环来实现这一点，因此我们可以在 O(n^2) 时间复杂度内执行此操作。这已经足够了，因为在如此小的 n 值下，性能影响可以忽略不计。

于 2012-06-07T23:54:28.690 回答
0

由于单个单词的长度可能“很小”，我将从基数排序http://en.wikipedia.org/wiki/Radix_sort开始，这需要 O(nk) 时间，其中 k 是最大单词长度。在这种情况下，您肯定希望首先根据长度（最多 n 个）将单词分类到单独的列表中。

因为您只对重复项感兴趣，您可以丢弃长度为 1 的任何列表（在此步骤或任何后续步骤中）。

对于每个列表，比较每个列表成员的最后一个字符，为每个看到的不同字符创建一个新的单词列表（最多 26 个，假设单词都是 ASCII 字符），截断最后一个字符。同样，抛出长度为 1 的列表并递归地对新列表进行排序。

在最坏的情况下（所有单词的长度相同，并且仅在第一个字符上有所不同，假设 LSD 基数排序）您将获得 O(nk) 时间。在最好的情况下（所有单词都有不同的长度）你会得到 O(n) 时间。在实际情况下，您可能会比 O(nk) 时间好得多，因此该解决方案应该可以很好地扩展到更长的单词列表。

于 2012-06-08T15:44:32.007 回答