程序员面试经常会遇到的面试题

发表于 更新于 分类于 ， Changyan： 本文字数： 4k 阅读时长 ≈ 15 分钟

无论何种编程语言算法和代码逻辑是相同的，不同的只是语法，本文计划收集面试中常会提到的算法或者算法的变种。

求最大质数

求某个数字范围内的最大质数。关于质数的介绍我们在学校数学课上都已经学过了，而且在rsa非对称加密数学计算原理剖析文章中也详细介绍了什么是质数，因数、互质数之类的。

先理下逻辑，肯定是要一个嵌套循环，外循环负责取出每个数字，内循环依次使用外循环取出的数字去跟比这个数字小的每个数去取余，如果余数为0，则证明这个数可以被其他数整除，可以跳过本次外循环了，继续下个数字进行一次取余。

可能文字看起来让人更懵了，那我们拿个小的数字做下演示就明白了了。

python正向查质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 定义一个列表存放4以内的所有质数
arr = []
# 比如我们取4以内的最大质数
num = 4
# 外循环取出每个数字
for i in range(2, num+1):
	# 内循环取出比当前数字小的所有数字，依次与当前数字进行取余操作
	for j in range(2, i):
		# 进行取余操作，如果余数为0则代表当前数字可以被其他数字整除，即不为质数，直接终止当前内循环，进行下个数字的比较
		if i%j == 0:
			break
	else:
		# 当前内循环走完依然没有被break掉，证明当前数字不能被整除，我们将其放在数组中
		arr.append(i)
print(arr)
print(max(arr))

# 输出结果：
# [2, 3]
# 3

# 即：4以内的最大质数为3

上面的方式走了两个步骤，先取出4以内的所有质数；在所有质数列表中获取最大值。

python反向查质数

上面的代码我们是否可以优化一下？我们发现正向的话需要取出所有的质数列表，如果我们反向呢？那第一个质数不就是最大的质数了吗？上面的代码我们只需要改变一小部分既可实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 比如我们取4以内的最大质数
num = 4
# 外循环取出每个数字（反向：4，3，2）
for i in range(num, 1, -1):
	# 内循环取出比当前数字小的所有数字，依次与当前数字进行取余操作
	for j in range(2, i):
		# 进行取余操作，如果余数为0则代表当前数字可以被其他数字整除，即不为质数，直接终止当前内循环，进行下个数字的比较
		if i%j == 0:
			break
	else:
		# 当前内循环走完依然没有被break掉，证明当前数字不能被整除，即当前是数字就是质数，另外我们是倒序查找的，所以肯定是最大的质数，也许往后循环再判断了，直接break掉。
		print(i)
		break

# 输出结果：
# 3

# 即：4以内的最大质数为3

php反向查质数

不是所有的语言都可以使用for else的，php就是，我遇到的刚好也是php，正向相对复杂，我这里直接用反向了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 比如我们取4以内的最大质数
$num = 4
# 外循环取出每个数字（反向：4，3，2）
for($i=$num, $i>1, $i--){
  # 标识当前数字能否被整除
  $status = true;
  # 内循环取出比当前数字小的所有数字，依次与当前数字进行取余操作
  for($j=1, $j<i, $j++){
    # 进行取余操作，如果余数为0则代表当前数字可以被其他数字整除，即不为质数，修改能否被整除的标识，然后直接终止当前内循环，进行下个数字的比较
    if($i%$j == 0){
      $status = false;
      break;
    }
  }
  # 当前内循环走完status依然等于0，证明当前数字不能被整除，即当前是数字就是质数，另外我们是倒序查找的，所以肯定是最大的质数，也许往后循环再判断了，直接break掉。
  if($status){
    echo "当前最大质数为：".$i;
    break;
  }
}


# 输出结果：
# 3

# 即：4以内的最大质数为3

可变类型参数

python不可变类型有Number（数字）、String（字符串）、Tuple（元组）；可变类型有Set（集合）、List（列表）、Dictionary（字典）。

不可变数据类型

