Jane街店面

这家面经不多，我来分享一下，为后面的面试攒人品。面试官是个年轻的程序媛，聊几句就能知道此人相当聪明，语速也极快，跟节奏很吃力。。。coding是在collabedit上，上来先问知道in order traversal吗，描述一遍后给了一张tree的图，要求你把in order的顺序报一遍。然后给了一个template<class T> 的TreeNode，里面有constructor以及left，r

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

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

ture情况，姐姐说他们大部分infrastructure都用Ocaml写的，lz表示了一下震惊。
本来以为挂了，今天很意外的收到onsite，因为之前听说他们很多轮店面，希望面试别问Ocaml，求米！

请问你是infra组吗？

发错了，内容已删除

1. #include <iostream>
   
2. #include <queue>
   
3. #include <unordered_map>
   
4. #include <unordered_set>
   
5. #include <vector>
   
6. 
   
7. using namespace std;
   
8. 
   
9. class TreeNode {
   
10.   TreeNode *left;
    
11.   TreeNode *right;
    
12.   int val;
    
13. 
    
14.   public:
    
15.   TreeNode(TreeNode *l, TreeNode *r, int v) : left(l), right(r), val(v) {}
    
16.   TreeNode(int v) : left(nullptr), right(nullptr), val(v) {}
    
17.   TreeNode *get_left() { return left; }
    
18.   TreeNode *get_right() { return right; }
    
19.   int get_val() { return val; }
    
20. };
    
21. 
    
22. // replace with a single val
    
23. TreeNode *copyReplaceValHelper(TreeNode *node, int v) {
    
24.   if (!node) return nullptr;
    
25. 
    
26.   TreeNode *left_copied = copyReplaceValHelper(node->get_left(), v);
    
27.   TreeNode *right_copied = copyReplaceValHelper(node->get_right(), v);
    
28.   return new TreeNode(left_copied, right_copied, v);
    
29. }
    
30. 
    
31. TreeNode *copyReplaceVal(TreeNode *tree, int v) {
    
32.   return copyReplaceValHelper(tree, v);
    
33. }
    
34. 
    
35. // replace with inorder
    
36. TreeNode *copyReplaceInorderHelper(TreeNode *node, const vector<int> &vals, int &idx) {
    
37.   if (!node) return nullptr;
    
38. 
    
39.   TreeNode *left_copied = copyReplaceInorderHelper(node->get_left(), vals, idx);
    
40.   int val_idx = idx++;
    
41.   TreeNode *right_copied = copyReplaceInorderHelper(node->get_right(), vals, idx);
    
42.   return new TreeNode(left_copied, right_copied, vals[val_idx]);
    
43. }
    
44. 
    
45. TreeNode *copyReplaceInorder(TreeNode *tree, const vector<int> &vals) {
    
46.   int idx = 0;
    
47.   return copyReplaceInorderHelper(tree, vals, idx);
    
48. }
    
49. 
    
50. // replace with level order
    
51. TreeNode *copyReplaceLevelOrderHelper(TreeNode *node, unordered_map<TreeNode *, int> &hmap, const vector<int> &vals) {
    
52.   if (!node) return nullptr;
    
53. 
    
54.   TreeNode *left_copied = copyReplaceLevelOrderHelper(node->get_left(), hmap, vals);
    
55.   TreeNode *right_copied = copyReplaceLevelOrderHelper(node->get_right(), hmap, vals);
    
56.   return new TreeNode(left_copied, right_copied, vals[hmap[node]]);
    
57. }
    
58. 
    
59. TreeNode *copyReplaceLevelOrder(TreeNode *tree, const vector<int> &vals) {
    
60.   if (!tree) return nullptr;
    
61. 
    
62.   // create node->idx mapping
    
63.   unordered_map<TreeNode *, int> hmap;
    
64.   queue<TreeNode *> q({tree});
    
65.   int idx = 0;
    
66.   while (!q.empty()) {
    
67.     TreeNode *node = q.front();
    
68.     q.pop();
    
69. 
    
70.     hmap[node] = idx++;
    
71.     if (node->get_left()) q.push(node->get_left());
    
72.     if (node->get_right()) q.push(node->get_right());
    
73.   }
    
74. 
    
75.   // copy
    
76.   return copyReplaceLevelOrderHelper(tree, hmap,vals);
    
77. }
    
78. 
    
