找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 6213|回复: 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 编辑
# |& y" Y" I( d( ]. _' J
: @" }, T/ n, e2 z! m9 _第一轮:定义buddy system为一棵complete binary tree。一个node可能为0也可能为16 E  w5 i+ B9 C6 [
. 它的9 t5 H' Q" M3 E; r  M) Z8 ^" @
value为1,当且仅当它所有的child的value均为1.
9 ]2 X( l1 v4 w$ E% `1
. d% A* Y! f! U: \+ \) s: b! Z0 ||             ) j; v! x/ o! z4 e
1             2' T/ g6 L$ B# o5 u/ @
|             |     
3 o8 E6 X; c' F9 m( ]3 f- Z; r1     2       3     47 n* r+ I: Q* s3 a! h
|     |      |    | % W9 S9 a7 i8 V3 t* F6 l8 {; L
1 2  3 4    5 6  7 8" V  D" D# ?' V4 n
7 `6 c/ Z- j2 V% b# r, K; H( v
实现下列的method。
+ P& C: ^$ I; S3 w! t0 w1' clearBit(int offset, int len);
+ q9 Y( Y" z0 a$ ?$ l2' setBit(int offset, int len);% V0 F/ e% Q9 D9 t3 Y- Y

1 W9 X& {2 R' z5 {( Z" k第二轮:设计一个task dispatching system,里面有一个task queue和两个function。, `3 Y5 b7 @  O, z$ Q) @) k# t
1’ trigger。这个function运行并清空task queue中所有的tasks。8 w7 s* X) g% I+ l
2‘ addTask。在trigger之前把task加入task queue,在trigger之后直接运行task。
! d1 ?9 A  E9 ^8 c, ?1 z6 ?7 `( A8 B
第三轮:产生一个圆上的所有坐标。不用sqrt, sin, cos等内建函数。
- c* X! X" W: H提示:所有的点都是整点。首先我们可以利用对称性把圆分成8块,先画出0-45度角内( j9 t6 ~4 N, ]- c2 ^
的点,然后映射之。对于其中0-45度角中的点,当X+1时,Y的值或者不变或者-1,然, F# v2 Y% i- D9 L$ f0 `1 Z5 h
后放入圆方程中看哪一个是对的。7 v3 L; O" a0 o2 D: _. |) H* v( \
; p$ V1 I% S! K6 c0 T
第四轮:设计一个Map<Integer, Integer>,满足下面的复杂度。3 @# S6 q& \. H2 z# c2 G
add: O(1)  deletion: O(1)  lookup: O(1)  clear:O(1)  iterate: O(number of + u7 e- H" B; b$ y
elements)。) |$ u+ ~- I' K/ u- f! S  p
提示:
& X$ g+ W, r, V: r' L5 d如果我们用randomly accessed array,复杂度如下:! t  O9 i! m; R" E& u
add: O(1)  deletion: O(1)  lookup: O(1)  clear: O(size of array)   iterate:
0 V( ]/ K. {# H# r  T5 tO(size of array)
! T' R5 L$ S5 o, c4 M6 w如果我么用sequential array, 复杂度如下:
- W7 ^' S, x- H3 m, {  D+ @add: O(1)  deletion: O(number of elements)  lookup:O(number of elements)   
. u3 D3 R  }1 p0 L' L1 R- Vclear: O(1) iterate:O(number of elements)
8 H) \+ H  R0 |  H3 @# z4 ~% A+ B" `5 ?所以我们需要把这两个方法整合起来。
9 P7 I4 F8 z# M, c, l- s" W4 c  @3 r: T; Q7 I( K8 S8 z

" d* K) t% n: W
' `7 E! b  L3 V3 O6 y( M- k) J+ R: ?: |0 W9 |

& ?" C2 }9 _5 g; u: `

评分

参与人数 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~~~
回复 支持 反对

使用道具 举报

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

本版积分规则

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