找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 5159|回复: 12
收起左侧

[Amazon] 亚麻SDE-2面经

[复制链接]

1122

主题

177

精华

3497

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3497
发表于 1-30-2017 09:06 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Sophia 于 1-31-2017 12:38 PM 编辑 + Z, @  s8 X" }: r( A

3 D% p3 w$ W8 ~* J6 A; o0 LGive a large multi MB byte file in memory, a system handles delete requests for segments typically of the order of bytes. The system has a constraint that individual purge requests of byte segments are expensive, so that the no. of purges are a minimum.
; E  [0 u4 B" Q! Z" _) [% q( u+ T5 s. u0 I% j" P- G5 Z3 x  A, |
Eg. a 5 MB file receives delete requests for offsets (1, 100), (250, 550),(1000, 1200), (400, 600), (800, 900), (1100, 1150)
: b9 @, K8 g1 }5 ^8 U5 H
$ e& a5 I+ N8 u" Q* FEffective delete requests - (1, 100) , (250, 600), (800, 900), (1000, 1200)
' I; S, c! t, \% f6 ]
7 S/ u, ]+ J" SThe users of the system always go by the absolute byte ordering of the file. Eg. if byte 1 is deleted, the users of the system will reference the actual byte 2 as byte 2.
! \- }4 C$ b, K6 u/ ^4 C  u5 W
4 ], ]/ p  ?0 g* P0 Z1 N) CWhat data structure would you use to store these intervals such that the following operations are efficient 1. Looking up an interval 2. Inserting a new interval that has no overlap with existing ones 3. Inserting a new interval that has partial overlaps with existing intervals. This would involve collapsing the existing intervals with the new interval to form a single large interval. Eg. Interval cache: {(1, 100), (250, 550), (1000, 1200)} , new interval : (400, 700) -> Interval cache: {(1,100), (250, 700), (1000, 1200)}

1190

主题

190

精华

3766

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

Update: As the problem looks like it need a data structure like cache to hold elements and perform operations. LinkedHashMap may be suitable to implement this as insertion and deletion are easy on it. ( Z' Y$ R- X, g$ j2 \" C
" K3 p3 H. @6 U& Y: p5 n
My below code is written using ArrayList and I am creating a result list every time when insert request comes which is not optimal. . [* o O. ]" f k( V
7 K0 d) `. L: f" P. O2 P- [
Previously: 5 p( N1 i$ l" E. _" \+ p
( r# X$ l& g9 B# v( D" U' u# x6 c
Possibility-1: This problem is combination of merge intervals and insert intervals case if the problem says the problem start with list of unsorted intervals. 5 ?+ R5 G9 b" g
; R8 D. T5 d, `4 m6 X
Possibility-2 : If the problem is to assume one interval comes at a time as input, then it is straight forward insert interval case. 7 s; l( ^8 N* q" d- _4 g+ E
. u. G- `. N. x+ _) I, O" M) P
Java Solution: 3 e V+ j4 N: k- ]! T' h9 y
, }$ @$ e6 H' o. H* b. ]5 T4 N
Interval object can be stored as below.

class Interval{
) E  G+ @- I; j" |. ~8 u	int start;
9 R9 \4 `) P* j% W+ F8 R	int end;( K2 `, y+ ?, X+ o7 \- {9 s; L. e- t
	public Interval(int start, int end){2 v( O: a3 B& Y! ^1 q- ]3 I* v; ]
		this.start = start;
: S- n; v+ B7 y/ x4 \		this.end = end;
7 s1 o7 y; c0 {( |# ]% |	}" H6 A7 K8 T- ^$ c* K4 Z
}

Key points: 9 l' q F/ j# x+ P& \- v
1. As the question is not clear, if the intervals are sorted or not incase of more intervals as a preprocessing step. # S5 D) e$ }/ g) W" L8 U( s! `
We can take initial List of initial set of inputs and sort them and merge them and keep it ready. 8 a) c8 O* m/ [( N8 ?4 i
; E+ ^5 f# W+ ~5 a" R
This can be a preprocessor step.$ _* o3 n$ u8 m* L% P- m
) \3 A/ C* ~# P& Y; F6 Q6 F
Merge (preprocess step) can be like below

public List<Interval> merge(List<Interval> input){
( `* U" [! p* b. J	List<Interval> results = new ArrayList<Interval>();" V- V9 [8 d- n. ?: o& |& l
        //sort the collection
/ ~% W1 r% q+ ?	Collections.sort(input,(i,j) -> (i.start = j.start ? (i.end.compareTo(j.end)) : i.start.compareTo(j.start) );
4 O% r+ x" ~8 j% x+ h* x# y. V6 R% ?6 y$ ^" p0 W
	//Loop through sorted input and merge  p( x% v' _7 D' ?
	Interval previous = null;
; ]# P! l4 _- J  Z& i4 m/ Z7 I        for(Interval curr: input){
6 h: j; i- _2 x            if(previous == null || previous.end < curr.start){ //non-overlap case
$ {, x9 c+ Q# M6 }* C& T" {                if(previous !=null){" Y& _  d$ F! X$ c) u; W& i
                    results.add(previous);, z5 q0 y5 S5 [$ i+ \8 A
                }) T, s' Y" z, Z) ~' W) k+ i
                previous = new Interval(curr.start, curr.end);
) ^. V7 V& m# Q/ p            }else{7 U2 N" a4 d% |- C, V" D! y
                previous.start = Math.min(previous.start, curr.start);
/ B5 p. f$ B+ r6 s                previous.end = Math.max(previous.end, curr.end);3 `+ R( ]; M0 O0 e
            }' t+ a, u1 K2 _6 j
        }
3 _/ Y  \6 W( z( f- W* E" B2 B' r        //Very important to add below code to handle last previous interval# W" n# d( v. Z* k* D
        if(previous != null){" q, R, t' n2 T/ G
            results.add(previous);
" k1 ?5 S- W( L. f; w        }
9 [: E* t4 P0 }        return results;' B; F- j. P3 ?' L
}

2. After step-1, for every new interval, it is a insert interval scenario (data is already sorted in step-1)

public List<Interval> insertAndMerge(List<Interval> input, Interval target){
) D9 g8 C: a2 R
5 ]  j; g; x- U# r6 ~        //handle single element cases here
* s/ g) h8 L) ?' F1 O" F        if(input.size()==0){- k# s8 N* a5 X( j7 S1 m/ c8 x
            return null;: r  x6 i" ~! M- @4 h
        }else if(input.get(0).start>target.end || input.get(input.size()-1).end < target.start){ //no overlap
" T2 O& v% _7 j  `3 J( A$ j5 b                input.add(target);4 I4 P% j; G  Y* Q$ N/ g' E- T
        }else{. ~* W' y' K" w  |5 f8 a5 Z
            int result = insertAndMerge2(input, 0, input.size() - 1, target);. t2 I- Y7 s$ ?
            if(result == -1){9 N. n( k0 j, `0 ?2 @$ D9 a9 H: Q
                input.add(target);
) X$ h2 B: \3 b5 [0 U            }
% Y( ~8 Z! Q0 y7 T& h8 H- a        }9 o. }, T2 ]) d8 o& M+ n  f
        return input;" B" v. `9 q3 I9 @( x* x
    }

回复 支持 反对

使用道具 举报

1141

主题

171

精华

3511

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

We can use the Interval Data structure or segment tree data structure for this Problem....

回复 支持 反对

使用道具 举报

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

本版积分规则

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