Google SDE coding 面经 (新题，求idea)

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

选举那道题我的解法：

1. public int solution(
   
2.         int num_states,
   
3.         int[] delegates,
   
4.         int[] votes_president_A,
   
5.         int[] votes_president_B,
   
6.         int[] votes_Undecided)
   
7. {
   
8.         // return minumber number people vote A
   
9.         var target = delegates.Sum();
   
10.         var dp = new int[target+1];
    
11.         Array.Fill(dp, int.MaxValue);
    
12.         dp[0] = 0;
    
13.         var votes = new int[num_states];
    
14.         for (var i = 0; i < num_states; ++i) {
    
15.                 // total number of votes
    
16.                 var total = votes_president_A[i] + votes_president_B[i] + votes_Undecided[i];
    
17.                 // votes required to win for A
    
18.                 votes[i] = total / 2 + 1 - votes_president_A[i];
    
19.         }
    
20.        
    
21.         // dp[j] = min(dp[j-delegates[i]] + votes[i], dp[j])   0 <= i < num_states
    
22.         for (var i = 0; i < num_states; ++i) {
    
23.                 for (var j = target; j >= 0; --j) {
    
24.                         if (j >= delegates[i] &&
    
25.                                 dp[j - delegates[i]] != int.MaxValue &&
    
26.                                 dp[j - delegates[i]] + votes[i] < dp[j]) {
    
27.                                 dp[j] = dp[j - delegates[i]] + votes[i];
    
28.                         }
    
29.                 }
    
30.         }
    
31.        
    
32.         // Find the minimum votes for delegates larger than half
    
33.         var result = int.MaxValue;
    
34.         for (var i = target/2+1; i <= target; ++i) {
    
35.                 result = Math.Min(result, dp[i]);
    
36.         }
    
37.        
    
38.         return result == int.MaxValue ? -1 : result;
    
39. }

复制代码

花擦 好牛逼 多谢分享！！

0-1 背包问题，用C++实现了一下，如果A不可能赢一个州的选举人票(比如，B已经赢了该州)，直接跳过。
没有编译和测试，欢迎大家指出问题。

1. 
   
2. /*
   
3. check if A can win election
   
4. find min votes needed for A to win
   
5. calculate min votes needed to win each state
   
6. calculate min votes needed to win majority of electors
   
7. 0/1 knapsack problem
   
8. Time Complexity: O(m * n)
   
9. Space Complexity: O(m * n)
   
10. m: number of states
    
11. n: total number of electors
    
12. */
    
13. int minVotesToWin(int numStates,
    
14. const vector<int>& electors,
    
15. const vector<int>& votesA,
    
16. const vector<int>& votesB,
    
17. const vector<int>& votesUndecided) {
    
18.         // validate parameters
    
19.         if (numStates <= 0 || numStates != electors.size() || numStates != votesA.size() || …) {
    
20.                 throw invalid_arguments(“”);
    
21.         }
    
22. 
    
23.         int totalElectors = accumulate(electors.begin(), electors.end(), 0);
    
24.         int electorsA = 0;
    
25.         vector<int> minVotes(numStates, INT_MAX);
    
26.         for (int i = 0; i < numStates; ++i) {
    
27.                 int votes = votesA[i] + votesB[i] + votesUndecided[i];
    
28.                 int majority = votes / 2 + 1;
    
29.                 if (votesA[i] + votesUndecided[i] >= majority) {
    
30.                         electorsA += electors[i];
    
31.                         minVotes[i] = majority - votesA[i];
    
32.                 }
    
33.         }
    
34.         if (electorsA < totalElectors / 2 + 1) {
    
35.                 return INT_MAX;
    
36.         }
    
37. 
    
38.         // 0-1 knapsack
    
39.         // table[i][j] : min votes needed to win j electors from first i states
    
40.         // table[i][j] = max(table[i-1][j], table[i-1][j-minVotes[i-1]] + minVotes[i-1])
    
41.         vector<vector<int>> table(numStates, vector<int>(totalElectors + 1, INT_MAX));
    
42.         for (int i = 0; i < numStates; ++i) {
    
43.                 table[i][0] = 0;
    
44.         }
    
45.         for (int j = 0; j <= totalVotes; ++j) {
    
46.                 table[0][j] = 0;
    
47.         }
    
48.         for (int i = 1; i < numStates; ++i) {
    
49.                 for (int j = 1; j <= totalElectors; ++j) {
    
50.                         int votes1 = INT_MAX, votes2 = INT_MAX;
    
51.                         if (j >= electors[i] && minVotes[i-1] != INT_MAX) {
    
52.                                 votes1 = table[i-1][j-electors[i-1]] + minVotes[i-1];
    
53.                         }
    
54.                         votes2 = table[i-1][j];
    
55.                         table[i][j] = min(votes1, votes2);
    
56.                 }
    
57.         }
    
58.         int result = INT_MAX;
    
59.         for (int j = totalVotes / 2 + 1; j <= totalVotes; ++j) {
    
60.                 result = min(result, minVotes[j]);
    
61.         }
    
62.         return result;
    
63. }
    

复制代码

请问undecided是啥意思啊？delagate是这个state一共可以投几票？

JoyForce 发表于 2021-1-17 14:24
选举那道题我的解法：
[mw_shl_code=java,true]public int solution(
        int num_states,

很clear，谢谢！

JoyForce 发表于 2021-1-17 14:24
选举那道题我的解法：
[mw_shl_code=java,true]public int solution(
        int num_states,

有一个小问题 是不是没考虑votes[i] < 0的情况？

JoyForce 发表于 2021-1-17 14:24
选举那道题我的解法：
[mw_shl_code=java,true]public int solution(
        int num_states,

如平票咋办？比如ab各一半，那这个state其实就没有任何贡献给任一方