面试官初体验

Kevinello

发布于 2022-08-19 11:23:44

2920

发布于 2022-08-19 11:23:44

文章被收录于专栏：Kevinello的技术小站

前言

近期作为后台开发面试官整理的一些简单面试题（仅供参考仅供参考仅供参考

基础题

Golang

Golang中函数调用是传值还是传引用

Golang中make和new的区别？

以下程序输出为？

实际输出为：

因为for range创建了迭代对象每个元素的副本，而不是直接返回每个元素的引用，如果使用该值变量的地址作为指向每个元素的指针，就会导致错误，在迭代时，返回的变量是同一个迭代过程中根据切片依次赋值的变量，所以最终map中存储的地址都是同一个变量的地址，而其值即为最后一次迭代中赋的值

以下程序输出为？

实际输出为：

每轮循环启动一个协程，而协程启动与循环变量递增不是在同一个协程，协程启动的速度远小于循环执行的速度，所以即使是第一个协程刚起启动时，循环变量可能已经递增完毕。由于所有的协程共享循环变量i，而且这个i会在最后一个使用它的协程结束后被销毁，所以最后输出结果时i是循环变量的末值即2，输出的都是nums[2]

package main

import (
	"fmt"
	"sync"
)

func main() {
	var nums = []int{1, 2, 3}
	var wg sync.WaitGroup
	for i := range nums {
		wg.Add(1)
		go func(i int) {
			fmt.Print(nums[i])
			wg.Done()
		}(i)
	}
	wg.Wait()
}

以下程序的输出是？

实际上这样写会使 Go 语言的编译器报错：

因为这样的运算溢出了

var b uint64 = 10
var c int64 = -3
atomic.AddUint64(&b, uint64(c))
fmt.Println(b)

go defer，多个 defer 的顺序，defer 在什么时机会修改返回值？

package main

import (
        "fmt"
)

func main() {
        fmt.Println("a return:", a())
        fmt.Println("b return:", b())
}

func a() int {
        var i int
        defer func() {
                i++
                fmt.Println("defer:", i)
        }()
        defer func() {
                i++
                fmt.Println("defer:", i)
        }()
        return i
}

func b() (i int) {
        defer func() {
                i++
                fmt.Println("defer:", i)
        }()
        defer func() {
                i++
                fmt.Println("defer:", i)
        }()
        return
}

a defer: ?
a defer: ?
a return: ?
b defer: ?
b defer: ?
b return: ?
c defer: ?
c defer: ?
c return: ?

a defer: 1
a defer: 2
a return: 0
b defer: 1
b defer: 2
b return: 2
c defer: 1
c defer: 2
c return: 2

返回值不同的原因：

Golang 中的interface是什么？

反射是什么？Golang中的反射是基于什么实现的？

Golang Reflection 三大法则：

总而言之，Golang中的反射是基于interface实现的，因为任意类型都实现了interface{}类型，所以可以把任意类型的变量转换成interface{}类型，所以反射能从interface{}的数据结构中反射出对象，也就是利用reflect.ValueOf和reflect.TypeOf从interface反射出对象的具体信息

以下程序会输出什么？

会Panic:

对应 Reflection 三大法则的第三条，要修改一个反射对象，它的值必须是能修改的；简单点说，就是通过反射，必须反射出它的本身，而不是它的一份拷贝

那怎么反射出它的本身，和我们函数传参的时候很像：地址；将上文的v := reflect.ValueOf(x)改为v := reflect.ValueOf(&x).Elem()即可，如果想要操作原变量，反射变量 Value 必须要 hold 住原变量的地址才行：

已关闭的channel再次读取会出现什么现象？

closed channel是可以被消费者继续读取的，在读完了有意义的数据之后，将读到一堆空值

如何判断一个channel已关闭？

函数中ch是一个只读的channel，因为<-ch左侧没有接收者，所以如果channel没有关闭，case <-ch就会被阻塞，又因为select中写了default语句，所以select会直接执行default的空分支，最终return false；如果channel关闭了，case <-ch就不会被阻塞，直接执行该分支return true

