上海C+AI 微软暑期实习2022 一面热经
2022年2月21号
上午10点-10点45
1、自我介绍
2、介绍实习做的事
3、系统设计题
有一台机器，上面存有许多大文件和小文件，需要拷贝这些文件到另一个机器上，这些机器都已经能被RestAPI等服务访问，包含Get/Set等方法，现在设计一个系统，这个系统可以在一台或者多台机器上运行，实现高效的复制功能，你的架构应该是怎么样的。
4、算法题
有个大文件，文件很大以至于不能全部读进内存，它的内容是空格隔开的字符串，我们把隔开的字符串称为单词，我们需要统计这个文件中出现次数前100的单词。
一些思路：
系统架构：应该是master-worker架构，master负责调度哪些worker来处理哪些文件复制，每个文件复制看成一个job，master维护一个job队列，检查worker可用情况，循环拿job给可用worker使用，worker处理完job，成功就返回成功ACK就行，失败就需要重新把job放回给队列，由master重新分配，如果出现单worker处理大文件负载压力过大，而其他worker处理小文件很快，而负载很小，应该设置worker处理的负载上限，当有些worker负载过大，后续大文件应该进行分片，不再给负载过大的worker分配任务。
算法题：
-
top词频可以使用分治+ Trie树/hash +小顶堆：
- 先将数据集按照Hash方法分解成多个小数据集
- 然后使用Trie树或者Hash统计每个小数据集中的query词频
- 之后用小顶堆求出每个数据集中出频率最高的前K个数
- 最后在所有top K中求出最终的top K。
- 时间复杂度：建堆时间复杂度是O(K),算法的时间复杂度为O(NlogK)。
- topK问题reference
