在国外一跟老外吵架口语立刻就不够用了

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 2670|回复: 6
收起左侧

g家電面

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

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

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

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

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

稍微介紹一下自己就開始了 (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. 1point 3acres 论坛
     / \  
   a     b
  /  \ /   \
k    c     d  


. visit 1point3acres for more.這樣一畫就很清楚了;  錯的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);.1point3acres网
        if (tmp == null) {       
           m.put(n.left, n);
        } else {
           n.left = null;. 留学申请论坛-一亩三分地
        return;
        }

        if (n.right != null) {. 留学申请论坛-一亩三分地
           Node tmp = m.get(n. right);
        if (tmp == null) {       
           m.put(n. right, n);.留学论坛-一亩-三分地
        } else {
           n. right = null;
        return;
        }
   findWrong(n.left);
   findWrong(n.right);}
}
. visit 1point3acres for more.

中間我找wrong edge 找的太高興了, 以為是找到return 就好, 提醒一下說是要delete, 也就把找到的node = null. Waral 博客有更多文章,

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

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

follow up:. visit 1point3acres for more.
Given the same problem, 1 edge is wrong, which left one node isolated, how do you fix it?. Waral 博客有更多文章,

我又聽不懂了 又花了兩分鐘畫了這個
      p. 留学申请论坛-一亩三分地
     / \  
   a     b
  /  \ /   \
k    c     d    y


.本文原创自1point3acres论坛要把 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 3 acres
你說g怎麼沒動作啊
.1point3acres网
面官吱吱嗚嗚地說go 不錯啊 根本沒回答我
然後就結束了

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

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

謝謝!
. 围观我们@1point 3 acres



. 牛人云集,一亩三分地


. 围观我们@1point 3 acres
-google 1point3acres


. 一亩-三分-地,独家发布
. 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;//记录下错误边的父节点,及错误的边是左还是右
  3.         unordered_set<TreeNode*> st;//记录树中连通的点. Waral 博客有更多文章,
  4.         st.insert(root);
  5.         dfs(root, st, wrongEdge);
  6.         for(auto node : st){
  7.                 if(nodes.count(node) == 0){
  8.                         if(wrongEdge.second){. Waral 博客有更多文章,
  9.                                 wrongEdge.first->left = node;
  10.                         }else{
  11.                                 wrongEdge.first->right = node;. 留学申请论坛-一亩三分地
  12.                         }
  13.                         break;
  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{
    . Waral 博客有更多文章,
  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;.1point3acres网
  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的节点。
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-23 04:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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