推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1124|回复: 20
收起左侧

狗家电面

[复制链接] |试试Instant~ |关注本帖
skylinezy0111 发表于 2017-8-11 08:36:27 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Other在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
目前Quality Engineer在职,狗家recuiter linkedin reach out,正好也在看他家的SETI职位,就给了简历。
刚刚电面完,自己感觉要跪,发个面经造福一下吧
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
Given a binary tree, write a function to erase a list of nodes from the tree and return the forest created from this operation
Example:

          1
       /      \
     2        3
   /  \       /  \. From 1point 3acres bbs
4     5    6    7

Erase(4, 3)

output: 3 trees

      1               6             7
     /
    2
     \
      5

自己决定输入输出形式,自己定义treenode结构。
前面分析题目都还可以,写的时候脑子抽了选了DFS,明明一个简单的recursion能解决的问题。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
最后给自己整蒙了,写了巨长,还自己找出了一个bug

最后问了问test case,让我问了几个问题就结束了。

面试官看名字应该是烙印,不过人很不错完全没有口音,讨论的时候也很积极的给回应。交流的倒是挺顺畅。总结下来还是思考的时候不够深入,着急选了一种solution就开始写,当写的不顺畅的时候没有跳出来想一想其他的方向。
-google 1point3acres
还不知道结果,求好运吧。. 鍥磋鎴戜滑@1point 3 acres


评分

3

查看全部评分

本帖被以下淘专辑推荐:

其实我掉线了 发表于 5 天前 | 显示全部楼层
如果是自己设计data structure,是不是可以考虑直接存一个parent node呢?比如:
class TreeNode<T> {
      T val;
      TreeNode left;
      TreeNode right;
      TreeNode parent;.鐣欏璁哄潧-涓浜-涓夊垎鍦
      //...
}

然后遍历的时候,在参数里面加一个boolean标注是左还是右子树
回复 支持 1 反对 0

使用道具 举报

ofdkk88 发表于 2017-8-11 09:20:34 | 显示全部楼层
祝楼主好运,offer有望

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Margaret601 发表于 2017-8-11 09:50:15 | 显示全部楼层
求问LZ简单的recursion怎么写。。。或者这是LC上的类似题么……感觉好难
回复 支持 反对

使用道具 举报

wxdsdtc 发表于 5 天前 | 显示全部楼层
试着做一下:
  1.     public List<TreeNode> res;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  2.     public List<TreeNode> main(TreeNode root, int[] erase) {
  3.                 res = new ArrayList<TreeNode>();. 鍥磋鎴戜滑@1point 3 acres
  4.         if(root == null) return res;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  5.         Set<Integer> set = new HashSet<Integer>();
  6.         for(int val : erase) set.add(val);
  7.         helper(root, set);
  8.         return res;.1point3acres缃
  9.     }
  10.    
  11.     private void helper(TreeNode root, HashSet<Integer> erase){
  12.         if(root == null) return;
  13.         TreeNode left = root.left;
  14.         TreeNode right = root.right;
  15.         if(erase.contains(root.val)){
  16.             if(root.left != null && !erase.contains(root.left.val)){
  17.                 res.add(left);
  18.             }
  19.             if(root.right != null && !erase.contains(root.right.val)){-google 1point3acres
  20.                 res.add(right);
  21.             }
  22.             root = null;
  23.         }
  24.         helper(left, erase);
  25.         helper(right, erase);
  26.     }
复制代码

补充内容 (2017-8-16 13:29):
多谢@bearicc 的提醒,的确还是需要而外一个变量记录父节点的,然后手动设置其father.left = null, father.right = null. 光把root = null只是取消引用,java会更快的回首内存,但是不是立刻,还是需要free/Delete
回复 支持 反对

使用道具 举报

reliveinfire 发表于 5 天前 | 显示全部楼层
试做一下 不知道这样思路正不正确?
如果发现是要erase 的node, 将parent 左/右 指成NULL

如果不是要erase的node, 则看是不是root, 是的话存起来.. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
class Solution {
        public:
        vector<TreeNode*> eraseBT(TreeNode* root, unordered_set<TreeNode*> remove){
                vector<TreeNode*> ans;
                helper(root, NULL, 1, remove, ans, 1);
        }

