肥死不可 onsite

应该是 跪了....

Round1: Read4K 2 (modified) 出了好几个bug，白板调了10分钟。（没做到第二题）

Round2: System Design Instagram

Round3: BQ 35 min 非常刁钻

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

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

div>

求米~！

补充内容 (2018-3-2 10:44):
第五题给的是 BST 的前序输出。

cexq 发表于 2018-3-3 01:16
如果原来是
    0
0      0

恩  我覺得你說得對  所以必須多加一個條件  如果是“1” 要判斷是否會把值改動回來
這是我多加的條件

public class Solution{
        Node root;

        public void updateNode(Node n, int val){
            n.setValue(val);
            Stack<Node> stack = new Stack<>();
            dfs(n, root, stack);
        }

        private void dfs(Node target, Node parent, Stack<Node> stack){
            if (parent == null) return;
            if(parent == target){
                //check change back
                if(target.val == 1){
                    checkChangeBack(target, stack);
                }else{
                    //update children
                    updateChildren(target);
                    //update parent
                    updateParent(target, stack);
                }
                return;
            }
            Node left = parent.left;
            Node right = parent.right;
            stack.push(parent);
            dfs(target, left, stack);
            dfs(target, right, stack);
        }

        private void checkChangeBack(Node target, Stack<Node> stack){
            //change back by children
            Node left = target.left;
            Node right = target.right;
            if(left != null && right != null){
                if((left.val == 0  && right.val == 0) || (left.val == 2 && right.val == 2) ){
                   target.val = left.val;
                }
            }
            //change back by parent
            if(!stack.isEmpty()){
                Node parent = stack.peek();
                if(parent.val == 0 || parent.val == 2){
                    target.val = parent.val;
                }
            }
        }

        private void updateChildren(Node root){
            if(root == null) return;
            if(root.val == 0 || root.val == 2){
                Node left = root.left;
                Node right = root.right;
                if (left != null) left.val = root.val;
                if (right != null) right.val = root.val;
                updateChildren(left);
                updateChildren(right);
            }
        }

        private void updateParent(Node target, Stack<Node> stack){
            if(target.val == 1) return;
            if(stack.isEmpty()) return;
            Node parent = stack.pop();
            Node sibling = target == parent.left ? parent.right : parent.left;
            if(sibling == null) return;
            if(target.val == sibling.val) parent.val = target.val;
            updateParent(parent, stack);
        }
    }

補代碼
public class Solution{
        Node root;

        public void updateNode(Node n, int val){
            n.setValue(val);
            Stack<Node> stack = new Stack<>();
            dfs(n, root, stack);
        }

        private void dfs(Node target, Node parent, Stack<Node> stack){
            if (parent == null) return;
            if(parent == target){
                //update children
                updateChildren(target);
                //update parent
                updateParent(target, stack);
                return;
            }
            Node left = parent.left;
            Node right = parent.right;
            stack.push(parent);
            dfs(target, left, stack);
            dfs(target, right, stack);
        }

        private void updateChildren(Node root){
            if(root == null) return;
            if(root.val == 0 || root.val == 2){
                Node left = root.left;
                Node right = root.right;
                if (left != null) left.val = root.val;
                if (right != null) right.val = root.val;
                updateChildren(left);
                updateChildren(right);
            }
        }

        private void updateParent(Node target, Stack<Node> stack){
            if(target.val == 1) return;
            if(stack.isEmpty()) return;
            Node parent = stack.pop();
            Node sibling = target == parent.left ? parent.right : parent.left;
            if(sibling == null) return;
            if(target.val == sibling.val) parent.val = target.val;
            updateParent(parent, stack);
        }
    }

yexiaojiaycc 发表于 2018-3-1 16:04
第五题只有一个preorder这个树不确定的吧，至少要2种遍历才能确定吧?

ls说的是蠡口易玲武吧

不过这第五题不是蠡口里面preorder的那几题吗 我有点懵..

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

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

给你一个已经合法的树，实现一个 改value 的函数 （node, targetValue）,难点在怎么连带 改其他需要 改值的node//为啥要连带改

第五题只有一个preorder这个树不确定的吧，至少要2种遍历才能确定吧?

cexq 发表于 2018-3-2 07:23
给你一个已经合法的树，实现一个 改value 的函数 （node, targetValue）,难点在怎么连带 改其他需要 改值的 ...

题目的意思是 任何 时候 这个tree 都要 符合那几条规则。

写的函数 需要 让用户随意的改任何点的 值，然后 函数会自动更新其余的点。

比如 一个树
  1
/  \
0   2

如果用户改了 【2】 -》 【0】，那么 树就要更新为

  0
/  \
0   0
这个题有很多corner case。 比如 用户如果把 顶上的1 改为 0， 那么，需要把下面所有的点 为 2的 更新为 0.....

這題的重點應該是要分開來討論   改動所有的 children  和改動所有的 parent    我覺得出的很不怎麼樣  兒且時間還只有 25 分鐘

能問一下樓主是在哪裡面的嗎？  Seattle or SF ?

hadesi816 发表于 2018-3-2 10:49
题目的意思是 任何 时候 这个tree 都要 符合那几条规则。

写的函数 需要 让用户随意的改任何点的 值， ...

如果原来是
    0
0      0

父结点改成1,子结点怎么改？只改一个子结点？

楼主有结果了吗？几天前面的呢？