# FB 店面

Question 1: https://leetcode.com/problems/product-of-array-except-self
Question 2: Variation of https://leetcode.com/problems/random-pick-with-weight
Given a list of cities and the population, pick randomly any city based on the population.
“NY”: 5M, “CA”: 10M, “WS”: 2M

Follow-up:
Given a complete ternary tree , count the number of nodes.

``````class TreeNode {
TreeNode left;
TreeNode mid;
TreeNode right;
}
``````

Example: For the full ternary tree, say of height `h` , the number of nodes `n` is

`n = (3^{h+1} - 1) / 2`

Why? Because the first level has `3^0` nodes, the second level has `3^1` nodes, and, in general, the `k-th` level has `3^{k-1}` nodes. Adding these up for a total of `h+1` levels (so height `h` ) gives

`n = 3^0 + 3^1 + 3^2 + 3^3 + ... + 3^h = (3^{h+1} - 1) / (3 - 1) = (3^{h+1} - 1) / 2`

``````public static int countNodes(TreeNode root) {
int leftHeight = getHeight(root, true);
int rightHeight = getHeight(root, false);

if (leftHeight == rightHeight) {
return (int) (Math.pow(3, leftHeight) - 1) / 2;
}

return 1 + countNodes(root.left) + countNodes(root.mid) + countNodes(root.right);
}

private static int getHeight(TreeNode node, boolean left) {
int h = 0;
while (node != null) {
h++;
node = left ? node.left : node.right;
}
return h;
}
``````