aonecode
BAN USER- 5of 5 votes
AnswersTree Game
- aonecode in United States
class TreeNode {
TreeNode parent; //parent node
TreeNode left; //left child
TreeNode right; //right child
}
Two people in a game, player scores by claiming nodes in binary tree, tree node class as shown above.
The player who eventually owns more nodes wins the game.
Player A and B each claims a node at first.
After the first round, a player will only be able to claim a node adjacent to any node owned by himself.
A tree node is adjacent to its parent, left right and right child.
A node owned cannot be re-claimed.
End game when all nodes are owned.
If player A gets the first claim at node N, find whether it is possible for player B to win.
If yes, find out which node player B should claim at his first move.
Follow up: if player B takes the first hand instead, which node should he pick?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm
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
- aonecode May 17, 2019
Answer followup:
Looking for interview experience sharing and coaching?
- aonecode May 17, 2019Visit 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!