2021年4月下旬， 百度机器学习/数据挖掘/NLP算法工程师实习面试8道

#这是我参与8月更文挑战的第7天，活动详情查看：8月更文挑战

1.编程题旋转有序数组，查找元素是否存在

思路：

1. 1. 暴力破解：遍历整个数组，查找元素是否存在；
   2. 二分查找：旋转后局部数组依然是有序的，所以此时依然可以使用二分查找算法；

参考代码：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 方法1：保留破解
        # return nums.intdex(target) if target in nums else -1
        
        # 方法2：二分查找
        if not nums: return -1


        left, right = 0, len(nums) - 1


        while left <= right:
            medium = (left + right) // 2


            if nums[medium] == target: return medium


            if nums[left] <= nums[medium]:
                if nums[left] <= target < nums[medium]:
                    right = medium - 1
                else:
                    left = medium + 1
            else:
                if nums[medium] < target <= nums[right]:
                    left = medium + 1
                else:
                    right = medium - 1
        return
复制代码

2.实现余弦相似度计算

余弦相似度：用两个向量夹角判断其相似程度；

• • • 向量夹角越大，距离越远，最大距离就是两个向量夹角180°；
    • 向量夹角越小，距离越近，最小距离就是两个向量夹角0°，完全重合。

所以余弦相似度越大，向量越相似；

计算公式：

\cos (\theta)=\frac{a \cdot b}{|A||B|}=\frac{\sum_{i=1}^{n} a_{i} \times b_{i}}{\sqrt{\sum_{i=1}^{n}\left(a_{i}\right)^{2}} \times \sqrt{\sum_{i=1}^{n}\left(b_{i}\right)^{2}}}

求余弦相似度方法：

• • Numpy:

def cal_cosineSimilarity_numpy(a,b):
    dot = a*b 
    a_len = np.linalg.norm(a,axis=1)
    b_len = np.linalg.norm(b,axis=1)
    cosineSimilarity = dot.sum(axis=1)/(a_len*b_len)
复制代码

• • Pytorch

def methodOne(a,b):
    d = torch.mul(a, b)#计算对应元素相乘
    a_len = torch.norm(a,dim=1)#2范数:模长
    b_len = torch.norm(b,dim=1)
    cosineSimilarity = torch.sum(d, dim=1)/(a_len*b_len)#得到相似度
 
def methodTwo(a,b):
    cosineSimilarity = torch.cosine_similarity(a,b,dim=1)
复制代码

• • Sklearn

from sklearn.metrics.pairwise import cosine_similarity
def cal_cosineSimilarity_sklearn(a, b)
cosineSimilarity = cosine_similarity(a,b)
复制代码

3. 验证二叉搜索树(BST)

二叉搜索树具有如下特征：

• • • 节点的左子树只包含小于当前节点的数。
    • 节点的右子树只包含大于当前节点的数。
    • 所有左子树和右子树自身必须也是二叉搜索树。

思路：

根据二叉搜索树的特征可知：如果二叉树的左子树不为空，则左子树上所有节点的值均小于它根节点的值；若它的右子树不空，则右子树上所有节点的值均大于它根节点的值；并且它的左右子树也为二叉搜索树。

可以设计一个递归函数 check(root, max_num, min_num) ，函数表示考虑以root为根的子树，判断子树中所有节点的值是否都在(max_num, min_num)的范围内。如果root节点的值val不在(max_num, min_num)的范围内说明不满足条件直接返回False，否则继续递归，检查它的左右子树是否满足，都满足则说明这是一棵二叉搜索树。

注意：在递归调用左子树时，需要把上界max_num改为root.val；递归调用右子树时，需要把下界min_num改为root.val.

函数递归调用的入口为check(root, float(“inf”), -float(“inf”))，float(“inf”)表示一个无穷大的值。

参考代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        return  self.valTree(root, float("inf"), -float("inf"))
    def valTree(self, root: TreeNode, max_num, min_num):
        if not root: return True
        val = root.val 
        if val >= max_num or val <= min_num: return False
        if not self.valTree(root.left, val, min_num): return False
        if not self.valTree(root.right, max_num, val):return False
        return True
