Google virtual onsite面经~

第一题有大神能给个题号吗？最优解的时间复杂度是什么？

第一题可以用3SUM做？

请问楼主之前是有电面吗？还是直接onsite？

第四题我的想法是，可以用hashmap记录所有可能的顺子，triple和对子，针对每一张牌，依次尝试去匹配顺子，triple和对子。
对于follow up，根据纸牌的数量N，可以算出顺子和triple的数量，因为只有一个对子。

下面是实现的代码，没有编译和测试，直接在google docs上写的。

1. constexpr int kCardNum = 14;
   
2. constexpr int kPairNum = 1;
   
3. constexpr int kStraightAndTripleNum = (kCardNum - 2) / 3;
   
4. 
   
5. bool canWin(vector<int>& cards) {
   
6.         if (cards.size() != kCardNum) {
   
7.                 return false;
   
8.         }
   
9.         unordered_map<int, unordered_set<int>>& straights;
   
10.         unordered_map<int, int>& triples,
    
11.         unordered_map<int, int>& pairs;
    
12.         return canWin(0, cards, straights, triples, pairs);
    
13. }
    
14. 
    
15. bool canWin(int index, const vector<int>& cards,
    
16. unordered_map<int, unordered_set<int>>& straights,
    
17. unordered_map<int, int>& triples,
    
18. unordered_map<int, int>& pairs) {
    
19. if (index == cards.size()) {
    
20.         return validate(straights, triples, pairs);
    
21. }
    
22. 
    
23. // try to form a straight
    
24. int currNum = cards[index];
    
25. for (int next = currNum; next >= max(1, currNum - 2); --next) {
    
26.         auto& straight = straights[next];
    
27.         if (straight.find(currNum) == straight.end()) {
    
28.                 straight.insert(currNum);
    
29.                 if (canWin(index + 1, cards, straights, triples, pairs)) {
    
30.                         return true;
    
31.                 }
    
32.                 straight.erase(currNum);
    
33.         }
    
34. }
    
35. 
    
36. // try to form a triple
    
37. if (triples[num] < 3) {
    
38.         triples[num]++;
    
39.         if (canWin(index + 1, cards, straights, triples, pairs)) {
    
40.                 return true;
    
41.         }
    
42.         triples[num]--;
    
43. }
    
44. 
    
45. // try to form a pair
    
46. if (pairs[num] < 2) {
    
47.         pairs[num]++;
    
48.         if (canWin(index + 1, cards, straights, triples, pairs)) {
    
49.                 return true;
    
50.         }
    
51.         pairs[num]--;
    
52. }
    
53. 
    
54. return false;
    
55. }
    
56. 
    
57. 
    
58. bool validate(unordered_map<int, unordered_set<int>>& straights,
    
59.                 unordered_map<int, int>& triples,
    
60.                 unordered_map<int, int>& pairs) {
    
61.         int numStraight = 0, numTriple = 0, numPair = 0;
    
62.         for (const auto& entry : straights) {
    
63.                 if (entry.second.size() == 3) {
    
64.                         ++numStright;
    
65.                 }
    
66.         }
    
67.         for (const auto& entry : triples) {
    
68.                 if (entry.second == 3) {
    
69.                         ++numTriple;
    
70.                 }
    
71.         }
    
72.         for (const auto& entry : pairs) {
    
73.                 if (entry.second == 2) {
    
74.                         ++numPair;
    
75.                 }
    
76.         }
    
77.         if (numStraight + numTriple == 4 && numPair == 1) {
    
78.                 return true;
    
79.         }
    
80.         return false;
    
81. }
    

复制代码

你好，能发一下题号吗？积分太低看不到

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

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

感觉题目难度合适，适合交流。希望未来自己遇到相同的题目。

请问第一题除了n^2的暴力解有优化吗

麻将题 一个牌可以当作顺子和triple重复用吗？没打过麻将不清楚。。。

user2198M 发表于 2021-3-7 05:19
第4题：DFS+Memorization，可以适用任何3n+2的张数，只要胡牌规则是除一对外其余牌都是顺或三同；先按数字1 ...

很清晰 谢谢！