鹏博士公司Python工程师面试题及感悟

阅读：评论：0

面试鹏博士的感觉：公司环境不是怎么好，技术人员不多整体让我感觉公司技术不太行，面试时间比较长，题出的难度属于中等。带着一颗增加面试经验的心来的，整个过程感觉还是挺轻松。

面试题都很快做完，逻辑题不少，唯一感觉是leetcode和剑指offer上的题还是刷的少，现在对逻辑题、算法、数据结构要求挺高。

首先看看笔试题，三道逻辑题、四道leetcode和剑指offer变型题。

逻辑题（逻辑题请把答案直接写在题下面，不要写思路）

1. 有三顶红帽子和两顶白帽子，将其中的三顶帽子分别戴在A、B、C三个人头上，这三人每人都只能看见其他两人头上的帽子，但看不见自己头上戴的帽子，并且也不知道剩余的两顶帽子的颜色。问A：“你戴的是什么颜色的帽子”，答A回答说“不知道”，接着，又以同样的问题问B。B想了想之后，也回答“不知道”。最后问C，C回答说：“我知道我戴的帽子是什么颜色了”，当然，C是在听了A、B的回答之后而做出回答的。请问：试问C戴的是什么颜色的帽子？

答案是：红帽子。

思路：

一、 A不知道自己戴的什么帽子，说明他看到是两种情况：

①. B、C都戴的红帽子

②. B、C中一人带红帽子、一人戴白帽子。

（B、C都戴白帽子的情况不可能出现，否则A就知道自己戴的什么帽子了）

二、 B在听了A的答案之后，思考后回答他不知道自己戴的什么颜色的帽子，说明以下情况：

①. B知道A想到的情况，就是B、C都是红帽子或B、C中一个红帽子和一个白帽子，这时，若B看到C戴的是白帽子，说明自己戴的是红帽子（因为A看到的肯定没有2个白帽子，否则他就知道自己什么帽子了）。

②. 如果B看到C 戴的是红帽子，那么B就不可能知道自己戴的是什么帽子（因为A戴的可能是红帽或白帽，无法判断B自己的帽子颜色）。这里B确实回答或不知道，那么说明C戴的是红帽子。

这里，C是通过A和B的眼睛和判断，得出自己的判断。C其实不用看A、B戴什么帽子。

2. 100个球两个人轮流取，每次最多取五个最少取一个，谁能拿到最后一个就赢，求第一个取球的人的必胜方法。

答案：先取4个

解决方法：

100除以6，余数是4，那么第一个拿4个球，假如对方拿x个球，那么你就拿6-x个，对方拿1个你就拿5个，对方拿5个你就拿1个这样子。

3. 在一条长度为1的线段上随机选取两点，把这条线段分成三条线段。请问这三条线段可以组成一个三角形的概率是多少？

答案：25%

思路：

x+y+z=1 x+y+z=1，x+y+z=1，当x+y=z x+y=z x+y=z时，有z=0.5 z=0.5 z=0.5，因此当x,y,z x,y,z x,y,z中有一个大于0.5时，就无法成立一个三角形。

当x−y=z x-y=z x−y=z时，将x−y=z x-y=zx−y=z代入x+y+z=1 x+y+z=1x+y+z=1，可得x=0.5 x=0.5x=0.5。因此当x,y,z x,y,zx,y,z中有一个大于0.5时，就无法成立一个三角形。

因此解空间刚好与一条长度为1的线段，随机剪两刀，求有一根大于0.5的概率相反。而一条长度为1的线段，随机剪两刀，求有一根大于0.5的概率的概率为0.75。因此这3段能组成一个三角形的概率是多少是1−0.75=0.25 1-0.75=0.251−0.75=0.25。

代码题（不接受伪代码，以时间复杂度、空间复杂度更低者更优以代码更简洁者更优）

4. 在一个排序数组中找一个数，返回该数出现的任意位置之一，如果不存在，返回-1。

给出数组[1, 2, 2, 4, 5, 5, 7]

如：

对于 target = 2，返回1或者2。

对于 target = 5，返回4或者5。

对于 target = 6，返回 -1。

思路：可以使用暴力破解法或内置的方法index 或二分查找法。

代码实现：二分查找，时间复杂度是O(log n)

def binary_search(sorted_array, val):if not sorted_array:return -1beg = 0                       # 指向开头end = len(sorted_array) - 1   # 指向结尾while beg <= end:mid = int((beg + end) / 2)  # 为了屏蔽Python2/3差异,使用类型强转。if sorted_array[mid] == val:return midelif sorted_array[mid] > val:end = mid - 1else:beg = mid + 1return -1