复制代码

4.用randomInt(5)实现randomInt(7)，只用讲思路

randomInt(5)：等概率生成整数[1, 2, 3, 4, 5]

randomInt(7): 等概率生成整数[1, 2, 3, 4, 5, 6, 7]

思路：

• • • 用(randomInt(5) – 1)构造等概率整数数组：[0, 1, 2 , 3, 4],
    • 用(randomInt(5) – 1)*5构造整数数组：[0, 5, 10, 15, 20],
    • 上面的两个整数组可以构造等概率的新数组：[0, 1, 2, 3, 4, 5, 6, 7, …. , 24];

(如果第2个数组选择2倍或者3倍，4倍则无法构造新的等概率数组)

• • • 选择新数组[0, 1, 2, 3 …. , 20]21个元组即可构造等概率的数组[1, 2, 3, 4, 5, 6, 7]

参考代码：

import random


def rand5():
    return random.randint(1, 5)


def rand7():
    while True:
        tmp_num = (rand5() - 1)*5 + (rand5() - 1)
        if tmp_num <= 20:
            break
    return tmp_num % 7 + 1


# 随机生成10000个1~7的整数，验证0~7各个数字生成的概率；
ls = []
for _ in range(10000):
    ls.append(rand7())
for i in range(1, 8):
    print(ls.count(i)/len(ls), end=" ")
# out：0.144 0.1459 0.14 0.1438 0.1444 0.1373 0.1446
# 观察可知0~7各个数字生成的概率是等
复制代码

5.编程题： 分割链表问题

分割链表：

给定一个链表的头节点 head 和一个特定值 x ，然后对链表进行分隔，使得所有小于x的节点都出现在大于或等于x的节点之前。同时保留两个分区中每个节点的初始相对位置。

如下图所示：

思路：

需维护两个链表small和large，small链表按顺序存储所有小于x的节点，large链表按顺序存储所有大于等于x的节点。遍历完原链表后，我们只要将small链表尾节点指向large链表的头节点即能完成对链表的分隔。

参考代码：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        small = ListNode()
        large = ListNode()
        smallHead, largeHead = small, large
        while head:
            if head.val < x:
                small.next = head
                small = small.next
            else:
                large.next = head
                large = large.next
            head = head.next
        large.next = None
        small.next = largeHead.next
        return smallHead.next
复制代码

6.怎么解决过拟合？怎么做图像增广？

常见缓解过拟合的方法：

• • • 降低模型复杂度
    • 增加更多的训练数据：使用更大的数据集训练模型
    • 数据增强
    • 正则化：L1、L2、添加BN层
    • 添加Dropout策略
    • Early Stopping
    • 重新清洗数据：把明显异常的数据剔除
    • 使用集成学习方法：把多个模型集成在一起，降低单个模型的过拟合风险

常见的数据增广方法：

• • • 水平/垂直翻转
    • 随机旋转
    • 随机缩放
    • 随机剪切
    • 颜色、对比度增强
    • CutOut
    • CutMix
    • Mixup
    • Mosaic
    • Random Erasing

7.梯度下降方法有哪些？

梯度下降算法有如下3种：

• • • 随机梯度下降法：SGD
    • 批量梯度下降法：BGD
    • min-batch小批量梯度下降法：MBGD

8.Sigmoid有哪些特性？激活函数了解多少？

Sigmod函数性质：

• • • 定义域：( −∞ , +∞ )；
    • 值域：(0 , 1 )；
    • 函数在定义域内为连续光滑函数；
    • 处处可导，导数为：

；

• • • 函数的取值在 0 到 1 之间，在 0.5 处呈中心对称，且越靠近 x = 0 的取值斜率越大。

常见激活函数：

• • • Sigmoid
    • Tanh
    • Relu 、Leaky Relu、P-Relu (Parametric ReLU)
    • Elu、Gelu
    • Swich
    • Selu

干货组小伙伴，最新升级的 《名企AI面试100题》 电子书，可免费发给需要的小伙伴，需要的可在评论区回复：【100题】,看到后直接私你。