找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 12119|回复: 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 编辑 3 J9 J7 Y( p( w4 H! |6 R0 I: {+ w

$ e, W7 L& K# B/ n. F* `+ v+ S1 q9 z第一轮:定义buddy system为一棵complete binary tree。一个node可能为0也可能为13 X  F$ W4 u8 l  h' K
. 它的
5 ]' J1 T! w- H: Ovalue为1,当且仅当它所有的child的value均为1.% q6 R+ h, C4 |7 q0 @
1
5 Q" f7 I5 x( a|            
3 U' q0 Q% j/ ~0 |/ A) G# W' |1             2
" f2 p4 R! w2 ]) W- ?|             |     * `, U& o& S$ l- v& c( t$ E$ w
1     2       3     4
) }2 A' Z- h% R: u% p/ W- E! Q|     |      |    |
8 p( N& Q& I7 ]7 A2 d) `6 U5 Z* P3 n1 2  3 4    5 6  7 8
; [4 y+ y: d' l" z, I* ]/ x7 E5 ~
2 Y' A( l' F+ }2 |实现下列的method。$ N7 p$ @# r$ Y1 r) {
1' clearBit(int offset, int len);
) \: y4 _  M3 p4 W! H" T2' setBit(int offset, int len);
5 h3 z* v& x2 f4 t/ K, u
( C1 y2 {. I8 w6 R6 v2 y第二轮:设计一个task dispatching system,里面有一个task queue和两个function。2 x5 n; t: V0 {$ h9 _7 y, }; y
1’ trigger。这个function运行并清空task queue中所有的tasks。
  n7 X  |7 t5 @1 p$ G2‘ addTask。在trigger之前把task加入task queue,在trigger之后直接运行task。0 i' E% y  w* Z6 H

  Z, ?" L- _6 [第三轮:产生一个圆上的所有坐标。不用sqrt, sin, cos等内建函数。
8 [+ @8 R* ~2 N提示:所有的点都是整点。首先我们可以利用对称性把圆分成8块,先画出0-45度角内
; X4 J# u. `, _5 G9 k的点,然后映射之。对于其中0-45度角中的点,当X+1时,Y的值或者不变或者-1,然
) e5 u0 s. r4 |* u5 W3 n. x, K4 {9 \: `后放入圆方程中看哪一个是对的。' U3 q8 i+ y# }. m. l

1 t, }. y8 ^8 [第四轮:设计一个Map<Integer, Integer>,满足下面的复杂度。) n! k0 D7 i$ [
add: O(1)  deletion: O(1)  lookup: O(1)  clear:O(1)  iterate: O(number of
- E; F8 o9 N3 u: n/ Belements)。
2 o! |5 Q7 F3 z" p提示:3 s2 E# h& [' _2 G& y
如果我们用randomly accessed array,复杂度如下:
* L6 p( Y- _" |7 E. k; [0 ladd: O(1)  deletion: O(1)  lookup: O(1)  clear: O(size of array)   iterate: , q' D$ r& @+ }  W- ~" L9 A
O(size of array); Z$ p; B, v/ x+ i, p$ E/ j! T
如果我么用sequential array, 复杂度如下:
- n6 A8 o: u9 B- P* B1 _+ u: J5 T( {add: O(1)  deletion: O(number of elements)  lookup:O(number of elements)   6 F8 r5 `8 f5 G/ M. c; d, J
clear: O(1) iterate:O(number of elements)
/ H4 L. @2 L" S6 m所以我们需要把这两个方法整合起来。
3 L/ J0 U) n5 v" T3 K  L7 E' Y2 V& Z
: I! U8 t6 Q- X; Y4 S% K6 C9 d6 R
  r( }. t3 ^/ z9 [) A' M  X2 J+ f
6 [  A+ c' k+ t+ {
4 N$ C9 ^% D8 Z3 t

评分

参与人数 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~~~
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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