书接前文，the coding guy delivered the feature of finding the closest friend in a timely manner. PM got new task from the leads team. They want to improve clubhouse users’ engagement. PM proposed the immediate idea that it would benefit the engagement if we can improve the joining rate of the rooms recommended to users. Dev said, I would prefer to join rooms with my closest friends in. That’s said, we can recommend rooms based on the closeness between the room and the user. ...
Clubhouse大火，平台迅速聚集了大量用户，每个用户都有自己的profile，profile里除了自己的id，还会标注推荐人。现在产品经理提出一个要求，希望能研究任意两个用户的最近的共同好友在哪。程序员也不知道pm为什么要提这么个要求，但这个功能不算费事，所以程序员决定不与pm多做讨论，因为一般情况下，所谓讨论都沦为给pm扩充知识理清思路的过程。简化起见，profile定义如下，完成TODO，注意，这个API可能会被多次调用。 class Profile { // Id of this profile. public String id; // Id of the person who nominated this person. public String nominatedBy; } public class Clubhouse { public Clubhouse(List<Profile> clubPool) { // TODO ? } public Profile getClosestCommonFriend(Profile a, Profile b) { // TODO } }
01背包问题（01 backpack problem） Problem Given N items and a bag of weight capacity W. Each item has weight w[i] and value v[i]. What’s the most value this bag can hold? E.g., N = 5, W = 10. w = [1 2 3 4 5], v = [5 4 3 2 1] Output: 14. Explanation: Choose item 1 2 3 4 whose total weight is 10 and total value is 14. Solution dp[i][j] := the most value to get if taken from item [1:i] and weight <= j. Then dp[N][W] is the answer to the problem. dp[0][j] = 0 // given 0 items, the value you can get is always 0 dp[i][j] = dp[i-1][j] // if j < w[i], item i cannot be put into the bag = max(dp[i-1][j] // don't take item i dp[i-1][j-w[i]] + v[i]) // take item i, // Time: O(NW), Space: O(NW) public int backpack(int N, int W, int[] w, int[] v) { int[][] dp = new int[N + 1][W + 1]; for (int i = 1; i <= N; i++) { for (int j = 0; j <= W; j++) { // Depends on if there is item of weight 0. // If yes, j starts from 0. Otherwise, j starts from 1. if (w[i - 1] > j) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]); } } } return dp[N][V]; } // Time: O(NW), Space: O(W) // Since dp[i][j] only depends on dp[i - 1][k], where k <= j, // we can use one dimension array dp[j] public int backpack(int N, int W, int[] w, int[] v) { int[] dp = new int[W + 1]; for (int i = 0; i < N; i++) { for (int j = W; j >= w[i]; j--) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } return dp[W]; }