Google实习电面

第一个人的第一个问题是Word BreakII.写完后他问我为什么选择set作为字典容器.我说我一般有3个选择. 1. Set(rbtree,logn time) 2.Unordered_set(hash table, may use more space,为了处理碰撞保持合适的load factor,空间小会退化成线性) 3.trie(空间小)。

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

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

充内容 (2015-11-9 02:53):
word breakII的链接     感觉面试好难  一开始就上来那么leetcode hard的题目，还问了25分钟system design

写了下merge logs的题，这题确实有些麻烦。。欢迎指教

1. public class MergeIntervalLogs {
   
2. 
   
3.         class Point {
   
4.                 int num;
   
5.                 int flag;
   
6.                 public Point(int num, int flag) {
   
7.                         this.num = num;
   
8.                         this.flag = flag;
   
9.                 }
   
10.         }
    
11.        
    
12.         class Record {
    
13.                 Point point;
    
14.                 int count;
    
15.                 public Record(Point p, int c) {
    
16.                         point = p;
    
17.                         count = c;
    
18.                 }
    
19.         }
    
20.         public List<int[]> mergeLogs(int[][] A, int[][] B) {
    
21.                
    
22.                 List<Point> points = new ArrayList<Point>();
    
23.                 for (int[] arr : A) {
    
24.                         points.add(new Point(arr[0], 1));
    
25.                         points.add(new Point(arr[1], 0));
    
26.                 }
    
27.                 for (int[] arr : B) {
    
28.                         points.add(new Point(arr[0], 1));
    
29.                         points.add(new Point(arr[1], 0));
    
30.                 }
    
31.                 Collections.sort(points, new Comparator<Point>() {
    
32.                         public int compare(Point p1, Point p2) {
    
33.                                 if(p1.num == p2.num) {
    
34.                                         return p1.flag - p2.flag;
    
35.                                 }
    
36.                                 return p1.num - p2.num;
    
37.                         }
    
38.                 });
    
39.                 int count = 0;
    
40.                 List<Record> records = new ArrayList<Record>();
    
41.                 for (Point p : points) {
    
42.                         if (p.flag == 1) {
    
43.                                 count++;
    
44.                         } else {
    
45.                                 count--;
    
46.                         }
    
47.                         records.add(new Record(p, count));
    
48.                 }
    
49.                
    
50.                 return getResult(records);
    
51.         }
    
52.         private List<int[]> getResult(List<Record> records) {
    
53.                 List<int[]> res = new ArrayList<int[]>();
    
54.                 int start = records.get(0).point.num;
    
55.                 int val = records.get(0).count;
    
56.                 for (int i = 1; i < records.size(); i++) {
    
57.                         res.add(new int[]{start, records.get(i).point.num, 2 - val});
    
58.                         start = records.get(i).point.num;
    
59.                         val = records.get(i).count;
    
60.                 }
    
61.                 return res;
    
62.         }
    
63.        
    
64.         public static void main(String[] args) {
    
65.                 int[][] A = {{1,4},{6,8}};
    
66.                 int[][] B = {{2,5}};
    
67.                 MergeIntervalLogs ml = new MergeIntervalLogs();
    
68.                 List<int[]> res = ml.mergeLogs(A, B);
    
69.                 for (int[] arr : res) {
    
70.                         System.out.println(arr[0] + " " + arr[1] + " " + arr[2]);
    
71.                 }
    
72.         }
    
73. }
    

复制代码

Augustus 发表于 2015-11-9 02:13
要跑test  case吗？感觉这么短时间写出来还能跑过case好难。。。

面试官给的case能跑过，但是我后来自己写了几个case,发现有bug...感觉这个interval的case太多了 泪奔TAT 只有2点积分，一小时只能回复2条消息 0.0

宝贝忆彼岸 发表于 2015-11-9 01:49
那这样岂不是[1,5],[6,8]都down掉了？为什么会产生[1,2,1]这样的数据？

B在[1,2]内是好的,[1,2]内A不能工作 B可以，所以是1

好难，求大米，求实习 ><

请问机器B[2,5]的意思是2-5 down掉了吗？还是说只有2和5是好的？

宝贝忆彼岸 发表于 2015-11-9 01:23
请问机器B[2,5]的意思是2-5 down掉了吗？还是说只有2和5是好的？

[2,5]range内都down了

abcd1992719g 发表于 2015-11-9 01:23
[2,5]range内都down了

那这样岂不是[1,5],[6,8]都down掉了？为什么会产生[1,2,1]这样的数据？

要跑test  case吗？感觉这么短时间写出来还能跑过case好难。。。

abcd1992719g 发表于 2015-11-9 02:14
B在[1,2]内是好的,[1,2]内A不能工作 B可以，所以是1

哦哦，明白了，感谢lz耐心解答！

好难的实习电面。。。