map 循环是有序的还是无序的？

Java

ArrayList和LinkedList的区别

HashMap 和 HashTable 区别

HashMap 不是线程安全的 HashMap 是 map 接口的实现类，是将键映射到值的对象，其中键和值都是对象，并且不能包含重复键，但可以包含重复值。HashMap 允许 null key 和 null value，而 HashTable 不允许
HashTable 是线程安全 Collection HashMap 是 HashTable 的轻量级实现，他们都完成了Map 接口，主要区别在于 HashMap 允许 null key 和 null value,由于非线程安全，效率上可能高于 Hashtable

HashMap允许将 null 作为一个 entry 的 key 或者 value，而 Hashtable 不允许。
HashMap 把 Hashtable 的 contains 方法去掉了，改成 containsValue 和 containsKey。因为 contains 方法容易让人引起误解。
HashTable 继承自 Dictionary 类，而 HashMap 是 Java1.2 引进的 Map interface 的一个实现。
HashTable 的方法是 Synchronize 的，而 HashMap 不是，在多个线程访问 Hashtable 时，不需要自己为它的方法实现同步，而 HashMap 就必须为之提供外同步。
Hashtable 和 HashMap 采用的 hash/rehash 算法都大概一样，所以性能不会有很大的差异。

List接口、Set接口和Map接口的区别

Java线程间的通信方式

判断对象是垃圾 ?

引用计数法，思路很简单，但是如果出现循环引用，即：A 引用 B，B 又引用 A，这种情况下就不好办了，所以 JVM 中使用了另一种称为“可达性分析”的判断方法

可达性分析法

如果 A 引用 B，B 又引用 A，这 2 个对象是否能被 GC 回收？

常用的 GC 算法

equals()和 ==的区别

public boolean equals(Object obj) {
    //this - s1
    //obj - s2
    return (this == obj);
}

我们对上面的两段内容做个总结吧：

Redis

redis事务满足关系性数据库事务的特性吗

zset的实现原理（或者说数据结构）

redis中pipeline的作用

LRU 和 LFU 是？

分布式锁的基本实现以及坑（展开到进阶实现）

利用 Redis set key 的 NX 参数来保证在这个 key 不存在的情况下写入成功，并且再加上 EX 参数设置过期时间

A进程释放了B进程的锁 如果进程 A 获取了锁设置了超时时间，但是由于执行周期较长导致到了超时时间之后锁就自动释放了。这时进程 B 获取了该锁，然而这时进程 A 执行完了，释放了该锁；这样就会出现进程 A 将进程 B 的锁释放了所以最好的方式是在每次解锁时都需要判断锁是否是自己的（生成uuid放到value中）
锁过期了，业务还没执行完 设置看门狗，在业务执行时自动延长锁的过期时间（举例子：假如加锁的时间是30秒，过10秒检查一次，一旦加锁的业务没有执行完，就会进行一次续期，把锁的过期时间再次重置成30秒）
redis 主从复制导致锁丢失在分布式redis中，主节点没来的及把刚刚set进来这条数据给从节点，就挂了，这就造成了redis异步复制造成的锁丢失使用RedLock：红锁算法认为，只要n/2+1个节点加锁成功，那么就认为获取了锁，解锁时将所有实例解锁。流程为：
1. 顺序向五个节点请求加锁
2. 根据一定的超时时间来推断是不是跳过该节点
3. 三个节点加锁成功并且花费时间小于锁的有效期
4. 认定加锁成功

Redis的内存碎片是什么？Redis的内存碎片清理机制是什么？

redis自己实现的内存分配器：在redis中新建key-value值时，redis需要向操作系统申请内存，一般的进程在不需要使用申请的内存后，会直接释放掉、归还内存；但redis不一样，redis在使用完内存后并不会直接归还内存，而是放在redis自己实现的内存分配器中管理，这样就不需要每次都向操作系统申请内存了，实现了高性能（但这样其它应用可就不高兴了，自私的Redis）
value的更新：redis的每个key-value对初始化的内存大小是最适合的，当这个value改变的并且原来内存大小不适用的时候，就需要重新分配内存了，重新分配之后，就会有一部分内存redis无法正常回收，一直占用着

