🌚字跳凉凉面经

有生以来第一次社畜面试,非常紧张特别紧张紧张到手凉然后做运动,而且很久没写题了甚至c++的NULL都写了null。啥也没答上来,凉透啦。但是经验总结还是要的。

一开始自我介绍,然后主要是介绍项目,这一块感觉还好,把我那市创介绍了下,后来室友说我听起来思路还算清楚就是用了太多连接词“然后”了,嗯有道理。然后面试官也问了蛮多项目里的问题,这还是在我的范围内的。

然后说到集成学习,就问我还了不了解集成学习的其他算法,我说我项目里用的Bagging,其他还有Boosting啥的,但是不了解,就把Bagging的思路讲了一遍。然后妆容迁移里有说到生成式对抗网络,话题就到了机器学习上。然后问了知不知道其他常见的Loss函数,我说我就用过平方的那个。。(甚至忘了他学名叫啥),然后说项目用的是RMSE,又聊了决策树是啥,正则化是啥(但是正则化当时写的时候我也没有特别了解原理,就套公式。。自己挖的坑现在都得还上)。

先补充补充知识点:

常见的损失函数

  1. 0-1函数,预测值和目标相等为0,不等为1
  2. 绝对值损失函数 L(Y,f(X))=|Y-f(X)|
  3. 对数损失函数 L(Y,P(Y|X))=-logP(Y|X)
  4. 平方损失函数 L(Y,f(X))=∑(Y-f(X))^2
  5. 指数损失函数 L(Y,f(X))=exp[-Yf(X)]
  6. Hinge损失函数 L(Y,f(X))=max(0,1-Yf(X)) 使分类器可以更专注于整体的误差
  7. 感知损失函数 L(Y,f(X))=max(0,-f(x)) 对判定边界附近的点(正确端)惩罚力度很高
  8. 交叉熵损失函数

🔗常见的损失函数(loss function)总结 - yyHaker的文章 - 知乎 https://zhuanlan.zhihu.com/p/58883095

正则化
目的:减小测试误差,因为复杂模型容易过拟合,导致泛化能力下降,正则化可以降低模型复杂度
常用方法:L1正则化惩罚项为L1范数、用于特征选择,L2正则化惩罚项为L2范数、用于防止模型过拟合、对特征系数进行一个比例缩放

然后开始做题。

第一个题是坐飞机的题(去网上找了找描述是下面这样):

有100个人上飞机,本应该按照各自的座位1-100号坐下,但其中有一个是疯子。疯子的行为是:随机选择一个座位坐下。正常人的行为是:尽量做自己的座位,如果自己的座位被占了,就随机选一个座位。问最后一个人坐在自己的位置的概率是多大。

🔗100人坐飞机,第一个乘客在座位中随便选一个坐下,第100人正确坐到自己坐位的概率是? - 知乎
https://www.zhihu.com/question/35950050

我第一反应宁夏区域赛也是坐飞机的题啊,当时推了个公式出来。然后我就从n=1、2、3开始推,然后面试官问我思路,我说一般推123然后答案就出来了,f(2)=1/2,f(3)=1/2,然后我就宕机了,我记得宁夏的答案是带n的啊,,然后就开始1/n+?的想。。。面试官说那换一个题

这题结果是1/2

知乎看见一个很巧妙的思路就是:
2-99号如果发现1号疯子占了自己的位置,就只能随机坐到位置x上,这等价于他们让疯子把自己的位置让出来,然后让疯子去坐x,这并不影响后面人的局面,所以到最后2-99都在自己位子上,疯子可能在1也可能在100,所以就是1/2的概率。

还有一个思路是:
分成三种情况讨论,第一种疯子坐对了、没事,第二种疯子坐到了第k个位置、那么2-(k-1)的人都坐对,对于第k个人来说、这又变成了一个疯子问题,第三种疯子坐到了第100个位置结束。所以第二个情况实际上无效,因为它变成了n小一些的子问题,那么只要看第一种和第三种的情况,这俩概率一样的,所以最后就是1/2。(这个思路也可以写成递推形式)

宁夏区域赛的那个题「Take Your Seat」是这样的:第一问和上面一样,第二问是大家会按照一个随机的顺序上飞机。(唉那个题当时还是我推的,结果面试考反倒没答出来,还是思路没那么清楚啊)

按照随机顺序上飞机之后,正常人是会好好坐的,所以只要看疯子是第几个上飞机,疯子最后一个上飞机肯定坐对,这是1*1/n,如果疯子不是最后一个上飞机那么疯子前面的人都是对的,后面其实就相当于疯子第一问第一个上飞机的问题,是(1/2)*(n-1/n),加起来就是(n+1)/2n

然后第二个题,一个圆周上有随机n个点,问这n个点落在同一个半圆内的概率,这个题我没懂意思,面试官好像也不好描述,他就说那下一个,后来查了查是这样意思的一个题:

🔗又是万能的知乎:在一个圆里随机取n个点,它们在同一个半圆的概率是多少? - 知乎 https://www.zhihu.com/question/341018905

