Square第二轮电面 2015/10/1

Square第二轮电面~

是写一个function, drop(double position, double size), 即从高处掉一个方块，左边的x坐标是position，方块的边长是size。然后它会一个个叠起

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

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

清楚了没有。

面试结束后1个小时就发来onsite邀请啦^_^

明天Google Onsite加油加油加油~~~！！！

Standard segment tree solution:

1. #include <iostream>
   
2. #include <vector>
   
3. #include <assert.h>
   
4. 
   
5. using namespace std;
   
6. 
   
7. struct Node {
   
8.     Node* left, *right;
   
9.     int start, end, maxHei;
   
10.     Node(int s, int e): start(s), end(e), maxHei(0), left(NULL), right(NULL) {}
    
11. };
    
12. 
    
13. class SegTree {
    
14. public:
    
15.     SegTree(int mr): minRange(1), maxRange(mr) {
    
16.         root = build(minRange, maxRange); // Initialize a range with height 0.
    
17.     }
    
18.    
    
19.     void drop(int position, int size) {
    
20.         int start = position, end = position + size - 1;
    
21.         int newHei = query(root, start, end) + size;
    
22.         modify(root, start, end, newHei);
    
23.     }
    
24.    
    
25.     int getHeight() {
    
26.         return root->maxHei;
    
27.     }
    
28.    
    
29. private:
    
30.     Node* root;
    
31.     int minRange, maxRange;
    
32.    
    
33.     Node* build(int start, int end) {
    
34.         if(start > end) return NULL;
    
35.         if(start == end) {
    
36.             Node* newnode = new Node(start, start);
    
37.             return newnode;
    
38.         }
    
39.         Node* node = new Node(start, end);
    
40.         int mid = start + (end - start) / 2;
    
41.         node->left = build(start, mid);
    
42.         node->right = build(mid+1, end);
    
43.         return node;
    
44.     }
    
45.    
    
46.     int query(Node* node, int start, int end) {
    
47.         if(!node) return INT_MIN;
    
48.         if(node->start >= start && node->end <= end) return node->maxHei;
    
49.         if(node->start > end || node->end < start) return INT_MIN;
    
50.         return max(query(node->left, start, end), query(node->right, start, end));
    
51.     }
    
52.    
    
53.     void modify(Node* node, int start, int end, int newHei) {
    
54.         if(node->start > end || node->end < start) return;
    
55.         if(node->start == node->end) {
    
56.             node->maxHei = newHei;
    
57.             return;
    
58.         }
    
59.         modify(node->left, start, end, newHei);
    
60.         modify(node->right, start, end, newHei);
    
61.         node->maxHei = max(node->left->maxHei, node->right->maxHei);
    
62.     }
    
63.    
    
64. };
    
65. 
    
66. int main(int argc, const char * argv[]) {
    
67.     int maxRange = 10;
    
68.     SegTree seg(maxRange);
    
69.     seg.drop(1, 2);
    
70.     seg.drop(5, 3);
    
71.     assert(seg.getHeight() == 3);
    
72.     seg.drop(2, 4);
    
73.     assert(seg.getHeight() == 7);
    
74.     seg.drop(8, 3);
    
75.     assert(seg.getHeight() == 7);
    
76.     seg.drop(1, 4);
    
77.     assert(seg.getHeight() == 11);
    
78.     seg.drop(7, 2);
    
79.     return 0;
    
80. }

复制代码

还没仔细学习线段树，自己先想了个方法来实现。基本思想就保存每次掉下来一个箱子之后他的start， end， 和height。然后根据height的高低来进行保存。从高往低，遍历每一个箱子。如果新掉下来的箱子start和end掉在某个箱子的位置范围内，就根据那个箱子的高度加上新的箱子的size得到新箱子的高度，然后保存。最后由于我们需要根据height来保存，所以要做一个排序。
时间复杂度有点高。drop是O(nlogn)， getHeight是O(1)。自己写了一些test case跑了一下没发现问题。请大神帮忙看一下。如果有问题，请留言。谢谢

1. class Solution:
   