        void helper(TreeNode* curr, TreeNode* parent, bool isLeft, unordered_set<TreeNode*> remove, vector<TreeNode*>& ans, int isRoot){
                if (curr == NULL).鏈枃鍘熷垱鑷1point3acres璁哄潧
                        return;
                if (remove.count(curr)!=0){.1point3acres缃
                        if (parent){
                                if (isLeft)
                                        parent->left = NULL;
                                else
                                        parent->right = NULL;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        }. 鍥磋鎴戜滑@1point 3 acres
                        helper(curr->left, curr, 1, remove, ans, 1);
                        helper(curr->right, curr, 0, remove, ans, 1);
                } else {
                        if (isRoot)
                                ans.push_back(curr);
                        helper(curr->left, curr, 1, remove, ans, 0);
                        helper(curr->right, curr, 0, remove, ans, 0);
                }
                return;
        }
};
回复 支持 反对

使用道具 举报

bearicc 发表于 5 天前 | 显示全部楼层
wxdsdtc 发表于 2017-8-14 09:02. more info on 1point3acres.com
试着做一下:
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
好像不太对,当发现要erase的node,你没有处理这个node的父节点:
需要作 parent->left = nullptr 如果 parent->left == cur

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

bearicc 发表于 5 天前 | 显示全部楼层
感觉是一个新题,于是做了下:
  1. void helper(TreeNode* parent, TreeNode* cur, unordered_set<int>& nodes, vector<TreeNode*>& result) {
  2.     if (!cur) return;                                                            
  3.     if (nodes.find(cur->val) != nodes.end()) {                                      
  4.         if (parent) {                                                               
  5.             if (parent->left == cur) {                                             
  6.                 parent->left = nullptr;                                             -google 1point3acres
  7.             } else {                                                                . more info on 1point3acres.com
  8.                 parent->right = nullptr;                                            
  9.             }                                                                       
  10.         }                                                                           
  11.         nodes.erase(cur->val);                                                      
  12.         if (cur->left && nodes.find(cur->left->val) == nodes.end()) {               
  13.             result.push_back(cur->left);                                            
  14.         }                                                                           . from: 1point3acres.com/bbs
  15.         if (cur->right && nodes.find(cur->right->val) == nodes.end()) {            
  16.             result.push_back(cur->right);                                          
  17.         }                                                                           . visit 1point3acres.com for more.
  18.         helper(nullptr, cur->left, nodes, result);                                  -google 1point3acres
  19.         helper(nullptr, cur->right, nodes, result);                                 
  20.     } else {                                                                        
  21.         helper(cur, cur->left, nodes, result);                                      
  22.         helper(cur, cur->right, nodes, result);                                    
  23.     }                                                                              
  24. }                                                                                   
  25.                                                                                     
  26. vector<TreeNode*> erase(TreeNode* root, vector<int> nodes) {                        
  27.     if (nodes.empty()) return {root};                                                                                                                                             
  28.     unordered_set<int> dict(nodes.begin(), nodes.end());                           
  29.     vector<TreeNode*> result;                                                       .鏈枃鍘熷垱鑷1point3acres璁哄潧
  30.     if (dict.find(root->val) == dict.end()) result.push_back(root);                 . Waral 鍗氬鏈夋洿澶氭枃绔,
  31.     helper(nullptr, root, dict, result);                                            
  32.     return result;                                                                  
  33. }
复制代码
回复 支持 反对

使用道具 举报

wxdsdtc 发表于 5 天前 | 显示全部楼层
bearicc 发表于 2017-8-14 10:38
好像不太对,当发现要erase的node,你没有处理这个node的父节点:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
需要作 parent->left = nullptr 如果  ...

我刚开始也是这么想的,后来发现如果当前node = null (第22行). 父节点自然会指向null。
我觉得我这样处理没错啊,我最开始写的和你楼上差不多,需要存父节点和标记左还是右,后来发现可以写的更简单。
回复 支持 反对

使用道具 举报

2011051305 发表于 5 天前 | 显示全部楼层
晕啊我连题都没读懂 根据这个Binary tree 执行erase(4,3)的操作 要返回3个tree 分别是6,7(因为3是6,7的父节点),那么1-2-5和4有什么关系呢? 。。。。 麻烦您能再clairfy一下么? 谢谢!!
回复 支持 反对

