已收到offer,基础架构方向-分布式存储-块存储/文件存储.

<>字节跳动一面(55min)

讲一下进程和进程之间有哪些关联?
我聊了进程通信的多种方式,讲了父子进程的关系。
数据库索引?
我提到了聚集索引和非聚集索引,他说只要讲聚集索引就可以
我提到了叶子节点存储数据,非页节点存储叶子节点的偏移量
叶子节点之间为什么要用双链表而不是单链表?
我没有了解过,但我认为存在这样的常见,查到的一个叶子节点,该页里的数据不够完整,还需要向前向后看是否还有满足条件的数据。
主要还是和一些时间的查询相关的一些情景(我不太理解)
你刚才说偏移量,偏移量怎么理解?
当时我有点懵逼了,现在想想,就是一个子节点的指针,就是一个物理地址,这有啥好问的无力吐槽。
Redis的有哪些数据类型?
5种基本数据类型,作为key的只有String,他们的内部实现除了跳跃表不大了解,其他的都有所了解。
Redis的RDB知道么?

我:我知道RDB可以把内存中的key-value键值对持久化到磁盘,通过SAVE和BGSAVE启动持久化,SAVE会阻塞主进程,BGSAVE会fork一个子进程,BGSAVE执行期间SAVE会被阻塞,这是为了防止两个子进程同时调用rdbSave,产生条件竞争。
他:SAVE为什么会阻塞?
我:Redis是单线程的设计。
他:让你自己实现BGSAVE怎么做?
我:一开始,把内存里的数据全部拷贝一份,然后把这一份持久化到磁盘,另一份则继续更新。
他:如果内存中数据量很大呢?你拷贝一份要花多久时间,而且内存空间浪费严重。

我:那直接在子进程把主进程的数据持久化到本地(由于父子进程共享数据),在这个过程中,主进程面对新来的修改操作,先把这些修改操作先暂存下来,等到子进程做完了持久化,发一个信号给父进程,在父进程的回调函数中把新的修改、插入、删除覆盖老数据。
给定1年的数据,数据记录包含(登录时间,登出时间,用户id),输入一个时间戳,求出该时间在线用户数量。(想不出来怎么做,求指点)
我说扫一遍表,然后每条记录判断一下,这样时间复杂度是O(n)。
他:你不要从算法的角度去考虑,有没有别的做法,我这样说是不想让你钻进死胡同。

我:我想了下,我能给出一个近似解,一般用户也不会登录很长时间,往前往后一周就可以了,因此对时间建立索引后,先按照时间把输入时间点的前一周和后一周的记录筛选出来,这个筛选过程的时间复杂度是O(lgn),这是由数据库B+树的查找时间复杂度决定的,然后在筛选出来的数据中,扫描一遍,这样数据量已经大大减少。因此,整体时间复杂度在数据分布均匀的情况下可以达到O(lgn)。
他:你再想想别的方法,不要从算法的角度去考虑这个问题
我:我总归还是想要从空间换时间的角度来考虑问题。
算法题:最大回文字符串

<>字节跳动二面(50min)

进程、线程、协程的区别与联系
Redis中RDB和AOF的区别
AOF中如果一段时间内有很多命令,有的命令冗余了,这样都存储下来会占据很多空间,你知道他是怎么解决这个问题的吗?
AOF的重写机制,原理是遍历内存中的键,构造出一条命令与之对应,然后存储下来。
细节是主进程除了执行新来的命令外,还会把命令写到AOF缓冲区和AOF重写缓冲区,子进程完成AOF重写(遍历父子进程的共享数据)
Redis、Memcache、Mysql、Mongo这几种数据库的区别知道吗?
如何基于RabbitMQ实现一个同步通信框架?
思考之后给出了一个大体的方向和思路
RabbitMQ中的几种exchange有所了解吗?
我说我简历上写的了解,就真的只是了解,不会这个,求别问RabbitMQ原理了
InnoDB和MyISAM的区别
balabala,没有提到行锁和表锁
他:你觉得InnoDB和MyISAM谁的性能更好?
我:思考中
他:提示一下,从锁的角度去分析。
我:哦哦,InnoDB是行级锁结合表级锁,MyISAM是表锁,因此InnoDB效率更好
他:那你讲一下数据库锁机制
讲了S锁、X锁、意向锁的设计原理,以及他们之间的兼容性
讲了锁带来的几个问题,提到了几个隔离级别、MVCC,以及MVCC解决的问题
场景题,一个用户打开了某个记录,然后另一个用户也打开了这个记录,他们看到的都是同样的数据,这时候A修改了记录,B也修改了记录,A的修改被B覆盖了,怎么办?
我:其实数据库的事物已经能够保证丢失更新问题不会出现,但这个问题其实就是逻辑意义上的丢失更新,有两种解决方案:
1.用户A的读数据加写锁 select …. for update.
2.无锁方式实现,用CAS的思想给他描述了一下。
算法题:判断是否为镜像二叉树
一开始写的不是最优解,先遍历自己构造了一颗镜像二叉树,然后遍历对比两颗树是否相同。
他:你这样,浪费了O(n)的空间,并且多了一次扫描
我修改了代码,一次扫描结束。

<>字节跳动三面(50min)

聊项目
如何实现读写锁?
用了两个变量去实现,讲了下思路
大佬问两个变量怎么实现原子性呢
给这两个变量的修改加上sychronized
synchronized太重了
想不出来,提示了我用1个数字的位来表示两个数字,也就不需要对这两个数字进行一个原子性的保证了。
算法题是最大子树和(先是必须包含叶子节点的)
做的比较快,二叉树的后序遍历写的比较熟
改了题,说不包含叶子节点也算。
讲了下思路,过了。
时间还比较多,我们再做一道算法题吧,讲下思路就可以,10亿url找频率topK大?
我给了一种思路的完整答案,另一种思路我想到了前缀树,在面试官的提示之下给出了答案。

技术
©2019-2020 Toolsou All rights reserved,
Unity-Demo实例之 ✨ 实现UI-背包装备拖拽功能计算机网络---计算机网络基本概念(协议、体系)某东14薪变16薪,是诚意还是套路?让人意想不到的Python之樱花树(turtle库的华丽样式)java四大函数式接口(重点,简单)06【若依框架解读】数据范围过滤--太牛了Unity3D之UGUI基础--画布的三种模式os模块的简单使用html写樱花树,写樱花树的作文