首页 > 笔经面经 > shopee面试问题整理

shopee面试问题整理

头像
Jun10ng
编辑于 2020-04-03 18:09:50 APP内打开
赞 13 | 收藏 140 | 回复18 | 浏览4349
上星期为了虾皮的面试,把牛客上的虾皮面经都过了一篇,整理下,现在分享给大家。许愿一个offer。
这是我一面的面经:(https://www.nowcoder.com/discuss/386923

以下是整理的问题:
(md文件我放在github了,有需要的话自行下载:https://github.com/Jun10ng/Gache/blob/master/shopee.md
** 推荐一个简历项目,当时投的golang,但是没有啥项目,于是参考了许多网上资料,最后决定做一个简单的类分布式缓存: **
有些问题都是老生常谈了,我就没写答案了。

Shopee面试问题整理

三握手四挥手 及其状态


Go操作redis

github 上面的rediGo

什么是平衡二叉树

编程:实现反转链表

MySQL复合索引

set的使用场景 有序set的使用场景

有序且去重的场景

1、 排行榜:有序集合经典使用场景。例如视频网站需要对用户上传的视频做排行榜,榜单维护可能是多方面:按照时间、按照播放量、按照获得的赞数等。

2、用Sorted Sets来做带权重的队列,比如普通消息的score为1,重要消息的score为2,然后工作线程可以选择按score的倒序来获取工作任务。让重要的任务优先执行。

反射 反射的弊端

优点:运行期类型的判断,动态类加载,动态代理使用反射。

缺点:性能是一个问题,反射相当于一系列解释操作,通知jvm要做的事情,性能比直接的java代码要慢很多。

进程调度算法

先来先服务 时间片轮转算法 短作业优先 最短剩余时间 高响应比 优先级

进程间怎么通信

管道 有名管道 套接字 消息队列 信号量

线程间通信

主要分为共享内存和消息传递

volatile关键字 wait/notify机制

事务隔离级别

隔离级别 脏读(Dirty Read) 不可重复读 幻读(Phantom Read)

未提交读(Read uncommitted) 可能 可能 可能

已提交读(Read committed) 不可能 可能 可能

可重复读(Repeatable read) 不可能 不可能 可能

可串行化(Serializable ) 不可能 不可能 不可能

MyISAM和InnoDB差别

MyISAM不支持事务,InnoDB支持。MyISAM不支持行锁,只支持表锁,InnoDB支持行锁。

InnoDB没有保存具体的行数,所以在统计行数的时候回扫描全表,MyISAM有保存。

myisam的索引以表名+.MYI文件分别保存。innodb的索引和数据一起保存在表空间里。

LINUX kill命令

在Linux/unix下,中止一个Java进程有两种方式,一种是kill -9 pid,一种是kill -15 pill(默认)。

SIGNKILL(9) 的效果是立即杀死进程. 该信号不能被阻塞, 处理和忽略

SIGNTERM(15) 的效果是正常退出进程,退出前可以被阻塞或回调处理。并且它是Linux缺省的程序中断信号(默认是15)。

TCP四次挥手的TIME_WAIT

在第三次挥手的时候,服务端发FIN给客户端,然后客户端再发ACK命令给客户端,然后进入TIME_WAIT状态,2MSL之后,进入CLOSED状态,从客户端的角度来说,第四次挥手是为了告诉服务端,我收到了你的FIN信号,一切正常,等待2MSL是为了确保服务端收到了ACK,如果因为网络波动导致服务端没收到ACK,那么服务端会重传FIN信号。从服务端的角度老说,第四次挥手能确保客户端收到FIN信号。

TCP UDP

TCP面向连接,UDP是无连接的,TCP能通过校验和,重传控制等,保证可靠传输,UDP不能保证可靠传输,但UDP实时性高且UDP对资源需要的少。

TCP 如何保证数据传输的可靠性

校验和 确认应答+序列号 超时重传 流量控制 拥塞控制

TCP3次握手的过程,为什么要3次 ,SYN攻击

大文件为什么越下载越快?

滑动窗口,慢启动算法,越传越快。

前面说过,还有一个ssthresh(slow start threshold),是一个上限,当cwnd >= ssthresh时,就会进入“拥塞避免算法”。一般来说ssthresh的值是65535,单位是字节,当cwnd达到这个值时后,算法如下:

1)收到一个ACK时,cwnd = cwnd + 1/cwnd

2)当每过一个RTT时,cwnd = cwnd + 1

