一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1234|回复: 6
收起左侧

g家電面

[复制链接] |试试Instant~ |关注本帖
aceldama 发表于 2016-10-7 09:28:01 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 本科 全职@Google - 网上海投 - 技术电面 |Fail在职跳槽

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
面試官準時到, 口音聽起來像白男說總共時間45mins, 最後留5mins 問問題

稍微介紹一下自己就開始了 (5 mins past)
. 1point 3acres 璁哄潧
You are given a binary tree of N nodes. While it is mostly alright,
there is one extra edge that violates the tree property. Your job is to find it and eliminate it.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
一開始慌了, 根本沒想過tree 還有連錯的; 問了下不是invalid btree
於是花了兩分鐘搞清楚

      p
     / \  -google 1point3acres
   a     b
  /  \ /   \
k    c     d  
-google 1point3acres
.鏈枃鍘熷垱鑷1point3acres璁哄潧
這樣一畫就很清楚了;  錯的edge 會有兩個parent, 所以只要建一個hashmap, key child, value parent. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
然後treverse tree, 中間一直maintain map,  contains key 就找到了

public Map <Node, Node> m = new HashMap<>();

Void findWrong(Node n) {
        if (n == null) return;
        if (n.left != null) {
           Node tmp = m.get(n.left);
        if (tmp == null) {       
           m.put(n.left, n);
        } else {
           n.left = null;
        return;
        }

. From 1point 3acres bbs        if (n.right != null) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
           Node tmp = m.get(n. right);
        if (tmp == null) {       
           m.put(n. right, n);
        } else {. 鍥磋鎴戜滑@1point 3 acres
           n. right = null;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        return;
        }
   findWrong(n.left);
   findWrong(n.right);}
}


中間我找wrong edge 找的太高興了, 以為是找到return 就好, 提醒一下說是要delete, 也就把找到的node = null

每隔個3-5 mins 我就會刺探一下問說我這樣對不對啊 回答都是可以啊

面官也沒說什麼, 就說要問follow up, 到現在時間過 20 mins

follow up:
Given the same problem, 1 edge is wrong, which left one node isolated, how do you fix it?
-google 1point3acres
我又聽不懂了 又花了兩分鐘畫了這個
      p
     / \  
   a     b
  /  \ /   \
k    c     d    y


要把 ac 或 bc delete 掉, 然後連 ay or by

一個node isolated 你tree 裡根本看不到啊,  一個看不到的node 你怎麼連啊
面官說你可以改 input, 我就說那我的input 改成hash map key child, value parent
我的algo 基本沒錯, 只要先找到落單的node 就好了 (find map node without parent). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
然後用之前的algo 去treverse, 找到不設null 改聯到落單node

我好激動啊, 批哩啪拉的把整個流程講了一遍, 面官說 fine 然後我開始寫
寫到最後時間不夠我就把該改的地方又講了一遍 面官也沒說啥

問問題我問:
g家近年上go, angular, swift, 倒是jvm 沒怎麼新動作, 現在外面 cotlin, scala, clojure 好火熱啊
. 1point 3acres 璁哄潧你說g怎麼沒動作啊 . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

面官吱吱嗚嗚地說go 不錯啊 根本沒回答我
然後就結束了

我以為我第一道做出來了 第二道題目出得有點怪 面官也沒搞清楚 應該會算我過吧
隔兩天打電話來拒了我 也沒說原因. 1point3acres.com/bbs

可以幫我看看我哪裡做不好嗎, 搞不好我第一部分錯了也不知道

謝謝!







-google 1point3acres

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴



. Waral 鍗氬鏈夋洿澶氭枃绔,





. 1point 3acres 璁哄潧
. 1point 3acres 璁哄潧
. 1point 3acres 璁哄潧

本帖被以下淘专辑推荐:

hellojay 发表于 2016-10-9 10:55:33 | 显示全部楼层
第一个题的话用hashset就可以了吧,不需要知道Parent是谁,只要知道之前遍历过就可以了吧
回复 支持 反对

使用道具 举报