Redis版本4.0以下

Redis版本4.0以上

TEXT
127.0.0.1:6379[6]> config set activedefrag yes
OK

TEXT
# Enabled active defragmentation
# 碎片整理总开关
# activedefrag yes

# Minimum amount of fragmentation waste to start active defrag
# 内存碎片达到多少的时候开启整理
active-defrag-ignore-bytes 100mb

# Minimum percentage of fragmentation to start active defrag
# 碎片率达到百分之多少开启整理
active-defrag-threshold-lower 10

# Maximum percentage of fragmentation at which we use maximum effort
# 碎片率小余多少百分比开启整理
active-defrag-threshold-upper 100

TEXT
127.0.0.1:6379> memory purge
OK

数据库

如何用Mysql实现分布式锁创建一张锁表，然后通过操作该表中的数据来实现加锁和解锁。当要锁住某个方法或资源时，就向该表插入一条记录，表中设置方法名为唯一键，这样多个请求同时提交数据库时，只有一个操作可以成功，判定操作成功的线程获得该方法的锁，可以执行方法内容；想要释放锁的时候就删除这条记录，其他线程就可以继续往数据库中插入数据获取锁
什么是触发器？触发器的使用场景有哪些? 触发器是用户定义在关系表上的一类由事件驱动的特殊的存储过程。触发器是指一段代码，当触发某个事件时，自动执行这些代码使用场景可以通过数据库中的相关表实现级联更改。实时监控某张表中的某个字段的更改而需要做出相应的处理。例如可以生成某些业务的编号。注意不要滥用，否则会造成数据库及应用程序的维护困难。大家需要牢记以上基础知识点，重点是理解数据类型CHAR和VARCHAR的差异，表存储引擎InnoDB和MyISAM的区别
MySQL中都有哪些触发器? 在MySQL数据库中有如下六种触发器： Before Insert After Insert Before Update After Update Before Delete After Delete
SQL 约束有哪几种？ NOT NULL: 用于控制字段的内容一定不能为空（NULL）。 UNIQUE: 控件字段内容不能重复，一个表允许有多个 Unique 约束。 PRIMARY KEY: 也是用于控件字段内容不能重复，但它在一个表只允许出现一个。 FOREIGN KEY: 用于预防破坏表之间连接的动作，也能防止非法数据插入外键列，因为它必须是它指向的那个表中的值之一。 CHECK: 用于控制字段的值范围
六种关联查询交叉连接（CROSS JOIN）内连接（INNER JOIN）外连接（LEFT JOIN/RIGHT JOIN）联合查询（UNION与UNION ALL）全连接（FULL JOIN）交叉连接（CROSS JOIN） SELECT * FROM A,B(,C)或者SELECT * FROM A CROSS JOIN B (CROSS JOIN C)#没有任何关联条件，结果是笛卡尔积，结果集会很大，没有意义，很少使用内连接（INNER JOIN）SELECT * FROM A,B WHERE A.id=B.id或者SELECT * FROM A INNER JOIN B ON A.id=B.id多表中同时符合某种条件的数据记录的集合，INNER JOIN可以缩写为JOIN
内连接分为三类等值连接：ON A.id=B.id 不等值连接：ON A.id > B.id 自连接：SELECT * FROM A T1 INNER JOIN A T2 ON T1.id=T2.pid 外连接（LEFT JOIN/RIGHT JOIN）左外连接：LEFT OUTER JOIN, 以左表为主，先查询出左表，按照ON后的关联条件匹配右表，没有匹配到的用NULL填充，可以简写成LEFT JOIN 右外连接：RIGHT OUTER JOIN, 以右表为主，先查询出右表，按照ON后的关联条件匹配左表，没有匹配到的用NULL填充，可以简写成RIGHT JOIN
varchar与char的区别 char的特点 char表示定长字符串，长度是固定的；如果插入数据的长度小于char的固定长度时，则用空格填充；因为长度固定，所以存取速度要比varchar快很多，甚至能快50%，但正因为其长度固定，所以会占据多余的空间，是空间换时间的做法；对于char来说，最多能存放的字符个数为255，和编码无关 varchar的特点 varchar表示可变长字符串，长度是可变的；插入的数据是多长，就按照多长来存储； varchar在存取方面与char相反，它存取慢，因为长度不固定，但正因如此，不占据多余的空间，是时间换空间的做法；对于varchar来说，最多能存放的字符个数为65532
索引有哪几种类型？主键索引: 数据列不允许重复，不允许为NULL，一个表只能有一个主键。唯一索引: 数据列不允许重复，允许为NULL值，一个表允许多个列创建唯一索引。可以通过 ALTER TABLE table_name ADD UNIQUE (column); 创建唯一索引可以通过 ALTER TABLE table_name ADD UNIQUE (column1,column2); 创建唯一组合索引普通索引: 基本的索引类型，没有唯一性的限制，允许为NULL值。可以通过ALTER TABLE table_name ADD INDEX index_name (column);创建普通索引可以通过ALTER TABLE table_name ADD INDEX index_name(column1, column2, column3);创建组合索引全文索引：是目前搜索引擎使用的一种关键技术。可以通过ALTER TABLE table_name ADD FULLTEXT (column);创建全文索引

