@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`));

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

很简单直接降序：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表示要跳过的数量 。

查找入职员工时间排名倒数第三的员工所有信息的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

在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                 |
+---------------------+

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

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

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

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

最好的方法就是使用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                    |
+------------------------+

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

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

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)

在这里提供内置的方法chain

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

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}]

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}

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']

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

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

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

补充下：对于组合，有两个自带的方法：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']

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

50、数组的排列组合 II

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

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

示例:

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

如果直接用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

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

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

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]

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

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

思路是使用遍历，但就是找到]的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))

54、数位之积

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

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

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

对于小于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

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

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

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

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

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

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

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

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

最后

以上就是纯情柜子为你收集整理的2020 年最全 Python 面试题汇总 （三）41、查找最晚入职员工的所有信息42、查找入职员工时间排名倒数第三的员工所有信息43、Leetcode175. 组合两个表44、Leetcode176 第二高的薪水45、Leetcode 177. 第N高的薪水46、将二维数组合并成一维数组47、将字典的values进行排序48、两个元组或者列表合并成字典49、字符串的排列组合50、数组的排列组合 II51、寻找完数52、压缩字符串53、腾讯校招压缩算法54、数位之积55、数位重排56、标准二分法的全部内容，希望文章能够帮你解决2020 年最全 Python 面试题汇总 （三）41、查找最晚入职员工的所有信息42、查找入职员工时间排名倒数第三的员工所有信息43、Leetcode175. 组合两个表44、Leetcode176 第二高的薪水45、Leetcode 177. 第N高的薪水46、将二维数组合并成一维数组47、将字典的values进行排序48、两个元组或者列表合并成字典49、字符串的排列组合50、数组的排列组合 II51、寻找完数52、压缩字符串53、腾讯校招压缩算法54、数位之积55、数位重排56、标准二分法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。