一人分享一道面试手撕题

1.排序与选择快排(LC 912）数组中第k大的元素(LC 215)数组中最小的k个数(LC面试题17.14）2.二分与数学（含概率）sqrt(x)(LC 69)pow(x, n)(LC 50)搜索旋转数组(LC33)Rand7实现 Rand10(LC470)3.双指针与滑动窗口三数之和（LC 15）滑动窗口最大值（LC239）有效三角形的个数（LC 611)最小覆盖子串（LC 76)长度最小子数组(LC 209）4.栈与队列/表达式有效的括号（LC 20）最长有效括号（LC 32)逆波兰表达式求值（LCR 036)5.链表反转链表（LC206)反转链表(LC 92)k个一组翻转链表（LC 25)环形链表/环形链表(LC 141/142)删除链表倒数第n个节点(LC19）6.树与图二叉搜索树的最近公共祖先(LC 235)二叉树的最大路径和(LC124）路径总和/路径总和（LC112/113）岛屿数量（LC 200）课程表(LC210）7.动态规划（序列/路径/计数/区间）最大子数组和(LC 53)最长递增子序列LIS(LC300）最小路径和（LC64）加油站（贪心/DP，LC134）最大乘积子数组（LC 152)打家劫舍(LC 213）不同的子序列（LC 115）爬楼梯（LC 70)最长公共子序列LCS(LC 1143)8.字符串最长回文子串（LC 5）最长回文子序列(LC516）字符串解码（LC394）编辑距离（LC 72)大数相乘(LC43)9.数组与哈希/前缀后缀除自身以外数组的乘积（LC 238）和为k的子数组（LC560）两数之和（LC167）缺失的第一个正数(LC41)合并区间（LC56)10.模拟螺旋矩阵（LC 54)，二维有序矩阵第k小(LC 378)

面试时候的手撕其实很少出得特别难，基本都是middle，考验你的基础，所以这里面是有一些高频考点的，我根据个人经历整理了一些比较通用的经典的手撕。🛠️ 数据结构与算法（典中典）LRU缓存 ：HashMap 存值，双向链表 存序。思路： 读写都把节点拔出来插到链表头，容量满了删链表尾。K个一组翻转链表： 递归/迭代 + 局部翻转。思路： 够K个就断开翻转，不够直接还回；递归拼接下一组的结果。合并K个升序链表： 最小堆 (PriorityQueue)。思路： 把所有链表的头结点扔进堆里，每次弹最小的连上，把它的next再扔进去。无重复字符的最长子串： 滑动窗口 + 哈希/Set。思路： 右指针狂...

面试官说这个是一到经典的数学问题：两杯没有刻度的水杯，分别容量是a升和b升，是否可以凑出c升的水。面试官先问我5和3是否可以凑出4，我说可以然后说了具体的操作，后面引导我推广到一般的情况，我代码中一直在减来凑，最后思路卡住了，面试官说时间不够了就先这样。根据数论中的结论，如果 c  是 a  和 b  的最大公约数（GCD）的倍数，那么可以通过倒水操作凑出 c  升的水。具体来说：计算 a  和 b  的最大公约数 GCD(a,b) 。如果 c  是 GCD(a,b)  的倍数，那么可以凑出 c  升的水；否则不能。

得物、拼多多经常考，倒计时组件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>);}

字节三面手撕地狱难度，撕不出来，也不让换题😇----------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.LRU缓存题目：请你设计并实现一个满足LRU (最近最少使用) 缓存约束的数据结构。2.合并K个升序链表题目：给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。3.排序链表题目：给你链表的头结点head ，请将其按升序排列并返回排序后的链表。4.数组中的第K个最大元素题目：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。5.零钱兑换题目：给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。6.最长递增子序列题目：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。7.最长递增子数组题目：和上一题类似，区别是一个是子序列，一个是子数组8.最长公共子序列题目：给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。总的来说，刷leetcode就够了。hot100和面试经典150题多刷一刷。还有用AI辅助编程的，不过不难。

【题目来源】公司/部门：腾讯-微信支付后台开发面试轮次：二面考察形式：共享屏幕现场编写【原题描述】实现一个函数，用于验证二叉搜索树(BST)的有效性。给定二叉树根节点，判断该树是否是有效的二叉搜索树。有效BST定义为：- 左子树所有节点值 < 当前节点值- 右子树所有节点值 > 当前节点值- 左右子树也必须是BST示例：输入：[5,1,4,null,null,3,6]输出：false（根节点5的右子树中包含值3，小于5）要求：时间复杂度尽可能优【面试官关注点】是否理解BST的本质定义（不仅是左右孩子大小关系）能否想到利用上下界递归验证的思路边界条件处理：空树、int边界值、重复值处理代码简洁性和变量命名可读性

我觉得在我找日常实习，暑假实习和秋招的时候，最长无重复子串出现频率很高，基本上平均五个面试中都会出一道这个题，大部分出现在一面的时候，一面大部分考查基础知识，出这个题在合适不过啦，反正这个题也是简单到家，有时候面试官觉得你还不错，放水也爱出这个题嘿嘿

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

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

没错，你没听错，就是快排，还有一个是带参数的装饰器。当时还以为耳朵听错了，但是面试官说，就这些，开始写吧😂😂😂，所以基础的排序算法和基础能力一定不能缺少

sql实现连续登录问题，主要考察窗口函数的应用sql实现排序问题，主要考察复杂排序问题另外在面试中必问数据倾斜问题的解决方案，以及日期函数的使用

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

hot100原题，直接秒了可能面试官发现我做过，现在想起来十分悔恨啊，X﹏X后面大家手撕如果发现是原题，记得装一下，思考一下😅😅😅

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

刚刚结束的，还热乎着呢，可惜没做出来，算法和数据结构忘干净了题目大概意思就是，一棵二叉树从右看是哪些值，依稀记得力扣有原题，思路是层序遍历记录每一层最右边的值，但是忘了层序遍历咋写了手撕手撕没做出来，面试也是一坨....除了实习内容以外，问了volatile，tcp-ip模型、Java IO等，基本都没答出来，一个多月没面忘干净了部门业务是做腾讯安全edgeone的，从问的问题来看，面试官更偏重于底层逻辑，比如计网、并发等，最近面云智的兄弟们可以针对性准备一下

计算机面试手撕题别只刷排序了！这道线程池实现题，我面字节、腾讯时都碰到过。核心是写任务队列 + 工作线程，用互斥锁保证队列安全，条件变量唤醒线程。一开始我没考虑任务结束的优雅退出，面试官直接指出漏洞。后来加了shutdown标志位，让线程能正常销毁。提醒大家，写的时候要讲清锁的作用和线程调度逻辑，光写代码不解释，等于白写！

我虽然不是应届生了，但手撕题，是我的话，我会出几方面的1.链表2,字符串3.DFS BFS4.树这些方面的比较能考察代码能力和细节的，比如字符串就要注意结束符等