GoogleNYC跪经

sunraincyq 发表于 2016-8-8 08:31
谢谢LZ分享这么详细的面经。请问是你要求到NYC ONSITE的吗还是你本来申请的POSITION是在NYC？

我联系的recruiter是在NYC的，所以他给我安排到NYC面试，但是我想去MTV。

楼主想问一下怎么能和NYC office面试，是投职位的时候就指定的还是他们给你安排的？

补充内容 (2016-8-8 13:31):
NVM看到楼上回复了

白羽幸 发表于 2016-8-6 01:40
第一题用dfs的话space complexity只有O(k)

请问第一题DFS怎么做？

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

求问有代码实现吗？

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

Josh 发表于 2016-8-20 07:16
感觉第一题BFS的空间复杂度也是O(K)啊，因为BFS的queue里面最多有两个level，第k层每个level的数量是O(K) ...

第k层的node数量不是o(k), 是2^(k-1)个

fay19 发表于 2016-8-20 07:21
第k层的node数量不是o(k), 是2^(k-1)个

对，我想错了抱歉

第一题有没有更简洁的DFS的方法呀？hxtang提供的代码，对于我来说，还是不太可能在面试中写出来的，（水平比较挫）