滴滴北京3面，已跪～

前面就是聊项目,balabala…
最后上算法，不对，智力题～
1.f()可以等概率生成1-6随机数，构造g(f)生成等概率1-10
2.地图上n个点，如何找到与其余点距离和最小的点
3.贝叶斯分类 loss推导

先说下自己的情况:
1.知道1-5生成2-7的套路，不好使…
2.计算中心点，距离最近中心点哪个就是
面试官讲中心点不是距离和最小点
3.感觉前面聊的不好，就直接讲记不清楚了，饿死了😭，去吃饭了😁

老铁们，有思路的交流下～

#滴滴#

全部评论

推荐最新楼层

运气

一脸茫然大学 Java

沙发，求解惑

点赞回复分享

发布于 2017-09-21 12:34

坂本大佬

中国科学院大学 Java

中心点明明就是距离之和最小的点。。。(采用欧式距离的话

点赞回复分享

发布于 2017-09-21 12:38

akalaka

中国科学院大学 C++

1. p() = 6*(f()-1)+f()-1, 随机数生成器 p 可随机生成[0, 35]的数, 每次产生的数据如果落到[1, 10]区间内则返回, 否则重新生成即可. 2. 如果将地图变成一维数组, 则要求的是中位数. 将此结论推广到二维, 二维中的距离是一个二次函数, 可以用三分求出最优解.

点赞回复分享

发布于 2017-09-21 12:40

ly0521

帝都小航算法工程师

第一题：f-1生成0-5，然后6*（f-1）生成0、6、12、18、24、30，6*（f-1）+（f-1）生成0-35，如果6*（f-1）+（f-1）生成的数大于29，则重复进行，直到结果在0-29，这样会等概率产生0-29，将得到的结果%10之后等概率产生0-9，然后加1 第二题：假设所有的点是（x1，y1），（x2，y2），......，（xN，yN），距离各个点距离和最小的点在（xi，yj）的集合中找，其中i，j=1，2，3......N 有点类似于网易内推的棋盘题，左神有一次讲过，至于为什么在这些点里面，要用到映射到坐标轴上（不太好解释）第三题：说的是朴素贝叶斯的loss么？

点赞回复分享

发布于 2017-09-21 12:43

Comple

南京大学 Java

同跪

点赞回复分享

发布于 2017-09-21 13:20

给个offer好不好

北京航空航天大学 C++

第二个用梯度下降迭代逼近可以吗

点赞回复分享

发布于 2017-09-21 15:28

Homura

福建大三本算法工程师

第二题，我觉得楼上的思路是可以的。如果是欧氏距离，设最优点是(x,y)，就是解无约束优化问题 minx,y d1+d2+...+dn 其中di = sqrt((x-xi)2+(y-yi)2) 然后就是用无约束搜索算法去求极值点，梯度下降、牛顿法/拟牛顿法之类的，只是不清楚上面这个优化问题是不是凸优化，如果非凸，那么找到的只是局部极小值。

点赞回复分享

发布于 2017-09-21 16:39

kelele67

百度_凤巢_开发工程师

之前看过一个给出[0, m) ,求[0, n)的随机数 static int getRandom(int n, int m) { int i = 1; while((n*i-1)%(m-1) != 0) i++; int factor = (n*i-1)/(m-1); int randomSum = 0; while(factor > 0){ randomSum += rand_m(); factor--; } return randomSum%n; }

点赞回复分享

发布于 2017-09-21 17:22

PepperZ

四川大学 C++

第二题应该建立二维的k-dTree来计算最小距离和

点赞回复分享

发布于 2017-09-22 14:51