找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 6928|回复: 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 编辑
" L$ k* {5 L3 \: ]& I& {- ?- H# {6 V4 X1 G8 i
第一轮:定义buddy system为一棵complete binary tree。一个node可能为0也可能为1! {* l" ~& p* w8 f
. 它的
8 q+ Q( i: g, m. y( Pvalue为1,当且仅当它所有的child的value均为1.( }; d6 O* G1 c& f  E6 |5 Z$ n' k
1
" v" d' S. a- O% q  c|             ( Y- k+ Y4 T; \1 e
1             2
9 V1 x4 i; y8 U- N5 |$ l6 Y( F|             |     
; P. [- O' t, m  A: P  e/ V: y1     2       3     49 h# T: i  J3 y0 r' W
|     |      |    | * l. C- h! W& ]+ N1 k$ @
1 2  3 4    5 6  7 8
# R# J' Y/ |6 h) D' R8 D! s: L" W6 ~/ B1 n& m' [
实现下列的method。
  I  i) U7 m; }/ n; `: T1' clearBit(int offset, int len);5 e- H: N& }: u- G: x. v
2' setBit(int offset, int len);3 r. _+ r! ~8 W7 ?# g3 q9 Q

! Y/ p! d: F& n第二轮:设计一个task dispatching system,里面有一个task queue和两个function。
6 U4 ~5 a% @8 d7 k( o6 F1’ trigger。这个function运行并清空task queue中所有的tasks。
. N8 z; E5 M/ H! W2‘ addTask。在trigger之前把task加入task queue,在trigger之后直接运行task。' [' x; O8 }6 p" ?0 D- m
9 z$ C9 }) {$ @2 G1 R" t
第三轮:产生一个圆上的所有坐标。不用sqrt, sin, cos等内建函数。
+ s- P3 Z, N7 a  g  Z, w5 n* J提示:所有的点都是整点。首先我们可以利用对称性把圆分成8块,先画出0-45度角内0 \: d# P5 M( E* S9 X) k3 i  W
的点,然后映射之。对于其中0-45度角中的点,当X+1时,Y的值或者不变或者-1,然1 {6 N- o  b) k4 E( \
后放入圆方程中看哪一个是对的。
# U3 C8 s% M$ t
3 Q% N; K* m$ E) n& l第四轮:设计一个Map<Integer, Integer>,满足下面的复杂度。
4 t* F( E) K& |7 k! Eadd: O(1)  deletion: O(1)  lookup: O(1)  clear:O(1)  iterate: O(number of $ C6 [- D9 r" w; H+ n0 ?
elements)。1 [6 f" |3 G; H9 f
提示:
: s* \/ X/ y* j3 x如果我们用randomly accessed array,复杂度如下:6 x' Z- X7 g% U( R5 N
add: O(1)  deletion: O(1)  lookup: O(1)  clear: O(size of array)   iterate: 2 z3 W1 z) F- h% d
O(size of array)
- d3 ?; I' ]- Z如果我么用sequential array, 复杂度如下:
- Z9 Q) s8 l# Y0 }) D/ i& Qadd: O(1)  deletion: O(number of elements)  lookup:O(number of elements)   
. D# |1 G! {' eclear: O(1) iterate:O(number of elements)
! V9 `& G+ N& u& d$ b: K9 Z- h; G所以我们需要把这两个方法整合起来。
/ P% w% A! X( P1 L' Y2 v/ N7 S. h: s1 {* c& r! B3 o6 U
5 f8 e; h+ [; A* ^3 L# {
' I/ k' J" z) N, X# G
* z0 U) B( R) ?4 `2 |
9 X* m# P6 K# S+ [

评分

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

使用道具 举报

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

本版积分规则

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