滴滴北京3面，已跪～

沙发，求解惑

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

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

第一题：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么？

同跪

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

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

之前看过一个给出[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;  }

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