面试前的笔试
面试开始前 先让做题 不过不是现场做 不限制场地 在规定时间内完成就行（周五下午大概五点给我发题 第二题早上十点前让我把代码发到邮箱）
大量的URL字符串，如何从中去除重复的，优化时间空间复杂度
这题最开始考虑到了KMP 把问题想复杂了，实际上如果用KMP，那么输入的数据就要以列表的形式，每个字符串是列表的一个元素，这样的话直接一个set就能解决 KMP也没高效到哪里...
如果输入的是一大坨字符串 中间夹杂着各种域名 就相对来说有些复杂，因为还有判断域名是否正确，各种协议前缀 包括http、https、www、ws等等 后缀也要判断 .com .cn .top等等 如果是这样的输入的话 实际上除了正则我真不知道要咋优化...
所以最后我感觉输入是以列表的形式，就直接用set完成的这道题 代码如下
from typing import List
class URLDeduplicator:
def deduplicate(self, urls: List[str]) -> List[str]:
seen = set()
result = []
for url in urls:
# 将URL转换为小写
url_lower = url.lower()
if url_lower not in seen:
seen.add(url_lower)
result.append(url)
return result
相当简陋
python实现单例模式
如果是java，单例模式就是将构造函数私有 然后写一个静态的构造方法和一个私有的字段 这个私有字段类型就是自己的实例化 每当调用这个静态方法 就检查私有字段是不是空 如果是就实例化一个 然后返回 如果字段不是空就返回这个实例化 这样就保证了这个类全局只有一个实例
public class Singleton {
// 全局唯一的实例
private static Singleton instance;
// 私有化构造函数
private Singleton() {}
// 静态构造方法
public static Singleton getInstance() {
if (instance == null) {
instance = new Singleton();
}
return instance;
}
}
python中没有严格意义上的私有关键字private 一般是通过将字段和方法名字前加一个_来表示这个是私有方法
但python实现单例也比较方便 只需要重写一个魔法函数__new__
# 使用魔法函数__new__方法
class Class2:
_instance = None
# 每次实例化都会调用这个方法
def __new__(cls):
if cls._instance is None:
cls._instance = super().__new__(cls)
return cls._instance
def __init__(self):
pass
其次也可以通过装饰器实现
定义一个类装饰器
class Singleton:
"""
单例装饰器
"""
# 初始化装饰器
def __init__(self, cls):
self._cls = cls
self._instance = None
# 重写被修饰类的__call__魔法函数
# 使得被类似Class1()调用时 拦截下来 执行装饰器的__call__函数
def __call__(self, *args, **kwargs):
if self._instance is None:
self._instance = self._cls(*args, **kwargs)
return self._instance
# 使用装饰器方式实现单例
@Singleton
class Class1:
def __init__(self):
pass
拥有最小值的栈
在一般栈的基础上，添加一个min函数，能够得到栈的最小元素
要求函数min、push以及pop的时间复杂度都是O(1)。
这题让我想到代码随想录的滑动窗口最大值
滑动窗口最大值是一个单调队列的问题 这题也是类似的思路 需要的是一个单调栈 栈顶到栈底是递增的 也就是栈顶最小
class MinStack:
def __init__(self):
# 维护一个主栈和一个单调栈
self.stack = [] # 存储所有元素
self.min_stack = [] # 单调栈 栈顶到栈底单调递增(栈顶最小)
def push(self, value):
self.stack.append(value)
# 如果单调栈为空
# 或者
# 当前值小于等于单调栈顶元素
if not self.min_stack or value <= self.min_stack[-1]:
self.min_stack.append(value)
def pop(self):
if not self.stack:
return None
value = self.stack.pop()
# 如果弹出的元素是当前最小值，单调栈也要弹出
if value == self.min_stack[-1]:
self.min_stack.pop()
return value
def min(self):
if not self.min_stack:
return None
return self.min_stack[-1]
这里pop部分可以通过判断当前弹出的值是不是最小值就能直接弹出 是以为最小栈数据的顺序和数据栈的顺序是一样的
具体可以举一个例子
入栈
5 3 1 5 2
单调栈为
5 3 1
弹出2 弹出5
单调栈还是5 3 1 因为保留了之前的顺序
一面
自我介绍
跟ieg那次差不多 就说自己班级 校园经理 实习 项目 技术栈
python中字典的底层数据结构
讲真的没了解过 最开始脱口而出说是哈希表 后面补充说 对python的底层不是很了解 但对java的hashmap比较了解
然后他让介绍一下说java的hashmap是怎么实现的 大概聊了一下：总体上hashmap是一个哈希表 每个key对应一个hash元素 当有hash冲突时 如果冲突的元素比较少是链表 如果比较多就是红黑树
hash的底层是什么？
这个也挺懵的 映象中是数组 因为hash映射的速度是O(1) 这就需要底层是支持随机访问的 就回答说是数组 他说还有树
复盘补充
python的字典和hashmap有些不同 比如处理冲突 字典使用的是开放寻址法 比如线性探测等
hash的一般实现就是数组 而且是两个数据 一个存放索引 一个存放值
其次hash也有通过树实现的 比如二叉树等等各种树 替代数组的优点是不需要处理hash冲突 但访问肯定是比数组慢的
python字典中 是基于数组实现的
class DictImplementation:
def __init__(self):
# indices数组：存储entries的索引
self.indices = []
# entries数组：存储实际的键值对
self.entries = []
python中list的底层数据结构 为什么可以存不同的数据
也没了解过 但大概聊了一下redis的压缩列表(ziplist) 就是每个元素末尾有一个偏移 可以知道下一个元素的位置 仍然是连续的空间
本来只是觉得这题答错了 亡羊补牢一下 但面试官说差不多 他接着补充说实际上存储的是各个元素的指针 然后我问是类似c语言的二维数组那样吗 他说是的
mysql底层实现是红黑树吗
基于B+树 具体介绍了一下红黑树和B树的区别 然后介绍B树和B+树的区别
红黑树和B树最关键区别在于节点的存放数量 B树可以存放多个键值对 红黑树只能存放一个 这样可以减少查找io
其次 B+树在B树的基础上再优化 让数据只能存储在叶子结点 其他结点只能放键值 这使得树的高度减小了 也减少了查找io
其次B+树叶子节点通过双向链表相连 减少了范围查找回溯的步骤 可以顺序查找
mysql的事务有哪些
这里卡了一下 当时没组织好语言太着急了
四种隔离阶段 读未提交 读已提交 可重复读 串行化
读未提交 可以读任何事物的更改 即使没有提交修改
读已提交 只能读别的事务提交的修改
可重复读 不会读到别的事务提交的内容 但可以读到新增的数据
串行化 别的事务的提交都读不到 只能读开启事务之前的和自己提交的数据
然后大概说了一下四个隔离是通过mvcc实现的 讲了一下mvcc的原理： 每行数据有两个隐藏字段 一个是当前这行数据的mvcc版本 一个是上一个版本的指针 指向undo日志的数据 每个事务查询的时候都有一个readview 事务查询数据的时候 只能查到readview规定能查的数据
mysql的日志 redolog和undolog
我答的时候是以执行一条sql语句的过程来答的
当一条sql语句执行时 在变化之前 会先将原来的数据存入undolog 然后将这条sql逻辑存入redolog 最后执行变化
undolog是用于事务回滚 redolog是用于崩溃处理 如果mysql突然崩溃 redolog会有一个checkpoint 下次启动就会从checkpoint开始执行恢复数据
三次握手
难绷的 这都问 大概介绍了一下tcp的三次握手
客户端发送带有SYN的包
服务端接受SYN包 发送一个ACK和SYN字段的包
客户端接收 发送一个ACK包
然后就能发送数据了 其实有时候第三次握手也可以发送数据
（回答的时候SYN这个还想不起来了 有空要看看计网）
redis的底层数据结构
string list hash set sorted set
redis是单线程吗
我回答说是增删改查这种命令的执行是单线程 并回答原因是redis的时间瓶颈不在增删改查上 其他有些地方是使用的多线程
幸好没问什么地方用的是多线程(
复盘补充
redis网络IO使用多线程（提高网络性能） 命令处理仍然是单线程（保证原子性）
线程和进程什么区别
回答说 进程是一个基本单位 线程是比进程更小的一个基本单位（回答的很抽象 生怕说多了答错 这块不太熟）
复盘补充
进程是资源分配的基本单位 拥有独立的内存空间和系统资源
线程是CPU调度的基本单位 需要共享所属进程的资源
异步io和同步io
回答说 异步相当于是有分身帮忙干活 同步是一件事情干完干下一步 还补充说异步效率一般比同步高 但是异步也有额外的管理成本
复盘补充
其实这题答的很烂 没有抓到关键 如果重新答 应该说
同步io执行任务会阻塞等待 异步io执行不会阻塞
一个具体的实现就是 异步相当于轮询等待 异步相当于回调 执行完之后通知
总结一下就是
同步会阻塞等待，资源利用率较低 适合CPU密集型
异步并不是相当于分身，而是不需要等待任务完成就可以继续执行其他任务 适合IO密集型
cpu密集型是指主要时间花在计算上的问题
IO密集型是指主要时间花在输入输出上 比如读写文件 http操作等等
算法题
面试官说不用写代码 直接说思路就好
具体题目是 求3的平方根
回答说用二分 最开始的区间是0-3 先求3的一半 然后看这个数的平方是大于3还是小于3
如果小于3 就取0和这个数的一半 如果大于 就取这个数和3的一半
递归一下 区间变成0-中间数后者中间数-3
然后我说要不要写出来 说的可能不太清楚 他说不用 很清楚了
反问
刚刚的面试过程中映象不好的回答
回答说 异步同步中的异步 感觉我回答的像是并发（ 让我去了解并发和异步的区别
然后就是线程那部分 更关键的区别是线程是对于cpu来说是调度的基本单位 进程是相对于资源分配来说的
进入后具体会做什么工作
说了一下公司的业务 主要是ai方面的研究 我进去的话 10%的工作会是数据处理和清洗 然后是用pytorch等ai相关的工具微调一些大模型 要自己寻找数据等等 如果效果比较好 就要商业化之类的
总结
异步和并发的区别
异步是一种编程模式，强调任务的执行方式，一个线程可以处理多个任务，不用等待当前任务完成
并发是多个任务在同一时间段内执行的现象 ，一定是多线程的
这次面试大多是八股 相对比较简单 算法也简单 不过我已经五天没写算法了 一直偷懒（
二面
是公司创始人面，没有什么技术问题，就大概问了一下关于本身的情况