一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3242|回复: 21
收起左侧

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

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

log2. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
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 | 显示全部楼层
t1[i], t2[j]时间, n1[i], n2[j]数量
while(i, j 不越界){
     if(t1[i+1]>t2[j+1]) j++
     else if(t1[i+1]<t2[j+1]) i++ . 1point3acres.com/bbs
     else {i++, j++}//相同时间
    combineNum[k] = n1[i]+n2[j]; //任意一个combine的元素都必须是n1和n2两个元素的和
    k++
}
把剩下n1或者n2的加到combineNum里
回复 支持 1 反对 0

使用道具 举报

Yoyo00 发表于 2016-6-1 07:40:41 | 显示全部楼层
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;. Waral 鍗氬鏈夋洿澶氭枃绔,
         1:02, 4; .鏈枃鍘熷垱鑷1point3acres璁哄潧
         1:03, 2]

Log2  [2:01, 4; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
          2:02: 5; .鏈枃鍘熷垱鑷1point3acres璁哄潧
         2:15:15]. Waral 鍗氬鏈夋洿澶氭枃绔,

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

使用道具 举报

cx00001 发表于 2016-6-2 06:14:59 | 显示全部楼层
这是道考验基本功的题呀
.鏈枃鍘熷垱鑷1point3acres璁哄潧
回复 支持 反对

使用道具 举报

norman_xin 发表于 2016-6-2 08:12:19 | 显示全部楼层
woaibai 发表于 2016-6-2 05:22
如果两个log完全没有交集怎么处理?
比如:
Log1 [1:00, 3;

如果没有交集的话就不用求和了,直接把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很简单,想到的一个优化是边界判断加二分
. 1point 3acres 璁哄潧
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完全没有交集怎么处理?
比如:
Log1 [1:00, 3;

不想交应该更晚的log要加上之前log 最后一次记录吧。想这个例子应该是
1:00 3. Waral 鍗氬鏈夋洿澶氭枃绔,
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. 1point 3acres 璁哄潧
1:00       5. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
1:15       7
log2
0:00    3
2:20    8

就想问
. 1point 3acres 璁哄潧2:00 和 1:15分别是什么值
回复 支持 反对

使用道具 举报

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

  2. import java.sql.Date;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  5. import java.util.HashMap;. visit 1point3acres.com for more.

  6. import leetcode.Q10;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  7. import sun.util.logging.resources.logging;

  8. /*
  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
    . 1point3acres.com/bbs
  23. * 2:15   10
  24. * 2:20   15
  25. * 3:00   25-google 1point3acres
  26. *
  27. * 如果 没有交集就不用求和
  28. */
  29. public class MergeLog {

  30.         public int[][] merge(int[][] log1, int[][] log2) {
  31.                 int ptr1 = 0;
  32.                 int ptr2 = 0;
  33.                 int preselect = 0;
  34.                 int preval = 0;
  35.                 ArrayList<int[]> reslist = new ArrayList<int[]>();
  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. 1point 3acres 璁哄潧
  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]) {. from: 1point3acres.com/bbs
  52.                                 reslist.add(new int[] { log2[ptr2][0],.鐣欏璁哄潧-涓浜-涓夊垎鍦
  53.                                                 log2[ptr2][1] + log1[ptr1][1] });
  54.                                 preselect = 0;
  55.                                 preval = 0;. From 1point 3acres bbs
  56.                                 ptr2++; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  57.                                 ptr1++;
  58.                         }
  59.                 }
  60. . Waral 鍗氬鏈夋洿澶氭枃绔,
  61.                 int[][] res = new int[reslist.size()][2];
  62.                 for (int i = 0; i < reslist.size(); i++)
  63.                         res[i] = reslist.get(i);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  64.                 return res;
  65.         }

  66.         public static void main(String[] args) {-google 1point3acres
  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 } })));. visit 1point3acres.com for more.
  75.                 // [[0, 5], [1, 8], [2, 10], [3, 15], [5, 25]]
  76. . 鍥磋鎴戜滑@1point 3 acres
  77.                 System.out.println(Arrays.deepToString(mergeLog.merge(new int[][] {
  78.                                 { 0, 5 }, { 2, 7 }, { 3, 3 }, { 5, 20 } }, new int[][] {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  79.                                 { 1, 3 }, { 4, 8 }, { 5, 5 } })));
  80.                 // [[0, 5], [1, 8], [2, 10], [3, 3], [4, 11], [5, 25]]

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

  85.                 System.out.println(Arrays.deepToString(mergeLog.merge(new int[][] {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  86.                                 { 0, 5 }, { 2, 7 }, { 5, 20 }, { 6, 6 } }, new int[][] {
  87.                                 { 1, 3 }, { 3, 8 }, { 5, 5 }, { 6, 8 } })));
  88.                 // [[0, 5], [1, 8], [2, 10], [3, 15], [5, 25], [6, 14]]

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

  91.                 System.out.println(Arrays.deepToString(mergeLog.merge(new int[][] { {
  92.                                 0, 5 } }, new int[][] { { 0, 5 } }))); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  93.                 System.out.println(Arrays.deepToString(mergeLog.merge(new int[][] {},-google 1point3acres
  94.                                 new int[][] { { 0, 5 } })));
  95. . from: 1point3acres.com/bbs
  96.         }
  97. }. more info on 1point3acres.com
复制代码

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

使用道具 举报

dfnjy 发表于 2016-7-13 04:18:18 | 显示全部楼层
给2个log各分配一个临时变量 记录两个log上一次的值 初始为(无限早,0). more info on 1point3acres.com
每次前进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;
  3.     int i=0,j=0;. visit 1point3acres.com for more.
  4.     t1.push_back("~");t2.push_back("~");. 1point3acres.com/bbs
  5.     vector<pair<string,int>> result;. more info on 1point3acres.com
  6.     while (i<n1.size()-1 || j<n2.size()-1){
  7.         if (t1[i]>t2[j]){
  8.             result.push_back(make_pair(t2[j],n2[j]+_n1));
  9.             _n2=n2[j++];
  10.         }. from: 1point3acres.com/bbs
  11.         else if (t1[i]<t2[j]){. 1point3acres.com/bbs
  12.             result.push_back(make_pair(t1[i],n1[i]+_n2));
  13.             _n1=n1[i++];. 1point3acres.com/bbs
  14.         }
  15.         else{.鏈枃鍘熷垱鑷1point3acres璁哄潧
  16.             result.push_back(make_pair(t1[i],n1[i]+n2[j]));
  17.             _n1=n1[i];_n2=n2[j];
  18.             i++;j++;
  19.         }
  20.     }
  21.     return result;. 1point3acres.com/bbs
  22. }
复制代码

只测了那一个case.鐣欏璁哄潧-涓浜-涓夊垎鍦
菜鸡瞎写一通大神轻喷
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 01:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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