找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: PattyZhou
收起左侧

[Amazon] 亚麻SDE-2面经

[复制链接]

1178

主题

174

精华

3584

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3584
发表于 1-30-2017 09:06 PM | 显示全部楼层

We can use Interval Tree or Segment Tree Data Structure ...

1173

主题

182

精华

3657

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3657
发表于 1-30-2017 09:06 PM | 显示全部楼层

Look up an interval O(1) + x' _: e m3 q W
Insert a new, non-overlapping interval O(n) % I' n* ]7 V6 T& j2 ?* B. n6 |3 O
Insert an interval that partially overlaps some existing interval(s) O(n + k) where `k` is the number of overlapping intervals.

function IntervalCache () {
, X( @: k6 O) H$ H3 J  a! E	this.intervals = {}$ X9 k; U/ c2 Z2 V
}
# U" i( v/ D! C7 w
4 W' ?! u# f  q3 V: L; Q' dIntervalCache.prototype.find = function (interval) {1 f0 v1 \. m, [5 @0 k* Q* I6 m
	return this.intervals[interval.join(',')], t. u2 V4 ~4 {4 Q
}( Y/ O2 I( n; i. s5 Q- x
6 E+ B" k, C  O5 R: s6 A
IntervalCache.prototype.insert = function (interval) {
+ S; z7 \1 a+ E# t% l3 @	var intersections = []
4 v1 D/ I0 h- s, h, |) f) d	for (var key in this.intervals) {
$ @* w, e# W3 Q$ L		if (({}).hasOwnProperty.call(this.intervals, key)) {
: u" P$ z2 i. L4 n1 ^) s, }  f			if ((interval[1] >= this.intervals[key][0] && interval[1] <= this.intervals[key][1]) ||
+ S6 v9 [, e& m! f# e				(interval[0] >= this.intervals[key][0] && interval[0] <= this.intervals[key][1]) ||  k9 G$ n  K! i9 U; }: @
				(interval[0] < this.intervals[key][0] && interval[1] > this.intervals[key][1])) {- H7 |% q! x/ b0 k
				intersections.push(this.intervals[key]). {: E+ g0 `+ m& H; V' c' B0 O) M. G
				delete this.intervals[key]$ P/ P8 f* X! }1 w: h' g
			}8 N0 N: t* T! Y5 N' T
		}+ ]( b4 ~5 E' Q) v) z
	}
- D% |4 T% ]% {& e/ U+ {	if (intersections.length === 0) {
& O4 N3 W2 a/ t5 ~: Z		this.intervals[interval.join(',')] = interval
& p8 j9 P" M7 g" v' f		return5 I5 [+ b; Q& [% G: V
	}
0 h% O5 l+ Q! [* F6 ~0 w	var min = interval[0]
" c* f6 m; @# h4 n, Z' n9 V	var max = interval[1]
7 t: j+ C9 v. u. w+ E" L; G	while (intersections.length) {9 O, S; U7 T" ]6 g* m
		interval = intersections.pop()7 A& s3 J& O6 q! n5 F
		if (interval[0] < min) {
' K. E. c* z! p7 r, `			min = interval[0]9 x* L" b" k1 F5 n2 C7 M: ^" j
		}
, J9 G3 E0 i. @/ L9 W  \  |2 I/ h3 g		if (interval[1] > max) {
6 m  G9 ?! ]( |+ N0 \9 Z* l6 ~% {5 G			max = interval[1]; Q$ x. H# g# H$ @, C4 L% a
		}* B! O' d" D* Z2 q0 M) \
	}
  s! N' O- e, ~	this.intervals[[min, max].join(',')] = [min, max]
" y' ?3 r: b( W  S/ f8 t* m: @2 i}
" c" r1 |' o) F& S+ V8 g. ~7 T9 l0 Q
var cache = new IntervalCache()9 u+ ]. n8 f9 g7 N. c& R: U
cache.insert([25,100])
9 C# l, _% {2 X3 d: ?$ G( b9 Y$ ccache.insert([250,550])
/ z1 B7 D2 ?/ M5 b' }& Y$ Rcache.insert([1000, 1200])
& G5 o$ N' J0 A  o" E# b2 Jcache.insert([400, 700])5 i6 l: D3 `$ [& n+ l) C8 g
cache.insert([30, 60])! {: g4 }# h6 W  A7 s  C3 z
& X6 U" V6 {3 v3 r* b$ ^. E
console.log(cache)

1141

主题

171

精华

3486

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3486
发表于 1-30-2017 09:06 PM | 显示全部楼层

@srterpe: That should be O(1) look up of interval.

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

本版积分规则

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