想问怎么解答面试题follow up - input特别大怎么改进？

感觉这是一类很经典的follow up，大概看过如下几类：
1）如果数组很大怎么改进？
2）如果matrix非常大几乎没有边界怎么改进？
3）如果input是一个stream怎么改进？

楼主其实CS基础知识还十分薄弱，想问下这类问题一般是在考察什么知识点，又有哪些常用solution？

举几个简单的例子，比如说第一个，input特别大。为了简化，我们直接把问题简化，比如让你求一个array的最大值，但是这个array非常大。
比如我们memory放不下，我们一次可以处理一部分数据，把最大值存下来，最后把所有存下来的最大值再比较一次。这个就比较容易并行化，做成map-reduce那种。
第三个的话，就是需要一个online的算法。比如kth smallest 那种问题，基本上意思就是你不能把之前所有的都存下来（可以存一些auxiliary的数据结构），只能来一个处理一个。
如果是kth smallest的话，用maxheap就是一种online algorithm，但是quick select就不是，因为quick select需要所有的数据都存下来。

一般分两种情况：
- 数据虽然大但是内存存得下：一般是优化算法不要超时
- 数据大到内存存不下：换外部算法(https://en.wikipedia.org/wiki/External_memory_algorithm)，按(3)所说的做流式处理也可以

比如数组求和:
arr=file.read_all();
for num in arr: sum += num;
要变成
while not file.eof(): sum += file.read_one()

至于(2)可以考虑用稀疏矩阵。但是一般都要具体问题具体分析。

视面试上下文可以考虑讨论内存访问pattern/缓存命中/分支预测等architecture细节。

个人觉得应该是memory limit的问题。就是memory一般比disk的存量要少很多，所以把所有data放进memory里处理是很不现实的。

如果是的话，答案应该是看看你能不能改进你的algo，做到只读一部分process一部分，再读再process这样。

a610062656 发表于 2021-2-14 18:53
个人觉得应该是memory limit的问题。就是memory一般比disk的存量要少很多，所以把所有data放进memory里处理 ...

请问这个“只读一部分process一部分，再读再process这样”是怎么体现的呢？需要在原来基础上加相关的function吗？

iSomnambulate 发表于 2021-2-15 02:25
请问这个“只读一部分process一部分，再读再process这样”是怎么体现的呢？需要在原来基础上加相关的func ...

你就想每次只能用1/10的input，你怎么改进你的algo来得出最终答案

1）如果数组很大怎么改进？
这条之前几楼说的都有道理，但是也有一种很罕见的情况是：面试官其实在告诉你你的解法并不是最优解，如果数组很大将会超时。
他让你写了之前的解法大概率是因为这种解法是非常显而易见的，而最优解要绕过好几个弯才可以想到。所以你之前提出的解法是在面试官的意料之中的。

这一系列的问题你可以搜索下External sorting (外排序)

先得问问面试官是想继续考算法还是考别的吧…
算法又可以分为sequential和parallel
往深里问还可以问到比如MapReduce和基于它的一系列框架；数据存储可以是RDB，key-value，stream，etc...