使用道具 举报

randrand1 发表于 5 天前 | 显示全部楼层
wxdsdtc 发表于 2017-8-14 09:02-google 1point3acres
试着做一下:

这个代码没有处理树的root node. 比如如果树就是只有一个node {1},然后erase是空集,这个代码返回的是空集。应该会把原来的树也返回。
用一个tag来表明parent node有没有删掉,感觉就可以了
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct TreeNode{. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  4.     int val;. From 1point 3acres bbs
  5.     TreeNode *left,*right;
  6.     TreeNode(int x):val(x),  left(NULL),  right(NULL) {}
  7. };
  8. .1point3acres缃
  9. void dfs(vector<TreeNode*>& res, TreeNode* root,  unordered_set<int> &s,  bool added) {
  10.     if (root == NULL) return;
  11.     if (s.find(root->val) == s.end()) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  12.         if (!added) res.push_back(root);
  13.         dfs(res,  root->left,  s,  true);
  14.         dfs(res,  root->right,  s,  true); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  15.         if (root->left != NULL && s.find(root->left->val) != s.end()) {
  16.             root->left = NULL;
  17.         }
  18.         if (root->right!= NULL && s.find(root->right->val) != s.end()) {
  19.             root->right= NULL;
  20.         }
  21.     } else {
  22.         dfs(res,  root->left,  s,  false);
  23.         dfs(res,  root->right,  s,  false);
  24.     } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  25. }
  26. -google 1point3acres
  27. vector<TreeNode*> eraseNodes(TreeNode* root,  vector<int> & erase) {
  28.     unordered_set<int> s(erase.begin(),  erase.end());
  29.     vector<TreeNode *> res;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  30.     dfs(res,  root,  s,  false);
  31.     return res;. 鍥磋鎴戜滑@1point 3 acres
  32. }

  33. void printTree(TreeNode* root)  {. 1point 3acres 璁哄潧
  34.     if (root == NULL) {. visit 1point3acres.com for more.
  35.         cout << " null "; return;
  36.     }. 1point 3acres 璁哄潧
  37.     cout <<" "<< root->val  <<" ";
  38.     printTree(root->left);
  39.     printTree(root->right);. 1point3acres.com/bbs
  40. }

  41. int main(int argc, const char *argv[])
  42. {
  43.     TreeNode* root = new TreeNode(1);
  44.     vector<int> erase;
  45.     auto v = eraseNodes(root,  erase);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  46.     for(auto i: v) {
  47.         printTree(i);
  48.         cout << endl;
  49.     }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  50.     root->left = new TreeNode(2);. Waral 鍗氬鏈夋洿澶氭枃绔,
  51.     root->right= new TreeNode(3);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  52.     root->right->left= new TreeNode(6);
  53.     root->right->right= new TreeNode(7);
  54.     root->left->left= new TreeNode(4);
  55.     root->left->right= new TreeNode(5);
  56.     erase = {3, 4};
  57.     v = eraseNodes(root,  erase);
  58.     for(auto i: v) {
  59.         printTree(i);
  60.         cout << endl;
  61.     }
  62.     return 0;
  63. }
复制代码
回复 支持 反对

使用道具 举报

bearicc 发表于 5 天前 | 显示全部楼层
wxdsdtc 发表于 2017-8-14 12:21
我刚开始也是这么想的,后来发现如果当前node = null (第22行). 父节点自然会指向null。
我觉得我这样 ...

不太了解Java。如果直接将root 设为null,不清楚其他指向这个object的对象是否也会指向null. 如果设成null是直接将那个object变为null而不是将reference指向null,那你的方法应该是可行的。
回复 支持 反对

使用道具 举报

bearicc 发表于 5 天前 | 显示全部楼层
bearicc 发表于 2017-8-14 22:33
不太了解Java。如果直接将root 设为null,不清楚其他指向这个object的对象是否也会指向null. 如果设成nul ...

typo, root -> current node
回复 支持 反对

使用道具 举报

