c - 所有单词中出现频率最高的 n-gram

Question

我遇到了以下编程面试问题:

挑战 1:N-gram

N-gram 是来自给定单词的 N 个连续字符的序列。对于单词“pilot”，有三个 3-grams:“pil”、“ilo”和“lot”。对于给定的一组单词和一个 n-gram 长度你的任务是

• write a function that finds the n-gram that is the most frequent one among all the words
• print the result to the standard output (stdout)
• if there are multiple n-grams having the same maximum frequency please print the one that is the smallest lexicographically (the first one according to the dictionary sorting order)

请注意，您的函数将接收以下参数:

• text
    ○ which is a string containing words separated by whitespaces
• ngramLength
    ○ which is an integer value giving the length of the n-gram

数据限制

• the length of the text string will not exceed 250,000 characters
• all words are alphanumeric (they contain only English letters a-z, A-Z and numbers 0-9)

效率约束

• your function is expected to print the result in less than 2 seconds

例子输入文本:“aaaab a0a baaab c”

输出aaangram长度:3

解释

对于上面显示的输入，按频率排序的 3-grams 是:

• "aaa" with a frequency of 3
• "aab" with a frequency of 2
• "a0a" with a frequency of 1
• "baa" with a frequency of 1

如果我只有一个小时的时间来解决这个问题，而我选择使用 C 语言来解决它:那么在这段时间内实现一个哈希表来计算 N-gram 的频率是否是个好主意？因为在 C 库中没有哈希表的实现...

如果是，我正在考虑使用带有有序链表的单独链接来实现哈希表。这些实现减少了您解决问题的时间....

这是最快的选择吗？

谢谢!!!

Answer 1

如果实现效率很重要并且您使用的是 C，我会初始化一个指向字符串中 n-gram 开头的指针数组，使用 qsort 根据 n 对指针进行排序-gram 它们是其中的一部分，然后遍历该排序数组并计算出计数。

这应该执行得足够快，并且不需要编写任何花哨的数据结构。