拼多多算法实习生二面面经 6.7

感觉好难啊, 和一面的感觉差太多了, 面试官也没开摄像头, 得不到反馈

1.自我介绍

2.为什么读博

3.之前是做自动驾驶的, 为什么现在要来pdd算法

4.介绍一下项目, 介绍了半天, 也没深问就过了

5.第一道算法题, 问至少要多少人才能保证有两人同月出生的概率大于90%. 一开始一维手推, 推半天推不出来, 然后面试官说可以写代码试试. 我的思路是暴力枚举, 首先假设取n个人, 那么每个人都能分配到一个月中, 也就用$12^n$ 种情况, 然后考虑没有重复月的情况, 就是在12个月中选n个月, 这是个组合数, 另外分配人需要考虑人的排列, 再乘上$n!$, 也就是不可能的情况的概率是 $n!*C(12,n)/12**n$ 然后遍历n从1到13, 第一个概率小于0.1的退出就可以. 思路感觉没问题, 但是我好像有地方写错了, 不能自己运行, 面试官也没说什么

6.第二道算法题, 字符流中第一次出现的第一个字母, 比如google, 第一个字符g, 出现一次, 输出g, 第二个字符o, o和g都出现一次, 但是g出现靠前, 输出g, 第三个字符g, 只有g出现一次, 输出g, 第四个字符g, 没有出现一次的字符, 输出'', 第五个字符l, 只有l出现一次, 输出l, 第六个字符e, l和e都出现一次, 但是l更靠前, 输出l. 我的思路是维护一个哈希表记录每个字母出现的个数, 同时再用一个列表存储字母出现的顺序. 遍历字母, 如果这个字母没有出现, 那么加入列表中, 然后更新哈希表, 如果字母出现了, 只更新哈希表. 然后从前往后遍历列表, 判断遍历到的字母的出现次数是不是1, 如果是1, 就加入答案中. 如果遍历完都没找到就将''加入答案中. 这个不能调试, 中间定义变量重名了, 错了三次...无语了, 最后面试官说, 列表中靠前的已经出现超过一次的字符存储是不是没什么用, 答可以用队列优化

7.第三道算法题, lc10. 正则表达式匹配. 想到了dp, 但是不能调试, 完全写不对, 后来给面试官说了思路, 面试官说思路没问题. 中间问面试官, 两个字符串是不是一个包含.* 一个不包含, 面试官说都可能包含, 感觉题目瞬间上了一个难度

8.问问面试官的建议, 面试官说感觉我代码能力很强, 后面上手应该很快, 但是需要想清楚, 因为和自动驾驶不太搭(主要不是自动驾驶不要我嘛, 才想着转方向)

感觉有点凉, 全程太紧张了, 只有txt编辑器确实有点难受, 感觉没有平时发挥的好, 许愿三面!