Q1. Recruiting Event Schedules

Our company is organizing a series of university recruiting events. Each day, we host an event at one university, but sometimes we want to take a break for one day before moving on to the next university.

Given a sequence of universities, print all possible schedules of the recruiting events.

Clarification:

Input: A string of universities. Each university is represented as a single capital letter.

Output: All possible schedules. A lowercase letter “x” means we take a break.

Assumption: Null.

Result: Because we are required to print all possible results, we use DFS to solve this problem. Each layer of recursion tree has two branches, add char + ‘x’ and add char but not add ‘x’.

Base case: when the index == String.length - 1, add the lasr char ‘c’.

Test:

Input: String = “ABC”

Output:

ABC

ABxC

AxBC

AxBxC

public class Solution {
  public List<String> allPossibleSchedules(String input) {
    List<String> result = new ArrayList<>();
    if (input == null || input.length() == 0) {
      return result;
    }
    allPossibleSchedules(result, input, 0, new StringBuilder());
    return result;
  }
  
  private void allPossibleSchedules(List<String> result, String input, int index, StringBuilder sb) {
    if (index == input.length() - 1) {
      sb.append(input.charAt(index));
      // at index 2 we add c but we also delete it after put it into result
      result.add(ab.toString());
      sb.deleteCharAt(sb.length() - 1);
      return;
    }
    
    // case 1
    ab.append(input.charAt(index)).append('x');
    // sb.append('x');
    allPossibleSchedules(result, input, index + 1, sb);
    // sb.remove(sb.length() - 2, sb.length());
    sb.deleteCharAt(sb.length() - 1);
    sb.deleteCharAt(sb.length() - 1);
    
    // case 2
    sb.append(input.charAt(index));
    allPossibleSchedules(result, input, index + 1, sb);
    sb.deleteCharAt(sb.length() - 1);
  }
}

Q2. Cousins in a Binary Tree

In a binary tree, two nodes are cousins of each other if they are at the same level and have different parents.

Clarification:

Input: TreeNode root, TreeNode one and TreeNode two.

Output: Boolean if two TreeNodes are cousins.

Assumption: Null.

Result: We can try three methods to solve this problem.

Naive solution seperate the definition of cousin into two piece: 1. at same level; 2. have different parents.

BFS solution uses a queue to generate and expand TreeNodes layer by layer; expand当前这一层，generate下一层；

三部曲 solution should define “我要从孩子要什么， 我这一层要做什么，我要向上传什么”.

Test: For example, in the following tree:

                     6

                  /     \

               3            5

            /     \      /     \

           7       8    1       2

7 and 1 are cousins.

3 and 5 are not cousins.

7 and 5 are not cousins.

Naive Solution:

level(node)

boolean isSameParent(TreeNode root, TreeNode n1, TreeNode n2) {

​ if (root == null) return false;

​ // check root is the parent of both n1 and n2

}

BFS Solution:

public class Solution {
  public boolean isCousin (TreeNode root, TreeNode a, TreeNode b) {
    if (root == null) {
      return false;
    }
    
    Queue<TreeNode> queue = new ArrayDeque<>();
    TreeNode pa = null; TreeNode pb = null;
    
    queue.offer(root);
    while (!queue.isEmpty()) {
      int count = queue.size();
      for (int i = 0; i < count; i++) {
        TreeNode cur = queue.poll();
        if (cur.left != null) {  // store the a and b's parent in generate phase
          if (cur.left == a) {
          pa = cur;
        	}
        	else if (cur.left == b) {
          	pb = cur;
        	}
        	queue.offer(cur.left);
        }
        
        if (cur.right != null) {
          if (cur.right == a) {
            pa = cur;
          }
          else if (cur.right == b) {
            pb = cur;
          }
          queue.offer(cur.right);
        }
      }
      
      if (pa != null && pb != null) {
        return pa != pb;
      }
      else if (pb != null || pb != null) {
        return false;
      }
    } 
    return false;
  }
}

三部曲 Solution:

Thinking: cousins: same level and also can not be same parent

Assume we are standing at one node, if we find the root a and root b, we can get what are their levels, check if the two childrens’ level are same and current node’s level < children’s - 1.

1. ask left and right, did you find a or b?
2. if you found it for me && my children’s level + 1 != current node’s level
3. return the level to my parent

public class Solution {
  public boolean isCousin (TreeNode root, TreeNode a, TreeNode b) {
  	if (root == null || a == null || b == null) {
      return false;
    }
    boolean[] result = new boolean[1];
    isCousin(root, a, b, 0, result);
    return result[0];
  }
  
