一人分享一道面试手撕题

看前须知  岗位均为测试/测开 包含暑期和秋招 不区分一二面,以公司为独立单元 笔者亲身经历,真实有效  好未来  给一个字符串,包含空格和数字,删除之后判断是否会回文串 全排列  美团  合并数组 字符串相加  快手  最长无重复子串长度  百度  逆序字符串,力扣151  智叟科技  判断是否是对称二叉树  阿里虎鲸文娱  罗马数字转换  招银网络科技  现场出的题，一个简单的模拟，把一个字符串中所有的数字都*2 a12d3 -- > a24d6  CVTE  快排  字节跳动  合并重叠区间  米哈游  版本号比较  网易云  最大连续子数组和   目前记得的 就这些了,后续想起来...

有次面试被问到：如何实现一个通用列表组件。题倒是不难，但从接口设计、状态管理、可拓展性开始，层次立即拉开。真正的手撕题，考的不是写多快，是你脑子里有没有结构。

需求规格 基本功能：LRUCache(int capacity) 初始化缓存容量int get(int key) 如果key存在则返回value，否则返回-1void put(int key, int value) 如果key已存在则更新，否则插入当缓存达到容量时，put操作应淘汰最久未使用的key性能要求：get和put操作的时间复杂度应为O(1)考虑线程安全扩展要求（根据面试时间）：支持过期时间（TTL）支持持久化到磁盘支持统计信息（命中率等）

字节三面手撕地狱难度，撕不出来，也不让换题😇----------9.19一面（感觉是leetcode困难题）手撕扔鸡蛋（没撕出来），两个问。（1）100层楼，N层以上扔下鸡蛋会碎，只有两个鸡蛋，最少扔几次能得到N。（2）M层楼，K个鸡蛋，最少扔几次能得到N9.21二面手撕最长无重复子字符串（leetcode中等原题，滑动窗口秒）9.24三面，题如图（应该是超级困难题），好理解，很难写，输入都不知道怎么接，没撕出来。----------

本篇为本人实习+秋招面试被考到的手撕算法题和编码题总结首先是算法题：1. 算法题部分，有很多题是非常高频的，仅仅从我个人的面试体验就能看出来，最为突出的就是LRU，到了最后我已经可以在8分钟以内写完一次LRU了2. hot100在其中的比例为7/20，但是如果算上重复的，那就超过50%了；另外还会有一些题目是从hot100的做题思想就能拓展出去的3. 无他，唯手熟尔需要编码的场景题通常涉及几个方面的思想：外部多路归并排序；位运算；拒绝采样；大模拟；特殊数据结构有一说一在面试后，我的这方面思想也得到了很大的提升⭐算法题（除去重复题目，共20道）：➡️ 打家劫舍（力扣No.198，hot100，简单）➡️ 树的路径总和 ×2（力扣No.112，简单）➡️ LRU缓存 ×5（力扣No.146，hot100，中等）➡️ 最小栈 （力扣No.155，hot100，中等）➡️ 重排链表 ×2（力扣No.143，中等）➡️ 螺旋矩阵II（力扣No.59，中等）➡️ 最大子数组和（力扣No.53，中等）➡️ 合并区间 ×2（力扣No.56，hot100，中等）➡️ 岛屿数量 ×2（力扣No.200，中等）➡️ 二叉树的层序遍历 ×2（力扣No.102，hot100，中等）➡️ 寻找峰值（力扣No.162，中等）➡️ 翻转链表II（力扣No.92，中等）➡️ 快排 ×2（中等）➡️ 数组中第k大的数，要求堆排序思想写 ×2次（力扣No.215，hot100，中等）➡️ 字符串中最长无重复字符的子串（力扣No.3，hot100，中等）➡️ 分发糖果（力扣No.135，困难）➡️ 小于n的最大数（字节高频题，非力扣，困难）➡️ 寻找旋转排序数组中的最小值（力扣No.153，中等）➡️ 整数反转（No.7，中等）➡️ n个六面的骰子，扔一次之后和为k的概率是多少（中等）⭐场景模拟题：➡️ 两个线程交替输出1-100➡️ 两个复杂字典，如何将字典1通过一些规定好的操作变成字典2➡️ 长为8位的无重复大量数据，如何从小到大输出？如果内存不够一次全部读入呢？➡️ 如果有10亿个32位的整数，如何找出那些只出现过一次的数？内存有限，无法一次性读入全部数据，另外时间复杂度越低越好⭐特殊题：➡️ 实现一个无锁的线程安全的循环队列 ×2，一次Java一次Go➡️ 给定一个数组，如何用最小的比较次数获得最大最小值➡️ 有一个rand函数，生成1的概率是p，0的概率是1-p，那么如何用它生成一个rand2()，使得生成1和0的概率都是0.5➡️ 用rand7()函数构造函数rand10()➡️ 带超时时间的LRU缓存➡️ 实现一个单例模式加油💪🏻祝大家都有自己满意的offer！