chaosMonkey 发表于 2016-10-9 13:11:43 | 显示全部楼层
你第一个问题的话,是不是应该把最一开始的根节点也加到集合中去,否则,比如说,当根节点的左孩子的左边指针又指回根节点,形成一个环,也是错误的吧, 而且,只用一个set来记录已经遍历过的节点就可以吧,如果左右孩子在已经访问过的节点集合中,说明有错误边,用map来记录父亲的这个信息感觉不是很必要。
回复 支持 反对

使用道具 举报

chaosMonkey 发表于 2016-10-9 13:55:48 | 显示全部楼层
follow up的话,的确看你怎么定义这个输入的形式,形式可以有多种,我的方法是输入root节点以及一个记录所有节点的set。解法仍然要遍历树,只不过这里不能一找到错误边就结束,要遍历整棵树,记录所有的点,这样才能找到isolated的点,同时我要记录下错误边的那个父亲节点,这样才能lsolated的点接到上面去。简单写了点代码,不知道是不是有更简洁的方法
  1. void deleteWrongEdge(unordered_set<TreeNode*> nodes, TreeNode* root){
  2.         pair<TreeNode*, bool> wrongEdge;//记录下错误边的父节点,及错误的边是左还是右. 1point 3acres 璁哄潧
  3.         unordered_set<TreeNode*> st;//记录树中连通的点
  4.         st.insert(root);
  5.         dfs(root, st, wrongEdge);. visit 1point3acres.com for more.
  6.         for(auto node : st){
  7.                 if(nodes.count(node) == 0){
  8.                         if(wrongEdge.second){
  9.                                 wrongEdge.first->left = node;
  10.                         }else{
  11.                                 wrongEdge.first->right = node;. 1point 3acres 璁哄潧
  12.                         }
  13.                         break;
  14.                 }. From 1point 3acres bbs
  15.         }
  16. }
  17. void dfs(TreeNode* root, set<TreeNode*>& st, pair<TreeNode*, bool>& wrongEdge){
  18.         if(!root)
  19.                 return;
  20.         if(root->left){
  21.                 if(st.count(root->left) == 0){
  22.                         st.insert(root->left);
  23.                 }else{
  24.                         root->left = NULL;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  25.                         wrongEdge.first = root;
  26.                         wrongEdge.second = true;. From 1point 3acres bbs
  27.                 }
  28.         }
  29.         if(root->right){. visit 1point3acres.com for more.
  30.                 if(st.count(root->right) == 0){
  31.                         st.insert(root->right);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  32.                 }else{
  33.                         root->right = NULL;
  34.                         wrongEdge.first = root;
  35.                         wrongEdge.second = false;
  36.                 }
  37.         }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  38.         dfs(root->left, st, wrongEdge);
  39.         dfs(root->right, st, wrongEdge);
  40. }
复制代码
回复 支持 反对

使用道具 举报

hellojay 发表于 2016-10-9 23:46:18 | 显示全部楼层
chaosMonkey 发表于 2016-10-9 13:55
follow up的话,的确看你怎么定义这个输入的形式,形式可以有多种,我的方法是输入root节点以及一个记录所 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我觉得可以不存父节点吧,直接先遍历一遍找落单的那个节点,然后再遍历一遍当发现某节点的子节点已经遍历过了,直接把落单节点接上就可以了吧
回复 支持 反对

使用道具 举报

wxl3691 发表于 2016-10-10 01:01:45 | 显示全部楼层
这题真难啊
回复 支持 反对

使用道具 举报

chaosMonkey 发表于 2016-10-10 11:53:20 | 显示全部楼层
hellojay 发表于 2016-10-9 23:46
我觉得可以不存父节点吧,直接先遍历一遍找落单的那个节点,然后再遍历一遍当发现某节点的子节点已经遍历 ...

如果错误的树的节点是一个孩子的左指针或者是右指针又指回它的父亲或者祖先节点,在遍历找已经的时候是不是会造成循环?所以我就在遍历的时候同时要删掉错误的边,这样才能保证正确的遍历,同时要全部遍历完这棵树才能找到isolated的节点。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 18:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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