当该数据类型的对应变量的值发生了改变，那么它对应的内存地址也会发生改变，对于这种数据类型，就称不可变数据类型。

我们就拿string字符串为例，x在修改后，它的内存地址也变了，所以字符串就是不可变的数据类型

1
2
3
4
5
6
7
8
9
10
x = 3
print("x的原始内存地址：", id(x))
print("数字3的内存地址：", id(x))
x = 8
print("x修改后的内存地址：", id(x))

# 输出
x的原始内存地址： 4475747664
数字3的内存地址： 4475747664
x修改后的内存地址： 4475747824

可变数据类型

当该数据类型的对应变量的值发生了改变，那么它对应的内存地址不发生改变，对于这种数据类型，就称可变数据类型。

我们拿列表为例，可以看到不管是我们增加还是修改它，它的内存地址没有发生改变，所以列表就是可变的数据类型

1
2
3
4
5
6
7
8
9
lis = [3, 4, 6]
print("lis的原始内存地址：", id(lis))
lis.append(8)
lis[1] = 9
print("lis修改后的内存地址：", id(lis))

# 输出
lis的原始内存地址： 4397477056
lis修改后的内存地址： 4397477056

面试题

列表作为函数参数,写出代码最后的打印结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def func(a, b=[]):
    b.append(a)
    return b


a = func(3)
b = func(4, [])
c = func(6)
print(a)
print(b)
print(c)

# 输出结果：
[3, 6]
[4]
[3, 6]

结果你想到了吗？我们在函数内部打印下b修改前后的内存id来看下就明白了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def func(a, b=[]):
    print("修改为%s前b的内存地址为：%s" % (a, id(b)))
    b.append(a)
    print("修改为%s后b的内存地址为：%s" % (a, id(b)))
    return b


a = func(3)
b = func(4, [])
c = func(6)
print(a, id(a))
print(b, id(b))
print(c, id(c))

# 输出结果：
修改为3前b的内存地址为：4370013440
修改为3后b的内存地址为：4370013440
修改为4前b的内存地址为：4370019968
修改为4后b的内存地址为：4370019968
修改为6前b的内存地址为：4370013440
修改为6后b的内存地址为：4370013440
[3, 6] 4370013440
[4] 4370019968
[3, 6] 4370013440

在第一次函数被调用a = func(3)，内存里已经为b开辟了一块内存空间，所有后面b的值如果有更改，它的内存地址一样不会改变的；而b = func(4, [])相当于一个新数组，开辟了一个新的内存空间，所以它不受前后被调用函数的影响,如果这行代码还是不理解的话我们可以更换下代码就明白了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def func(a, b=[]):
    print("修改为%s前b的内存地址为：%s" % (a, id(b)))
    b.append(a)
    print("修改为%s后b的内存地址为：%s" % (a, id(b)))
    return b


l = ['x', 'y', 'z']
print("修改前l的内存地址为：%s" % id(l))
a = func(3)
b = func(4, l)
l.append('s')
c = func(6)
print("修改后l的内存地址为：%s" % id(l))
print(a, id(a))
print(b, id(b))
print(c, id(c))

# 输出结果
修改前l的内存地址为：4404205120
修改为3前b的内存地址为：4404198592
修改为3后b的内存地址为：4404198592
修改为4前b的内存地址为：4404205120
修改为4后b的内存地址为：4404205120
修改为6前b的内存地址为：4404198592
修改为6后b的内存地址为：4404198592
修改后l的内存地址为：4404205120
[3, 6] 4404198592
['x', 'y', 'z', 4, 's'] 4404205120
[3, 6] 4404198592

我们这次传入了数组l，不适用空数组了，而且我们是在l被赋值给函数后做的修改，结果依然影响了函数内部的返回结果。打印结果中也可以看出，l的内存地址为函数内部b的内存地址一致。

同理如果换成是字典呢？都是可变类型的，当然执行的逻辑也是相同的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def func(a, b={}):
    print("开始：", id(b))
    b[a] = a
    print("结束：", id(b))
    return b