网络

讲讲Nginx负载均衡
- 轮询、轮询是默认的，每一个请求按顺序逐一分配到不同的后端服务器，如果后端服务器down掉了，则能自动剔除
- ip_hash、个请求按访问IP的hash结果分配，这样来自同一个IP的访客固定访问一个后端服务器，有效解决了动态网页存在的session共享问题。
- weight、weight是设置权重，用于后端服务器性能不均的情况，访问比率约等于权重之比
- fair(第三方)、这是比上面两个更加智能的负载均衡算法。此种算法可以依据页面大小和加载时间长短智能地进行负载均衡，也就是根据后端服务器的响应时间来分配请求，响应时间短的优先分配。Nginx本身是不支持fair的，如果需要使用这种调度算法，必须下载Nginx的upstream_fair模块。
- url_hash(第三方)此方法按访问url的hash结果来分配请求，使每个url定向到同一个后端服务器，可以进一步提高后端缓存服务器的效率。Nginx本身是不支持url_hash的，如果需要使用这种调度算法，必须安装Nginx 的hash软件包。
正向代理，反向代理是什么？ 正向代理，也就是传说中的代理, 简单的说，我是一个用户，我访问不了某网站，但是我能访问一个代理服务器，这个代理服务器呢，他能访问那个我不能访问的网站，于是我先连上代理服务器，告诉他我需要那个无法访问网站的内容，代理服务器去取回来，然后返回给我。从网站的角度，只在代理服务器来取内容的时候有一次记录，有时候并不知道是用户的请求，也隐藏了用户的资料，这取决于代理告不告诉网站。 反向代理：结论就是，反向代理正好相反，对于客户端而言它就像是原始服务器，并且客户端不需要进行任何特别的设置。客户端向反向代理的命名空间(name-space)中的内容发送普通请求，接着反向代理将判断向何处(原始服务器)转交请求，并将获得的内容返回给客户端，就像这些内容原本就是它自己的一样。
Cookie和Session的区别 cookie和session都是用来跟踪浏览器用户身份的会话方式区别：
- cookie数据保存在客户端，session数据保存在服务器端。简单的说，当你登录一个网站的时候, 如果web服务器端使用的是session，那么所有的数据都保存在服务器上，客户端每次请求服务器的时候会发送当前会话的sessionid，服务器根据当前sessionid判断相应的用户数据标志，以确定用户是否登录或具有某种权限。由于数据是存储在服务器上面，所以你不能伪造。
- sessionid是服务器和客户端链接时候随机分配的. 如果浏览器使用的是cookie，那么所有的数据都保存在浏览器端，比如你登录以后，服务器设置了cookie用户名，那么当你再次请求服务器的时候，浏览器会将用户名一块发送给服务器，这些变量有一定的特殊标记。服务器会解释为cookie变量，所以只要不关闭浏览器，那么cookie变量一直是有效的，所以能够保证长时间不掉线。如果你能够截获某个用户的 cookie变量，然后伪造一个数据包发送过去，那么服务器还是认为你是合法的。所以，使用 cookie被攻击的可能性比较大。
如果设置了的有效时间，那么它会将 cookie保存在客户端的硬盘上，下次再访问该网站的时候，浏览器先检查有没有 cookie，如果有的话，就读取该 cookie，然后发送给服务器。如果你在机器上面保存了某个论坛 cookie，有效期是一年，如果有人入侵你的机器，将你的 cookie拷走，然后放在他的浏览器的目录下面，那么他登录该网站的时候就是用你的的身份登录的。所以 cookie是可以伪造的。当然，伪造的时候需要主意，直接copy cookie文件到 cookie目录，浏览器是不认的，他有一个index.dat文件，存储了 cookie文件的建立时间，以及是否有修改，所以你必须先要有该网站的 cookie文件，并且要从保证时间上骗过浏览器两个都可以用来存私密的东西，同样也都有有效期的说法,区别在于session是放在服务器上的，过期与否取决于服务期的设定，cookie是存在客户端的，过去与否可以在cookie生成的时候设置进去。 (1)cookie数据存放在客户的浏览器上，session数据放在服务器上 (2)cookie不是很安全，别人可以分析存放在本地的COOKIE并进行COOKIE欺骗,如果主要考虑到安全应当使用session (3)session会在一定时间内保存在服务器上。当访问增多，会比较占用你服务器的性能，如果主要考虑到减轻服务器性能方面，应当使用COOKIE (4)单个cookie在客户端的限制是3K，就是说一个站点在客户端存放的COOKIE不能3K。
csrf攻击是什么？常见的防御手段有什么？ 跨站点请求伪造 简单来说就是通过伪装成受信任用户的请求来利用受信任的网站 在用户信息通过验证后，网站A产生Cookie信息并返回给浏览器，此时用户登录网站A成功，可以正常发送请求到网站A；用户未退出网站A之前，在同一浏览器中，打开一个TAB页访问网站B；网站B接收到用户请求后，返回一些攻击性代码，并发出一个请求要求访问第三方站点A；浏览器在接收到这些攻击性代码后，根据网站B的请求，在用户不知情的情况下携带Cookie信息，向网站A发出请求。网站A并不知道该请求其实是由B发起的，所以会根据用户C的Cookie信息以C的权限处理该请求，导致来自网站B的恶意代码被执行防御手段：
- 验证HTTP Referer字段
- 在请求地址中添加token并验证
- 在HTTP头中自定义属性并验证
请说明一下http和https的区别 https协议要申请证书到ca，需要一定经济成本；2） http是明文传输，https是加密的安全传输；3）连接的端口不一样，http是80，https是443；4）http连接很简单，没有状态；https是ssl加密的传输，身份认证的网络协议，相对http传输比较安全
请讲一下浏览器从接收到一个URL，到最后展示出页面，经历了哪些过程 1.DNS解析 2.TCP连接 3.发送HTTP请求 4.服务器处理请求并返回HTTP报文 5.浏览器解析渲染页面

