找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 7915|回复: 7
收起左侧

[PureStorage] Pure Storage面经

[复制链接]

11

主题

6

精华

295

积分

高级会员

Rank: 3Rank: 3

积分
295
发表于 4-11-2016 11:18 AM | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 Sophia 于 4-11-2016 02:35 PM 编辑
- `( j+ f, b; _- s+ e4 S& Q( d. K* P; p! }( q  p9 [+ U% V, q
第一轮:定义buddy system为一棵complete binary tree。一个node可能为0也可能为1+ W3 E- D7 V% b5 g
. 它的; o9 U: d) s3 h3 L2 C2 V
value为1,当且仅当它所有的child的value均为1.
0 v( [7 [# f$ e/ e8 v1; _+ s0 V: P5 [+ N) R1 Q) Q: I
|            
) C3 f% K% a- C; W; U" F0 t2 n& p8 n. ?/ x1             2
( n. F: D8 U2 Z|             |     
) o& u- ^* D( g, A1     2       3     47 \! o3 M  f9 @  Q# a* r* S
|     |      |    | ; u/ o) u- b3 j1 d2 D; p- i% i+ f
1 2  3 4    5 6  7 8
* Z; P2 W  A* i$ Q
) l6 R# d  _. u) R. l0 f! L/ B6 Q" w实现下列的method。0 }5 f% H1 O, J# i( |. s8 U
1' clearBit(int offset, int len);: Q4 x5 @5 ]; d9 L& Y2 I+ ^
2' setBit(int offset, int len);4 a/ _0 Q( o9 W0 k

  c; a) h+ _8 \% U第二轮:设计一个task dispatching system,里面有一个task queue和两个function。
2 ]2 i. S& ?0 x, d1’ trigger。这个function运行并清空task queue中所有的tasks。& N  N8 c6 S, S3 e& G9 a
2‘ addTask。在trigger之前把task加入task queue,在trigger之后直接运行task。
- R  S, ~* L5 @6 x) |  W
; \. y5 _5 c4 N) [- s; x第三轮:产生一个圆上的所有坐标。不用sqrt, sin, cos等内建函数。
* S, O# w7 h; T7 N$ ?' N2 J! R提示:所有的点都是整点。首先我们可以利用对称性把圆分成8块,先画出0-45度角内
+ q- [4 V4 H, k0 b( a0 n, s8 S% [的点,然后映射之。对于其中0-45度角中的点,当X+1时,Y的值或者不变或者-1,然
0 `* D3 \( C; [+ d. ]后放入圆方程中看哪一个是对的。  S- n/ ~8 u3 }) ]# _9 ?# a

5 W) x* I# U6 d7 z1 I$ k第四轮:设计一个Map<Integer, Integer>,满足下面的复杂度。; {  l) E2 {2 N! e4 a/ U
add: O(1)  deletion: O(1)  lookup: O(1)  clear:O(1)  iterate: O(number of , U: s: V. u3 l: N* ~& n* B
elements)。& }+ @  \8 b: Y; G' w. V
提示:
) t5 j4 L! V3 J8 @4 y如果我们用randomly accessed array,复杂度如下:
, M3 ]# s: ?2 a# u' ~add: O(1)  deletion: O(1)  lookup: O(1)  clear: O(size of array)   iterate: , m9 C' o* R' ^  m  F' _
O(size of array)9 u% Y+ |1 r1 [5 {7 t' t7 E' d
如果我么用sequential array, 复杂度如下:/ ^* z4 i, t. s* L
add: O(1)  deletion: O(number of elements)  lookup:O(number of elements)   
- B6 X* C3 ~$ t) l9 [! k& sclear: O(1) iterate:O(number of elements)
5 t* @$ [; O* N: O& J所以我们需要把这两个方法整合起来。) o4 B" ^  |% p' m% A% Y' `

$ S0 A' Z, Y( m8 x
/ I; [2 c+ J- m1 z7 M# Z  @0 ?3 y+ J5 O, D% V
$ U7 a5 I6 e: }6 m
) q  |* C+ n) k  c- C

评分

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

查看全部评分

0

主题

0

精华

0

积分

新米人

Rank: 1

积分
0
发表于 4-11-2016 11:19 AM | 显示全部楼层
感谢azhao155分享~~~好人一生平安~~~
回复 支持 反对

使用道具 举报

发表于 4-11-2016 11:35 AM 来自美国米群网手机版 | 显示全部楼层
感谢您这么详细的面经分享~~~精华积分满满送上了~~~也祝福您拿下dream offer~~~
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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