题目1：实现一个支持泛型的栈（包含min函数）题目2：用队列实现栈题目3：LFU缓存（比LRU更难）题目4：跳表SkipList实现题目5：正则表达式匹配题目6：KMP算法手撕题目7：数独求解器题目8：八皇后所有解题目9：实现线程池题目10：生产者-消费者（多种变体）

得物、拼多多经常考，倒计时组件1.倒计时组件2.如何实现精确计时（setInterval 1s先就update以前知道写但没考虑到为什么，时间戳同步）// Countdown.jsximport React, { useEffect, useState, useRef } from 'react';/*** props:*  - endAt: number (timestamp ms) 或 Date*  - onFinish?: () => void*  - tickMs?: number (minimal tick granularity, default 1000)*/export default function Countdown({ endAt, onFinish, tickMs = 1000 }) {const endTs = typeof endAt === 'number' ? endAt : endAt.getTime();const [remaining, setRemaining] = useState(Math.max(0, endTs - Date.now()));const mounted = useRef(true);useEffect(() => {mounted.current = true;// initial syncfunction update() {const now = Date.now();const rem = Math.max(0, endTs - now);if (!mounted.current) return;setRemaining(rem);if (rem === 0) {onFinish?.();return;}// Align next update to wall-clock second boundary (or tickMs)const delay = Math.min(tickMs,1000 - (now % 1000) // align to next second for nicer UX);// If <1s left, use requestAnimationFrame for smoothnessif (rem <= 1000) {requestAnimationFrame(update);} else {setTimeout(update, delay);}}update();return () => {mounted.current = false;};}, [endTs, onFinish, tickMs]);const sec = Math.ceil(remaining / 1000);const mm = Math.floor(sec / 60);const ss = sec % 60;return (<div>{mm}:{String(ss).padStart(2, '0')}</div>);}

秋招面到小米三面，做不出来直接整段垮掉！#一人分享一道面试手撕题#

实现一个令牌桶限流器（Token Bucket），要求：支持初始化桶的容量（最大令牌数）和令牌生成速率（每秒生成多少个令牌）提供 Take() 方法，尝试获取 1 个令牌：有令牌时立即返回 true无令牌时阻塞等待，直到获取到令牌或超时（超时返回 false）保证并发安全，支持多 goroutine 同时调用 Take() 方法提供 Stop() 方法，优雅停止令牌生成的后台 goroutine

外来npc进入游戏本土该怎么办

讲一下多路io复用；讲一下Linux中进程是怎么管理的；Linux怎么实现多线程的；Pthread库中怎么实现的；如何用多进程模拟多线程；僵尸进程和孤儿进程，如何解决；孤儿进程被init进程收留的过程，数据结构角度讲；从数据结构讲一下父子进程关系，PCB里有没有相关内容。缓存：Redis用的什么数据结构；如何用Redis实现一个消息队列，如何实现异步返回。手撕：给出二叉树中两个子节点，子节点中有指向父节点的指针，找出两个子节点的祖先节点，要求常量级空间复杂度。

