推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 4205|回复: 21
收起左侧

Uber 新鲜面经,估计挂了,不报希望。

[复制链接] |试试Instant~ |关注本帖
anikin0617 发表于 2016-6-1 05:33:36 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Uber - 内推 - 技术电面 |Other在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
刚电面的Uber,从来没见过的题目,挂了估计,难受,Uber算是最想去的公司吧。在地里也算刷了一段时间,回报大家。大概意思是两个log, log1, log2, merge成一个log
log1
timestamp : num of driver. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
1:00       5
2:15       7
3:00      20
-google 1point3acres
log2.鏈枃鍘熷垱鑷1point3acres璁哄潧
1:05     3
2: 20    8
3:00     5

combined
1:00     5. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
1:05     8
2:15   10
2:20   15
3:00   25

大概意思是这样,具体可能有偏差,最开始我以为 top k 问题,面试官说只有两个log,大概想了想用 two pointers来做。解释了下,就开始写代码。可能edge  case太多,或者我没仔细分析题目。中间的逻辑有问题。最后run代码的时候又一直有语法错误。白人小哥很耐心,可我的表现实在太差。没戏了肯定是。各位大神们好好分析,希望能帮到别人吧。.鐣欏璁哄潧-涓浜-涓夊垎鍦

评分

2

查看全部评分

captor 发表于 2016-6-2 02:36:44 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
t1[i], t2[j]时间, n1[i], n2[j]数量. 鍥磋鎴戜滑@1point 3 acres
while(i, j 不越界){
     if(t1[i+1]>t2[j+1]) j++
     else if(t1[i+1]<t2[j+1]) i++ . 1point 3acres 璁哄潧
     else {i++, j++}//相同时间. 鍥磋鎴戜滑@1point 3 acres
    combineNum[k] = n1[i]+n2[j]; //任意一个combine的元素都必须是n1和n2两个元素的和
    k++
}
把剩下n1或者n2的加到combineNum里
回复 支持 1 反对 0

使用道具 举报

Yoyo00 发表于 2016-6-1 07:40:41 | 显示全部楼层
关注一亩三分地微博:
Warald
Good luck to you! Can you please explain a bit more about how the value is calculated in the combined log? Is it the sum of all the num of drivers, before the current timestamp? Then why 2:15 is 10 then? Shouldn't it be 5+7+3 = 13? Thanks!
回复 支持 反对

使用道具 举报

 楼主| anikin0617 发表于 2016-6-1 07:52:20 | 显示全部楼层
Yoyo00 发表于 2016-6-1 07:40
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴Good luck to you! Can you please explain a bit more about how the value is calculated in the combine ...

其实我没太明白题目的意思,一看是新题就有点慌,大概的意思是2:15的时候log1中有,log2中没有,就要加上log2上一条的数据,所以是7 + 3. 里面corner case很多。如果一个timestamp在两个log都有的话,直接相加就好。
回复 支持 反对

使用道具 举报

norman_xin 发表于 2016-6-1 08:14:55 | 显示全部楼层
onsite也遇到过这道题,如果输入只有两个log的话,可以用两个指针ptr1,ptr2分别遍历两个log,循环每次取ptr1或ptr2中较小的timestamp并计算结果加入result
回复 支持 反对

使用道具 举报

hkc593 发表于 2016-6-1 23:41:24 | 显示全部楼层
可以直接先merge了,lz的那个例子的就是 T= [5,3,7,8,25]. 如果第i个timestamp没有在两个log中都出现的话,就update T[i] = T[i] + T[i-1]. T‘ = [5, 8 , 10, 15, 25]
回复 支持 反对

使用道具 举报

woaibai 发表于 2016-6-2 05:22:59 | 显示全部楼层
norman_xin 发表于 2016-5-31 19:14
onsite也遇到过这道题,如果输入只有两个log的话,可以用两个指针ptr1,ptr2分别遍历两个log,循环每次取pt ...

如果两个log完全没有交集怎么处理?
比如:
Log1 [1:00, 3;
         1:02, 4;
         1:03, 2]

Log2  [2:01, 4;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
          2:02: 5;
         2:15:15]

还需要和前一个时间内的另一个log合并么?还是直接按顺序合并返回
回复 支持 反对

使用道具 举报

cx00001 发表于 2016-6-2 06:14:59 | 显示全部楼层
这是道考验基本功的题呀
回复 支持 反对

使用道具 举报

