Square第二轮电面 2015/10/1

你们面square的后来都怎么样了啊

square onsite面经好少啊，强烈建议楼主onsite回来share下下，提前预祝楼主拿offer哈哈

cjqhenry 发表于 2015-10-7 08:05
楼主能说下具体咋做的么？ 感觉略难啊，多谢！

就是类似于Skyline的思路。弄一个map，然后把所有高度变化的节点都存在Map里，然后每掉下来一个方块就update map就好了

开水蛙 发表于 2015-10-8 17:43
你们面square的后来都怎么样了啊

还没onsite啊

这题用segment tree吧

zxl9171 发表于 2015-10-27 16:20
这题用segment tree吧

我也觉得用segment tree, 但是建树要有个上限，这道题不知道有没有给上限

所以这道题到底应该怎么做啊

这个题是比较典型的线段树（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)

如此即可。

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. }

复制代码

这题首先区间范围并没有给定。可能是 0 - DOUBLE_MAX。再者 position都是double的数字。所以segment tree似乎无法真正解决。