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

朱雀 2020-10-27 12:30 898阅读 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 -1
    	beg = 0                       # 指向开头
    	end = len(sorted_array) - 1   # 指向结尾
    	while beg <= end:
    		mid = int((beg + end) / 2)  # 为了屏蔽Python2/3差异,使用类型强转。
    		if sorted_array[mid] == val:
    			return mid
    		elif sorted_array[mid] > val:
    			end = mid - 1
    		else:
    			beg = mid + 1
    	return -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 = 0
            for i in range(1,month):
                if i ==2 and ((year % 4 == 0 and year % 100 != 0) or year % 400 == 0):
                    d += 29
                else:
                    d += c[i-1]
            d += day
            return 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 False
        if root.left==None and root.right==None:
            return sum - root.val == 0
        return 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 = 0
            max_sub_sum = nums[0]
            for num in nums:
                sum += num
                if sum > max_sub_sum:
                    max_sub_sum = sum
                if sum < 0:
                    sum = 0
            return 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] = submax
            return max(nums)

面试时面试官提问题：

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

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

**层遍历代码实现：**

# Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
     
    class 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_nodes
                    if node.left:
                        next_nodes.append(node.left)
                    if node.right:
                        next_nodes.append(node.right)
                if next_nodes:                # 下一层结点不为空时加入res
                    res.append(
                        [i.val for i in next_nodes]
                    )
                cur_nodes = next_nodes  # 更新当前结点为next_nodes
                next_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个均分成两组称一次，如果相等则再称剩下的两个。如果不相等取重的一组，取两个称。

###       此次面试综合考察还是挺强的，对比这种面试还是需要平常多多训练没事就在leetcode上做做题，对于平常考的二分查找、快排、二路归并等就练练手写代码。 ###