知乎这个题说的是圆里,但是其实无论圆里还是圆周上都是一样的。思路是把这n个点看成是在n条直径上,那么对于任意一个圆周上的点来说,他可以在直径的一条半径,也可以在另一条半径,所以如果这n个点在同一个半圆上,也就是这n个点所在半径都相邻的概率。问题转化为在n个直径中选n个半径,n个半径相邻的概率是多少?
那么只要选定一条边界之后剩下的要么取一边要么取另一边,n条直径会把圆形分成2n个部分,以每一个部分为界,所以总共有2n个可行解,所以ans=2n/2^n=n/2^(n-1)


然后又看到一个蛮有意思的同理的题:🔗圆上任选三点组成三角形,这个三角形是锐角、钝角和直角三角形的概率分别是多少? - 知乎 https://www.zhihu.com/question/19824740

先按照上面半圆的思路想了下,对于直角三角形来说,必须两个点得是直径,圆上任选两个点为直径的概率几乎为0,所以直角三角形概率为0;对于钝角三角形来说,其实就是三个点在同一个半圆内才能形成钝角,套一下上一题推出来的公式p(钝角)=3/2^(3-1)=3/4,剩下的就是锐角三角形的概率了,p(锐角)=1=3/4=1/4


然后可以继续扩展到球上的情况,🔗在一个球内任取n个点,则这n个点落在同一个半球内的概率是多少? - 知乎 https://www.zhihu.com/question/342593905

按照之前的思路问题可以转化为在n个直径中选n个半径,总方法数还是2^n。然后就是考虑在三维空间里出现在同一半球的方法数,那么考虑n条直径可以把三维球分成多少部分,一条直径就是两个部分,2条直径就是四个部分,n条直径是n^2-n+2个部分,推导就是已知f(1)=2,f(n)=f(n-1)+2*(n-1)然后用高中数列的错位相减法求f(n)。

1
2
3
4
5
6
f(n)-f(n-1)=2*(n-1)
f(n-1)-f(n-2)=2*(n-1-1)
...
f(2)-f(1)=2*(2-1)
n-1个式子求和得f(n)-f(1)=2*((n+2)*(n-1)/2-(n-1))
化简得f(n)=n^2-n+2

那么选一个部分作为边界剩下的就确定了,所以就是n^2-n+2种情况,概率就是ans=(n^2-n+2)/2^n

第三个是抛硬币的题,一个不均匀的硬币一面是p一面是1-p,问有没有公平的抛法。

没想出来。我只觉得答案肯定是多抛几次,但是不知道咋抛抛。

用硬币的A面对应决定a,B面对应决定b,抛N次
然后用硬币的B面对应决定a,A面对应决定b,抛N次
总共抛2N次

感觉其实和以前练的博弈思维挺像的,博弈论里比如巴什博弈也是看对手的操作然后决定自己的操作,一对一对凑好了就是最优策略。

然后说那写代码吧,凉凉预警。

让写个翻转链表,输出表头返回表头,一开始写了个2n的方法,先记下来然后再建一个链表,然后面试官问有没有直接转向的方法,然后写了个while循环里面四行这样的直接迭代的方法:tmpp先存下右边,中间的tmp指向左边上一个,上一个res更新为中间的,中间的移动到存好的下一个位置:

1
2
3
4
5
6
while(tmp!=null){
node* tmpp=tmp->next;
tmp->next=res;
res=tmp;
tmp=tmpp;
}

我感觉没啥问题0.0,然后面试官问我返回值,我就返回了res,感觉没啥问题。他说这样会不会哪里有问题。。

面试之后去写了一下「leetcode 206. 反转链表」:

然后我写的果然有问题。。执行出错了,首先发现是错在最后那个NULL,所以要判断一下加个NULL,if(res==head)res->next=NULL;,然后又在开头执行错误了,发现没有判断一开始就是NULL的特例,改了就过了。太久没写题了太意识流了以至于很随便,也不考虑特殊情况边界处理啥的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* res=head;
if(res==NULL)return res;
ListNode* tmp=res->next;
while(tmp!=NULL){
ListNode* tmpp=tmp->next;
tmp->next=res;
if(res==head)res->next=NULL;
res=tmp;
tmp=tmpp;
}
return res;
}
};

题目里说有迭代和递归两种思路,我写的那种是迭代,然后补了一下递归的:

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==NULL||head->next==NULL)return head;
ListNode* res=reverseList(head->next);
head->next->next=head;
head->next=NULL;
return res;
}
};

就这样时间差不多过去了一个小时,面试官问还有没有想问他的,我就问那个硬币的到底咋做,他说让我回去想想。别的问题就没有了,我是真的不知道要问啥。。第一次面试真的是来刷经验了我太菜了。

面试就这样结束了,面试官说回去等通知,凉透了凉透了,不过也没有那么惨烈。体验了一把收获还是很大的,面试官人也很nice就正常交流。

以后面试应该不会这么紧张了。接下来还是好好刷leetcode吧,得把以前学过的东西都捞捞。记不住的那些东西感觉被问了一遍之后反倒记住了,这样就可以把会的东西列下来,平时给自己模拟模拟试试。

From now on。

打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2018-2020 LeFlacon

奶茶一杯 快乐起飞

支付宝
微信