锁

悲观锁总是假设最坏的情况，每次去拿数据的时候都认为别人会修改，所以每次在拿数据的时候都会上锁，这样别人想拿这个数据就会阻塞直到它拿到锁（共享资源每次只给一个线程使用，其它线程阻塞，用完后再把资源转让给其它线程）。传统的关系型数据库里边就用到了很多这种锁机制，比如行锁，表锁等，读锁，写锁等，都是在做操作之前先上锁。Java中synchronized和ReentrantLock等独占锁就是悲观锁思想的实现
乐观锁总是假设最好的情况，每次去拿数据的时候都认为别人不会修改，所以不会上锁，但是在更新的时候会判断一下在此期间别人有没有去更新这个数据，可以使用版本号机制和CAS算法实现。乐观锁适用于多读的应用类型，这样可以提高吞吐量，像数据库提供的类似于write_condition机制，其实都是提供的乐观锁。在Java中java.util.concurrent.atomic包下面的原子变量类就是使用了乐观锁的一种实现方式CAS实现的
两种锁的使用场景从上面对两种锁的介绍，我们知道两种锁各有优缺点，不可认为一种好于另一种，像乐观锁适用于写比较少的情况下（多读场景），即冲突真的很少发生的时候，这样可以省去了锁的开销，加大了系统的整个吞吐量。但如果是多写的情况，一般会经常产生冲突，这就会导致上层应用会不断的进行retry，这样反倒是降低了性能，所以一般多写的场景下用悲观锁就比较合适。 读的多，冲突几率小，乐观锁。写的多，冲突几率大，悲观锁。

