题目重点:一行一个整数,文件大于内存时只保存局部最大值。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 训练UTF-8/ASCII整数文本,每非空行一个带符号整数,空行/非法行按合同拒绝或跳过;数值可超过64位。
- 文件静态快照、可seek;压缩流或远程非seek输入不直接适用字节分块。
解题路线
- 顺序版逐行parse并更新max,初值None而非0,空文件返回无值。内存为当前最长行+最大整数位数,不能read全部。
- 并行按字节边界b分段:worker从b seek,若b不是行首先跳到下个换行;只处理行起始offset落在[b,nextB)的整行,允许读到nextB以外完成最后一行。前块负责该跨边界行,后块跳过,恰一次。
- 各worker返回(localMax,lineCount,error)聚合max;非法行不能被简单归为无值。并行被磁盘吞吐/parseCPU限制,workers越多不一定更快;长单行、CRLF、最后无换行和文件变更都应覆盖。
手动走一遍
全负数−9/−2/−7结果−2,初始0错误。块边界切在−12345的23中间,前块读整行,后块跳到下一行;不得把45当另一整数。
规模与取舍
N字节输入至少Ω(N)I/O;Pworker理想CPU O(N/P),聚合O(P),实际受带宽。每worker空间O(最长行+整数位数),不能声称数值任意大仍固定O(1)字节。
易错点与追问
容易失分的边界
- 按换行截块但遗漏最后未换行数字。
- 压缩文件字节位置不是原文本行边界,需要可分割格式或先解压。
继续深挖
- 文件在扫描中增长,是否读固定size/version快照?
- 如何输出最大值所在全部行号并避免结果巨大?
