找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2603|回复: 6
收起左侧

[Google] 2015年10月22日 google MTV onsite

[复制链接]

8

主题

5

精华

357

积分

高级会员

Rank: 3Rank: 3

积分
357
发表于 10-22-2015 10:16 PM | 显示全部楼层 |阅读模式

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

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

x
# I' ]$ `. s8 f$ i5 P) u
2015年10月22日 google MTV onsite% P9 }/ \6 E, _5 [, h' {
共计5轮, 没有老印, 没有老中, 4个老美, 2个像是南美人, 最后一轮是2个人, |# H. M8 m7 N( h. G! T" m
没有design, 没有tech communication, 顺便说下, 感觉google的45分钟,好紧张呀, 可能还是我弱的厉害
  V# X, }' K2 p
% q; j2 C! z$ B9 g8 J7 q( D1. 实现一个动态数组, 可以自动扩容那种, 用了loadfactor. % V% {" C& i1 W# n! V
4 i4 x/ N7 O( k- R: N, d6 X, z
2. 画了一个图, 两端是A和B, A,B之间有若干个stop points, 一个人要从A走到B, 中间可以任意停在stop点上,
7 d) o6 g8 d3 H5 ea. 这些点的间隔不一样, 例如(想象个一维坐标, e.g. A: 0, B, 1000), 我们有 stop 点 50,60,85, 100.。。。。7 V" L! r8 b( f9 m
b. 50 penalty, 假如从一点到另外一点的距离是50, penalty为0, 否则penalty=Math.abs(50-distance);  e$ u6 h" M4 ^+ T+ f& n, G
找出来从A走到B最小的penalty.
3 H4 N0 T" M% f6 r  r! ^$ Xe.g. input{0, 50, 60, 85, 100} where 0 is A, 100 is B, ! S' _6 q6 [2 w5 z. n: |4 R
so penalties are:
9 }. |' m" [8 W# |, s: u: V) [( k(0-50:0), (50-100:0) total=0
( I4 u6 F' g# m( w* V(0-50, (50-60:10), (60-100:10) total=20
" X! e3 x7 h3 Y! L1 g....
3 B- ?" ]( \% K4 |, \, ~, w(0-85:35), (85-100:15) total=50.
, k3 D" S, P2 Y0 J6 k6 F/ t
, H( l" E! h- o! L9 jSo (0-50-100) is what we want, 只用返回最小值, 不用求序列, 可以用dp O(n^2) 解决。 7 p" W3 c! t0 k( o/ r! w0 ~# W- ~( a

( y1 G  H% t2 t% _4 `3. 给你一个整数数组{2,3,5}, 一个target 33, 求出所有能用数组中数组成的<=target的数  n5 Q1 h9 a& r# U8 W3 P4 e; M' Y
例如: , f; g  F9 g1 s3 B
2,3,5: y9 F9 x' H; B% F0 D9 F* |
22,23,25" s* k. x, {+ S' Q( B
32,33
( I6 t9 q% f$ o' A  X! G
. }3 }$ e- X/ u4 G$ N8 }8 x; rsubset的变种, 在23,32的时候纠结了一会。 , o4 Q& x6 ^) o

' a3 p. u/ I0 B6 x4. 给你一个无向图edge list, 求里面的三角形, 南美人不友好, 不给hint, 就自己在那边干活, 而且最后我就做出来个暴力解, 他没留意, 还讲了半天才明白, 我了个去。
8 K$ |3 d4 L/ [6 p; o2 {a.
! z: V% N( v9 r& W4 V+ H0-1" ~! i  j, p0 H/ O$ d5 O1 f: R1 }
1-2& g( ~% z2 t8 ~2 G
3-2
8 Y, O0 R* [5 R1 J# N4-3
/ N+ q8 {/ a# V% P# c$ v1-07 {+ N2 u! @0 _9 V
自己想如何设计数据结构来表示input.
$ s; p# ~4 h( E( G* _3 D  _" Yb. 求里面的三角形  M9 U7 w' _- X7 r
我会求cycle, 但是三角形, 没想到太好的解法, 说完题目都过了20分钟了, 因为之前还扯了别的, 最后给了个最暴力的解法1 H9 I$ g( k# U1 o7 J4 t
i. 对于每个node, 找出他们的邻居' p- {% `. N2 ?- ~0 K
ii. 看邻居之间有没有相连, 有则找到, 没有继续
8 G) h" ^9 U  e! j$ X" @% H& o+ N# k. [0 n& O
5. 给你一个循环链表, 4-7-3-5-2-4, 一个大圈的那种链表, 代表一个roadmap, # m5 k" k, Z; Y  x' @
a. 每个节点的整数是在该节点能够加的油。 # Q! O8 u" B8 M
b. 然后告诉你从一个节点到另一个节点的边上是有cost的, 既要花费的油,当当前攒的油+当前节点加的油-到下一个节点cost<0就代表不能走了
: z: w# |& Y% A* q& p. ?0 `: I问, 给你任意一个环上的node, 让你返回一个set<node> 包含哪些可以走一圈的节点, 3 p' k" a3 D2 H, Z
有点象是gas station+linkedlist的应用。
  J* }# Q8 Q/ t, N  s' q7 }( m
" U* K7 y. w0 G  [$ W8 X$ P弱呀, 每轮都只做了一个题。。。去年面google的时候还是9个算法+1个设计。。。。。。。, 老了7 l; k: `2 Y8 I: ~) n; S8 @
% o1 Q: [3 R8 i6 {$ }
积极发面经, 攒人品, 希望下面onsite能拿到offer, 现在都成了onsite就死了, 真。。。。。。
" G2 b" w) ?) T, i* ~6 l' ^- ]0 I: e4 {; @' F: S

评分

参与人数 1金钱 +30 收起 理由
Sophia + 30 感谢您的认真和用心的分享!大米满满送上!

查看全部评分

781

主题

575

精华

5670

积分

顶级版主

Rank: 9Rank: 9Rank: 9

积分
5670

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

发表于 10-22-2015 11:40 PM | 显示全部楼层
感谢您这么详细和用心的面经分享~~~祝福您拿到自己的Dream offer~~~精华积分满满送上了~~~
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

2

主题

1

精华

29

积分

新米人

Rank: 1

积分
29
发表于 10-23-2015 03:26 PM | 显示全部楼层
楼主是跳槽么
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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