Docker

docker多层构建镜像的意义

最大的使用场景是将编译环境和运行环境分离

讲讲docker网络模式（bridge, host）

bridge: 默认的网络驱动模式。如果不指定驱动程序，bridge 便会作为默认的网络驱动模式。当应用程序运行在需要通信的独立容器 (standalone containers) 中时，通常会选择 bridge 模式
host：移除容器和 Docker 宿主机之间的网络隔离，并直接使用主机的网络。host 模式仅适用于 Docker 17.06+
overlay：overlay 网络将多个 Docker 守护进程连接在一起，并使集群服务能够相互通信。您还可以使用 overlay 网络来实现 swarm 集群和独立容器之间的通信，或者不同 Docker 守护进程上的两个独立容器之间的通信。该策略实现了在这些容器之间进行操作系统级别路由的需求
macvlan：Macvlan 网络允许为容器分配 MAC 地址，使其显示为网络上的物理设备。 Docker 守护进程通过其 MAC 地址将流量路由到容器。对于希望直连到物理网络的传统应用程序而言，使用 macvlan 模式一般是最佳选择，而不应该通过 Docker 宿主机的网络进行路由
none：对于此容器，禁用所有联网。通常与自定义网络驱动程序一起使用。none 模式不适用于集群服务

如何在一个自定义ip上运行docker容器？

dockerFile中最常见的指令是什么?

ADD和COPY的区别：

Docker的常用命今?

如何临时退出一个正在交互的容器的终端，而不终止它？

什么是docker-compose?

如何退出容器时候自动删除?

Kubenetes

简述Kubernetes和Docker的关系?
Kubernetes中的相关基础概念（deployment,service,pod,job等）
简述Kubernetes中Pod的健康检查方式

现场算法题

子集(78)

Tag: 位运算 / 回溯

题目要求

给你一个整数数组 nums ，数组中的元素互不相同 ，返回该数组所有可能的子集（幂集）

解集不能包含重复的子集，你可以按任意顺序返回解集

时间要求

15 min

输入输出示例

示例 1：输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：输入：nums = [0] 输出：[[],[0]]

提示

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

参考代码

func subsets(nums []int) [][]int {
    res := `make`([][]int, 0)
    length := len(nums)
    for position := 0; position < 1<<length; position++ {
        subset := `make`([]int, 0)
        for j:=0; j < length; j++ {
            if position&(1<<j) > 0 {
                subset = append(subset, nums[j])
            }
        }
        res = append(res, subset)
    }
    return res
}

TOP K(215)

Tag: 分治 / 堆

题目要求

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素

时间要求

20 min

输入输出示例

示例 1：输入: [3,2,1,5,6,4] 和 k = 2 输出: 5
示例 2：输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4

提示

1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104

参考代码

func findKthLargest(nums []int, k int) int {
    return quickSelect(nums, 0, len(nums)-1, k)
}

func quickSelect(nums []int, left, right, k int) int {
    if index := randomPartition(nums, left, right); index == k-1 {
        return nums[index]
    } else if index > k-1 {
        return quickSelect(nums, left, index-1, k)
    } else {
        return quickSelect(nums, index+1, right, k)
    }
}

