找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 8234|回复: 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 编辑 * p* L' q6 e) A% |; P

& c- K7 c9 O; [1 C* z/ r6 Q第一轮:定义buddy system为一棵complete binary tree。一个node可能为0也可能为1
0 w7 l) v( C9 v* m+ n- `  m. 它的9 z: q) g  ~5 s6 ~9 i; P
value为1,当且仅当它所有的child的value均为1.
+ j/ m4 D; `$ X' U; b$ F9 \1: M% @6 T: Q/ E' {& L% o
|             * p$ i- D1 Y7 t$ u! i% s
1             2
$ ~5 ~, A0 \$ e' g' O% Z|             |     
: ?6 S  k9 W  A& _$ p1     2       3     45 o  g: I* u) x5 o7 r7 N
|     |      |    | $ \' Y6 W* j2 g' @( ~
1 2  3 4    5 6  7 8# u; e& z, b/ A% z4 h9 v2 r& L

6 |2 X2 i9 ?: ?, C实现下列的method。
# a3 \" t7 i% @' ?7 A2 O  k1' clearBit(int offset, int len);! Q0 d# b" N/ E$ F5 o9 ^- G1 y
2' setBit(int offset, int len);  H  V$ j$ m# D  c6 K
- j# }# ]. r! j. J$ P; s
第二轮:设计一个task dispatching system,里面有一个task queue和两个function。* [7 p3 W$ V- h5 Z2 e
1’ trigger。这个function运行并清空task queue中所有的tasks。
# t2 D' ?2 Q' ^) A+ h7 R5 o2‘ addTask。在trigger之前把task加入task queue,在trigger之后直接运行task。+ q" k, Z9 c0 M4 y
3 C+ ?6 [0 H4 t% O; \3 J2 n6 k, E
第三轮:产生一个圆上的所有坐标。不用sqrt, sin, cos等内建函数。6 u8 w( W  a3 k# D7 Y
提示:所有的点都是整点。首先我们可以利用对称性把圆分成8块,先画出0-45度角内
; F5 F1 M5 @, v" e* `的点,然后映射之。对于其中0-45度角中的点,当X+1时,Y的值或者不变或者-1,然$ j" c8 _/ z. p" y0 \: b8 Y
后放入圆方程中看哪一个是对的。
7 f& s& r' G5 [0 W8 T( n) `6 P# |# k2 v+ C' T
第四轮:设计一个Map<Integer, Integer>,满足下面的复杂度。
) o# M* h0 `) b& A2 Aadd: O(1)  deletion: O(1)  lookup: O(1)  clear:O(1)  iterate: O(number of 3 ~' O7 K$ p! u6 j
elements)。
$ F6 S& Q, |* P8 N1 ~3 t0 ^9 Y提示:
% e; y. S) ~  w如果我们用randomly accessed array,复杂度如下:$ K: `. `6 [. h0 _/ E% N1 ^2 W& [
add: O(1)  deletion: O(1)  lookup: O(1)  clear: O(size of array)   iterate:
' t1 I# K. @" I0 {, _" l1 ZO(size of array)8 m; Y  B% }2 s8 ^! Z7 r3 E! C, H
如果我么用sequential array, 复杂度如下:; D0 P1 s* H6 ]4 {
add: O(1)  deletion: O(number of elements)  lookup:O(number of elements)   - Z0 A0 ?6 L4 R3 C
clear: O(1) iterate:O(number of elements)" l3 h/ B. i" L
所以我们需要把这两个方法整合起来。
1 H' q  q& V1 n* ]( [6 A2 m; m1 ^9 f1 C  d. s: w5 q) U: g

9 i( W$ v! F% u( ~( m
( u& L/ d1 g" I& n  ]9 J/ C" L8 L7 w. C/ N

8 e4 ^/ O0 W6 p+ G4 e8 P2 d

评分

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

使用道具 举报

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

本版积分规则

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