小红书 Java 实习一面压力面：项目八股不问、全程手撕

《面试题目》

1. 给前序和中序遍历，画出树、写出后序遍历，并回答能否唯一确定一棵二叉树。
2. 给一段代码判断输入输出（给的是 C++ 代码，被问到能不能换成 Java）。
3. 给一段代码判断会不会死锁，是锁竞争还是死锁。
4. 手撕：快速排序的变式。
5. 手撕：LRU 缓存。
6. 手撕：反转链表。

《参考解析》

前中序构造与唯一性：前序遍历的第一个元素是根，在中序里定位这个根就能把序列切成左右两棵子树，递归处理即可重建整棵树，最后按「左—右—根」输出后序。唯一性结论要背准：前序加中序、后序加中序都能唯一确定一棵二叉树，前序加后序不能——只有一个孩子的节点无法区分它是左孩子还是右孩子。如果节点值允许重复，即使给了中序也可能对应多棵树，需要额外约束才能保证唯一。实现上先用哈希表存中序的下标映射，把每层的查找从线性降到 O(1)，整体 O(n)；递归深度接近节点数时要改成显式栈，避免栈溢出。

代码输出判断题的解法：这类题考的是语言细节而非算法：值传递与引用传递、i++ 与 ++i 的求值顺序、短路求值、隐式类型转换与整数溢出、字符串常量的存储位置、临时对象的生命周期与析构时机。稳妥做法是画一张状态表逐行推演，把每一步变量的值写下来，而不是凭感觉念代码。遇到题意含糊的题先问清楚：按哪个语言标准、有没有未定义行为、输出格式要求是什么——问清楚是加分项，硬猜才丢分。

死锁与锁竞争的区别：锁竞争只是暂时拿不到锁、在等待队列里排队，锁一释放就能继续；死锁是多个线程互相持有对方需要的锁、形成循环等待，谁都无法推进。死锁的产生要同时满足四个条件：互斥、持有并等待、不可剥夺、循环等待，破坏任意一个就能避免。判断一段代码要看加锁顺序有没有交叉、有没有在持锁期间再去申请另一把锁。排查靠线程 dump，看每个线程持有哪些锁、在等哪把锁；预防手段是全局统一加锁顺序、用带超时的 tryLock、缩小临界区、避免锁嵌套。

LRU 的实现要点：核心结构是哈希表加双向链表——哈希表负责 O(1) 定位节点，链表维护访问顺序：get 命中后把节点移到头部，put 时若容量已满就淘汰尾节点。手写易错点包括：用头尾哨兵节点省掉大量空判断、先摘链再插头的顺序别写反、容量为 0 或 1 的边界、更新已存在的 key 时不要重复插入导致链表断裂。Java 里也能直接用 LinkedHashMap 的 accessOrder 配合 removeEldestEntry 实现，但要能说清它底层仍然是哈希表加双向链表，否则会被追问穿。

反转链表：迭代写法用三个指针 pre/cur/next，逐个把 cur.next 指回 pre，注意先把 next 存下来再改指向，循环结束时 pre 就是新的头节点。递归写法递归到末尾返回新头，回溯时让后继指回自己、自己指向空，代价是 O(n) 的栈空间。边界要照顾空链表与单节点，写完自己用两个节点和三个节点各跑一遍。

快速排序的常见变式：手撕从快排变式起手，常见考法有：手写快排并说明分区方案（Lomuto、Hoare、三路划分处理大量重复元素）、用快排思想求第 k 大或 TopK（快速选择，平均 O(n)，必须随机化 pivot 否则有序输入退化成 O(n²)）、非递归实现、小区间改用插入排序的优化。回答时顺带讲清快排不稳定、最坏情况怎么来的，比只背代码模板更能体现理解。

压力面怎么应对：面试官语速快、不给反馈、反问也不回答，本身也是一种考察，看的是情绪稳定与节奏控制。可用的动作：拿不到反馈就先按自己的假设把思路讲清楚，主动说明大概需要多久；一道题卡住超过几分钟就换一道能写对的题，别在一棵树上耗完整个面试；反问被挡回来就换一个更具体的问题问，或者干脆问流程与后续安排。事后复盘要把「项目和八股一个没问」当信息用——投递前看清 JD 与团队的实际考察方式，别把准备全押在背诵上。