GoogleNYC跪经

上周一Google NYC面的，今天得知没有过HC。


第一轮: Print BST Kth level alternatively
比如  5 ,k = 2的话， 打印结果1 8 3 6
    /  \
   2    7
  / \  / \
  1 3 6  8
比如  5 ,k = 2的话， 打印结果3 8 6
    /  \
   2    7
    \  / \
    3 6  8
这道题虽然说是BST,但跟BST没啥关系。
一开始我没有很好的思路，然后面试官提示DFS/BFS，我就想到BFS+deque的做法：

1. 
   
2. void printBSTKthLevelAlt(TreeNode *root, int k) {
   
3.   if (root == nullptr || k < 0) {
   
4.     return;
   
5.   }
   
6.   deque<TreeNode*> q;
   
7.   int level = 0;
   
8.   q.push_back(root);
   
9.   while(!q.empty()) {
   
10.     if (level == k) {
    
11.       printLevel(q);
    
12.       return;
    
13.     }
    
14.     auto ls = q.size();
    
15.     for(auto i = 0; i < ls; ++i) {
    
16.       auto node = q.front();
    
17.       q.pop_front();
    
18.       if (q->left != nullptr) {
    
19.         q.push_back(q->left);
    
20.       }
    
21.       if (q->right != nullptr) {
    
22.         q.push_back(q->right);
    
23.       }
    
24.     }
    
25.     ++k;
    
26.   }
    
27. }
    
28. 
    
29. void printLevel(const deque<TreeNode*>& q) {
    
30.   bool left = true;
    
31.   while (!q.empty()) {
    
32.     TreeNode* node;
    
33.     if (left) {
    
34.       node = q.front();
    
35.       q.pop_front();
    
36.     }
    
37.     else {
    
38.       node = q.back();
    
39.       q.pop_back();
    
40.     }
    
41.     cout << node->val << ' ';
    
42.     left != left;
    
43.   }
    
44.   cout << endl;
    
45. }
    

复制代码

然后面试官问我time&space complexity是什么，我答道O(n), O(2^k)。
然后他说怎么可以在保持time complexity的同时优化space。我就开始纠结了。
他提示说用DFS，我比划了半天也没想出来。然后时间快到的时候，他告诉了我他的思路：
维护两个stack，一个stack先push right child，另一个先push left child
比如我们有      a1                        这棵树，我们想打印k=3这层，
                 /            \
        a2             a3
          /    \        /      \
     a4    a5      a6      a7
    / \   /

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

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

们根本不需要原本的顺序，只要知道两个vector有哪些相同的indexes就好了。
而且面试官也没有说要再把我们的数据结构还原成sparse vector。赖我自己没有精确的理解面试官的意图。
然后面试官又问我如果是matrix的话，怎么表示。我这个时候又特别跳的说不知道可不可以用quardTtree。面试官微笑的说，因垂丝汀，用quardTree的话，space complexity是什么？我，。。。
不过也没有过多的询问我，最后让我用别的数据结构表示。我就告诉面试官类似的思路，不过是two d array。

面试官人都挺好的，交流的也都挺愉快的。除了第二轮外，感觉都是东欧人。
没有遇到难题，第二，三轮都挺水的。第一轮解决了问题，但follow up没有跟上面试官的逻辑。
整体上感觉自己题解虽然还可以，但还是面试经历太少，自己有点儿跳，板书也有点儿慢。
再接再厉吧。


补充内容 (2016-8-5 07:06):
第四轮代码
if (it1 == p_to_m_.end()) 和 if (it2 == p_to_m_.end())
里面有bug

chenqidi 发表于 2016-8-8 20:17
求问有代码实现吗？

1. struct TreeNode {
   
2.     int val;
   
3.     TreeNode* left, * right;
   
4.     TreeNode(int v) : val(v), left(NULL), right(NULL) {};
   
5. };
   
6. 
   