func randomPartition(nums []int, left, right int) int {
    randomIndex := (left+right)>>1
    
    nums[randomIndex], nums[right] = nums[right], nums[randomIndex]
    pivot := nums[right]
    for i := left; i < right; i++ {
        if nums[i] > pivot {
            nums[i], nums[left] = nums[left], nums[i]
            left++
        }
    }
    nums[left], nums[right] = nums[right], nums[left]
    return left
}

口答算法题

判断一个链表是否有环，如何找到这个环的起点

给定一个单链表，只给出头指针h： 1、如何判断是否存在环？ 2、如何知道环的长度？

1、对于问题1，使用追赶的方法，设定两个指针slow、fast，从头指针开始，每次分别前进1步、2步。如存在环，则两者相遇；如不存在环，fast遇到NULL退出。 2、对于问题2，记录下问题1的碰撞点p，slow、fast从该点开始，再次碰撞所走过的操作数就是环的长度s。

设计一种数据结构

满足：push、pop、getLast、getmax

在单链表中如何用最快的方法找到中间元素？

快慢指针

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

题目解析

根据题目描述，由于加上了时间复杂度必须是 O(n) ，并且空间复杂度为 O(1) 的条件，因此不能用排序方法，也不能使用 map 数据结构。

程序员小吴想了一下午没想出来，答案是使用 位操作Bit Operation 来解此题。

将所有元素做异或运算，即a[1] ⊕ a[2] ⊕ a[3] ⊕ …⊕ a[n]，所得的结果就是那个只出现一次的数字，时间复杂度为O(n)。

异或

异或运算A ⊕ B的真值表如下：

AB⊕FFFFTTTFTTTF

动画演示

有一个 n 个元素的数组，除了两个数只出现一次外，其余元素都出现两次，让你找出这两个只出现一次的数分别是几，要求时间复杂度为 O(n) 且再开辟的内存空间固定(与 n 无关)。

示例 :

输入: [1,2,2,1,3,4] 输出: [3,4]

题目再解析

根据前面找一个不同数的思路算法，在这里把所有元素都异或，那么得到的结果就是那两个只出现一次的元素异或的结果。

然后，因为这两个只出现一次的元素一定是不相同的，所以这两个元素的二进制形式肯定至少有某一位是不同的，即一个为 0 ，另一个为 1 ，现在需要找到这一位。

根据异或的性质 任何一个数字异或它自己都等于 0，得到这个数字二进制形式中任意一个为 1 的位都是我们要找的那一位。

再然后，以这一位是 1 还是 0 为标准，将数组的 n 个元素分成两部分。

将这一位为 0 的所有元素做异或，得出的数就是只出现一次的数中的一个
将这一位为 1 的所有元素做异或，得出的数就是只出现一次的数中的另一个。

这样就解出题目。忽略寻找不同位的过程，总共遍历数组两次，时间复杂度为O(n)。

动画再演示

两个水杯的问题

题目描述

有一种玻璃杯从一栋100层的大楼扔下，该种玻璃杯超过某一层楼会摔碎。现在给你两个杯子，问确定最低摔碎的楼层需要摔多少次？

题目分析

这道题的假设是：最低摔碎的楼层可能是每一层楼，且概率相同。我们需要找一种方法，使得定位到[1-100]之间的任意一个数都是快速的。

解题思路

最简单的方法是用一个杯子从第一层开始，不断一层层的往上试。但是这样的时间复杂度是O(n)。直觉也告诉我们想放大步子扔。

因为我们有两个杯子，可以考虑成一个杯子Cup1不断扔直到破碎，它用来确定最低摔碎的楼层在什么范围，

另一个杯子Cup2再此基础上一层层的扔。用来准确确定最低摔碎的楼层是多少。如果凭空想象，我们可能会想到二分法，每次隔5个楼层扔，10个楼层扔…

可是我们马上也应该会想到这么分的不妥之处在于：

确定最低摔碎的楼层所需次数是不均匀分布的。

我们再来看：每次扔的楼层间隔会带来什么影响？

确定最低摔碎的楼层：

总次数 = Cup1扔的次数 + Cup2扔的次数

楼层间隔越大，Cup2需要扔的次数越多。