a = func(3)
b = func(4, {})
c = func(6)
print(a, b, c)

# 结果：
开始： 4481035584
结束： 4481035584
开始： 4481035648
结束： 4481035648
开始： 4481035584
结束： 4481035584
{3: 3, 6: 6} {4: 4} {3: 3, 6: 6}

类成员方法中的参数添加至类成员属性列表中

其结果跟函数也是类似的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Obj:
    items = []
    def set_items(self, option):
        self.items.append(option)

o1 = Obj()
o2 = Obj()
o1.set_items(666)
o1.set_items('Tony')
o2.set_items('你好世界')
print(o1.items, o2.items, Obj.items)

# 输出结果
[666, 'Tony', '你好世界'] [666, 'Tony', '你好世界'] [666, 'Tony', '你好世界']

求列表中只出现过一次的元素

从[2, 3, 4, 5, 2, 3, 5, 6, 7]取出只出现过一次的元素

使用count

使用列表方法count直接统计

直接for循环

1
2
3
4
5
6
lis = [2, 3, 4, 5, 2, 3, 5, 6, 7]
res = []
for i in lis:
  	# 如果当前元素在列表中出现的次数1则证明只出现过一次
    if lis.count(i) == 1:
        res.append(i)

列表推导式

1
2
lis = [2, 3, 4, 5, 2, 3, 5, 6, 7]
res = [i for i in lis if lis.count(i) == 1]

使用filter

filter匿名函数

1
2
3
4
5
lis = [2, 3, 4, 5, 2, 3, 5, 6, 7]
# filter返回值为迭代器
res = filter(lambda x: lis.count(x) == 1, lis)
# 迭代器转为列表
res = list(res)

filter回调函数

1
2
3
4
5
6
7
lis = [2, 3, 4, 5, 2, 3, 5, 6, 7]
def func(x):
    return lis.count(x)==1
# filter返回值为迭代器
res = filter(func, lis)
# 迭代器转为列表
res = list(res)

使用列表（错误演示）

其实上述的count为内置函数，大多数情况下其实面试官是不让你用的，就是考你的算法，结果你直接用内置好的算法解决了，就考察不出来你的水平了。

1
2
3
4
5
6
7
8
9
10
11
lis = [2, 3, 4, 5, 2, 3, 5, 6, 7]
# 空列表用来接收只出现一次的元素
res = []
# 循环该列表
for i in lis:
		如果该元素已经在结果列表中，证明出现的次数不止一次了，直接删除；否则添加该元素到结果列表中
    if i in res:
        res.remove(i)
    else:
        res.append(i)
print(res)

运行也没有出问题，但是自己检查下代码你会发现疑问，代码中执行过程为遇见结果中包含的元素了，证明是第二次遇到，好我把它删了，如果这个元素重复了3次或者说是奇数次呢？第二次删除后，第三次又循环到该元素，好嘛结果列表中没有该元素了，证明该元素也是第一次出现，这合理吗？

使用扩展包

collections.Counter的作用为计算出可迭代对象中每个元素出现的次数

1
2
3
4
5
6
7
8
9
10
11
12
import collections
lis = [2, 3, 4, 5, 2, 3, 5, 6, 7]
# 存放结果
res = []
# 计算列表中每个元素出现的次数，返回值为字典，选项为每个元素及对应出现的次数
dic = collections.Counter(lis)
# Counter({2: 2, 3: 2, 5: 2, 4: 1, 6: 1, 7: 1})
for key, val in dic.items():
    # 如果该元素对应的值小于2证明只出现了一次，取出
    if val < 2:
        res.append(key)
print(res)

使用字典

1
2
3
4
5
6
7
8
9
10
11
12
13
14
lis = [2, 3, 4, 5, 2, 3, 5, 6, 7]
# 用来存放最终只出现过1次的元素
res = []
# 由于字典键的唯一性，我们使用字典存放每个元素出现的次数，初始都为0
dic = dict.fromkeys(lis, 0)
# 循环列表，为当前元素对应字典键的值+1
for i in lis:
    dic[i] += 1
