找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 5146|回复: 18
收起左侧

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

  [复制链接]

6

主题

4

精华

500

积分

超级会员

Rank: 4

积分
500
发表于 1-26-2015 05:58 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Sophia 于 1-26-2015 06:03 PM 编辑
% `7 g+ Q) P8 V7 h: [) p8 q2 h$ u0 I2 W9 I
从去年11月on campus,到圣诞前的on site,再到现在(1月)拿到offer,G家的面试贯穿了整个求职历程,报喜讯的同时顺便也把on site的面筋分享一下。# p4 D0 q: s) N! v

( A4 p9 }- h8 x$ x* j5 i2 S; P
on campus面筋戳这里http://www.meetqun.com/thread-2227-1-1.html,on site有3轮,上午10点左右开始,午饭前两轮,午饭后一轮。- Z7 {$ @. ^% e" \
+ U3 C; G% q2 s
第一轮================================
" F  n  U2 M2 N1 P5 Kwarm up 小于5分钟,然后就开始做题,关于用树表达图像的题目。假设一个矩形画布(理解为一个区域),该区域只能由黑白两种颜色填充,然后根节点表示的就是这个矩形画布。
3 D7 g2 f' W) d1. 一个节点表示图中的某一个区域,如果该区域全黑或者全白,那么它将不会有children(不会被split)。
* l' f" m8 K' C+ K1 o5 m. Z  D# J' F2. 如果该节点中颜色错杂,那么把该区域平均划分成四块(左上,右上,左下,右下),这时该节点就有4个子节点。
. c6 V: k8 _. W/ Y3 y
  N! O, T# `! L- m( u( t3. 这样一直递归下去+ j5 ]! K# w- w/ d$ g
上面就是基本的情景,然后要求写出树节点的Class表达方式,为后面问题作铺垫。" e3 D/ }, Z+ C6 L( Z! _

5 R4 a7 z- I; p5 ~/ o) k* ?第一个问题很简单,求树的高度,用了两种方法,一是根据树递归构建的性质进行递归遍历,另一个就是层次遍历(滚动数组)来做。, A1 y- e. B) B, s3 G' X
第二个问题就是将两幅大小相同的图merge为一个新图,merge规则为对于两幅图上的同一个像素点,如果颜色相同,那么颜色不变,如果1黑1白,那么merge之后为白色。当然面试官是通过画了一个示例图来讲述的题目,可能会更好理解一些。我就用最容易想到的recursive的方法来做了。
- i% Z2 S& ]: b* D! M/ Z$ ^! u. l+ |1 ?$ M
第二轮================================9 U2 k4 m) L4 i; [# G( U
warm up 5~10分钟,然后就开始类似于聊天方式的做题(是个设计题),情景很长,跟gmail里显示广告有关。精练后就是有一个server,用来处理client向server发送的request请求,这个server会针对每个request返回true or false,这样得到true的client就可以向advertisement server发送获取广告的请求。这样做的目的就是限制访问,免得ad server宕机。问怎么设计这个server。。。5 X4 T8 X- v; t0 i
7 w& `; O$ s$ V# S* ?
第三轮================================! \: z+ f  {* c
个人觉得这一轮命悬一线,一上来就直接做题。
+ \$ {4 L/ a9 |) b% N( B
8 ~  M: P1 Z2 l$ v4 H第一题给一个BST(树节点的索引都是不重复的),然后给一个threshhold value,该value可能出现在树中,可能没有,要求分开成两棵树,一棵节点值小于等于threshhold,另一个大于threshold。这个题关键是定义好递归方程的API(即每层递归到底要做什么),然后静下心来做。3 }# w6 x2 x5 N1 }# F

; P2 R. d" P, i0 H: Q0 o1 B, M第二题是关于二维的region merge,当然题目被封装成描绘城市轮廓。在2维平面上的一堆矩形方块,每一个方块表示一个建筑物在地平面上的横截面,默认这些建筑都在同一水平线上,所以一个方块的数据结构可以表示为Building <startX, endX, Height>,即在水平线上左右轮廓的坐标和高度。现在问题来了,给你一堆的方块,这些方块可能重合,那么要求返回所有方块的整体轮廓。返回结果的数据结构需要自己定义。
1 e+ j9 J1 ~. A) k5 H
, \! v( ?3 S4 ?. z/ h# X. V# E2 @. m) }# l
总结================================
! P6 H5 H! d! L6 Q' Q# d& A由于master才读的CS,没有任何实习经验,一直都觉得能拿到G家offer真是一种看缘分的事情,可遇不可求。。。所以面试过程中心态还算好。码代码的过程中也出现了一些bug,也有一些地方还待优化,都是面试官提醒才改过来的。所以大家不要因为在过程中出现了bug就影响情绪,个人觉得相比于bug free,过程中与面试官的交流会更加重要。然后再强调一下心态的重要性,在第三轮BST题出来的时候,我就有种“完了,好难”的感觉,因为这种树的递归题,说容易也容易,说难也难,关键是在那个时间那个地点你想明白没有,做得出来OK,做不出来也不能说明什么,真的有种看天意的感觉,所以就抱着挂掉的心里准备安安静静分析,死马当活马医。。。
/ ~$ @+ c1 f: C6 t7 ^% J4 B# Q/ Z3 [3 [- l- h

: L( A- y( C1 v, r, Q6 l6 ?( U5 Z来源: 报个G家offer+面筋

本帖被以下淘专辑推荐:

1

主题

1

精华

212

积分

高级会员

Rank: 3Rank: 3

积分
212
发表于 1-27-2015 01:52 AM | 显示全部楼层
CHazyhabiT 发表于 1-27-2015 12:40 AM
% o& f$ E6 {: ?+ w0 k, S+ M* Z有要求,相对位置不变。
" S, B( j1 Z4 H* y8 i
乱写了个,请问lz这思路对吗?
7 L8 t( Y) l1 b# G4 s& u7 n* z# }( W% z5 G' d! V

  1. 2 P- \2 ]) e, c0 G6 X% l0 o
  2. void splitTree(Node* node, int target, Node* &smalltree, Node* &largetree) {
    4 d5 @- k* m7 `: G
  3.     if (!node) {
      H0 W# F* @4 @3 d8 k5 c5 `7 t% ~) ?
  4.         smalltree = largetree = NULL;
    8 f, H/ `  h6 c: x7 P. K3 h% H& m
  5.         return;2 M: I* }5 Y  u( C  {
  6.     }
    ; @' P+ @# q4 y. n

  7. 0 I0 O$ p) \8 P
  8.     if (node -> val == target) {
    1 ]2 y2 x0 a6 s2 @4 x1 Q
  9.         smalltree = node -> left;- t; ^" b( C- L, d
  10.         largetree = node -> right;! I& v( \1 O' L5 p1 g) x  S
  11.         return;
    ! f' E& L, o. {1 y) ]
  12.     }
    ( y& D5 t) H+ p" v0 H3 t% o# Z6 U
  13.    5 M# b- d* A; e2 ~) F: K" F
  14.     if (node -> val > target) {6 {9 Z( G3 R7 O1 E$ A
  15.         largetree = node;% o) ^8 {% g! P
  16.         Node* leftsmall, leftlarge;2 ^% f8 ~7 V. g' _( h* F
  17.         splitTree(node -> left, target, leftsmall, leftlarge);
    8 v( N0 n7 Q! n: v% [% o
  18.         node -> left = leftlarge;& m' z( q% g+ i9 V* b' K! K
  19.         smalltree = leftsmall# E# b9 [5 G' C* w2 L% Z4 \
  20.     } else {
    / q- t6 \# [; |
  21.         smalltree = node;% h' l% {8 ~* O8 N5 J
  22.         Node* rightsmall, rightlarge;4 E% ~0 x% b" Q. k
  23.         splitTree(node -> right, target, rightsmall, rightlarge);& ^  C4 B# m. z
  24.         node -> right = rightsmall;% u5 U% k' y) ~. P
  25.         largetree = rightlarge;; Y  W$ Q2 ?" |0 _5 \# O* K# a7 h
  26. }
复制代码
; w- P5 s  h6 S: U7 F. x2 w  M
补充内容 (1-27-2015 01:54 AM):& N+ N8 e8 ^% L$ v( {+ p* W; l8 s
8到12行等于的部分应该去掉。20行开始的else这段来处理相等的情况

781

主题

575

精华

5670

积分

顶级版主

Rank: 9Rank: 9Rank: 9

积分
5670

活跃会员热心会员优秀版主

发表于 1-26-2015 05:59 PM | 显示全部楼层
Big congrats!!!
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

32

主题

10

精华

499

积分

高级会员

Rank: 3Rank: 3

积分
499
发表于 1-26-2015 06:37 PM | 显示全部楼层
怎么onsite只面三轮。这要多牛的人呀。
: ]" n% I5 k( y8 y; M一般都4-5轮。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表