这样就可以避免增长过快导致网络拥塞,慢慢的增加调整到网络的最佳值。很明显,是一个线性上升的算法。

Innodb 自增主键

上文讨论过InnoDB的索引实现,InnoDB使用聚集索引,数据记录本身被存于主索引(一颗B+Tree)的叶子节点上。这就要求同一个叶子节点内(大小为一个内存页或磁盘页)的各条数据记录按主键顺序存放,因此每当有一条新的记录插入时,MySQL会根据其主键将其插入适当的节点和位置,如果页面达到装载因子(InnoDB默认为15/16),则开辟一个新的页(节点)。

如果表使用自增主键,那么每次插入新的记录,记录就会顺序添加到当前索引节点的后续位置,当一页写满,就会自动开辟一个新的页。这样就会形成一个紧凑的索引结构,近似顺序填满。由于每次插入时也不需要移动已有数据,因此效率很高,也不会增加很多开销在维护索引上。

HTTP 无状态 无连接

无连接的含义是限制每次连接只处理一个请求。服务器处理完客户的请求,并收到客户的应答后,即断开连接。采用这种方式可以节省传输时间。为请求时建连接、请求完释放连接,以尽快将资源释放出来服务其他客户端,可以加KeepAlive弥补无连接的问题

无状态是指协议对于事务处理没有记忆能力,服务器不知道客户端是什么状态。即我们给服务器发送 HTTP 请求之后,服务器根据请求,会给我们发送数据过来,但是,发送完,不会记录任何信息。 可以通过Cookie和Session来弥补这个问题。

Cookie 和 Session

cookie 是一种发送到客户浏览器的文本串句柄,并保存在客户机硬盘上,可以用来在某个WEB站点会话间持久的保持数据。

Session的本质上也是cookie,但是不同点是存在服务器上的。这就导致,你如果使用cookie,你关闭浏览器之后,就丢掉Cookie了,但是如果关掉浏览器,重新打开之后,发现还有相应的信息,那就说明用的是Session。因为cookie是存在本地的,所以也会有相应的安全问题,攻击者可以去伪造他,填写相应的字段名,就能登录你的账户,还有如果cookie的有效期很长的话,也不安全。

session 由服务器产生,对于客户端,只存储session id在cookie中。

LRU算法是如何实现的?

双向链表加 哈希表

数组中出现次数最高的K个数

map+优先队列

先用map统计每个数的出现次数,然后维护 一个大小为K的优先队列(堆)。

volatile 内存屏障

CPU有可能会把相应代码的CPU指令进行一次重排序,这虽然能提高运行的效率,但是也可能会影响一些数据的可见性,而volatile通过 内存屏障 这个指令,来保证了相应代码块的执行顺序。内存屏障还会强制更新一次CPU缓存。加载最新的内容。

快排的优化

快排有三个步骤:

  1. 选择基准

  2. 分割操作

  3. 递归地对两个序列快速排列,直到序列为空或只有一个元素。

所以可以针对这三个方面做优化

选择基准:最理想的基准就是,每次划分都能分成登长的两个子序列。最坏的情况 就是基准是最大最小值。

可以选的基准有:固定位置,随机位置,三数取中。

三数取中是指 取 最左 最右 中间元素 三个数的中间值。

其他优化方式

  1. 当排序序列分割到一定大小的时候,可以使用插入排序

  2. 如果有key相等的元素,可以聚在一起,下次排序的时候,就不用对相等的元素再排序了

  3. 优化递归操作

  4. 多线程