2.         def __init__(self):
   
3.                 self.boxes = []
   
4. 
   
5.         def drop(self, pos, size):
   
6.                 start = pos
   
7.                 end = pos + size
   
8.                 if not self.boxes:
   
9.                         self.boxes.append([start, end, size])
   
10.                 else:
    
11.                         for i in xrange(len(self.boxes)-1, -1, - 1):
    
12.                                 s = self.boxes[i][0]
    
13.                                 e = self.boxes[i][1]
    
14.                                 h = self.boxes[i][2]
    
15.                                 if s < start < e or s < end < e:
    
16.                                         self.boxes.append([start, end, h + size])
    
17.                                         break
    
18.                                 if i == 0:
    
19.                                         self.boxes.append([start, end, size])
    
20.                 self.boxes.sort(key=lambda x: [x[2], x[0], x[1]])
    
21. 
    
22.         def getHeight(self):
    
23.                 if not self.boxes:
    
24.                         return 0
    
25.                 return self.boxes[-1][2]
    
26. 
    
27. s = Solution()
    
28. s.drop(1, 4)
    
29. s.drop(2, 3)
    
30. s.drop(1,1)
    
31. s.drop(6,10)
    
32. s.drop(10, 1)
    
33. print(s.getHeight())

复制代码

这个题是比较典型的线段树（segment tree）。一种解法是：
1. define Node { double x1, x2, h }，即代表X轴上坐标x1到x2之间能够遇到的最大高度为h
2. 每次来一个方块，设x坐标范围为(a, b)，高度ht, 那么查找segment tree，得到(a, b)之间最大高度，设为H，则（a，b）区间的新高度需要变成（H+ht）
3. 更新segment tree，使（a, b）区间新高度为（H+ht）：从根节点开始遍历，
    1）如果cur_node的（x1，x2）完全包括了（a，b)
          1) cur_node.h = (H+ht)
          2) 如果cur_node有子节点, 递归更新子节点
    2) 如果(x1, x2)跟（a，b）部分重合，假设 a < x1 < b < x2:
           1）生成一个新节点，范围：（a，x2）
           2）新节点left_child生成新节点, 范围(a，x1），right_child = cur_node (范围为x1-x2)
           3) 递归更新cur_node, 但范围从开始的（a，b）变成了（x1，b)

如此即可。

LZ是用Map<Integer, Set<Integer>>这样的map来做的？

f1371342385 发表于 2015-10-2 10:53
LZ是用Map这样的map来做的？

木有~就map<double, double>。跟Skyline有点像，就是记录高度变化的节点们~

Yunying 发表于 2015-10-2 11:02
木有~就map。跟Skyline有点像，就是记录高度变化的节点们~

好的，感谢LZ哈

正整数还好，double感觉好难啊，我怎么觉得应该用interval来做。。

请问楼主，Square的电面每个人都是两轮吗？有没有第二轮和第一轮的表现有关吗？小弟上周刚面了第一轮，面完不到一小时就HR就发邮件问第二次电面的availability，下周要面第二轮。问一下，有第二轮说明第一轮过关了吗？还是说所有人都有第二轮？

obama555 发表于 2015-10-3 03:11
请问楼主，Square的电面每个人都是两轮吗？有没有第二轮和第一轮的表现有关吗？小弟上周刚面了第一轮，面完 ...

有第二轮当然是第一轮过关了啊。。。不过也没什么差吧。。。

Yunying 发表于 2015-10-3 12:13
有第二轮当然是第一轮过关了啊。。。不过也没什么差吧。。。

大大地不一样有，如果所有人都有第二轮，那就不能因为有第二轮就认为第一轮过关，万一第一轮没过关就给第二轮，那无论第二轮面的多好都是fail，太伤感情了，花了时间不得好果子吃

obama555 发表于 2015-10-3 12:23
大大地不一样有，如果所有人都有第二轮，那就不能因为有第二轮就认为第一轮过关，万一第一轮没过关就给第 ...

应该是过了第一轮才有第二轮，反正不管怎么样，都得好好面啊。 加油！