传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 2459|回复: 6
收起左侧

g家電面

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

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

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

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

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

.鏈枃鍘熷垱鑷1point3acres璁哄潧稍微介紹一下自己就開始了 (5 mins past)

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
     / \  
   a     b
  /  \ /   \
k    c     d  
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
.鐣欏璁哄潧-涓浜-涓夊垎鍦
這樣一畫就很清楚了;  錯的edge 會有兩個parent, 所以只要建一個hashmap, key child, value parent-google 1point3acres
然後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;
        }
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        if (n.right != null) {.1point3acres缃
           Node tmp = m.get(n. right);
        if (tmp == null) {        . Waral 鍗氬鏈夋洿澶氭枃绔,
           m.put(n. right, n);-google 1point3acres
        } else {-google 1point3acres
           n. right = null;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        return;
        }
   findWrong(n.left);
   findWrong(n.right);}
}


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

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

面官也沒說什麼, 就說要問follow up, 到現在時間過 20 mins. 鍥磋鎴戜滑@1point 3 acres

follow up:
Given the same problem, 1 edge is wrong, which left one node isolated, how do you fix it?
. 1point 3acres 璁哄潧
我又聽不懂了 又花了兩分鐘畫了這個
      p
     / \  
   a     b
  /  \ /   \
k    c     d    y
. 1point3acres.com/bbs
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
要把 ac 或 bc delete 掉, 然後連 ay or by

一個node isolated 你tree 裡根本看不到啊,  一個看不到的node 你怎麼連啊
面官說你可以改 input, 我就說那我的input 改成hash map key child, value parent
-google 1point3acres我的algo 基本沒錯, 只要先找到落單的node 就好了 (find map node without parent)
然後用之前的algo 去treverse, 找到不設null 改聯到落單node

我好激動啊, 批哩啪拉的把整個流程講了一遍, 面官說 fine 然後我開始寫
寫到最後時間不夠我就把該改的地方又講了一遍 面官也沒說啥
-google 1point3acres
問問題我問:
g家近年上go, angular, swift, 倒是jvm 沒怎麼新動作, 現在外面 cotlin, scala, clojure 好火熱啊
你說g怎麼沒動作啊 . more info on 1point3acres.com

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

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

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

謝謝!

. from: 1point3acres.com/bbs






.鐣欏璁哄潧-涓浜-涓夊垎鍦








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

. visit 1point3acres.com for more.


本帖被以下淘专辑推荐:

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;//记录下错误边的父节点,及错误的边是左还是右
  3.         unordered_set<TreeNode*> st;//记录树中连通的点
  4.         st.insert(root);
  5.         dfs(root, st, wrongEdge);
  6.         for(auto node : st){
  7.                 if(nodes.count(node) == 0){
  8.                         if(wrongEdge.second){
  9.                                 wrongEdge.first->left = node;
  10.                         }else{. 1point3acres.com/bbs
  11.                                 wrongEdge.first->right = node;. 1point3acres.com/bbs
  12.                         }. visit 1point3acres.com for more.
  13.                         break;. 鍥磋鎴戜滑@1point 3 acres
  14.                 }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  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;
  27.                 }
  28.         }
  29.         if(root->right){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  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. from: 1point3acres.com/bbs
我觉得可以不存父节点吧,直接先遍历一遍找落单的那个节点,然后再遍历一遍当发现某节点的子节点已经遍历 ...

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-22 09:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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