  private int isCousin(TreeNode root, TreeNode a, TreeNode b, int level, boolean[] result) {
    if (root == null) {
      return 0;
    }
    if (root == a || root == b) {
      return level;
    }
    int left = isCousin(root.left, a, b, level + 1, result);
    int right = isCousin(root.right, a, b, level + 1, result);
    if (left == right && left - level > 1) {
      result[0] = true;
    }
    return left == 0? right : left;
  }
}

| Time Complexity | Space Complexity | | :————————–: | :—————————-: | | O(n) | O(height) | | Go through一遍所有的TreeNode | Recursion 直上直下的粉红色路径 |

Q3. Packing Up the Swags

Our company is going to distribute swags at the recruiting event. We will put the swags into square-shaped boxes. Each box has to be completely filled so that the swags wouldn’t break during transportation. For example, a box can contain 1 swag, 4 swags, 9 swags, etc. (The boxes can be sufficiently large.)

Clarification:

Input: The number of swags.

Output: The minimum number of swags.

Assumption: Null.

Result: We use the dynamic programming method, linear scan回头看

左大段（Subproblem） + 右小段（不可分割的一部分）

Remember to set the initial value in the first for loop!

Test:

Input: 10

Output: 2 (one 3x3 box and one 1x1 box)

public class Solution {
  public int minBox(int n) {
    // Assumption: n > 0
    
		// 这一段可要可不要
    for (int i = 1; i < n/2; i++) {
      if (n == i * i) {
        return 1;
      }
    }
    
    int[] M = new int[n+1];
    // M[i] represents the minimum number of boxes to pack num swags up
    // initialize
    M[1] = 1;
    for (int i = 2; i <= n; i++) {
      M[i] = i;
      for (int j = 1; j * j <= i; j++) {
        M[i] = Math.min(M[i - j * j] + 1, M[i]);
      }
    }
    return M[n];
  }
}

Q4. Infinite Loop Around the Dinner Table

After the event, our company will take the students out for dinner. The restaurant has a large round table that can fit the whole party. We want to know if we can arrange the students so that the names of all students around the table form an “infinite loop.” For each pair of neighboring students s1 and s2, the last letter of s1’s name must be identical to the first letter of s2’s name.

For example, “ALICE” and “ERIC” can sit together, but “ALICE” and “BOB” cannot.

Clarification:

Input: An array of names. Each name contains capital letters only.

Output: True or false.

Assumption: Null.

Result: We use DFS to solve the all conditions, judge if there is a solution.

There are two points we should know:

1. all the element should be used.

2. the relative order can be changed.

   -> permutation.

   -> from all the possible permutations, find out if there is any one that meets our requirements.

Test:

Input: String[] = {“ALICE”, “CHARLES”, “ERIC”, “SOPHIA”}

Output: true

public class Solution {
  public boolean canChain(String[] strArr) {
    // skip corner case
    return canChain(strArr, 1);
  }
  
  private boolean canChain(String[] strArr, int index) {
    // base case
    if (index == strArr.length) {
      return canConnect(strArr[index - 1], strArr[0]);
    }
    
    for (int i = index; i < strArr.length; i++) {
      if (canConnect(strArr[index - 1], strArr[i])) {
        swap(strArr, index, i);
        if (canChain(strArr, index + 1)) {
          return true;
        }
        swap(strArr, index, i);
      }
    }
    return false;      
  }

  private boolean canConnect(String s1, String s2) {
    return s1.charAt(s1.length() - 1) == s2.charAt(0);
  }
  
  private void swap(String[] array, int left, int right) {
    String tmp = array[left];
    array[left] = array[right];
    array[right] = tmp;
  }
}

吕老师点评后总结：

1. 经过IDE测试，结果通过；

   

2. 这道题总体的思路类似于DFS I经典例题的最后一道：All Permutation，分析过程如下：

   **a. **要求在recursion的过程中所有的元素都必须用上，最后的果是各种元素排序的总和，每个元素缺一不可，所以总体思路是通过swap，swap来实现；

​ b.框架： helper function, output is boolean;

​ canConnect function, to judge whether we can link two String(the last character of the first String == the first character of the second String);

​ swap function, to swap two String.

​ c. return canChain(strArr, 1); index从1开始的原因是helper function中有

` return canConnect(strArr[index - 1], strArr[0]); ` 如果写成0 会out of bound；

​ d.

	if (canChain(strArr, index + 1)) {
      return true;

在当前index的这个循环内，调用recursion并判断，如果下一层也满足，return true，一头扎到底然后一层一层返回上来；

index -> index + 1 -> index + 2 -> … -> strArr.length - 1 —> return true

return true <- return <- return <- … return