励志贴: 报个G家offer+面筋

CHazyhabiT

1 ]! D; l9 J% j1 w9 _% L5 s8 g4 \
从去年11月on campus，到圣诞前的on site，再到现在（1月）拿到offer，G家的面试贯穿了整个求职历程，报喜讯的同时顺便也把on site的面筋分享一下。
6 b- e  a6 f) |( X0 D7 O& N

- L" X* w+ S* B& j+ `8 f% @on campus面筋戳这里http://www.meetqun.com/thread-2227-1-1.html，on site有3轮，上午10点左右开始，午饭前两轮，午饭后一轮。

( s$ I) C+ F  f) b+ f1 Y5 ?' i第一轮================================
warm up 小于5分钟，然后就开始做题，关于用树表达图像的题目。假设一个矩形画布（理解为一个区域），该区域只能由黑白两种颜色填充，然后根节点表示的就是这个矩形画布。
  L4 ]6 c+ R1 t; X# Q& q1. 一个节点表示图中的某一个区域，如果该区域全黑或者全白，那么它将不会有children（不会被split）。
2. 如果该节点中颜色错杂，那么把该区域平均划分成四块（左上，右上，左下，右下），这时该节点就有4个子节点。
" ^3 Z! [1 c. T6 b" R
3. 这样一直递归下去
上面就是基本的情景，然后要求写出树节点的Class表达方式，为后面问题作铺垫。

第一个问题很简单，求树的高度，用了两种方法，一是根据树递归构建的性质进行递归遍历，另一个就是层次遍历（滚动数组）来做。
第二个问题就是将两幅大小相同的图merge为一个新图，merge规则为对于两幅图上的同一个像素点，如果颜色相同，那么颜色不变，如果1黑1白，那么merge之后为白色。当然面试官是通过画了一个示例图来讲述的题目，可能会更好理解一些。我就用最容易想到的recursive的方法来做了。

& d  z2 W4 M- _# J$ [, u. @第二轮================================
* _& h. Z( G8 H( i2 S' b$ Y6 h* A- rwarm up 5~10分钟，然后就开始类似于聊天方式的做题（是个设计题），情景很长，跟gmail里显示广告有关。精练后就是有一个server，用来处理client向server发送的request请求，这个server会针对每个request返回true or false，这样得到true的client就可以向advertisement server发送获取广告的请求。这样做的目的就是限制访问，免得ad server宕机。问怎么设计这个server。。。
& q. Q& l" k9 v" A6 P
1 U3 C: |3 O* E0 a第三轮================================
个人觉得这一轮命悬一线，一上来就直接做题。
/ k# z2 A8 p, O4 W7 O: {+ C
+ J* E( y3 d1 Z第一题给一个BST（树节点的索引都是不重复的），然后给一个threshhold value，该value可能出现在树中，可能没有，要求分开成两棵树，一棵节点值小于等于threshhold，另一个大于threshold。这个题关键是定义好递归方程的API（即每层递归到底要做什么），然后静下心来做。

第二题是关于二维的region merge，当然题目被封装成描绘城市轮廓。在2维平面上的一堆矩形方块，每一个方块表示一个建筑物在地平面上的横截面，默认这些建筑都在同一水平线上，所以一个方块的数据结构可以表示为Building <startX, endX, Height>，即在水平线上左右轮廓的坐标和高度。现在问题来了，给你一堆的方块，这些方块可能重合，那么要求返回所有方块的整体轮廓。返回结果的数据结构需要自己定义。


2 d3 z. d1 X; ~* L( f5 t总结================================
由于master才读的CS，没有任何实习经验，一直都觉得能拿到G家offer真是一种看缘分的事情，可遇不可求。。。所以面试过程中心态还算好。码代码的过程中也出现了一些bug，也有一些地方还待优化，都是面试官提醒才改过来的。所以大家不要因为在过程中出现了bug就影响情绪，个人觉得相比于bug free，过程中与面试官的交流会更加重要。然后再强调一下心态的重要性，在第三轮BST题出来的时候，我就有种“完了，好难”的感觉，因为这种树的递归题，说容易也容易，说难也难，关键是在那个时间那个地点你想明白没有，做得出来OK，做不出来也不能说明什么，真的有种看天意的感觉，所以就抱着挂掉的心里准备安安静静分析，死马当活马医。。。
, g+ @. k. J1 {: ~; T4 A2 T$ X3 }

3 G( S/ L. s% V6 X  A0 l# l来源: 报个G家offer+面筋

changhaz

CHazyhabiT 发表于 1-27-2015 12:40 AM
有要求，相对位置不变。

乱写了个，请问lz这思路对吗？

1. 
   
2. void splitTree（Node* node, int target, Node* &smalltree, Node* &largetree） {
   
3.     if (!node) {
   6 B$ ?% N% K, G' Y7 n9 u* g
4.         smalltree = largetree = NULL;
   $ X8 \* S6 G1 U
5.         return;
   
6.     }
   
7. 
   
8.     if (node -> val == target) {
   9 W" Z+ [1 ]- E1 W
9.         smalltree = node -> left;
   ' C! k5 j  M" ?& v+ a2 ~
10.         largetree = node -> right;
      B1 _5 y; P- h6 v' S; a" Z
11.         return;
    
12.     }
    0 K7 F; P/ f6 d+ [0 B$ B
13.    
    
14.     if (node -> val > target) {
    
15.         largetree = node;
    
16.         Node* leftsmall, leftlarge;
    
17.         splitTree(node -> left, target, leftsmall, leftlarge);
      E. z5 X" ~+ Q
18.         node -> left = leftlarge;
    
19.         smalltree = leftsmall
    6 d0 G# C! f% U$ J* o; k- \
20.     } else {
    
21.         smalltree = node;
    
22.         Node* rightsmall, rightlarge;
    
23.         splitTree(node -> right, target, rightsmall, rightlarge);
    4 [; {9 b: ^9 Z
24.         node -> right = rightsmall;
    + _$ H# G4 W' h7 Q1 Z: I, c, {# S
25.         largetree = rightlarge;
    
26. }

复制代码

( }  q8 ]+ N. ?3 X" f补充内容 (1-27-2015 01:54 AM):
. d1 `6 @. c5 P' V6 A1 @/ s8到12行等于的部分应该去掉。20行开始的else这段来处理相等的情况

Sophia

Big congrats!!!

averill

怎么onsite只面三轮。这要多牛的人呀。
一般都4-5轮。