---
# System prepended metadata

title: Untitled

---

### Day 1. Invert Binary Tree

Invert a binary tree.

Example:
```
Input:
     4
   /   \
  2     7
 / \   / \
1   3 6   9

     4
   /   \
  2     7
 / \   / \
3   1 6   9

     4
   /   \
  2     7
 / \   / \
3   1 9   6

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Output:
     4
   /   \
  7     2
 / \   / \
9   6 3   1

   2
  /\
 1 3
```
Trivia:
This problem was inspired by this original tweet by Max Howell:



Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.right = left;
        root.left = right;
        return root;
    }
}
```

### Day 3. Two City Scheduling


```
class Solution {
    // [[10,20],[30,200],[400,50],[30,20]]
    // -170, -10, 350, 10,
    // [30,200],[10,20],[30,20],[400,50]
    public int twoCitySchedCost(int[][] costs) {
        Arrays.sort(costs, new Comparator<int[]>(){
            public int compare(int[] a, int[] b) {
                return (a[0] - a[1]) - (b[0] - b[1]); 
            }
        });
        
        int result = 0;
        int half = costs.length / 2;
        for (int i = 0; i < costs.length; i++) {
            if (i < half) {
                result += costs[i][0];
            } else {
                result += costs[i][1];
            }
        }
        
        return result;
    }
}
```
[[10,20],[30,200],[400,50],[30,20]]
[
  [0,  20,  220],
  [10, 50,  100],
  [40, 90,  110]
]
N = 2

```
class Solution {
    public int twoCitySchedCost(int[][] costs) {
        int N = costs.length / 2;
        int[][] dp = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            dp[i][0] = dp[i - 1][0] + costs[i - 1][0];
        }
        for (int j = 1; j <= N; j++) {
            dp[0][j] = dp[0][j - 1] + costs[j - 1][1];
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                dp[i][j] = Math.min(dp[i - 1][j] + costs[i + j - 1][0], dp[i][j - 1] + costs[i + j - 1][1]);
            }
        }
        return dp[N][N];
    }
}
```