狗家新鲜电面跪经

其实题目非常简单，但是我个人的问题把电面当做了onsite来做，把Google Doc当成白板来写我的推理思路，结果浪费很多时间在打字上，再加上调整改错啥的，时间到了只写了一题。。。

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

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

结论就是电面因为题目普遍不难还是要重视时间，会做尽量秒了，尤其是不怎么跟你唠嗑的（比较忙没太多心思听你细节/结果导向），宁愿少交流先找张纸默默帮助自己理清思路（当然code写完一个段落还是要解释给面试官听的）迅速把code码完然后上unit test walk through，也别用时太多。吸取我惨痛的教训

照着我自己的想法写了个code，觉得自己有些地方处理的不是很简洁啊，尤其是关于index和层数的处理部分……求给点建议啊啊啊。
还有，我给的test case有限，基本算法写错了一定要告诉我啊啊啊啊……感谢感谢！

1. 
   
2. struct TreeNode {
   
3.     int val;
   
4.     TreeNode *left, *right;
   
5.     TreeNode(int v) {
   
6.         val = v;
   
7.         left = nullptr;
   
8.         right = nullptr;
   
9.     }
   
10. };
    
11. 
    
12. void bfsPrint(TreeNode* root) {
    
13.     if (root==nullptr) return;
    
14.     queue<TreeNode*> Q;
    
15.     Q.push(root);
    
16.     while (!Q.empty()) {
    
17.         int len = Q.size();
    
18.         for (int i=0; i<len; i++) {
    
19.             TreeNode* cur = Q.front();
    
20.             Q.pop();
    
21.             cout << cur->val << " ";
    
22.             if (cur->left) Q.push(cur->left);
    
23.             if (cur->right) Q.push(cur->right);
    
24.         }
    
25.         cout << endl;
    
26.     }
    
27. }
    
28. 
    
29. bool isNodeValid_iterative(TreeNode* root, int id) {
    
30.     //not sure these two corner cases are valid, better way?
    
31.     if (id<=0 || root==nullptr) return false;
    
32.     if (id==1 && root!=nullptr) return true;
    
33.    
    
34.     // find which layer the id is in
    
35.     int h = 1;
    
36.     while (id>(1<<h)-1) h++;
    
37. //    cout << h << endl;
    
38.     while (root!=nullptr && id>1) {
    
39.         // on the right bra
    
40.         // ((1<<h-1)-1): number of nodes on all preivous layers
    
41.         // 1<<h-2: half of number of nodes on this layer
    
42. //        cout << id << " " << h << endl;
    
43.         if (id - ((1<<h-1)-1) > 1<<h-2) {
    
44.             root = root->right;
    
45.             id -= 1<<h-1;
    
46.         } else {
    
47.             root = root->left;
    
48.             id -= 1<<h-2;
    
49.         }
    
50.         h--;
    
51.     }
    
52.     return root!=nullptr && id==1;
    
53. }
    
54. 
    
55. bool helper_recursive(TreeNode* root, int id, int h) {
    
56.     if (root==nullptr) return false;
    
57.     if (id==1) return true;
    
58. //    cout << id << " " << h << endl;
    
59.     if (id - ((1<<h-1)-1) > 1<<h-2)
    
60.         return helper_recursive(root->right, id - (1<<h-1), h-1);
    
61.     else
    
62.         return helper_recursive(root->left, id - (1<<h-2), h-1);
    
63. }
    
64. 
    
65. bool isNodeValid_recursive(TreeNode* root, int id) {
    
66.     //not sure these two corner cases are valid, better way?
    
67.     if (id<=0 || root==nullptr) return false;
    
68.     if (id==1 && root!=nullptr) return true;
    
69.    
    
70.     // find which layer the id is in
    
71.     int h = 1;
    
72.     while (id>(1<<h)-1) h++;
    
73. //    cout << h << endl;
    
74.     return helper_recursive(root, id, h);
    
75. }
    
76. 
    
77. int main() {
    
78.     TreeNode* root = new TreeNode(1);
    
79.     root->left = new TreeNode(2);
    
80.     root->right = new TreeNode(3);
    
81.     root->left->left = new TreeNode(4);
    
82.     root->left->right = new TreeNode(5);
    
83.     root->right->left = new TreeNode(6);
    
84.     root->left->left->left = new TreeNode(8);
    
85.     root->left->left->right = new TreeNode(9);
    
86.     root->left->right->left = new TreeNode(10);
    
87.     bfsPrint(root);
    
88.     cout << endl;
    
89. 
    
90.     cout << "Iterative & Recursive" << endl;   
    
91.     for (int i=0; i<22; i++) {
    
92.         cout << i << ": " << (isNodeValid_iterative(root, i) ? "True" : "False") << endl;
    
93.         cout << i << ": " << (isNodeValid_recursive(root, i) ? "True" : "False") << endl;
    
94.     }
    
95.     return 0;
    
96. }
    

复制代码

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

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

感觉是这样的。上次店面的时候面试官来晚了，然后我在解答他基础概念问题和做题的时候一直唠叨，导致时间有点紧，然后经面试官提醒赶紧找点test case过了一下。但时间还是很紧所以要加面

楼主您好，我能想到的方案是，不断用 index ％ 2 判断从下到上来自左子树还是右子树，把结果存起来，然后从上到下遍历一遍check是否为null，请问有不需要两次遍历＋o（n） 空间支出的做法吗？已加米！

飞人殿下 发表于 2018-10-30 12:52
楼主您好，我能想到的方案是，不断用 index ％ 2 判断从下到上来自左子树还是右子树，把结果存起来，然后从 ...

按照我的递归方法就不用存了，因为index固定你每次都能列公式算出来当前搜索的范围，试一试就知道了，那个数字关系很容易就能找出来

请问能求一下递归的代码吗？

飞人殿下 发表于 2018-10-29 22:52
楼主您好，我能想到的方案是，不断用 index ％ 2 判断从下到上来自左子树还是右子树，把结果存起来，然后从 ...

不用存啊，一边算余数一边往下走就行了吧

Heinrich 发表于 2018-10-31 12:46
照着我自己的想法写了个code，觉得自己有些地方处理的不是很简洁啊，尤其是关于index和层数的处理部分…… ...

recursive 和 iterative都写了

suntopia 发表于 2018-10-30 13:37
按照我的递归方法就不用存了，因为index固定你每次都能列公式算出来当前搜索的范围，试一试就知道了，那 ...

您说的当前搜索范围指的是确定走左子树还是右子树吗？