Mysql 的 redo undo

Undo日志记录某数据被修改前的值,可以用来在事务失败时进行回滚;Redo日志记录某数据块被修改后的值,可以用来恢复未写入data file的已成功事务更新的数据。

死锁的四个条件 和预防

互斥,不可剥夺,循环等待,请求和保持

预防,检测,避免死锁,接触死锁

银行家算法

多路IO模型 NIO

在多路复用IO模型中,会有一个线程(Java中的Selector)不断去轮询多个socket的状态,只有当socket真正有读写事件时,才真正调用实际的IO读写操作。因为在多路复用IO模型中,只需要使用一个线程就可以管理多个socket,系统不需要建立新的进程或者线程,也不必维护这些线程和进程,并且只有在真正有socket读写事件进行时,才会使用IO资源,所以它大大减少了资源占用。

五种网络IO模型

阻塞IO 非阻塞IO 多路IO复用,信号驱动IO(不常用),异步IO,

前四种都是同步IO

像listen()、send()、recv()这些接口都是阻塞的,一问一答型的。这就给网络编程带来了一个问题,如果在调用send的时候,线程将被阻塞,在此期间,无法执行任何运算或相应任何的网络请求。于是有了多路IO模型,一个socket可以多次accept多次,比如Java中的selcetor 不断轮询多喝socket的状态,只有当socket真正有读写事件的时候,才会调用实际的IO读写操作,还有想Golang里的select+多个channel,这样只需要一个线程就可以管理多个socket,能减少大量资源占用。

非阻塞IO模型

在非阻塞IO模型中,用户进程不需要主动询问对方是否准备好数据与否,比如进程发出read操作,如果对方没有准备好,会返回一个error,这表示对方没有准备好,但是进程并不会阻塞在这一步,而是继续执行,等对方准备好数据后,再去调用它。

异步IO

异步IO是真正意义上的非阻塞IO,用户进程发起read操作后,立刻就可以开始做其他事,而另一方面,当他收到一个异步请求时,会立即返回一个值,所以不会对用户进程产生任何阻塞,等数据准备完后,再将数据拷贝到用户内存,当这一切都完成后,再给用户进程发送一个signal,告诉他read操作完成了。

非阻塞IO和异步IO的区别

虽然非阻塞IO在大多时间内不会被阻塞,但是它要求进程去主动监察对方数据是不是准备好了,一旦准备好了,会再次要求进程调用接收函数将数据拷贝过来。而异步IO完全不管这些,就像吧IO操作外包掉,等他人做完再发信号通知,这个期间内,进程不要检查也不用主动的去拷贝。

Golang里的Sync包

互斥锁:Mutex,读写锁:RWMutex. WaitGoup,Cond实现一个条件变量,Once 使对象只执行一次。

Java线程的6种状态及切换

初始:新建一个线程对象

运行:调用了start后就是运行状态

阻塞:线程被锁阻塞

等待,进入该状态的线程需要等待其他线程做出一些动作(通知或者唤醒

超时等待:

终止:

虚拟内存

虚拟内存使得应用程序认为它拥有连续的可用内存,这样一来,就在逻辑层面上扩大了内存容量。但是实际上,只是把比较常用的内存片段取出来了而已,还有部分资源是放在磁盘存储器上的。需要的时候再进行数据交换。

调度方式有,分页式,段式,段页式。比较流行方式是段页式,他结合了前两者的优点,以页为单位替换,以段为单位使用。

常见的替换替换算法有4种,随机算法,先进先出算法,LRU算法,最优算法。 比较常使用的是LRU算法,他在redis里也有使用,当redis的内存满了的时候就是使用LRU算法替换掉旧内存。


二面的问题:
手撕算法。


更多模拟面试

18条回帖

回帖
加载中...
话题 回帖

相关热帖

笔经面经近期热帖

近期精华帖

热门推荐