mushbunny 发表于 4 天前 | 显示全部楼层
这是我的java code,用了recursion,参考的思路是leetcode 450 delete node in BST, 我大致跑了几个test case感觉好像是对的
  1. public class Solution {
  2.         public List<TreeNode> remove(TreeNode root, List<TreeNode> toRemove) {. from: 1point3acres.com/bbs
  3.                 List<TreeNode> prevForest = new ArrayList<>();. From 1point 3acres bbs
  4.                 prevForest.add(root);
  5.                 for (TreeNode r : toRemove) {
  6.                         List<TreeNode> currForest = new ArrayList<>();
  7.                         for (TreeNode smRoot : prevForest) {
  8.                                 remove(smRoot, currForest, r);
  9.                         }
  10.                         prevForest = currForest;
  11.                 }
  12.                 return prevForest;
  13.         }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  14.         private TreeNode remove(TreeNode root, List<TreeNode> prev, TreeNode toRemove) {
  15.                 if (root == null) {
  16.                         return null;
  17.                 }
  18.                 if (root == toRemove) {
  19.                         if (root.left != null) {
  20.                                 prev.add(root.left);
  21.                         }
  22.                         if (root.right != null) {. from: 1point3acres.com/bbs
  23.                                 prev.add(root.right);
  24.                         }. From 1point 3acres bbs
  25.                         return null;
  26.                 }
  27.                 root.left = remove(root.left, prev, toRemove);
  28.                 root.right = remove(root.right, prev, toRemove);. visit 1point3acres.com for more.
  29.                 return root;
  30.         }
  31. }
复制代码
回复 支持 反对

使用道具 举报

mushbunny 发表于 4 天前 | 显示全部楼层
啊,14楼是错的,请大家忽略,这一版丢掉了原来的root,应该是下面的这个
  1. public class Solution {
  2.         public List<TreeNode> remove(TreeNode root, List<TreeNode> toRemove) {
  3.                 List<TreeNode> prevForest = new ArrayList<>();
  4.                 prevForest.add(root);
  5.                 for (TreeNode r : toRemove) {
  6.                         List<TreeNode> currForest = new ArrayList<>();
  7.                         for (TreeNode smRoot : prevForest) {
  8.                                 remove(smRoot, currForest, r);
  9.                                 if (smRoot != r) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  10.                                         currForest.add(smRoot);
  11.                                 }
  12.                         }
  13.                         prevForest = currForest;
  14.                 }
  15.                 return prevForest;
  16.         }
  17.         private TreeNode remove(TreeNode root, List<TreeNode> prev, TreeNode toRemove) {
  18.                 if (root == null) {
    . more info on 1point3acres.com
  19.                         return null;
  20.                 }
  21.                 if (root == toRemove) {
  22.                         if (root.left != null) {
  23.                                 prev.add(root.left);
  24.                         }
  25.                         if (root.right != null) {. 1point3acres.com/bbs
  26.                                 prev.add(root.right);.1point3acres缃
  27.                         }
  28.                         return null;
  29.                 }
  30.                 root.left = remove(root.left, prev, toRemove);. more info on 1point3acres.com
  31.                 root.right = remove(root.right, prev, toRemove);
  32.                 return root;
  33.         }
  34. }
复制代码
应该是下面这个
回复 支持 反对

使用道具 举报

randrand1 发表于 4 天前 | 显示全部楼层
mushbunny 发表于 2017-8-15 02:15. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
啊,14楼是错的,请大家忽略,这一版丢掉了原来的root,应该是下面的这个
应该是下面这个

这个复杂度看起来要删掉几个node,就需要遍历几遍剩下的nodes?
回复 支持 反对

使用道具 举报

mushbunny 发表于 4 天前 | 显示全部楼层
randrand1 发表于 2017-8-15 03:05
这个复杂度看起来要删掉几个node,就需要遍历几遍剩下的nodes?