# 循环字典
for i in dic:
    # 该元素对应的值为1则抛出
    if dic[i] == 1:
        res.append(i)
print(res)

以上代码我们想想还有优化的地方吗？当然是有的，循环列表的时候，当字典中当前元素对应的值大于1的时候，我们直接删除字典中的这一项，后面对于循环字典不是效率更好了吗？优化后的代码看似代码更多了，但是效率却更高了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
lis = [2, 3, 4, 5, 2, 3, 5, 6, 7]
# 用来存放最终只出现过1次的元素
res = []
# 由于字典键的唯一性，我们使用字典存放每个元素出现的次数，初始都为0
dic = dict.fromkeys(lis, 0)
# 循环列表，为当前元素对应字典键的值+1
for i in lis:
  	# 当该元素在字典中对应的值已经为1时，则证明当前元素出现的次数一定大于1了，直接在字典中删除该元素的计数
  	if dic[i] == 1:
      del dic[i]
    else:
    	dic[i] += 1
# 循环字典
for i in dic:
    # 该元素对应的值为1则抛出
    if dic[i] == 1:
        res.append(i)
print(res)

高级进阶(异或，位运算)

这个算法只针对于列表中只有一个只出现一次的元素，多个只出现1次的元素则无效了，另外重复元素的重复次数也只能是2次或者偶数次

相同的数字异或的结果是0：2^2=0;和0异或是本身：0^2=2。

我们来看下关于位移或运算符官方的解释：

按位异或运算符：当两对应的二进位相异时，结果为1 ；相同则为0；

其实从概念中就可以理解了，相同的为0，相异为1，如果列表是[1, 2, 1, 4, 6, 4, 6]，那么1相同抵消为0了，4抵消为0，6抵消为1，就只剩下2了

1
2
3
4
5
6
alist = [1, 2, 1, 4, 6, 4, 6]
a = 0
for i in alist:
  # 循环列表，依次进行2进制比较
	a ^= i
print("a:", a)

我们拿2进制演示一个简单的数组[2, 3, 3, 4, 2]

为了便于计算，我们将上述数组都转为3位数的2进制

转换后依次为：[010, 011, 011, 100, 010]我们开始循环计算

第一轮计算：

相同为0， 相异为1

010

011

结果为：001

第二轮计算：

001

011

结果为：010

第三轮计算：

010

100

结果为：110

第四轮计算：

110

010

结果为：100

转为10进制，即为4，所以只出现奇数次的为4

求列表中的偶数元素

从[2, 3, 4, 5, 2, 3, 5, 6, 7]取出偶数元素

直接for循环

1
2
3
4
5
6
lis = [2, 3, 4, 5, 2, 3, 5, 6, 7]
res = []
for i in lis:
  	# 如果当前元素取余2等于0，则证明该元素为偶数
    if i%2==0:
        res.append(i)

列表推导式

本人之前面试直接用的for循环，面试官让用推导式写，本人刚开始写的是[i for i in lis : i%2==0]，条件和循环之间用了冒号。

1
2
3
lis = [2, 3, 4, 5, 2, 3, 5, 6, 7]
# 列表推导式中循环和条件之间使用if，
res = [i for i in lis if i%2==0]

使用filter

filter匿名函数

1
2
3
4
5
lis = [2, 3, 4, 5, 2, 3, 5, 6, 7]
# filter返回值为迭代器
res = filter(lambda x: lis.count(x) == 1, lis)
# 迭代器转为列表
res = list(res)

filter回调函数

其实面试的时候很多都是面试的基础的东西，在上述面试官让用推导式写好后又让用filter，本人基础不太上心，大概记得大部分内置函数都是调用了一个回调函数。

1
2
3
4
5
6
7
lis = [2, 3, 4, 5, 2, 3, 5, 6, 7]
def func(x):
    return lis.count(x)==1
# filter返回值为迭代器
res = filter(func, lis)
# 迭代器转为列表
res = list(res)

本人当时直接filter(func(x), lis)了， 好低级的错误，带括号就是执行了啊，长点心吧。