滴滴出行

全程一对一面试，两面的面试官都是搞技术的，一面：面试官挺随和的，虽然我挺紧张的。问了一个动态规划问题，一个二维矩阵，第一行一个数字，第二行两个，第N行N个，求从头到尾最大值为多少。我说了思想，代码没在规定时间内写出来。第二题数三减一，就是小朋友抱成圈，数到三删除一个人，考代码实现能力。虽然我还是没写上来，但动态规划说出来就过了。 二面：让我写之字打印二叉树，同上，只说了思想。然后侃侃逻辑，说滴滴鼓励拼车，毕竟是第一次面试，，以为不搞技术了，谁知道到最后又来了一道动态规划题目，是国王挖金矿的变体，对！是变体，所以当时以为还在侃，所以也没想出来，聊的挺开心，然后就跪了。

一面：1. 1000桶水有一桶有毒，一头猪喝了有毒的水之后过15分钟会死掉，问最少需要多少头猪来找到有毒的水，在一个小时之内；2. 文本分类项目；3. 实习项目；4. 括号匹配问题，给一个不匹配额括号串，只包含左括号和右括号，这个串去掉一个字符可以变成匹配串，找到所有可能的匹配串；5. 线程和进程的区别；6. 两个线程同时访问同一段代码程序。 二面：1. 实习的项目内容；2. 多个有序数组求交集；3. 多个有序数组求并集；4. 旋转数组中的查找；5. SVM；三面：1. 实习内容，顺便问了learning to rank；2. 离散型属性和连续性属性的优缺点，连续性属性离散化的好处和坏处，好处就是可以维度扩展，从而可以训练处非线性模型，坏处就是容易过拟合，过拟合了之后怎么解决？计入正则项，或者去看离散化之后的特征，哪个特征所包含的样本太少的话就把这维特征去掉，去噪声，在特征的数量上进行制约；3. 有m件物品，每件物品分别有不同的重量是一个m大小的数组，n个背包1~n编号，每个背包的容量为T，把物品往背包里面装，一个背包在容量运行的范围内可以装多个物品，但是装背包必须按照背包的编号来，并且开始往第二个背包里面装物品之后就不能再往前面的背包里面装了，问最多可以装多少件物品。（类似买卖k次股票的问题）