Uber 电面

11/15/2017 Uber 电面
在Uber两年多的中国人，做machine learning/automation的， 电话信号不是很好其他的没怎么听清楚。问了一些基本的关于现在工作的问题。
题目是given a sorted list of integers as data, a target integer, and a number k, 输出离target最近的k个elements， 比如 data = [1,

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

续，问了他几个问题就结束了。

总体感觉不乐观，找closest的时候index off by 1 的问题纠结了一会，还是不够熟练的问题，正在准备的同学可以先练习一下怎么把传统binary search改写成找到最接近的元素。

找到最接近的以后，比如坐标m，答案肯定在m-k到m+k之间，然后比较m-k/2和m+k/2，如果m+k/2离target更近，则m-k到m-k/2可以舍弃，以后继续这样二分来比

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

1. public int[] getNearestInteger02(int[] data, int target, int k){               
   
2.                 int m=0;               
   
3.                 while( (m+k)<data.length && data[m+k-1]<target ){
   
4.                         m += k;
   
5.                 }
   
6.                 int start, end;
   
7.                 if(m+k > data.length ){
   
8.                         start =data.length-k; end=data.length;
   
9.                 }else{
   
10.                         start = m; end = m+k;
    
11.                         while(target-data[start-1]<data[end-1]-target){
    
12.                                 start--;end--;
    
13.                         }
    
14.                 }
    
15.                 return Arrays.copyOfRange(data, start, end);
    
16.         }

复制代码

补充内容 (2017-12-3 15:05):
pass the given test

永远做不到logk，因为最后要输出这K个数的值。。。

难道不是里扣 六五吧？

sj1456 发表于 2017-11-16 05:58
找到最接近的以后，比如坐标m，答案肯定在m-k到m+k之间，然后比较m-k/2和m+k/2，如果m+k/2离target更近，则 ...

嗯，我想了一下觉得应该就是这样的

hyj143 发表于 2017-11-16 06:33
永远做不到logk，因为最后要输出这K个数的值。。。

不不，只要求输出index，不需要输出k个数的值

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

xmasry 发表于 2017-12-3 15:05
补充内容 (2017-12-3 15:05):
pass the given test

O(Math.max(n/k, k))