Google onsite 新鲜面经 9/10

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

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

handsomecool 发表于 2015-9-15 10:42
四位数字的密码有10000种可能对吧，那这个string要包含这10000种可能？
你举的这个123456 的例子里只有1 ...

比如...难道你要我把string全写出来？

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

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

lz很厉害啊，这些题我都不会。。。请问lz，第一题是啥意思。。。

lz，好厉害啊，第二题应该就是这个，能不能麻烦lz贴一下代码或者私信一下代码？实在是不会做啊，我这周五onsite，怎么感觉要跪。。。

http://www.mitbbs.com/article_t1/JobHunting/32604357_0_1.html

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

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

hbsophia 发表于 2015-9-15 14:24
lz很厉害啊，这些题我都不会。。。请问lz，第一题是啥意思。。。

第一题估计是用贪心法，每次把出现最多的字母解决，我试着用priority_queue写了下：

1. unordered_map<char, int> map;
   
2. string noSameNeighbor(string & s){
   
3.         string ans = "";
   
4.         for (char c : s)
   
5.                 map[c]++;               
   
6.        
   
7.         auto comp = [](char char1, char char2){return map[char1] < map[char2]; };
   
8.         priority_queue <char, vector<char>, decltype(comp)> pq(comp);
   
9.         for (pair<char, int> p : map)
   
10.                 pq.push(p.first);
    
11. 
    
12.         while (!pq.empty()){
    
13.                 char c = pq.top();
    
14.                 pq.pop();
    
15.                 if (pq.empty()){
    
16.                         ans += c;
    
17.                         break;
    
18.                 }
    
19.                 char d = pq.top();
    
20.                 pq.pop();
    
21.                 ans += c;
    
22.                 ans += d;
    
23.                 map[c]--;
    
24.                 map[d]--;
    
25.                 if (map[c] > 0) pq.push(c);
    
26.                 if (map[d] > 0) pq.push(d);
    
27.         }
    
28. 
    
29.         return ans;
    
30. }

复制代码

handsomecool 发表于 2015-9-15 15:28
第一题估计是用贪心法，每次把出现最多的字母解决，我试着用priority_queue写了下：

请问大牛，这个你是用minHeap? 为啥不用max heap?
多谢

handsomecool 发表于 2015-9-15 15:28
第一题估计是用贪心法，每次把出现最多的字母解决，我试着用priority_queue写了下：

试了下这个代码，works well。 但是不知道为啥minheap works 但是， max heap不work？

啥意思呢，多谢多谢！

为什么第一题需要heap？