找回密码
 立即注册

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)! u S+ Y B5 ? [) s# ]
Insert a new, non-overlapping interval O(n)' N% W% I; d, w
Insert an interval that partially overlaps some existing interval(s) O(n + k) where `k` is the number of overlapping intervals.

function IntervalCache () {
# x$ _; C6 J% y" l4 ?	this.intervals = {}
/ p; a# l* b, U; D! r. d# D: O% L. }}
2 \! o9 e6 H+ R1 d
: _1 k3 r; P; y. TIntervalCache.prototype.find = function (interval) {7 M  h  l2 {: T0 g1 D. ^3 p$ M( a/ q
	return this.intervals[interval.join(',')]( x, ?) g7 Y: C" p# l% v
}* g( e( r% W1 k. ]4 f' {

8 K" l5 G$ M3 ^- A6 A, XIntervalCache.prototype.insert = function (interval) {
/ [: C, s: H* t' @	var intersections = []* F4 W7 s4 K8 k& R7 e3 H$ Q
	for (var key in this.intervals) {  r) E6 f7 [- n6 _5 P% {% R- ~5 u
		if (({}).hasOwnProperty.call(this.intervals, key)) {0 d$ L- [5 u9 R1 t& S* d4 J$ ^/ e
			if ((interval[1] >= this.intervals[key][0] && interval[1] <= this.intervals[key][1]) ||
9 p+ a6 p+ m) ~2 k				(interval[0] >= this.intervals[key][0] && interval[0] <= this.intervals[key][1]) ||9 W/ U) A- {6 p; G
				(interval[0] < this.intervals[key][0] && interval[1] > this.intervals[key][1])) {
# I, j: H/ u5 W; A7 x# k& G$ q; m* i/ p				intersections.push(this.intervals[key])
+ _: J9 o+ B1 A9 T				delete this.intervals[key]/ A" c9 F' y5 w
			}* Y$ ~/ c  g( D4 h2 a  s8 J
		}
. D( K* m; p5 V$ W	}
4 H) y4 o+ k' G8 q+ _& [	if (intersections.length === 0) {
- X0 V& [' Q1 k7 F2 \		this.intervals[interval.join(',')] = interval5 p9 I- {, w; I
		return0 V  i6 N: |3 b) Q
	}) a% p  n! e8 q
	var min = interval[0]0 t7 {7 i9 |7 O+ c% T4 B
	var max = interval[1]; f6 G: {& U( g/ s! j) L
	while (intersections.length) {4 q; U8 O9 X( A) q2 ?
		interval = intersections.pop()1 X3 w& G7 D4 V8 M! M5 @# e
		if (interval[0] < min) {
, a  X4 P3 t- K$ p* p			min = interval[0]
0 s8 b0 K: Y) s+ `+ d		}
* S% Q  t0 A8 H4 H# I- `# @		if (interval[1] > max) {. _" |% U) ?, C* |5 m* j
			max = interval[1]9 [' M2 C6 j* A9 s2 t3 A3 c) W& L
		}9 Y: T' k; I, w
	}2 H0 l7 I/ P# `
	this.intervals[[min, max].join(',')] = [min, max]
, }. Z4 J" p# z+ e4 _' s}
5 G; _) S, Y2 t4 X( f' b6 E' {: `, t$ C5 X2 \2 ]% k! Y) y+ k$ |% j
var cache = new IntervalCache()
0 E# o* u5 O! B( e4 d2 z9 _6 Rcache.insert([25,100])
$ z, E. Z; p; L/ S# d- p$ fcache.insert([250,550])
2 u- I  [1 W* |6 Rcache.insert([1000, 1200])4 i3 j4 {) J" O/ S
cache.insert([400, 700])+ D( h5 t! D1 e8 I- K+ d4 D; J
cache.insert([30, 60])! ?3 K# t  h/ _% t8 u6 O7 b
9 r. j( }8 y. w( L: s
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.

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

本版积分规则

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