难倒我的笔试题整理

1. 一本书里有100万个单词，判断其中可能写错的单词有那些，并给出正确的拼写，评估其时间和空间复杂度

答：

要判断一本书中可能写错的单词，可以使用一个已知的正确单词列表进行比对。以下是一种可能的解决方案： （1）创建一个包含正确单词的字典，可以使用一个哈希表或者字典数据结构来存储。这个字典可以包含常见的英文单词，也可以包含特定领域的专业术语等。 （2）遍历书中的每个单词，将其与字典中的单词进行比对。如果书中的单词不在字典中，那么它可能是写错的单词。 （3） 对于可能写错的单词，可以使用拼写检查算法（如Levenshtein距离算法）来找到最接近的正确拼写。这个算法可以计算两个单词之间的编辑距离，即需要进行多少次插入、删除或替换操作才能将一个单词转换为另一个单词。 （4）对于每个可能写错的单词，找到编辑距离最小的正确拼写，并将其作为建议的正确拼写。 （5）评估时间复杂度：遍历书中的每个单词需要O(n)的时间，其中n是书中单词的数量。对于每个可能写错的单词，需要计算其与字典中每个单词的编辑距离，这个操作的时间复杂度为O(m)，其中m是字典中单词的数量。因此，总的时间复杂度为O(n * m)。 （6）评估空间复杂度：需要存储正确单词的字典，其空间复杂度为O(m)。此外，还需要存储书中的每个单词，其空间复杂度为O(n)。因此，总的空间复杂度为O(n + m)。

2. 有一个数据表， 有三个字段A， B， C， 一共有1000万行， 其中字段A中不同的值有100万个， 字段B中不同的值有10万个， 以字段A为行维度， 字段B为列维度， 对字段C做求和计算， 得到一个100万行， 10万列的一个交叉表， 在浏览器端显示这个交叉表时每页显示100行， 10列， 那么浏览器端开始计算这个交叉表， 然后显示第一页的数据以及总页数的时间和空间复杂度是什么样的， 在浏览器端输入页码， 返回对应页码数据的时间和空间复杂度是什么样的

答：

浏览器端计算和显示交叉表的时间和空间复杂度取决于以下几个因素： 1. 计算交叉表的时间复杂度： - 遍历1000万行数据，对每一行进行求和计算，时间复杂度为O(1000万)。 - 对于每个不同的字段A值，需要遍历10万个不同的字段B值，时间复杂度为O(100万 * 10万)。 - 因此，计算交叉表的总时间复杂度为O(1000万 + 100万 * 10万)。 2. 显示第一页数据和总页数的时间复杂度： - 显示第一页数据需要获取100行10列的数据，时间复杂度为O(100 * 10)。 - 计算总页数需要根据总行数和每页显示的行数进行计算，时间复杂度为O(100万 / 100)。 - 因此，显示第一页数据和总页数的总时间复杂度为O(100 * 10 + 100万 / 100)。 3. 显示特定页码数据的时间复杂度： - 根据输入的页码，计算需要跳过的行数和列数，时间复杂度为O(页码 * 每页行数 * 每页列数)。 - 获取特定页码数据需要获取每页行数 * 每页列数的数据，时间复杂度为O(每页行数 * 每页列数)。 - 因此，显示特定页码数据的总时间复杂度为O(页码 * 每页行数 * 每页列数 + 每页行数 * 每页列数)。 4. 空间复杂度： - 存储1000万行数据的空间复杂度为O(1000万)。 - 存储交叉表数据的空间复杂度为O(100万 * 10万)。 - 存储每页数据的空间复杂度为O(每页行数 * 每页列数)。 - 因此，总的空间复杂度为O(1000万 + 100万 * 10万 + 每页行数 * 每页列数)。 需要注意的是，以上复杂度分析是基于一般情况下的估计，实际的复杂度可能会受到具体实现细节和硬件性能的影响。