分享一下暑期遇到的手撕

本篇为本人实习+秋招面试被考到的手撕算法题和编码题总结首先是算法题：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.项目（25分钟） 1.1 合作模式：上游下游合作模式，指标谁负责，开发时间不足如何协调，开发优先级 1.2 模型建设：数仓分层，表设计，举例指标（说下比较复杂的指标，说下来自什么表，数据量），最佳使用的模型设计，给你一个场景重新设计模型，增全量设计，ads用户标签画像宽表窄表设计，数据集市建设 1.3 数据质量：交付前如何保障数据质量，线上数据质量dqc，长期跟踪监测源头数据 ...

1.自我介绍2.项目是从网上找的练手项目吗介绍一下订餐平台（苍穹外卖）代码有在原有基础上进行改造吗3.如何保证redis和db的数据一致性先删除再更新会怎么样redis常用数据结构zset的底层 为什么用跳表 范围查询时间复杂度红黑树和平衡二叉树的区别4.redis内存淘汰策略如果存在大量过期的key 会全部找出来删除吗LRU LFU区别 分别适合什么场景设计实现LFU 会用什么数据结构 提供什么方法5.什么是死锁 什么情况下会发生死锁编码过程中如何避免死锁有哪几种锁 并发包里提供哪些锁 读写锁一般用在什么场景6.Jwt和Session的区别一个分布式系统中，怎么用Session做登录检验，保证所有机器都能识别用户登录状态redis怎么做高可用讲一下redis集群怎么保证分片均匀度 哈希分片数的值7.设计索引要考虑哪些角度给了一个订单表 where后有userid status ordertime 怎么设计索引 为什么索引失效8.算法 数据流中的中位数如果加入一个删除功能怎么修改虽然每个问题都是从八股入手，但是最后问的都不是八股，只能说不愧是宇宙厂

这是一个典型的“消息分发模型”设计问题，微博/社交平台在设计大V发博分发时，推模式（push） 和 拉模式（pull） 各有利弊。下面结合你提到的“大V发博客”场景详细分析：一、两种模式简介推模式（push）大V一发微博，系统立即将内容推送到每一个粉丝的时间线中（如写入粉丝的消息队列或Feed中）拉模式（pull）粉丝查看时间线时，实时去拉取他关注的人（如大V）最新发布的内容，再合并排序显示二、微博类应用场景选型✅ 小V/普通用户：使用 推模式粉丝数少，推送量小；内容分发量级低；直接推送到粉丝的 Feed 表中，读取快，体验好。⚠️ 大V用户（如百万粉丝）：不能用纯推模式，会有严重问题顺便吆喝...