7. class TreeIterator {
   
8. public:
   
9.         TreeIterator(TreeNode* root, int k) : max_level(k) {
   
10.                 if (root) stk.push(make_pair(0, root));
    
11.         }
    
12.        
    
13.         bool has_next() { return !stk.empty(); }
    
14.        
    
15.         int next() {
    
16.                 if (stk.empty()) throw "out of range";  
    
17.                 int ret_val = stk.top().second->val;
    
18.                 stk.pop();
    
19.                 traverse();
    
20.                 return ret_val;
    
21.         };       
    
22.        
    
23.         virtual TreeNode* get_left (TreeNode *n)=0;
    
24.         virtual TreeNode* get_right(TreeNode *n)=0;
    
25. 
    
26. protected:       
    
27.         void traverse() {
    
28.                 while (!stk.empty() && stk.top().first != max_level) {
    
29.                         int next_level = stk.top().first+1;
    
30.                         TreeNode* left  = get_left (stk.top().second);
    
31.                         TreeNode* right = get_right(stk.top().second);
    
32.                         stk.pop();
    
33.                         if (right) stk.push(make_pair(next_level, right));
    
34.                         if (left)  stk.push(make_pair(next_level, left ));
    
35.                 }               
    
36.         }
    
37.         stack<pair<int, TreeNode*>> stk;
    
38.         int max_level;
    
39.        
    
40. };
    
41. 
    
42. class TreeForwardIterator : public TreeIterator {
    
43. public:
    
44.     TreeForwardIterator(TreeNode* root, int k) : TreeIterator(root, k) { traverse(); };
    
45.         TreeNode* get_left (TreeNode* n) { return n->left;  };
    
46.         TreeNode* get_right(TreeNode* n) { return n->right; };
    
47. };
    
48. 
    
49. 
    
50. class TreeReverseIterator : public TreeIterator {
    
51. public:
    
52.     TreeReverseIterator(TreeNode* root, int k) : TreeIterator(root, k) { traverse(); };
    
53.         TreeNode* get_left (TreeNode* n) { return n->right; };
    
54.     TreeNode* get_right(TreeNode* n) { return n->left;  };       
    
55. };
    
56. 
    
57. vector<int> tree_level_alt(TreeNode *root, int k) {
    
58.         TreeForwardIterator i_left (root, k);
    
59.         TreeReverseIterator i_right(root, k);
    
60.         vector<int> result;
    
61.        
    
62.         int l = INT_MIN, r = INT_MAX;
    
63.         while (l < r){
    
64.                 l = i_left.has_next()  ? i_left.next()  : INT_MAX;
    
65.                 r = i_right.has_next() ? i_right.next() : INT_MIN;
    
66.                 if (l < r) { result.push_back(l); result.push_back(r);}
    
67.                 else { if (l == r) result.push_back(l); }
    
68.         }
    
69.         return result;
    
70. };

复制代码

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

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

第四轮可以用trie来代替hash table来节省空间，面试时也忘了提了

1. 不是level order 遍历么？

第一题我觉得你的思路更好啊

bluepp 发表于 2016-8-5 22:53
1. 不是level order 遍历么？

差不多，打印顺序不同

第一题从空间complexity来说确实是他的小。stack就是前序遍历非递归算法那个stack，栈内元素照理说是不超过树的高度的k。但是BFS需要维护每层所有元素，空间上是2^k。
另外对DFS来说假设树是BST是有意义的。因为两个指针有可能会相互错过对方。BST可以用来判断终止条件（左指针指向的元素<右指针）。

第一题用dfs的话space complexity只有O(k)

hxtang 发表于 2016-8-6 01:36
第一题从空间complexity来说确实是他的小。stack就是前序遍历非递归算法那个stack，栈内元素照理说是不超过 ...

了解了，谢谢

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

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

第四题，直接用hash table 存储每个名字的manager 不行吗？ 这样不是每个功能都能实现？