找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

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

  [复制链接]

6

主题

4

精华

500

积分

超级会员

Rank: 4

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

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

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

x
本帖最后由 Sophia 于 1-26-2015 06:03 PM 编辑
1 ]! D; l9 J% j1 w9 _% L5 s8 g4 \% {8 `) _! J  G( d$ [" {' g
从去年11月on campus,到圣诞前的on site,再到现在(1月)拿到offer,G家的面试贯穿了整个求职历程,报喜讯的同时顺便也把on site的面筋分享一下。
6 b- e  a6 f) |( X0 D7 O& N& K" ^0 S9 B; b7 C

- L" X* w+ S* B& j+ `8 f% @on campus面筋戳这里http://www.meetqun.com/thread-2227-1-1.html,on site有3轮,上午10点左右开始,午饭前两轮,午饭后一轮。7 U. U" q: A9 W) i( U3 Y" n. ~5 W

( s$ I) C+ F  f) b+ f1 Y5 ?' i第一轮================================; \6 j0 \& Z* G9 y- p. ^
warm up 小于5分钟,然后就开始做题,关于用树表达图像的题目。假设一个矩形画布(理解为一个区域),该区域只能由黑白两种颜色填充,然后根节点表示的就是这个矩形画布。
  L4 ]6 c+ R1 t; X# Q& q1. 一个节点表示图中的某一个区域,如果该区域全黑或者全白,那么它将不会有children(不会被split)。0 _2 {. Q- S! L/ O1 }, s
2. 如果该节点中颜色错杂,那么把该区域平均划分成四块(左上,右上,左下,右下),这时该节点就有4个子节点。
" ^3 Z! [1 c. T6 b" R$ J4 V: w$ U/ K% o
3. 这样一直递归下去5 k5 G  {6 r/ G/ {* c. o
上面就是基本的情景,然后要求写出树节点的Class表达方式,为后面问题作铺垫。+ o7 ?4 @9 D& a  w: y+ Q+ f
( F. d, Y9 ^# i5 p3 P; T- P
第一个问题很简单,求树的高度,用了两种方法,一是根据树递归构建的性质进行递归遍历,另一个就是层次遍历(滚动数组)来做。; p  I1 t! [. i. d( ~
第二个问题就是将两幅大小相同的图merge为一个新图,merge规则为对于两幅图上的同一个像素点,如果颜色相同,那么颜色不变,如果1黑1白,那么merge之后为白色。当然面试官是通过画了一个示例图来讲述的题目,可能会更好理解一些。我就用最容易想到的recursive的方法来做了。/ Z" C, d3 Q2 u8 V4 j9 _

& 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第三轮================================2 f  ?. n* ?0 y; @# M
个人觉得这一轮命悬一线,一上来就直接做题。
/ k# z2 A8 p, O4 W7 O: {+ C
+ J* E( y3 d1 Z第一题给一个BST(树节点的索引都是不重复的),然后给一个threshhold value,该value可能出现在树中,可能没有,要求分开成两棵树,一棵节点值小于等于threshhold,另一个大于threshold。这个题关键是定义好递归方程的API(即每层递归到底要做什么),然后静下心来做。$ {1 }& T" r& F; q6 @
- r$ O" ]+ o1 K$ v) W4 Y
第二题是关于二维的region merge,当然题目被封装成描绘城市轮廓。在2维平面上的一堆矩形方块,每一个方块表示一个建筑物在地平面上的横截面,默认这些建筑都在同一水平线上,所以一个方块的数据结构可以表示为Building <startX, endX, Height>,即在水平线上左右轮廓的坐标和高度。现在问题来了,给你一堆的方块,这些方块可能重合,那么要求返回所有方块的整体轮廓。返回结果的数据结构需要自己定义。) _/ C$ y9 m: L- k" l
8 |3 w: l7 ]- ~0 ?

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

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

本帖被以下淘专辑推荐:

1

主题

1

精华

212

积分

高级会员

Rank: 3Rank: 3

积分
212
发表于 1-27-2015 01:52 AM | 显示全部楼层
CHazyhabiT 发表于 1-27-2015 12:40 AM  \+ E4 @6 B# X& K& d
有要求,相对位置不变。
, y1 T0 L+ x# b* Q
乱写了个,请问lz这思路对吗?3 u5 R3 e" X0 {8 U4 E% T+ j
0 c$ |, X) b0 \5 c
  1. & L& J4 Y1 I% G# {
  2. void splitTree(Node* node, int target, Node* &smalltree, Node* &largetree) {7 A+ E; ^) I  s% ?
  3.     if (!node) {
    6 B$ ?% N% K, G' Y7 n9 u* g
  4.         smalltree = largetree = NULL;
    $ X8 \* S6 G1 U
  5.         return;* }1 S, K: Q: s$ `- {' m( s
  6.     }+ ]3 A4 B9 V) X4 m- o
  7. . i9 |4 K  L) c5 N  Y
  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;' {7 @* k% x; h0 y7 k" s/ _
  12.     }
    0 K7 F; P/ f6 d+ [0 B$ B
  13.    ( l: z+ m7 ?/ R* e
  14.     if (node -> val > target) {0 ^; S4 |. K! ~* B; _
  15.         largetree = node;& o3 j3 w) ]  c+ n9 r% Z& ^; x
  16.         Node* leftsmall, leftlarge;2 u  f6 z& W( x3 |* b, i6 {
  17.         splitTree(node -> left, target, leftsmall, leftlarge);
      E. z5 X" ~+ Q
  18.         node -> left = leftlarge;+ W! E/ {3 k: W1 [0 T
  19.         smalltree = leftsmall
    6 d0 G# C! f% U$ J* o; k- \
  20.     } else {6 D7 t1 c( L( h* Q% ]* x
  21.         smalltree = node;1 ?. ?" P9 W" y( G' U+ B9 U
  22.         Node* rightsmall, rightlarge;$ N# \; q% @5 Y6 }
  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;! T0 }6 o" Q) b  i5 E7 r  n, h
  26. }
复制代码

( }  q8 ]+ N. ?3 X" f补充内容 (1-27-2015 01:54 AM):
. d1 `6 @. c5 P' V6 A1 @/ s8到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; w8 o+ K1 @/ x# W8 s6 T# z3 _0 \
一般都4-5轮。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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