有一次嵌入式面试，面试官没有问太多八股文，直接给了一道现场手撕题。背景是设备需要统计状态寄存器中异常位的数量，本质就是统计一个 32 位寄存器里有多少个 bit 为 1。题目不难，但面试官强调两点：这是跑在单片机上的代码，效率要高，不能浪费算力。如果只会一位一位右移去数，很容易被追问有没有更优解。这道题考的不是能不能写出来，而是你平时有没有真正写过底层代码，是否对位运算和性能敏感。写完代码后，面试官还会继续追问在中断里用、在低功耗场景下用，有没有需要注意的地方。这种题目，很贴近真实嵌入式开发，也最容易拉开水平差距。

反转链表。题目描述：给定一个单链表的头节点 head，请你反转链表，并返回反转后的头节点。（这应该是最经典的手撕题之一）答案如下：一、迭代法（时间复杂度O(n)，空间复杂度O(1)）pythondef reverselist(head):prev = None          # 前驱节点初始化为空curr = head          # 当前节点从头开始while curr:nextnode = curr.next  # 临时保存下一个节点curr.next = prev       # 反转指针方向prev = curr            # 前驱节点后移curr = next_node       # 当前节点后移return prev           # 最终prev成为新头节点关键点：通过三指针（prev/curr/next）逐步调转箭头方向，注意指针更新的顺序。

利用hash表查询o(1)时间复杂度，遍历数组 nums，i 为当前下标，每个值都判断map中是否存在 target-nums[i] 的 key 值如果存在则找到了两个值，如果不存在则将当前的 (nums[i],i) 存入 map 中，继续遍历直到找到为止

手写 LRU 缓存淘汰算法，要求实现 get 和 put 方法，时间复杂度 O (1)，核心是结合哈希表与双向链表，处理缓存的增删查和优先级调整。

一道好的手撕题，不在于其形式的奇巧，而在于它能像一面清晰的多棱镜，折射出候选人不同维度的能力。它往往从一个看似基础的编程任务出发，却能自然而然地引导出对数据结构、算法效率和并发控制等核心知识的纵深探讨。面试官通过观察解题过程，评估的不仅是最终代码的正确性，更是思考路径的严谨性、边界条件的敏感度以及面对追问时的知识迁移能力。这类题目的典型特征，是要求在一个明确的约束条件下（如时间复杂度、空间限制或线程安全），实现一个具有完整功能的小型模块。它剥离了业务系统的复杂外衣，直指编程中最本质的抽象与逻辑组织能力。解题过程如同一次微型的架构设计，需要在有限时间内，在代码的简洁性、执行的效率性以及后续的可扩展性之间做出恰当的权衡与抉择。最终，一道经典手撕题的价值，往往体现在它所带来的持续对话上。一个干净的实现仅仅是对话的起点，随之而来的层层追问——从时间复杂度的分析、到并发场景的推演、再到不同设计方案的对比——才是真正的核心战场。它考察的是候选人能否将孤立的代码块，置于更广阔的“工程语境”中进行审视和辩护，这恰恰是区分熟练工与思考者的关键所在。

第一题：最长连续序列，面试要求 O(n)，还追问了 unordered_map 相关的内容； 第二题：手写快速选择算法（第 k 大），也是均摊 O(n) 的，挺考验功底的。

刚开始就叫写这个 没有别的要求  然后主播就在想选哪种实现方法呢  嗯最垃圾的是使用n次递归计算然后是使用dp  还有更高级的是利用大学学的线代知识 加上一个快速幂来写  但是稍微有点复杂了 然后选了一个abc动态规划的写法

来分享一个快速排序的实操代码，数组a[]，左边界l，右边界r。核心是partition函数：选a[r]当基准，用i标记小于基准的区域，遍历数组把小于基准的数交换到左边，最后把基准放到正确位置。递归处理左右子数组，几行代码就能搞定啦int partition(int a[],int l,int r){int p=a[r],i=l;for(int j=l;j<r;j++)if(a[j]<p)swap(a[i++],a[j]);swap(a[i],a[r]);return i;}void qsort(int a[],int l,int r){if(l<r){int m=partition(a,l,r);qsort(a,l,m-1);qsort(a,m+1,r);}}