2020 年最全 Python 面试题汇总 (三)

举报
毛利 发表于 2021/07/15 03:02:10 2021/07/15
【摘要】 @Author:Runsen 求职季在即,技巧千万条,硬实力才是关键,听说今年疫情大环境不好,更要好好准备才行。于是Runsen在牛客网,Leetcode,九章算法,不断地寻找面试真题,共计100题,包括Python基础,算法,数据库,SQL,Linux。 大四刷题拼offer系列,不拼不行啊。我先刷下牛客网的Python的题目和知识点,适当的记录下自己做 错的题目...

@Author:Runsen

求职季在即,技巧千万条,硬实力才是关键,听说今年疫情大环境不好,更要好好准备才行。于是Runsen在牛客网,Leetcode,九章算法,不断地寻找面试真题,共计100题,包括Python基础,算法,数据库,SQL,Linux。

大四刷题拼offer系列,不拼不行啊。我先刷下牛客网的Python的题目和知识点,适当的记录下自己做
错的题目。然后刷Java面试题。

41、查找最晚入职员工的所有信息

这个题目的是入门的水平,就是目前所有的数据里员工入职的日期都不是同一天(sqlite里面的注释为–,在mysql中为comment)

CREATE TABLE `employees` (
`emp_no` int(11) NOT NULL,  -- '员工编号'
`birth_date` date NOT NULL,
`first_name` varchar(14) NOT NULL,
`last_name` varchar(16) NOT NULL,
`gender` char(1) NOT NULL,
`hire_date` date NOT NULL,
PRIMARY KEY (`emp_no`));

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

其实就是有一个员工表,查找最晚入职员工的所有信息。

很简单直接降序:select * from employees order by hire_date desc limit 1

还有一种方法激素使用子查询,针对的是最后一天的时间有多个员工信息:select * from employees where hire_date = (select max(hire_date) from employees);

42、查找入职员工时间排名倒数第三的员工所有信息

这个题目和上面变了,现在寻找倒数第三。那么就使用limit+offset 。offset 就是区间长度的意思,可以是一个数,也可以是一个区间,记得是从0开始,和Python列表完全一样。

下面举几个limit+offset 的示例。

以下的两种方式均表示取2,3,4三条条数据。
1.select* from test LIMIT 1,3;
当limit后面跟两个参数的时候,第一个数表示要跳过的数量,后一位表示要取的数量。

2.select * from test LIMIT 3 OFFSET 1;(在mysql 5以后支持这种写法)
当 limit和offset组合使用的时候,limit后面只能有一个参数,表示要取的的数量,offset表示要跳过的数量 。

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

查找入职员工时间排名倒数第三的员工所有信息的SQl代码:select * from employees order by hire_date desc limit 1 offset 2

43、Leetcode175. 组合两个表

表1: Person
+-------------+---------+
| 列名 | 类型 |
+-------------+---------+
| PersonId | int |
| FirstName   | varchar |
| LastName | varchar |
+-------------+---------+
PersonId 是上表主键

表2: Address

+-------------+---------+
| 列名 | 类型 |
+-------------+---------+
| AddressId   | int |
| PersonId | int |
| City | varchar |
| State | varchar |
+-------------+---------+
AddressId 是上表主键
编写一个 SQL 查询,满足条件:无论 person 是否有地址信息,都需要基于上述两表提供 person 的以下信息:

FirstName, LastName, City, State


  
 
  • 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

在Leetcode这题有一个要求:无论 person 是否有地址信息,都需要基于上述两表提供 person 的以下信息。其实这就是左连接。

select FirstName,LastName,City,State from Person left join Address on Person.PersonId = Address.PersonId

44、Leetcode176 第二高的薪水

编写一个 SQL 查询,获取 Employee 表中第二高的薪水(Salary) 。
+----+--------+
| Id | Salary |
+----+--------+
| 1  | 100 |
| 2  | 200 |
| 3  | 300 |
+----+--------+
例如上述 Employee 表,SQL查询应该返回 200 作为第二高的薪水。如果不存在第二高的薪水,那么查询应返回 null。

+---------------------+
| SecondHighestSalary |
+---------------------+
| 200 |
+---------------------+


  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

首先考虑选取最高工资的, 然后再选取次高, 其中用到了嵌套

SELECT max(Salary) AS SecondHighestSalary FROM Employee WHERE Salary < (SELECT MAX(Salary) FROM Employee);

  
 
  • 1

用order BY 排序,再LIMIT output,输出更加快。

