CareerCup

Looking for interview experience sharing and coaching?

Visit AONECODE.COM for ONE-ON-ONE private lessons by FB, Google and Uber engineers!

SYSTEM DESIGN (recommended for candidates of FB, LinkedIn, Amazon, Google and Uber etc.),
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms, Clean Coding),
latest interview questions sorted by companies,
mock interviews.

Get offers from G, U, FB, Amazon, LinkedIn, Twitter and other top-tier companies.

Email us aonecoding@gmail.com with any questions. Thanks!

Solution

class TreeNode {
        int id;
        TreeNode left;
        TreeNode right;
        TreeNode parent;
    
        TreeNode(int id) {
            this.id = id;
        }
    }	
    /*
        The opponent's first move on Node N divides the tree into 3 components - left subtree, right subtree and parent branch of N.
        Your best move is to claim a node adjacent to Node N at the biggest component.
        Function countNodes() counts the sizes of 3 components. Function win() finds the largest component, whose size is your score.
    */

    public static boolean win(TreeNode root, TreeNode n) { //N is the first move by opponent
        int sizeParent = countNodes(n.parent, n); //size of parent component
        int sizeLeft = countNodes(n.left, n);   //size of left subtree component
        int sizeRight = countNodes(n.right, n); //size of right subtree component

        int myScore = Math.max(Math.max(sizeParent, sizeLeft), sizeRight); //I take the biggest component
        int treeSize = 1 + sizeParent + sizeLeft + sizeRight;
        int opponentScore = treeSize - myScore; //opponent takes remaining nodes
        System.out.print("my best score is " + myScore + "/" + treeSize + ". ");
        if(myScore > opponentScore) {
            TreeNode bestmove = myScore == sizeParent ? n.parent: myScore == sizeLeft ? n.left : n.right;
            System.out.println("my first move on " + bestmove.id);
        }
        return myScore > opponentScore;
    }

    private static int countNodes(TreeNode node, TreeNode ignore) {
        if(node == null) return 0;
        int count = 1;
        if(node.parent != ignore) {
            count += countNodes(node.parent, node);
        }
        if(node.left != ignore) {
            count += countNodes(node.left, node);
        }
        if(node.right != ignore) {
            count += countNodes(node.right, node);
        }
        return count;
    }

Please find the solution for followup question in the next comment

Answer followup:

/*     
        To find the best move we must count the sizes of 3 adjacent components for every node in the tree.
        If exists a node whose biggest adjacent component is smaller than treesize/2, the node is your best move, cuz your opponent won't be able to get a score higher than treesize/2.
        In some cases there is no winning play, like on a tree with 2 nodes.

        We can store the component sizes of every node in a 2-dimensional cache.
        1st dimension: node
        2nd dimension: which component (parent, left or right)
        value: size of component

    */

    public static int bestMove(TreeNode root) {
        if(root == null) return -1;
        if(root.left == null && root.right == null) return root.id;

        // map stores size of every component
        // each node at most has 3 components - to its left, to its right, to its top (parent)
        // Map<node, Map<which component, size>>
        Map<TreeNode, Map<TreeNode, Integer>> components = new HashMap<>();
        TreeNode dummy = new TreeNode(-1);
        dummy.left = root;

        //calculate size of child components for all nodes
        getComponentSize(dummy, root, components);

        int treeSize = components.get(dummy).get(root);
        for(TreeNode node: components.keySet()) {
            int maxComponentSize = 0; //maximum score possible for opponent
            for(int size: components.get(node).values()) {
                if(size > maxComponentSize) maxComponentSize = size;
            }
            if(treeSize / 2.0 > maxComponentSize) { //opponent cannot get half of the tree. You win.
                return node.id; //best first move
            }
        }
        return -1; //no winning play
    }

    private static int getComponentSize(TreeNode n, TreeNode branch, Map<TreeNode, Map<TreeNode, Integer>> components) {
        if(n == null || branch == null) return 0;

        if(components.containsKey(n) && components.get(n).containsKey(branch)) {
            return components.get(n).get(branch); // component size of a branch from node n (n excluded)
        }
        // a node n has 3 branches at most - parent, left, right
        if(!components.containsKey(n)) {
            components.put(n, new HashMap<>());
        }

        int size = 1; // 1 is the size of TreeNode branch
        if(branch == n.left || branch == n.right) {
            //size of the subtree 'branch' is size(branch.left) + size(branch.right) + 1
            size += getComponentSize(branch, branch.left, components);
            size += getComponentSize(branch, branch.right, components);
        } else { //else when (branch == n.parent)
            //see the tree from left-side or right-side view (see parent as a child; see one of the children as parent)
            //size of the component is size(branch.parent) + size(branch.left/right child)
            size += getComponentSize(branch, branch.parent, components);
            size += branch.left == n ? getComponentSize(branch, branch.right, components) : getComponentSize(branch, branch.left, components);
        }
        components.get(n).put(branch, size); // cache the result of recursion
        getComponentSize(n, n.parent, components); // calculate size of parent component for current node
        return size;
    }

Looking for interview experience sharing and coaching?

Visit aonecode.com for private lessons by FB, Google and Uber engineers

ONE ON ONE real-time coaching on SYSTEM DESIGN, ALGORITHMS, and mock interviews.

Feel free to email us aonecoding@gmail.com with any questions. Thanks!

Dear admin, could you ban these advertisers from india please? These are not actual interview questions from google, they are just questions they thought of writing to add to their website. They just put junk here.

Dear admin, could you ban these advertisers from india please? These are not actual interview questions from google, they are just questions they thought of writing in their website to make money. They just put junk here.