客路校招笔试记录

《面试题目》

1. 选择题：数据结构、数据库、操作系统等，英文题干。
2. 编程题：给定长度为 n 的字符串和长度 m，从第 1 个字符开始数 m 个字符翻转，再从第 2 个字符开始数 m 个翻转，依次直到结尾，求翻转后的字符串。
3. 编程题：大小为 n 的数组，给定 m 天和 k；每天每个元素加 k，然后找到最大值并折半（乘以 0.5），问 m 天后数组元素的和。

《参考解析》

字符串分块翻转：题意是每个起点 i 取长度为 m 的子串（越界截断）翻转，暴力做法是 O(nm)；如果 m 固定且操作有重叠，可以用差分/懒惰翻转或双端队列优化。笔试先保证正确性，注意边界：最后一组不足 m 个字符时只翻转子串，不要越界。

每日加 k 再折半最大值：暴力每天遍历找最大值是 O(nm)，n、m 大时会超时。可以用大根堆维护当前最大值，但“所有元素加 k”是全局偏移，堆里存原始值、比较时加偏移即可；最大值折半后更新堆。求和可以维护总和：每天先加 n*k，再减去 max/2。注意浮点精度，若题目要求整数，确认折半是向下取整还是保留小数。