是的是的,谢谢提醒。我按照上面的思路重写了下面的样子,这个应该是O(#nodes)了。基本思路是如果root不要被remove,就丢到result里,然后顺着他的children往下找。如果需要remove就把他的children加到buffer里来直到需要remove的node全部被remove或者没有unvisited nodes了
  1. public class Solution {
  2.         public List<TreeNode> remove(TreeNode root, Set<TreeNode> toRemove) {
  3.                 List<TreeNode> res = new ArrayList<>();
  4.                 Queue<TreeNode> buffer = new LinkedList<>();
  5.                 buffer.add(root);
  6.                 while (!toRemove.isEmpty() && !buffer.isEmpty()) {
  7.                         TreeNode curr = buffer.poll();
  8.                         if (!toRemove.contains(curr)) {. 1point3acres.com/bbs
  9.                                 res.add(curr);
  10.                         }
  11.                         helper(curr, buffer, toRemove);
  12.                 }
  13.                 res.addAll(buffer);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  14.                 return res;
  15.         }
  16.        
  17.         private TreeNode helper(TreeNode curr,  
  18.                         Queue<TreeNode> buffer, Set<TreeNode> toRemove) {
  19.                 if (curr == null) {
  20.                         return null;
  21.                 }
  22.                 if (toRemove.isEmpty()) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  23.                         return curr;
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  24.                 }.1point3acres缃
  25.                 if (toRemove.contains(curr)) {
  26.                         if (curr.left != null) {. From 1point 3acres bbs
  27.                                 buffer.offer(curr.left);
  28.                         }
  29.                         if (curr.right != null) {-google 1point3acres
  30.                                 buffer.offer(curr.right);
  31.                         }
  32.                         toRemove.remove(curr);
  33.                         return null;
  34.                 }
  35.                 curr.left = helper(curr.left, buffer, toRemove);
  36.                 curr.right = helper(curr.right, buffer, toRemove);
  37.                 return curr;. 1point3acres.com/bbs
  38.         }
  39. }
复制代码
回复 支持 反对

使用道具 举报

zzgzzm 发表于 4 天前 | 显示全部楼层
wxdsdtc 发表于 2017-8-14 09:02.1point3acres缃
试着做一下:

我也基本是这个思路。. 1point3acres.com/bbs

但我觉得必须是一定要将非空child nodes加到res中,而不是判断"!erase.contain(root.left.val)". 否则这样将失去所有subtree的node.
.鏈枃鍘熷垱鑷1point3acres璁哄潧
例如: 1   将“2”删去,结果还是有“3”的。
         /
       2
      /
     3

补充内容 (2017-8-15 10:21):
不好意思。你的solution应该是对的,因为在“if(erase.contains(root.val))”条件下没有返回,而是继续在左右子节点递归。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 4 天前 | 显示全部楼层
我是若root本身被删除的话也留在临时结果“roots”中,最后再统一去除空nodes.
  1. vector<TreeNode*> roots;

  2. // helper function
  3. void preOrderSplit(TreeNode* cur, unordered_set<TreeNode*>& toRemove) {
  4.     if (!cur || toRemove.empty()) return;
  5.     if (toRemove.count(cur)) {      
  6.         if (cur->left) roots.push_back(cur->left);. Waral 鍗氬鏈夋洿澶氭枃绔,
  7.         if (cur->right) roots.push_back(cur->right);
  8.         toRemove.erase(cur); delete cur;
  9.         return;
  10.     }
  11.     preOrderSplit(cur->left, toRemove);. 鍥磋鎴戜滑@1point 3 acres
  12.     preOrderSplit(cur->right, toRemove);
  13. }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  14. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  15. vector<TreeNode*> split(TreeNode* r, unordered_set<TreeNode*>& toRemove) {
  16.     roots = {r};
  17.     for (int i = 0; i < roots.size(); ++i)
    . from: 1point3acres.com/bbs
  18.       preOrderSplit(roots[i], toRemove);
  19.    
  20.     vector<TreeNode*> res;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  21.     for (auto r : roots) if (r) res.push_back(r);
  22.     return res;
  23. }
复制代码
回复 支持 反对

使用道具 举报

wxdsdtc 发表于 3 天前 | 显示全部楼层
bearicc 发表于 2017-8-14 22:33
不太了解Java。如果直接将root 设为null,不清楚其他指向这个object的对象是否也会指向null. 如果设成nul ...

你说的是对的,设置为null只能让GC更快的回首这块空间,但是只是取消了引用而已,我真恨不得java也有free或者delete可以用,白写一堆代码。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-8-19 19:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表