SELECT max(Salary) AS SecondHighestSalary FROM Employee WHERE Salary < (SELECT Salary
FROM Employee ORDER BY Salary DESC LIMIT 1);

  
 
  • 1
  • 2

最好的方法就是使用ifnull + limit + offset

ifnull(expression,value)

  • 当expression获得数据为空的时候,返回value,有点类似python的 dict.get(x,value)的形式,即当一个查询没有对应的值的时候,返回一个默认值,这个默认值可以自定义

limit x offset y

  • 跳过y条记录,返回x条记录

order by xx

  • 这个就是按照xx字段排序,后面可以用desc/asc指定是降序还是升序

  • 那么,综合以上,就是要按照Salary字段排序且按降序排序,并跳过排序结果的第一条,再返回一条

  • 因为是跳过了降序排序结果的第一条,再返回一条,那么返回的就是第二高的记录

  • 并用ifnull函数控制查询结果为空的时候的返回结果

select ifnull((select distinct Salary from Employee order by Salary desc limit 1 offset 1),null) as SecondHighestSalary

45、Leetcode 177. 第N高的薪水


编写一个 SQL 查询,获取 Employee 表中第 n 高的薪水(Salary)。

+----+--------+
| Id | Salary |
+----+--------+
| 1  | 100 |
| 2  | 200 |
| 3  | 300 |
+----+--------+
例如上述 Employee 表,n = 2 时,应返回第二高的薪水 200。如果不存在第 n 高的薪水,那么查询应返回 null。

+------------------------+
| getNthHighestSalary(2) |
+------------------------+
| 200 |
+------------------------+


  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

代码逻辑基本和上一题的一样,就是多了一个判断的条件。

CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
  if N<0 then RETURN (select min(Salary) from Employee);
  else set N = N-1; RETURN ( # Write your MySQL query statement below. select ifnull((select distinct Salary from Employee order by Salary desc limit N,1),null) as NthHighestSalay );
  end if;
END

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

46、将二维数组合并成一维数组

extend这个需要和append区别开来。extend将二维数组合并成一维数组,很多人不知道的。

lst = [[1,2,3],[4,5,6],[7,8,9]]
ll=[]
for l in lst: # ll+=l ll.extend(l)
print(ll)

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

在这里提供内置的方法chain

from itertools import chain
list(chain.from_iterable(lst))

  
 
  • 1
  • 2

47、将字典的values进行排序

将列表alist=[{'name':'a','age':25},{'name':'b','age':30},{'name':'c','age':20}],按照age的值从大到小排列。

alist=[{'name':'a','age':25},{'name':'b','age':30},{'name':'c','age':20}]
blist=sorted(alist,key=lambda x:x['age'],reverse=True)
print(blist)
# [{'name': 'b', 'age': 30}, {'name': 'a', 'age': 25}, {'name': 'c', 'age': 20}]

  
 
  • 1
  • 2
  • 3
  • 4

48、两个元组或者列表合并成字典

写代码:如何由tuple1=('a','b','c','d','e'),和tuple2=(1,2,3,4,5)得到res={'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}

tuple1=('a','b','c','d','e')
tuple2=(1,2,3,4,5)
res=dict(zip(tuple1,tuple2))
print(res)
# {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5

49、字符串的排列组合

面试中常见到:输入一个字符串,输出该字符串的字符的所有组合。如输入'abc',输出["abc","acb","bac","bca","cab","cba"].

字符串的排列组合 II其实本身就是一个回溯算法的一个例子。

def permutation(s): if len(s) == 1: return [s] res = [] for i, x in enumerate(s): n = s[:i] + s[i+1:] for y in permutation(n): res.append(x+y) return list(set(res))
print(permutation('abc'))

# ['bca', 'abc', 'acb', 'cba', 'cab', 'bac']

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

下面是Python中itertools内置的做法,一行代码就可以搞定

import itertools
print(list(set([''.join(x) for x in list(itertools.permutations(list('abc')))])))

# ['bca', 'abc', 'acb', 'cba', 'cab', 'bac']

  
 
  • 1
  • 2
  • 3
  • 4

补充下:对于组合,有两个自带的方法:itertools.combinations和 itertools.combinations_with_replacement,其中前者不放回抽取,后者为放回抽取。

In [15]: print(list(set([''.join(x) for x in list(itertools.combinations_with_replacement('abcd',3))])))
['acd', 'abc', 'aaa', 'bbb', 'acc', 'aac', 'cdd', 'bbc', 'abd', 'ccd', 'add', 'bdd', 'bcd', 'aad', 'ddd', 'bcc', 'aab', 'bbd', 'abb', 'ccc']

In [16]: print(list(set([''.join(x) for x in list(itertools.combinations('abcd',3))])))
['acd', 'bcd', 'abc', 'abd']

  
 
  • 1
  • 2
  • 3
  • 4
  • 5

上面的题目其实是Leetcode上第46题全排列的。

50、数组的排列组合 II

上面一题是全排列的,这题是Leetcode的第78题子集问题。

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

如果直接用Python内置的itertools,代码非常简单。

import itertools

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res = [] for i in range(len(nums)+1): # 不放回抽取 for tmp in itertools.combinations(nums, i): res.append(tmp) return res

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

这题更多的考察的是回溯算法,原理是一条路黑到底。

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res = [[]] for i in nums: res = res + [[i] + num for num in res] return res

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

51、寻找完数

一个数如果恰好等于它的因子之和,这个数就称为‘完数’,比如6=1+2+3,下面编程找出10000以内的所有的完数。

wanshu=[]
for i in range(1,10001): s=0 for j in range(1,i//2+1): if i % j ==0: s+=j else: if i==s: wanshu.append(i)
print(wanshu)
# [6, 28, 496, 8128]

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

52、压缩字符串

a='aaabbcccdddde'这种形式的字符串,压缩成a3b2c3d4e1这种形式。’

a='aaabbcccdddde'
aa=''
for i in sorted(list(set(a)),key=a.index): aa=aa+i+str(a.count(i))
print(aa)
# a3b2c3d4e1

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

53、腾讯校招压缩算法

这是腾讯2020校招后端的算法题题目链接

题目:小Q想要给他的朋友发送一个神秘字符串,但是他发现字符串的过于长了,于是小Q发明了一种压缩算法对字符串中重复的部分进行了压缩,对于字符串中连续的m个相同字符串S将会压缩为m|S,例如字符串ABCABCABC将会被压缩为[3|ABC],现在小Q的同学收到了小Q发送过来的字符串,你能帮助他进行解压缩么?

输入例子1:
HG[3|B[2|CA]]F

输出例子1:
HGBCACABCACABCACAF

例子说明1:
HG[3|B[2|CA]]F−>HG[3|BCACA]F−>HGBCACABCACABCACAF

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

思路是使用遍历,但就是找到]的index,就是break,同时储存前面的[的index,和|的index,这样就不断地进行递归解码,直到一个中括号都没有。

def decode(s): i = 0 x, y, z = -1, -1, -1 while i < len(s): if s[i] == '[': x = i elif s[i] == '|': y = i elif s[i] == ']': z = i break i += 1 if x != -1 and y != -1 and z != -1: times = int(s[x + 1:y])  # 次数 sub = s[y + 1:z]  # 子串 decode_str = s[:x] + times * sub + s[z + 1:]  # 解码 return decode(decode_str)  # 递归解码 return s  # 如果一个中括号都没有,说明没有需要解码的部分


if __name__ == '__main__': s = input() print(decode(s))


  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

54、数位之积

数位之积这题是vivo的校招题,题目链接

题目是这样的:现给定任意正整数 n,请寻找并输出最小的正整数 m(m>9),使得 m 的各位(个位、十位、百位 … …)之乘积等于n,若不存在则输出 -1。

输入
36
输出
49
# 36=4*9

  
 
  • 1
  • 2
  • 3
  • 4
  • 5

对于小于10的数n,输出1n。
对于大于10的数,需要分解为若干个个位数之积,数字的个数尽可能少。这个数字可以分解为以9,8,…,2的因子之积。然后从小到大输出即可。

class Solution: def solution(self, n): # write code here if n < 10: return 10+ n else: result, nums = 0, 1 for i in range(9, 1, -1): while n % i == 0: result = result + i * nums n /= i nums *= 10 if n != 1: return -1 else: return result

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

55、数位重排

数位重排:题目链接

输入包括t+1行,第一行包括一个整数t (1 ≤ t ≤ 10),

接下来t行,每行一个整数x (1 ≤ x ≤ 10^6)

输出描述:
对于每个x,如果可能重排之后变为自己的倍数输出"Possible", 否则输出"Impossible".

'''
输入
2
14  
1035
输出
Impossible #41 不是14的倍数
Possible #3015是1035的倍数
'''

import itertools
t = int(input())
# 题目要求使用x的原始数字重排,即重排后的位数等于x的位数,即只需判断x的2到9倍中的数是否存在由x重排得到的数
def f(s): x = itertools.permutations(s) for n in x: for k in range(2,10): a = "".join(list(n)) if int(a) == (k*int(s)): return "Possible" return "Impossible"
i = 0
while i < t: s = input() print(f(s)) i = i + 1

  
 
  • 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

56、标准二分法

二分查找算法是在面试题中出现的频率很高的,特别是二分法的四个变种问题。二分查找算法的条件需要有序的,所以只要题目中出现有序的数组八成就是二分,或者先是一个无序,然后通过快排再进行二分。

下面是一个标准的二分算法。

'''
@Author: Runsen
标准的二分查找
'''

a = [1, 2,4, 5, 8,10,11,16]
def bsearch(a,value): low = 0 high = len(a) -1 while low <= high: mid = (low + high) // 2 if a[mid] == value: return mid elif a[mid] < value: low = mid + 1 else: high = mid -1

if __name__ == '__main__': print(bsearch(a,10)) # 5 print(bsearch(a,11)) # 6 print(bsearch(a,16)) # 7 print(bsearch(a,1)) # 0


  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

57、二分变形:第一个等于定值的

求第一个等于定指的 有重复值。比如nums=[1, 2, 2, 3, 3, 3, 4, 4, 5], target=4)

注意点:while low <= high: 需要 <=

mid = low + ((high - low) >> 1)最好用位运算,比//2好,防止泄露

  • 小了:说明要往右移动:low = mid + 1
  • 大了:说明要往左移动:high = mid - 1

时刻要注意:端点的情况

def f1(nums,target): '''求第一个等于定值的 ''' low = 0 high = len(nums) - 1 # 这里需要 <= while low <= high: # 这里需要注意: 就是使用((high - low) >> 1)需要双扩号 mid = low + ((high - low) >> 1) if nums[mid] < target: low = mid + 1 elif nums[mid] > target: high = mid - 1 else: if mid == 0 or nums[mid-1] != target: return mid else: high = mid -1 return -1 print(f1(nums=[1, 2, 2, 3, 3, 3, 4, 4, 5], target=4)) # 6

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

58、二分变形:最后一个等于定值的

def f2(nums,target): '''求最后一个等于定值的''' low = 0 higt = len(nums) -1 while low <= higt: mid = low + ((higt- low) >>1 ) if nums[mid] > target: higt = mid - 1 elif nums[mid] < target: low = mid +1 else: if mid == (len(nums) -1) or nums[mid] != nums[mid+1]: return mid else: low = mid +1 return  -1


print(f2(nums=[1, 2, 2, 3, 3, 3, 4, 4, 5], target=4)) # 7


  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

59、二分变形:第一个大于等于值,不一定存在定值

def f3(nums,target): '''求第一个大于等于值''' low = 0 higt = len(nums) -1 while low <= higt: mid = low + ((higt - low) >> 1) if target <= nums[mid]: if (nums[mid-1] < target) or (mid == 0): return  mid else: higt = mid -1 else: low = mid + 1 return -1


print(f3(nums=[1, 2, 4, 5, 8,9,11,15], target=3)) # 2
print(f3(nums=[1, 2, 4, 5, 8,9,11,15], target=9))# 5


  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

60、二分变形:最后一个小于等于定值,不一定存在定值

def f4(nums,target): '''求最后一个小于等于值''' low = 0 higt = len(nums) -1 while low <= higt: mid = low + (( higt -low ) >> 1) if nums[mid] <= target: if (mid == len(nums) -1) or (nums[mid + 1] > target): return mid else: low = mid +1 else: higt = mid -1 return  -1


if __name__ == '__main__': print(f4(nums=[1, 2, 4, 5, 8,9,11,15], target=10))  #5 print(f4(nums=[1, 2, 4, 5, 8,9,11,15], target=3))  #1 print(f4(nums=[1, 2, 4, 5, 8,9,11,15], target=7))  #3

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

注:上面二分的变种是看王争算法专栏总结套路的。

如果你想跟博主建立亲密关系,可以关注博主,或者关注博主公众号“Python之王”,了解一个非本科程序员是如何成长的。
博主ID:润森(weixin_44510615),希望大家点赞、评论、收藏

文章来源: maoli.blog.csdn.net,作者:刘润森!,版权归原作者所有,如需转载,请联系作者。

原文链接:maoli.blog.csdn.net/article/details/108655357

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200