找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 11791|回复: 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 编辑 + F) L8 V) V( K) [( R! L! s

0 X! K% ~6 j9 y% c( D4 O第一轮:定义buddy system为一棵complete binary tree。一个node可能为0也可能为1
( C1 m& c9 ?1 q4 c7 S( D. 它的
* s3 K1 d& ~  E! J0 S( Xvalue为1,当且仅当它所有的child的value均为1.: L! y' s- N( n% |3 e/ `; U' [. P
1
7 W* W1 ^  f: d1 Z* t4 g" t|            
8 ]2 ~3 k  X7 x9 _- I1             27 ?  G8 Z: T$ a' k2 B" x: S' N
|             |     ' I# T  P5 }) Z2 q
1     2       3     4
, a% |+ ]2 h1 v8 @- ?9 K7 R|     |      |    | 1 T% t" {/ w# n4 S& Z5 v9 C- E, G( x
1 2  3 4    5 6  7 8
6 q. d# C) V5 @/ _$ R! F" @/ z  n/ _5 }6 |4 d8 P' O1 F
实现下列的method。  k) o# a9 f+ m3 {1 u  x3 `& D0 ^
1' clearBit(int offset, int len);* d( W0 X# m. D
2' setBit(int offset, int len);9 D& T1 D& R" H! F
0 Y- F# `# H& v$ u/ A9 N
第二轮:设计一个task dispatching system,里面有一个task queue和两个function。
6 Y' y4 I& Z$ U- R2 v1’ trigger。这个function运行并清空task queue中所有的tasks。, c# A3 ]4 }5 D
2‘ addTask。在trigger之前把task加入task queue,在trigger之后直接运行task。
7 B' ^( V8 c" \- h, a" g
. F) }$ }( C9 y& \第三轮:产生一个圆上的所有坐标。不用sqrt, sin, cos等内建函数。
* f9 H* m  G8 F0 y6 @提示:所有的点都是整点。首先我们可以利用对称性把圆分成8块,先画出0-45度角内
, m; P6 i' U% i/ x. c的点,然后映射之。对于其中0-45度角中的点,当X+1时,Y的值或者不变或者-1,然
: ?" J& @4 y0 z5 P8 w& o后放入圆方程中看哪一个是对的。! x! V+ |0 w/ E$ n

2 V5 K# }! E7 W8 R第四轮:设计一个Map<Integer, Integer>,满足下面的复杂度。
6 D) N: W) Y( f& x: k8 Oadd: O(1)  deletion: O(1)  lookup: O(1)  clear:O(1)  iterate: O(number of 6 n: M) [) k% }9 y0 ]
elements)。! ~* x4 `* v. F7 I! G+ ~
提示:
) Y7 I. b; C9 V4 \: }* ^如果我们用randomly accessed array,复杂度如下:
. G8 f1 F3 N8 K1 n; J( Tadd: O(1)  deletion: O(1)  lookup: O(1)  clear: O(size of array)   iterate:
7 c2 \1 C( Y5 G9 IO(size of array)
# v, a5 {5 ~& Q3 Q4 q0 U. d如果我么用sequential array, 复杂度如下:5 `# Q  O' r# f: q4 x' Z" Y" N' L
add: O(1)  deletion: O(number of elements)  lookup:O(number of elements)   
4 F% m0 ^* k) T( ~) e- D7 sclear: O(1) iterate:O(number of elements)5 n5 l  j# u8 j7 ]/ A
所以我们需要把这两个方法整合起来。
" z( y1 J/ w  k: o) t+ l  I+ N. X, s! V
) ^8 J8 q; A( N* _+ o- p

; g$ N5 g* o* z! o7 j* }7 e5 c0 n. C( L! w# u/ q( e& A, m
" \+ z4 F) _3 Q5 N) n7 B6 o

评分

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

查看全部评分

0

主题

0

精华

0

积分

新米人

Rank: 1

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

781

主题

575

精华

5670

积分

顶级版主

Rank: 9Rank: 9Rank: 9

积分
5670

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

发表于 4-11-2016 11:35 AM 来自美国米群网手机版 | 显示全部楼层
感谢您这么详细的面经分享~~~精华积分满满送上了~~~也祝福您拿下dream offer~~~
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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