SWE · Phone Coding

Apple C Airplane 座位预订:结构体、所有权与可移动规则

逐一拆解 create/print/free/reserveSeat 可见接口,说明内存布局、座位解析与预订原子性;附件缺失的座位布局留待核。

题目重点:逐一拆解 create/print/free/reserveSeat 可见接口,说明内存布局、座位解析与预订原子性;附件缺失的座位布局留待核。

题意与假设

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

  • 可见题面不能确定 seats 是每行座位数还是总数,isle1/isle2 是过道前的列号还是字符位置,以及 canMove 选哪个替代座位。正文只设计可签约实现,不冒称附件的布局。
  • 若训练实现:用 rows×seats 个占用位,行号 1 起、座位字母 A 起;过道位置单独用于 print,不能占座位编号;canMove=true 时按同排距请求座最近、再按列号顺序选空位。这些均须面试官确认。

解题路线

  1. 先固定结构体不变量:rows、seats 非负且乘积/分配字节数不溢出;创建分配结构体和占用位数组,失败逐项释放并返回 NULL。
  2. 解析四字节 seat 前最多三字符且必须 NUL 结尾,识别十进制行号与末尾字母;检查行/列边界,拒绝非法输入或已占位;不能用无界 strlen 读出缓冲。
  3. reserveSeat 成功时只在选定位置写占用状态并返回 0;canMove=false 已占位就失败。可移动时必须先确认距离/同排/跨排规则,再实现确定性的候选比较,不能擅自选第一个全机空位。
  4. printAirplane 只读结构体,依据已核实的过道语义插入显示间隔;freeAirplane 释放内部数组再释放结构体,允许 NULL,不能重复释放同一对象。若多线程调用,检查并占用需同一锁保护。

手动走一遍

按明示训练规则,4B 空位时 reserve(4B,0) 写占用并返回 0;再次 reserve(4B,0) 返回 −1。若 canMove=1,则查同排最近空位;同距怎样平局取舍必须明确。若输入 `123A` 超四字节缓冲,不能在没有额外长度的签名下安全接收。

规模与取舍

占用矩阵空间 O(rows×seats),指定座位解析/检查 O(1)(缓冲最长 4 字节);如可移动要同排扫空位则 O(seats),跨全机搜则 O(rows×seats)。打印 O(rows×seats)。

易错点与追问

容易失分的边界

  • 把附件中不可见的过道/座位映射编成唯一原题。
  • 用 `sscanf` 或 `strlen` 读取无 NUL 的四字节 seat,越界读。
  • rows×seats 或 malloc 大小乘法溢出。
  • 先标占用再判断可移动候选导致失败时状态变化。
  • 把 free 后的指针再次访问或并发预约同位不加同步。

继续深挖

  • isle1/isle2 的单位是什么?
  • 可移动是否只能同排,同距如何选?
  • 如果 seat buffer 正好四字节但无 NUL,接口如何改?
  • 多线程同时抢同位,哪一步是线性化点?
✓已复制微信号!