SDS MLE · HM Coding Followup

Apple MLE:Python `s[::-1]` 与双指针反转的时间空间边界

比较不可变字符串切片、新字符串构造和可变数组原地双指针;明确 Unicode 字符与用户可见字素的区别。

题目重点:比较不可变字符串切片、新字符串构造和可变数组原地双指针;明确 Unicode 字符与用户可见字素的区别。

题意与假设

这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。

  • 这里只分析独立的字符串反转操作,不把未知 coding 原题还原成反转字符串。
  • 标准 Python str 不可变;双指针 O(1) 辅助空间只对已有可变字符数组原地交换成立。

解题路线

  1. `s[::-1]` 复制 n 个 code point,时间 O(n)、新字符串空间 O(n),表达简洁;Python 具体内部可能针对紧凑表示优化常数,但不会让一般新结果变 O(1) 空间。
  2. 若输入是 `list[str]` 并允许原地修改,用 i=0、j=n−1 逐对交换,时间 O(n)、额外空间 O(1);若从 str 先做 list(s)、交换、再 join,整体仍 O(n) 额外空间。
  3. 说明“反转字符”语义:切片按 code point 逆序,不保证用户可见的组合字素、emoji 序列或双向文本的显示正确;真实产品需先定义是否按 grapheme cluster 处理。
  4. 在工程中优先选可读且满足数据量约束的实现,性能瓶颈先 profile;面试追问则清楚给出输入可变性、空间核算和 Unicode 边界。

手动走一遍

`s='abc'` 得 `cba`;对可变列表 ['a','b','c'],交换 0/2 后原列表变 ['c','b','a']。若字符串由 `e` 加组合重音构成,按 code point 逆序可能让重音附着对象改变,因此不能用此实现承诺自然语言视觉反转。

规模与取舍

切片 O(n) 时间/O(n) 新结果;已有可变数组双指针 O(n) 时间/O(1) 额外空间;从不可变 str 转成列表再 join 仍 O(n) 辅助空间。

易错点与追问

容易失分的边界

  • 说 `s[::-1]` 原地反转。
  • 把 str→list→join 的临时内存遗漏。
  • 把双指针当未知原 coding 题的标准答案。
  • 把 code point 顺序与用户可见字符顺序等同。

继续深挖

  • 输入是 bytearray、list 或 str,答案有何不同?
  • 如果字符串太大,如何按块处理且保留字符编码边界?
  • 只要求判断回文,是否需要构造反转结果?
  • 如何处理组合字符和 emoji 序列?
✓已复制微信号!