79. void printTree(const std::string &prefix, TreeNode *node, bool isLeft) {
    
80.   if (node != nullptr) {
    
81.     std::cout << prefix;
    
82. 
    
83.     std::cout << (isLeft ? "├──" : "└──");
    
84. 
    
85.     // print the value of the node
    
86.     std::cout << node->get_val() << std::endl;
    
87. 
    
88.     // enter the next tree level - left and right branch
    
89.     printTree(prefix + (isLeft ? "│   " : "    "), node->get_left(), true);
    
90.     printTree(prefix + (isLeft ? "│   " : "    "), node->get_right(), false);
    
91.   }
    
92. }
    
93. 
    
94. void printTree(TreeNode *node) {
    
95.   printTree("", node, false);
    
96. }
    
97. 
    
98. int main() {
    
99.   // size = 6
    
100.   TreeNode *input = new TreeNode(new TreeNode(new TreeNode(1), new TreeNode(3), 2), new TreeNode(new TreeNode(5), nullptr, 6), 4);
     
101.   printTree(input);
     
102. 
     
103.   // replace val
     
104.   cout << "replace val " << endl;
     
105.   printTree(copyReplaceVal(input, 0));
     
106. 
     
107.   // replace inorder
     
108.   cout << "replace inorder " << endl;
     
109.   printTree(copyReplaceInorder(input, {1, 3, 5, 7, 9, 2}));
     
110. 
     
111.   // replace level order
     
112.   cout << "replace level order " << endl;
     
113.   printTree(copyReplaceLevelOrder(input, {1, 2, 3, 4, 5, 6}));
     
114. }

复制代码

1. package src;
   
2. 
   
3. import java.util.HashMap;
   
4. import java.util.LinkedList;
   
5. import java.util.List;
   
6. import java.util.Map;
   
7. import java.util.Queue;
   
8. 
   
9. public class ImmutableTree {
   
10.     class TreeNode {
    
11.         TreeNode left;
    
12.         TreeNode right;
    
13.         Integer val;
    
14. 
    
15.         public TreeNode(int v, TreeNode l, TreeNode r) {
    
16.             val = v;
    
17.             left = l;
    
18.             right = r;
    
19.         }
    
20.     }
    
21. 
    
22.     public TreeNode inorderReplaceValue(TreeNode root, int v) {
    
23.         if (root == null)
    
24.             return null;
    
25.         TreeNode left = inorderReplaceValue(root.left, v);
    
26.         TreeNode right = inorderReplaceValue(root.right, v);
    
27.         return new TreeNode(v, left, right);
    
28.     }
    
29. 
    
30.     int idx = 0;
    
31. 
    
32.     public TreeNode inorderReplaceList(TreeNode root, List<Integer> list) {
    
33.         if (root == null)
    
34.             return null;
    
35.         TreeNode left = inorderReplaceList(root.left, list);
    
36.         int value = list.get(idx);
    
37.         idx++;
    
38.         TreeNode right = inorderReplaceList(root.right, list);
    
39.         return new TreeNode(value, left, right);
    
40.     }
    
41. 
    
42.     private TreeNode levelOrderReplaceHelper(TreeNode root, List<Integer> list, Map<TreeNode, Integer> map) {
    
43.         if (root == null)
    
44.             return null;
    
45.         TreeNode left = levelOrderReplaceHelper(root.left, list, map);
    
46.         TreeNode right = levelOrderReplaceHelper(root.left, list, map);
    
47.         return new TreeNode(list.get(map.get(root)), left, right);
    
48.     }
    
49. 
    
50.     public TreeNode levelOrderReplaceList(TreeNode root, List<Integer> list) {
    
51.         Map<TreeNode, Integer> node2IdxMap = new HashMap<>();
    
52.         Queue<TreeNode> q = new LinkedList<>();
    
53.         if (root != null) {
    
54.             q.offer(root);
    
55.         }
    
56.         int curIdx = 0;
    
57.         while (!q.isEmpty()) {
    
58.             int size = q.size();
    
59.             for (int i = 0; i < size; i++) {
    
60.                 TreeNode curNode = q.poll();
    
61.                 node2IdxMap.put(curNode, curIdx);
    
62.                 curIdx++;
    
63.                 if (curNode.left != null)
    
64.                     q.offer(curNode.left);
    
65.                 if (curNode.right != null)
    
66.                     q.offer(curNode.right);
    
67.             }
    
68.         }
    
69.         return levelOrderReplaceHelper(root, list, node2IdxMap);
    
70.     }
    
71. 
    
72. }
    

复制代码