一些面试题

这个周末去体验了一次面试官,就没写博客了,把准备的面试题分享下吧~

编程题

快速排序

给定一个数字数组,写一个快速排序算法。

分治法,找定一个轴点,每次遍历都将大于该轴点值的数放到右边,小于该轴点值的数放到左边。

def quickSort(nums, low, high):
    if low <= high:
        pivot = nums[low]
        i = low
        j = high
        while i < j:
            while i<j and nums[j] >= pivot:
                j -= 1
            while i<j and nums[i] <= pivot:
                i += 1
            if i < j:
                swap(nums, i, j)
        swap(nums, low, i)
        quickSort(nums, low, i-1)
        quickSort(nums, i+1, high)

def swap(nums, i, j):
    tmp = nums[j]
    nums[j] = nums[i]
    nums[i] = tmp

判断两个链表是否相交

给出两个单向链表的头指针,比如h1h2,判断这两个链表是否相交。假设这两个链表均不带环。

进一步拓展:
– 如果链表有环呢?
– 需要返回两个链表相交的第一个节点呢?

机器学习

逻辑回归推导

逻辑回归使用一个函数来归一化y值,使得y的取值在(0,1)内。这个函数成为logistic函数,也成为sigmoid函数,函数公式如下:

g(z)=\frac{1}{1+e^{-z}}

性质:
g(z)’ = g(z)(1-g(z))

逻辑回归的本质是线性回归,只是在特征到结果的映射中加入了一层函数映射:即先把特征先求和,然后使用函数g(z)作为假设函数来预测:

h_{\theta}(x)=g(\theta^Tx)=\frac{1}{1+e^{-\theta^Tx}}

对于输入的x分类结果为12的概率分别为:

P(y=1|x;\theta)=h_\theta(x)
P(y=0|x;\theta)=1-h_\theta(x)

对上面的表达式合并一下:

P(y|x;\theta)=(h_\theta(x))^y(1-h_\theta(x))^{1-y}

构建似然函数,然后最大似然估计,最后推导出\theta的迭代更新公式。

L(\theta) = p(\vec{y}|X;\theta) = \prod_{i=1}^n p(y^{(i)}|x^{(i)};\theta) = \prod_{i=1}^n (h_\theta(x^{(i)}))^{y^{(i)}}(1-h_\theta(x^{(i)}))^{1-y^{(i)}}

为了简化计算,对两边取对数:

\ln(\theta)=\ln L(\theta)=\sum_{i=1}^n y^{(i)}\ln (h_\theta (x^{(i)})) + (1-y^{(i)})\ln(1-h_\theta (x^{(i)}))

使用梯度上升法求解:
\frac{\delta L(\theta)}{\delta \theta} = \sum_{i=1}^n (y^{(i)}\cdot \frac{1}{h_\theta({x^{(i)}})}\cdot \frac{\delta h_\theta(x^{(i)})}{\delta \theta}-(1-y^{(i)})\cdot \frac{1}{1-h_\theta(x^{(i)})}\cdot \frac{\delta h_\theta (x^{(i)})}{\delta \theta})
= \sum_{i=1}^n (y^{(i)}\cdot \frac{1}{h_\theta({x^{(i)}})}-(1-y^{(i)})\cdot \frac{1}{1-h_\theta(x^{(i)})}) \cdot \frac{\delta h_\theta (x^{(i)})}{\delta \theta}
=\sum_{i=1}^n (y^{(i)}\cdot \frac{1}{h_\theta({x^{(i)}})}-(1-y^{(i)})\cdot \frac{1}{1-h_\theta(x^{(i)})})\cdot h_\theta(x^{(i)}) \cdot (1-h_\theta(x^{(i)}) \cdot x^{(i)}

= \sum_{i=1}^n (y^{(i)}\cdot (1-h_\theta(x^{(i)}))-(1-y^{(i)})\cdot h_\theta (x^{(i)})) \cdot x^{(i)}
=\sum_{i=1}^n (y^{i}-h_\theta(x^{(i)}))\cdot x^{(i)}

这样就得到了梯度上升法迭代的上升公式:
\theta := \theta + \alpha\sum_{i=1}^n (y^{(i)}-h_\theta (x^{(i)}))\cdot x^{(i)}

过拟合

  • 造成过拟合的原因?
    • 训练集和测试集特征分布不一致
    • 模型太过复杂而样本量不足
  • 怎么避免出现过拟合现象?
    • 收集多样化的样本,简化模型,交叉检验

数据不均衡

SVM核函数

  • 核函数分类
    • 多项式核
    • 高斯核
    • 线性核
  • 核函数的选择
    • 样本的特征很多时,特征的维数很高,这是往往样本线性可分,可考虑用线性核函数的SVM或LR(如果不考虑核函数,LR和SVM都是线性分类算法,也就是说他们的分类决策面都是线性的)
    • 当样本的数量很多,但特征较少时,可以手动添加一些特征,使样本线性可分,再考虑用线性核函数的SVM或LR
    • 当样特征维度不高时,样本数量也不多时,考虑用高斯核函数(RBF核函数的一种,指数核函数和拉普拉斯核函数也属于RBF核函数)
打赏
微信扫一扫支付
微信logo微信扫一扫, 打赏作者吧~

mickey

记录生活,写给几十年后的自己。

发表评论

电子邮件地址不会被公开。 必填项已用*标注