Google Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
of 3 vote

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 with any questions. Thanks!


class TreeNode {
        int id;
        TreeNode left;
        TreeNode right;
        TreeNode parent;
        TreeNode(int 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 " +;
        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

- aonecode May 17, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
of 2 vote

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;

        // 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; //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 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 with any questions. Thanks!

- aonecode May 17, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.

Add a Comment

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.


is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More


CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More