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

这道题直接merge很简单，想到的一个优化是边界判断加二分

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

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

请问楼主面的是那个组？谢谢！

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 就会出错

加州刺史白十五 发表于 2016-6-2 05:22
如果两个log完全没有交集怎么处理？
比如：
Log1 [1:00, 3;

不想交应该更晚的log要加上之前log 最后一次记录吧。想这个例子应该是
1:00 3
1:02 4
1:03 2
2:01 6
2:02 7
2:15 17

这就是merge sort的merge部分

LZ 这题真不明白意思 就问一种情况
timestamp : num of driver
1:00       5
1:15       7
log2
0:00    3
2:20    8

就想问
2:00 和 1:15分别是什么值

1. package uber;
   
2. 
   
3. import java.sql.Date;
   
4. import java.util.ArrayList;
   
5. import java.util.Arrays;
   
6. import java.util.HashMap;
   
7. 
   
8. import leetcode.Q10;
   
9. import sun.util.logging.resources.logging;
   
10. 
    
11. /*
    
12. * http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=192016&pid=2471458&page=1&extra=page%3D1%26filter%3Dsortid%26sortid%3D311#pid2471458
    
13. * 这题描述的不太清楚
    
14. * log1.
    
15. * timestamp : num of driver
    
16. * 1:00       5
    
17. * 2:15       7
    
18. * 3:00      20.
    
19. 
    
20. * log2
    
21. * 1:05     3
    
22. * 2: 20    8
    
23. * 3:00     5.
    
24. 
    
25. * combined
    
26. * 1:00     5
    
27. * 1:05     8
    
28. * 2:15   10
    
29. * 2:20   15
    
30. * 3:00   25
    
31. *
    
32. * 如果 没有交集就不用求和
    
33. */
    
34. public class MergeLog {
    
35. 
    
36.         public int[][] merge(int[][] log1, int[][] log2) {
    
37.                 int ptr1 = 0;
    
38.                 int ptr2 = 0;
    
39.                 int preselect = 0;
    
40.                 int preval = 0;
    
41.                 ArrayList<int[]> reslist = new ArrayList<int[]>();
    
42.                 while (ptr2 < log2.length || ptr1 < log1.length) {
    
43.                         if (ptr2 >= log2.length
    
44.                                         || (ptr1 < log1.length && ptr2 < log2.length && log1[ptr1][0] < log2[ptr2][0])) {
    
45.                                 preval = preselect == 1 ? 0 : preval;
    
46.                                 reslist.add(new int[] { log1[ptr1][0], preval + log1[ptr1][1] });
    
47.                                 preselect = 1;
    
48.                                 preval = log1[ptr1][1];
    
49.                                 ptr1++;
    
50.                         } else if (ptr1 >= log1.length
    
51.                                         || (ptr1 < log1.length && ptr2 < log2.length && log2[ptr2][0] < log1[ptr1][0])) {
    
52.                                 preval = preselect == 2 ? 0 : preval;
    
53.                                 reslist.add(new int[] { log2[ptr2][0], preval + log2[ptr2][1] });
    
54.                                 preselect = 2;
    
55.                                 preval = log2[ptr2][1];
    
56.                                 ptr2++;
    
57.                         } else if (log2[ptr2][0] == log1[ptr1][0]) {
    
58.                                 reslist.add(new int[] { log2[ptr2][0],
    
59.                                                 log2[ptr2][1] + log1[ptr1][1] });
    
60.                                 preselect = 0;
    
61.                                 preval = 0;
    
62.                                 ptr2++;
    
63.                                 ptr1++;
    
64.                         }
    
65.                 }
    
66. 
    
67.                 int[][] res = new int[reslist.size()][2];
    
68.                 for (int i = 0; i < reslist.size(); i++)
    
69.                         res[i] = reslist.get(i);
    
70.                 return res;
    
71.         }
    
72. 
    
73.         public static void main(String[] args) {
    
74.                 MergeLog mergeLog = new MergeLog();
    
75.                 System.out.println(Arrays.deepToString(mergeLog.merge(new int[][] {
    
76.                                 { 0, 5 }, { 2, 7 }, { 4, 20 } }, new int[][] { { 1, 3 },
    
77.                                 { 3, 8 }, { 5, 5 } })));
    
78.                 // [[0, 5], [1, 8], [2, 10], [3, 15], [4, 28], [5, 25]]
    
79. 
    
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 } })));
    
83.                 // [[0, 5], [1, 8], [2, 10], [3, 15], [5, 25]]
    
84. 
    
85.                 System.out.println(Arrays.deepToString(mergeLog.merge(new int[][] {
    
86.                                 { 0, 5 }, { 2, 7 }, { 3, 3 }, { 5, 20 } }, new int[][] {
    
87.                                 { 1, 3 }, { 4, 8 }, { 5, 5 } })));
    
88.                 // [[0, 5], [1, 8], [2, 10], [3, 3], [4, 11], [5, 25]]
    
89. 
    
90.                 System.out.println(Arrays.deepToString(mergeLog.merge(new int[][] {
    
91.                                 { 0, 5 }, { 2, 7 }, { 5, 20 } }, new int[][] { { 1, 3 },
    
92.                                 { 3, 8 }, { 5, 5 }, { 6, 8 } })));
    
93.                 // [[0, 5], [1, 8], [2, 10], [3, 15], [5, 25], [6, 8]]
    
94. 
    
95.                 System.out.println(Arrays.deepToString(mergeLog.merge(new int[][] {
    
96.                                 { 0, 5 }, { 2, 7 }, { 5, 20 }, { 6, 6 } }, new int[][] {
    
97.                                 { 1, 3 }, { 3, 8 }, { 5, 5 }, { 6, 8 } })));
    
98.                 // [[0, 5], [1, 8], [2, 10], [3, 15], [5, 25], [6, 14]]
    
99. 
    
100.                 System.out.println(Arrays.deepToString(mergeLog.merge(new int[][] { {
     
101.                                 0, 5 } }, new int[][] {})));
     
102. 
     
103.                 System.out.println(Arrays.deepToString(mergeLog.merge(new int[][] { {
     
104.                                 0, 5 } }, new int[][] { { 0, 5 } })));
     
105. 
     
106.                 System.out.println(Arrays.deepToString(mergeLog.merge(new int[][] {},
     
107.                                 new int[][] { { 0, 5 } })));
     
108. 
     
109.         }
     
110. }
     

复制代码

补充内容 (2016-6-16 12:19):
LZ这题其实真的很难， 辛苦LZ的 还有机会的 祝好运

给2个log各分配一个临时变量 记录两个log上一次的值 初始为（无限早，0）
每次前进2指针中较早的指针 加上另一个数组的临时变量值 输出当前timestamp
同时前进需要特殊处理一下貌似……

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;
   
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]){
   
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];
    
18.             i++;j++;
    
19.         }
    
20.     }
    
21.     return result;
    
22. }

复制代码

只测了那一个case
菜鸡瞎写一通大神轻喷