相同楼层间隔下：最低摔碎的楼层越高，Cup1需要扔的次数越多，Cup2需要扔的次数可认为相同。

我们的目的其实是需要尽可能保证：不管最低摔碎的楼层是第一层还是第99层，扔的总次数都尽可能一致且减少。

如果小伙伴有看我上篇文章中LSMT分层步隆过滤器的实现，有没有受到启发？

这里我们可以使Cup1需要扔的楼层间隔递减，这样可改善高楼层所需Cup1/Cup2扔的次数。

假设第一次扔的楼层间隔为X，此后依次递减1层，直到楼层间隔为2.则： x+(x-1)+(x-2)+…+2 >=100

求解出答案为14。

如何得到一个数据流中的中位数？

数据是从一个数据流中读出来的，数据的数目随着时间的变化而增加。如果用一个数据容器来保存从流中读出来的数据，当有新的数据流中读出来时，这些数据就插入到数据容器中。

如果从数据流中读出奇数个数值，那么中位数就是所有值排序之后位于中间的数值。如果数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

数组是最简单的容器。如果数组没有排序，可以用 Partition 函数找出数组中的中位数。在没有排序的数组中插入一个数字和找出中位数的时间复杂度是 O(1)和 O(n)。

我们还可以往数组里插入新数据时让数组保持排序，这是由于可能要移动 O(n)个数，因此需要 O(n)时间才能完成插入操作。在已经排好序的数组中找出中位数是一个简单的操作，只需要 O(1)时间即可完成。

排序的链表时另外一个选择。我们需要 O(n)时间才能在链表中找到合适的位置插入新的数据。如果定义两个指针指向链表的中间结点（如果链表的结点数目是奇数，那么这两个指针指向同一个结点），那么可以在 O（1）时间得出中位数。此时时间效率与及基于排序的数组的时间效率一样。

思路：

如果能够保证数据容器左边的数据都小于右边的数据，这样即使左、右两边内部的数据没有排序，也可以根据左边最大的数及右边最小的数得到中位数。如何快速从一个容器中找出最大数？用最大堆实现这个数据容器，因为位于堆顶的就是最大的数据。同样，也可以快速从最小堆中找出最小数。因此可以用如下思路来解决这个问题：用一个最大堆实现左边的数据容器，用最小堆实现右边的数据容器。往堆中插入一个数据的时间效率是O(logn).由于只需O(1)时间就可以得到位于堆顶的数据，因此得到中位数的时间效率是O(1).

接下来考虑用最大堆和最小堆实现的一些细节。首先要保证数据平均分配到两个堆中，因此两个堆中数据的数目之差不能超过1（为了实现平均分配，可以在数据的总数目是偶数时把新数据插入到最小堆中，否则插入到最大堆中）。还要保证最大堆中里的所有数据都要小于最小堆中的数据。当数据的总数目是偶数时，按照前面分配的规则会把新的数据插入到最小堆中。如果此时新的数据比最大堆中的一些数据要小，怎么办呢？

可以先把新的数据插入到最大堆中，接着把最大堆中的最大的数字拿出来插入到最小堆中。由于最终插入到最小堆的数字是原最大堆中最大的数字，这样就保证了最小堆中的所有数字都大于最大堆中的数字。

当需要把一个数据插入到最大堆中，但这个数据小于最小堆里的一些数据时，这个情形和前面类似。

编程题

协程池

原生实现一个协程池package，使用者应能使用该协程池package并发完成自己输入的一系列自定义任务（要求解耦，即协程池本身和自定义任务完全无关）

示例：

输入任务列表（以下仅为伪代码，具体任务的数据结构请自行设计）

[(“fibonacci”, 6), (“padovan”, 11), (“js_error_rate”, {“pv”: 30627846, “js_error_num”: 78456})]

使用者应能基于自定义的handler完成并发任务（上述任务分别是斐波那契数列的第n个数、巴都万数列的第n个数、计算js_error率），得到以下输出：

8, 12, 0.002562

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-01-10，如有侵权请联系 cloudcommunity@tencent.com 删除

云服务器

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！