norman_xin 发表于 2016-6-2 08:12:19 | 显示全部楼层
woaibai 发表于 2016-6-2 05:22
如果两个log完全没有交集怎么处理?
比如:
Log1 [1:00, 3;
. Waral 鍗氬鏈夋洿澶氭枃绔,
如果没有交集的话就不用求和了,直接把timestamp加到结果里就好。
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-7 22:13:29 | 显示全部楼层
这个就是mergesort 吧,设置一个prev = 0, prev记录上一个merge进去的 number。
回复 支持 反对

使用道具 举报

Wingszero 发表于 2016-6-8 03:58:57 来自手机 | 显示全部楼层
这道题直接merge很简单,想到的一个优化是边界判断加二分
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-8 05:02:19 | 显示全部楼层
Wingszero 发表于 2016-6-8 03:58
这道题直接merge很简单,想到的一个优化是边界判断加二分

hmmm, feels like add binary search will make the code long .... even merge is already pretty long....
回复 支持 反对

使用道具 举报

seekingJob320 发表于 2016-6-8 07:45:04 | 显示全部楼层
请问楼主面的是那个组?谢谢!
回复 支持 反对

使用道具 举报

ccrjohn8787 发表于 2016-6-12 11:16:59 | 显示全部楼层
hkc593 发表于 2016-6-1 23:41
可以直接先merge了,lz的那个例子的就是 T= [5,3,7,8,25]. 如果第i个timestamp没有在两个log中都出现的话, ...
  1. T[i] = T[i] + T[i-1]
复制代码
不行吧,如果T[i-1]是同一个log 就会出错
回复 支持 反对

使用道具 举报

ccrjohn8787 发表于 2016-6-12 11:18:37 | 显示全部楼层
woaibai 发表于 2016-6-2 05:22
如果两个log完全没有交集怎么处理?.鏈枃鍘熷垱鑷1point3acres璁哄潧
比如:
Log1 [1:00, 3;

不想交应该更晚的log要加上之前log 最后一次记录吧。想这个例子应该是
1:00 3
1:02 4
1:03 2
2:01 6.鐣欏璁哄潧-涓浜-涓夊垎鍦
2:02 7
2:15 17
回复 支持 反对

使用道具 举报

DaveLiu 发表于 2016-6-15 22:36:37 | 显示全部楼层
这就是merge sort的merge部分
回复 支持 反对

使用道具 举报

陈润鹏 发表于 2016-6-16 02:18:19 | 显示全部楼层
LZ 这题真不明白意思 就问一种情况
timestamp : num of driver.鐣欏璁哄潧-涓浜-涓夊垎鍦
1:00       5. 1point 3acres 璁哄潧
1:15       7
log2
0:00    3
2:20    8

就想问
2:00 和 1:15分别是什么值
回复 支持 反对

使用道具 举报

陈润鹏 发表于 2016-6-16 11:44:29 | 显示全部楼层
  1. package uber;

  2. import java.sql.Date;
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  5. import java.util.HashMap;. Waral 鍗氬鏈夋洿澶氭枃绔,

  6. import leetcode.Q10;
  7. import sun.util.logging.resources.logging;

  8. /*.鏈枃鍘熷垱鑷1point3acres璁哄潧
  9. * http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=192016&pid=2471458&page=1&extra=page%3D1%26filter%3Dsortid%26sortid%3D311#pid2471458
  10. * 这题描述的不太清楚
  11. * log1.
  12. * timestamp : num of driver
  13. * 1:00       5
  14. * 2:15       7
  15. * 3:00      20.

  16. * log2
  17. * 1:05     3
  18. * 2: 20    8
  19. * 3:00     5.

  20. * combined
  21. * 1:00     5
  22. * 1:05     8
  23. * 2:15   10. From 1point 3acres bbs
  24. * 2:20   15.鏈枃鍘熷垱鑷1point3acres璁哄潧
  25. * 3:00   25
  26. *
  27. * 如果 没有交集就不用求和
  28. */
  29. public class MergeLog {

  30.         public int[][] merge(int[][] log1, int[][] log2) {. 1point3acres.com/bbs
  31.                 int ptr1 = 0;
  32.                 int ptr2 = 0;
  33.                 int preselect = 0;
  34.                 int preval = 0;
  35.                 ArrayList<int[]> reslist = new ArrayList<int[]>();. Waral 鍗氬鏈夋洿澶氭枃绔,
  36.                 while (ptr2 < log2.length || ptr1 < log1.length) {
  37.                         if (ptr2 >= log2.length
  38.                                         || (ptr1 < log1.length && ptr2 < log2.length && log1[ptr1][0] < log2[ptr2][0])) {
  39.                                 preval = preselect == 1 ? 0 : preval;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  40.                                 reslist.add(new int[] { log1[ptr1][0], preval + log1[ptr1][1] });. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  41.                                 preselect = 1;
  42.                                 preval = log1[ptr1][1];
  43.                                 ptr1++;
  44.                         } else if (ptr1 >= log1.length
  45.                                         || (ptr1 < log1.length && ptr2 < log2.length && log2[ptr2][0] < log1[ptr1][0])) {
  46.                                 preval = preselect == 2 ? 0 : preval;
  47.                                 reslist.add(new int[] { log2[ptr2][0], preval + log2[ptr2][1] });
  48.                                 preselect = 2;
  49.                                 preval = log2[ptr2][1];
  50.                                 ptr2++;
  51.                         } else if (log2[ptr2][0] == log1[ptr1][0]) {
  52.                                 reslist.add(new int[] { log2[ptr2][0],
  53.                                                 log2[ptr2][1] + log1[ptr1][1] });
  54.                                 preselect = 0;
  55.                                 preval = 0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  56.                                 ptr2++;
  57.                                 ptr1++;
  58.                         }
  59.                 }

  60.                 int[][] res = new int[reslist.size()][2];
  61.                 for (int i = 0; i < reslist.size(); i++)
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  62.                         res[i] = reslist.get(i);
  63.                 return res;
  64.         }
  65. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  66.         public static void main(String[] args) {
  67.                 MergeLog mergeLog = new MergeLog();
  68.                 System.out.println(Arrays.deepToString(mergeLog.merge(new int[][] {
  69.                                 { 0, 5 }, { 2, 7 }, { 4, 20 } }, new int[][] { { 1, 3 },
  70.                                 { 3, 8 }, { 5, 5 } })));
  71.                 // [[0, 5], [1, 8], [2, 10], [3, 15], [4, 28], [5, 25]]

  72.                 System.out.println(Arrays.deepToString(mergeLog.merge(new int[][] {
  73.                                 { 0, 5 }, { 2, 7 }, { 5, 20 } }, new int[][] { { 1, 3 },
  74.                                 { 3, 8 }, { 5, 5 } })));. 1point 3acres 璁哄潧
  75.                 // [[0, 5], [1, 8], [2, 10], [3, 15], [5, 25]]

  76.                 System.out.println(Arrays.deepToString(mergeLog.merge(new int[][] {
  77.                                 { 0, 5 }, { 2, 7 }, { 3, 3 }, { 5, 20 } }, new int[][] {
  78.                                 { 1, 3 }, { 4, 8 }, { 5, 5 } })));.鐣欏璁哄潧-涓浜-涓夊垎鍦
  79.                 // [[0, 5], [1, 8], [2, 10], [3, 3], [4, 11], [5, 25]]

  80.                 System.out.println(Arrays.deepToString(mergeLog.merge(new int[][] {
  81.                                 { 0, 5 }, { 2, 7 }, { 5, 20 } }, new int[][] { { 1, 3 },
  82.                                 { 3, 8 }, { 5, 5 }, { 6, 8 } })));
  83.                 // [[0, 5], [1, 8], [2, 10], [3, 15], [5, 25], [6, 8]]

  84.                 System.out.println(Arrays.deepToString(mergeLog.merge(new int[][] {
  85.                                 { 0, 5 }, { 2, 7 }, { 5, 20 }, { 6, 6 } }, new int[][] {
  86.                                 { 1, 3 }, { 3, 8 }, { 5, 5 }, { 6, 8 } })));
  87.                 // [[0, 5], [1, 8], [2, 10], [3, 15], [5, 25], [6, 14]]. 1point 3acres 璁哄潧

  88.                 System.out.println(Arrays.deepToString(mergeLog.merge(new int[][] { {
  89.                                 0, 5 } }, new int[][] {})));. 鍥磋鎴戜滑@1point 3 acres

  90.                 System.out.println(Arrays.deepToString(mergeLog.merge(new int[][] { {
  91.                                 0, 5 } }, new int[][] { { 0, 5 } })));

  92.                 System.out.println(Arrays.deepToString(mergeLog.merge(new int[][] {},
  93.                                 new int[][] { { 0, 5 } })));

  94.         }
  95. }
复制代码

补充内容 (2016-6-16 12:19):
LZ这题其实真的很难, 辛苦LZ的 还有机会的 祝好运
回复 支持 反对

使用道具 举报

dfnjy 发表于 2016-7-13 04:18:18 | 显示全部楼层
给2个log各分配一个临时变量 记录两个log上一次的值 初始为(无限早,0)
. Waral 鍗氬鏈夋洿澶氭枃绔,每次前进2指针中较早的指针 加上另一个数组的临时变量值 输出当前timestamp
同时前进需要特殊处理一下貌似……
回复 支持 反对

使用道具 举报

dfnjy 发表于 2016-7-13 05:39:58 | 显示全部楼层
  1. vector<pair<string,int>> itry(vector<int> n1,vector<int> n2,vector<string> t1,vector<string> t2){
  2.     int _n1=0,_n2=0;. Waral 鍗氬鏈夋洿澶氭枃绔,
  3.     int i=0,j=0;
  4.     t1.push_back("~");t2.push_back("~");
  5.     vector<pair<string,int>> result;
  6.     while (i<n1.size()-1 || j<n2.size()-1){
  7.         if (t1[i]>t2[j]){. 1point3acres.com/bbs
  8.             result.push_back(make_pair(t2[j],n2[j]+_n1));
  9.             _n2=n2[j++];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  10.         }
  11.         else if (t1[i]<t2[j]){
  12.             result.push_back(make_pair(t1[i],n1[i]+_n2));
  13.             _n1=n1[i++];
  14.         }
  15.         else{
  16.             result.push_back(make_pair(t1[i],n1[i]+n2[j]));
  17.             _n1=n1[i];_n2=n2[j];-google 1point3acres
  18.             i++;j++;
  19.         }
  20.     }
  21.     return result;
  22. }
复制代码

只测了那一个case
菜鸡瞎写一通大神轻喷
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-25 22:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表