## Google Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
3
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 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

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

``````/*
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!

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

Name:

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

### Books

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

### Videos

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.