5. 输入一个日期字符串，返回这个日期是那一年的第几天。比如：

Input: data = “2019-01-09” Output: 9

Input: data = “2019-02-10” Output: 41

思路：可以使用内置方法或暴力破解法。

代码实现：

class Solution:def dayOfYear(self, date: str) -> int:year = int(date[0:4])month = int(date[5:7])day = int(date[8:])c = [31,28,31,30,31,30,31,31,30,31,30,31]d = 0for i in range(1,month):if i ==2 and ((year % 4 == 0 and year % 100 != 0) or year % 400 == 0):d += 29else:d += c[i-1]d += dayreturn d

6. 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这个路径上所有节点值相加等于目标和。说明：叶子节点是指没有子节点的节点。

示例：

给定如下二叉树，以及目标和 sum = 22，

       5/ 4     8/      /11    13   4/          
7    2          1

返回 true，因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2

Def has_path_sum(self, root, sum:int) ->bool:

代码实现：递归方法

def has_Path_Sum(self, root, sum: int) -> bool:if not root:return Falseif root.left==None and root.right==None:return sum - root.val == 0return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right,sum-root.val)

7. 给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例：

输入：[-2, 1, -3, 4, -1, 2, 1, -5, 4]

输出：6

解释：连续子数组 [4, -1, 2, 1] 的和最大，为6。

def max_sub_array(self, nums: List[int]) -> int:

代码实现：

方法一：普通方法

class Solution:def maxSubArray(self, nums: List[int]) -> int:sum = 0max_sub_sum = nums[0]for num in nums:sum += numif sum > max_sub_sum:max_sub_sum = sumif sum < 0:sum = 0return max_sub_sum

方法二：动态规划法

class Solution:def maxSubArray(self, nums: List[int]) -> int:# 动态规划法le = len(nums)for i in range(1, le):# 前i-1个最大的结果已经存在i-1中，每次都可看做是两个数相加submax = max(nums[i]+nums[i-1], nums[i])# 把每次最大的结果赋值给当前值，然后继续下一个两数相加nums[i] = submaxreturn max(nums)

面试时面试官提问题：

算法：二分查找(见笔试题中的第4题)，层遍历

这里要说明一下为什么笔试题考过还让写二分查找，我在笔试题实现代码用的内置方法index，所以面试官让我优化该题目代码。

层遍历代码实现：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def levelOrder(self, root: TreeNode) -> List[List[int]]:if not root:                 # root为空时直接返回[]return []res = []                     # 返回的最终结果cur_nodes = [root]           # 当前访问层next_nodes = []              # 下一层需要访问的res.append([i.val for i in cur_nodes])     # 先把第一层的值放入res中while cur_nodes or next_nodes:    # 当前结点或下一层结点不为空for node in cur_nodes:        # 当前结点的所有孩子都加入next_nodesif node.left:next_nodes.append(node.left)if node.right:next_nodes.append(node.right)if next_nodes:                # 下一层结点不为空时加入resres.append([i.val for i in next_nodes])cur_nodes = next_nodes  # 更新当前结点为next_nodesnext_nodes = []  # 下一层结点置空return res

逻辑题：

(1) 砝码称重问题，有1,2,3,4,5,6克外观一样的6个砝码,如何用天平称两次,可分辨出每个砝码各自的重量？

思路：

先把标有 1 、 2 、 3 的砝码放在天平左边,把 6 放在天平右边.注意到,如果其中三个砝码的重量之和等于另一个砝码的重量,则 1 + 2 + 3 = 6 是唯一的情况.因此,假如天平平衡,那么天平左边一定就是 1 克、 2 克、 3 克的砝码,天平右边就一定是 6 克的砝码.
但是,这只能说明, 6 克的砝码是标对了的.我们仍然不排除 1 、 2 、 3 这三个砝码之间标混了的情况,同时也不能排除 4 、 5 两个砝码标反的情况.接下来该怎么办呢?
下一步——很难想到——是把 3 、 5 两个砝码放在天平左边, 1 、 6 两个砝码放在天平右边.如果左边比右边重,即可说明所有的砝码都标对了.这是因为,如果在 {1, 2, 3} 和 {4, 5} 中各挑一个放在一起,再在 {1, 2, 3} 里挑一个和 6 放在一起,结果前者比后者更重,那么 3 + 5 > 1 + 6 是唯一的解.这就表明, 1 、 3 、 5 这三个砝码都是标对了的.因此,余下的 2 和 4 就都标对了.

(2) 7个等重量的球还有一个稍重的球共8个怎么用天平2次找出最重的一个？

思路：取6个均分成两组称一次，如果相等则再称剩下的两个。如果不相等取重的一组，取两个称。