给Google onsite面经添砖加瓦

jfree811 发表于 2016-10-16 11:50
第一问是不是就是让你求二进制数上面 所以1的个数？然后follow up的解法是不是从二进制数从最右开始有多少 ...

就服你                                      

猫头鹰也是猫 发表于 2016-10-23 00:23
不用专门去乘2啊，dfs的时候自然会handle这些

对不起啊楼主有点没想明白，比如说他让我们算还剩一个whole一个half的概率，那像你说的树里面会有很多这样的node，所以我们要都找完把他们的概率加起来吗？还是找到一个就return他的概率就行了～我不知道自己理解的对不对～感谢感谢！

whitney94 发表于 2016-10-23 01:33
对不起啊楼主有点没想明白，比如说他让我们算还剩一个whole一个half的概率，那像你说的树里面会有很多这 ...

是的要都加起来

诶想问一下楼主呀～odd设计你是用了什么data structure 模拟这个的呀～谢谢啦

whitney94 发表于 2016-10-23 13:57
诶想问一下楼主呀～odd设计你是用了什么data structure 模拟这个的呀～谢谢啦

我这题真心乱答的，你还是自己再想想吧。。我好像是用一个HashMap来记用户的选择，然后一个Set来记available的座位。

第四轮 药片题：药瓶中每一个状态是由w（整片个数）， h（半片个数）以及到达该状态的概率p唯一决定的。这样就可以定义一个状态State的struct. 然后根据题意根容易写出状态转移方程：
1. State(w=0,h=0) has no next state;
2. State(w>0,h) changes to State(w-1,h+1) with chance=w/(w+h) and to State(w,h-1) with chance=h/(w+h);
3. State(w=0,h>0) always changes to State(0,h-1) with change=1.
然后用这些 State change就可以模拟每天药瓶状态。
对于求某个状态的概率，可以将每个State看成binary tree的一个node, 每一天的所有可能状态正好是binary tree同一层上的所有nodes, 第k天的状态就在第k层上。用queue做level order traversal到第198层，然后将所有State为w=1,h=0的概率叠加即可（因为tree从root到某一层任意node的path都是互斥时间，所以总概率相加）

1. // drug state in the bottle
   
2. struct State {
   
3.   int w, h; // number of whole and half pills
   
4.   double p; // probability of current state
   
5.   State(int whole, int half, double prob):w(whole),h(half),p(prob){}
   
6. };
   
7. 
   
8. class Drug {
   
9.   private:   
   
10.   int w, h, w0; // number of whole, half and initial whole pills
    
11.   queue<State> states; // all possible states today
    
12.   
    
13.   public:
    
14.   Drug(int whole):w(whole),h(0),w0(whole) {
    
15.       states.emplace(whole, 0, 1.0);
    
16.   }
    
17.   
    
18.   // a random state next day
    
19.   void nextDay() {
    
20.      if (w + h == 0) return;
    
21.      if (rand()%(w+h) < w) { w--; h++; } else h--;
    
22.   }
    
23.   
    
24.   // print current state
    
25.   void printState() const {
    
26.     cout << "Current number of whole = " << w << ", half = " << h << endl;  
    
27.   }
    
28.   
    
29.   // all possible states next day
    
30.   void nextDayStates() {
    
31.     queue<State> nextstates;
    
32.     while (!states.empty()) {
    
33.       auto state = states.front(); states.pop();
    
34.       int ww = state.w, hh = state.h;
    
35.       if (ww + hh == 0) return; // empty bottle
    
36.       if (ww) { // whole pill exists
    
37.         // pick a whole pill
    
38.         nextstates.emplace(ww-1,hh+1, ((double)ww)/(ww+hh));
    
39.         // pick a half pill
    
40.         if (hh) nextstates.emplace(ww,hh-1, ((double)hh)/(ww+hh));
    
41.       }
    
42.       // no whole pill, has to pick a half pill
    
43.       else nextstates.emplace(0,hh-1, 1.0);
    
44.     }
    
45.     states.swap(nextstates); // update states for next day
    
46.   }
    
47.   
    
48.   // get probability of a given state
    
49.   double getStateProb(int whole, int half) {
    
50.     double prob = 0.0;
    
51.     if (whole < 0 || half < 0) return prob;
    
52.     int nDays = 2*w0 - (2*whole+half); // days elapsed
    
53.     if (nDays < 0) return prob;
    
54.     queue<State> empty; states.swap(empty);
    
55.     states.emplace(w0, 0, 1.0); // reset to initial state
    
56.     while (nDays-- > 0) nextDayStates();
    
57.     while (!states.empty()) { // combine probability of given states
    
58.       auto state = states.front(); states.pop();
    
59.       if (state.w == whole && state.h == half) prob += state.p;
    
60.     }
    
61.     return prob;
    
62.   }
    
63. };

复制代码

补充内容 (2016-10-24 14:39):
Typo: "因为tree从root到某一层任意不同的node的path都代表互斥事件，所以总概率相加"

zzgzzm 发表于 2016-10-24 14:37
第四轮 药片题：药瓶中每一个状态是由w（整片个数）， h（半片个数）以及到达该状态的概率p唯一决定的。这 ...

还有个code中的概率计算问题，就是计算下一个状态概率时我忘计乘以当前状态概率了，独立事件乘法原理了。大家见谅！

g家的问题都是这么难吗？

恭喜大神，请问过完hc就是offer吗还是要先team match？

chaosMonkey 发表于 2016-11-11 19:11
g家的问题都是这么难吗？

看了地里很多面经，的确感觉G家最难，但也有随机例外的，所以运气也重要（无语。。。）

我觉得感觉得看怎么难。如果光题目的setup就很复杂，或者是那种“知道就会不知道就不会”的题就不是好的纯粹知识的面试题（见过G家这样的面经，据说这种问题应该banned的，但...）。关键是在基础知识的范围之外再比谁知道的多的话，我个人觉得就没有什么意义了，因为这种问题往往没有什么可推广性，而且candidates背景也各不相同。我觉得好的适合面试的题目应该是在简单的setup上用逻辑就可以推理出来的，而不是牵扯到需要复杂的理论证明。