Indeed 电面面经

大概在上周面的Indeed, 已经收到了Onsite，最近空下来一点点，来写个面经攒点人品。

职位应该是Full Stack Engineer, Experienced.

一个男生面的我，然后题有1道，容易。
T1 （CodePair):
input: [1, 2, 3, 5, 8, 10, 11, 12, 13, 14]
output: "1-3, 5, 8, 10-14"
大概就是从左往右扫一次就可以完成了，遇到连续的就记一下右边界，左边界也记着，遇到不连续的来了，就把前面的1-3输出，单个的也输出，注意一下边界条件，包括到了最后面的情况，好像并没有跑，只是手动run test，这算是一个小面试技巧，你创建一个test case，然后一步一步看各个值是多少，人工跑一次看对不对。

Follow up:
假如说输入的数组没有排序，如何优化？
input: [1, 3, 9, 2, 4, 5]

楼主想法是：使用Interval来解决
Interval {
  int start;
  int end;
}

然后过一次数组，丢到一个Set里，再从index = 0 开始，创建一个Interval，往左往右看，是不是可以Grow这个interval，例如：
1 - 1-2 -> 1-3 -> 1-4 -> 1-5
这样Set

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

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

int[] test1 = new int[] {
   7,
   1,
   5,
   4,
   2,
   ...

补充内容 (2017-9-10 14:57):
package indeed;

import java.util.*;

public class MergeInterval {

public static void main(String[] args) {
  // write your code here
  int[] test1 = new int[] {
   7,
   1,
   5,
   4,
   2,
   ...

这是解法1的改进，修了BUG，测过有效，只能对sorted有效果！

1. package indeed;
   
2. 
   
3. import java.util.*;
   
4. 
   
5. public class MergeInterval {
   
6. 
   
7.     public static void main(String[] args) {
   
8.             // write your code here
   
9.         int[] test1 = new int[]{7,1,5,4,2,0};
   
10. 
    
11.         // "1-3, 5, 7-9, 11"
    
12.         System.out.println(sortedInterval(new int[]{1, 2, 3, 5, 7, 8, 9, 11}));
    
13.     }
    
14. 
    
15.     static class Interval {
    
16.         public int start;
    
17.         public int end;
    
18. 
    
19.         public int getStart() {
    
20.             return start;
    
21.         }
    
22. 
    
23.         Interval(int start, int end) {
    
24.             this.start = start;
    
25.             this.end = end;
    
26.         }
    
27.     }
    
28. 
    
29.     public static String intervalToStr(int start, int end) {
    
30.         String s = start + "";
    
31.         if (start == end) {
    
32.             return s + ',';
    
33.         } else {
    
34.             return s + '-' + end + ',';
    
35.         }
    
36.     }
    
37. 
    
38.     public static String sortedInterval(int[] arr) {
    
39.         int len = arr.length;
    
40.         if (len == 0) {
    
41.             return "";
    
42.         }
    
43. 
    
44.         int start = arr[0];
    
45.         int end = arr[0];
    
46. 
    
47.         StringBuilder sb = new StringBuilder();
    
48.         for (int i = 1; i < arr.length; i++) {
    
49.             int n = arr[i];
    
50.             if (n - end == 1) {
    
51.                 end = n;
    
52.             } else {
    
53.                 sb.append(intervalToStr(start, end));
    
54.                 start = n;
    
55.                 end = n;
    
56.             }
    
57.         }
    
58. 
    
59.         sb.append(intervalToStr(start, end));
    
60.         sb.deleteCharAt(sb.length() - 1);
    
61.         return sb.toString();
    
62.     }
    
63. }
    

复制代码

1. package indeed;
   
2. 
   
3. import java.util.*;
   
4. 
   
5. public class MergeInterval {
   
6. 
   
7. public static void main(String[] args) {
   
8.   // write your code here
   
9.   int[] test1 = new int[] {
   
10.    7,
    
11.    1,
    
12.    5,
    
13.    4,
    
14.    2,
    
15.    0
    
16.   };
    
17. 
    
18.   // Output: 0-2,4-5,7
    
19.   System.out.println(printInterval(test1));
    
20. }
    
21. 
    
22. static class Interval {
    
23.   public int start;
    
24.   public int end;
    
25. 
    
26.   public int getStart() {
    
27.    return start;
    
28.   }
    
29. 
    
30.   Interval(int start, int end) {
    
31.    this.start = start;
    
32.    this.end = end;
    
33.   }
    
34. }
    
35. 
    
36. public static String printInterval(int[] arr) {
    
37.   HashSet < Integer > set = new HashSet < > ();
    
38.   HashSet < Integer > setUsed = new HashSet < > ();
    
39. 
    
40.   if (arr.length == 0) {
    
41.    return "";
    
42.   }
    
43.   StringBuilder sb = new StringBuilder();
    
44. 
    
45.   ArrayList < Interval > intervalList = new ArrayList < > ();
    
46. 
    
47.   for (int i: arr) {
    
48.    set.add(i);
    
49.   }
    
50. 
    
51.   Iterator < Integer > it = set.iterator();
    
52.   while (it.hasNext()) {
    
53.    Integer num = it.next();
    
54.    if (setUsed.contains(num)) {
    
55.     continue;
    
56.    }
    
57. 
    
58.    int start = num;
    
59.    int end = num;
    
60.    while (set.contains(end + 1)) {
    
61.     end++;
    
62.     setUsed.add(end);
    
63.    }
    
64. 
    
65.    while (set.contains(start - 1)) {
    
66.     start--;
    
67.     set.remove(start);
    
68.     setUsed.add(end);
    
69.    }
    
70. 
    
71.    intervalList.add(new Interval(start, end));
    
72.   }
    
73. 
    
74.   intervalList.sort(Comparator.comparing(Interval::getStart));
    
75. 
    
76.   for (Interval interval: intervalList) {
    
77.    int start = interval.start;
    
78.    int end = interval.end;
    
79.    if (start == end) {
    
80.     sb.append(start + ",");
    
81.    } else {
    
82.     sb.append(start + "-" + end + ",");
    
83.    }
    
84.   }
    
85. 
    
86.   sb.deleteCharAt(sb.length() - 1);
    
87.   return sb.toString();
    
88. }
    
89. }

复制代码

补充内容 (2017-9-10 14:58):
这个是改进后的代码，测过有效。

补充内容 (2017-9-11 07:12):
有一个小BUG, 67行应删除。

这答案测试结果
input : [7, 1, 5, 4, 2, 0]
output: 7,1,5,4,2
好像不对啊

unsorted list那题set存的是什么？ 是Interval吗？
怎么才能实现1 - 1-2 -> 1-3 -> 1-4 -> 1-5？

xiaojunji 发表于 2017-9-10 08:16
这答案测试结果
input : [7, 1, 5, 4, 2, 0]
output: 7,1,5,4,2

有可能是有小BUG的 我也没有调。

xiaojunji 发表于 2017-9-10 08:16
这答案测试结果
input : [7, 1, 5, 4, 2, 0]
output: 7,1,5,4,2

另外，这个答案只是第一步，只能是有序的，对于无序的，这个答案不能处理。
无序的答案，我讲了一下，并没有写在这里。

xiaojunji 发表于 2017-9-10 08:42
unsorted list那题set存的是什么？ 是Interval吗？
怎么才能实现1 - 1-2 -> 1-3 -> 1-4 -> 1-5？

Interval.  答案不是太方便贴，我等一下写一下给你看？

真好，讲的很详细

弱弱的说下 Palo Alto Networks 不止问算法题 还问很多别的。。。。我面挂过。。。祝好运