找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

[Amazon] 亚麻SDE-2面经

[复制链接]

1129

主题

177

精华

3511

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

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

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

x
本帖最后由 Sophia 于 1-31-2017 12:38 PM 编辑 8 D' w5 q: [$ L: _- s9 d

, n* |4 S1 r  D+ z4 @Give 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.4 g: |! C" Q$ W& K  d8 ?- o$ r/ p
+ ~  O; R0 O* \) w2 e0 z
Eg. a 5 MB file receives delete requests for offsets (1, 100), (250, 550),(1000, 1200), (400, 600), (800, 900), (1100, 1150)) H/ ]3 E' I& K( m0 V  R' k
6 [- m4 `2 L, L/ D1 a& L/ G
Effective delete requests - (1, 100) , (250, 600), (800, 900), (1000, 1200)
" r; f/ s8 J+ O
7 [. U, Z- ^! R) A! ^The 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.
6 @7 u" }  |8 m, n" B" m- w( b* d" i( f0 O  c) @5 [7 _. T1 `# m  B) D
What 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)}

1194

主题

191

精华

3785

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3785
发表于 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. , T3 U4 @' X( F( R: \, A I6 X
, k: L" s( W3 S* U1 u# i# d
My below code is written using ArrayList and I am creating a result list every time when insert request comes which is not optimal. , l: W9 h* v/ W9 l5 H
; y/ [: P& K o
Previously:$ s0 x; O; {0 h6 D
1 J, c4 K5 }- Q1 z+ n
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.; e5 n. D N; e/ @3 l5 Y9 T A
* n0 ^, `: r4 P3 b: U8 F
Possibility-2 : If the problem is to assume one interval comes at a time as input, then it is straight forward insert interval case.6 I r8 M* O4 J& b- Y
' W0 `( H7 M4 L: j" s! Z) p
Java Solution: 4 W7 M. `6 |: ~4 u. P3 Q
: b/ d8 ]3 j: `# I6 h. z& R/ a/ W
Interval object can be stored as below.

class Interval{
9 a$ w% T: K8 M, e5 ^" O" }+ S# l	int start;
7 q* r7 |" t; ^- P7 k6 M) S/ n  O	int end;# n, t( Y" U% E+ T/ T. }+ _
	public Interval(int start, int end){
+ y# v" e3 v. n5 d		this.start = start;+ K% a, X+ _' D4 D
		this.end = end;
+ f/ Q) e# P4 \& _! }* `0 w! j	}: B/ i8 n) g. g# Y, _1 b
}

Key points: , B9 P3 r2 l% n7 z" `; B/ f0 B
1. As the question is not clear, if the intervals are sorted or not incase of more intervals as a preprocessing step. ; D7 J) w! L6 l# i& O- S) `
We can take initial List of initial set of inputs and sort them and merge them and keep it ready.1 {4 R3 U* f9 D9 E0 _5 G
3 I7 L7 m/ I" @" |% H
This can be a preprocessor step.& Q& k7 I8 R0 C! d7 l$ U& o$ T- O
4 k& W1 x3 B: m$ }
Merge (preprocess step) can be like below

public List<Interval> merge(List<Interval> input){+ y/ q7 ~, u$ g4 I  E
	List<Interval> results = new ArrayList<Interval>();
7 `5 y4 d4 l- T" O3 D0 P        //sort the collection$ }# E& x0 j$ o7 f7 |
	Collections.sort(input,(i,j) -> (i.start = j.start ? (i.end.compareTo(j.end)) : i.start.compareTo(j.start) );
; K( k# Y# a% ~$ Y- m5 {( f, z" p( j! R% E' ?0 K
	//Loop through sorted input and merge2 r5 G) R6 o; _& q" A9 A. p
	Interval previous = null;* ~- j0 ]3 r1 c, h& g1 q
        for(Interval curr: input){
- H% D/ H) J/ ~& [" k4 b3 g9 v            if(previous == null || previous.end < curr.start){ //non-overlap case
6 H& y: B9 e9 `; R7 y                if(previous !=null){
0 o7 @8 }! K& R& d1 B/ B                    results.add(previous);
9 e$ z; x# M' g( H2 m3 g# ~$ |                }
/ U. k" o1 d$ u" k+ u5 ^                previous = new Interval(curr.start, curr.end);4 S; e, j0 ^% q% _7 W# z
            }else{- i4 p* f" L' v% e# T
                previous.start = Math.min(previous.start, curr.start);. z$ S6 O2 d1 v
                previous.end = Math.max(previous.end, curr.end);$ U! y+ O( T+ h( y
            }( F% q) X& Z! G# t8 ?
        }, [* E; ^0 X! s2 a& ]
        //Very important to add below code to handle last previous interval# J' n, R! `* k( x$ f5 S
        if(previous != null){. ^5 R6 H3 e3 @8 G8 \+ r) C4 V5 J
            results.add(previous);
+ M6 @0 R8 E" q1 F        }4 q0 o% F: ]+ ?: u8 P
        return results;
- [* H- e8 Z6 Q# f3 K9 u& }) l6 y; i}

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){
7 R  p$ d% t- q3 b: |
& Q; z% D  F1 t, g8 V3 _        //handle single element cases here
3 d" l6 ^% t0 `. K1 h5 D& F        if(input.size()==0){. o+ H8 B2 J1 ^( V& v
            return null;" s2 \, O2 n4 p# @1 Y3 ?
        }else if(input.get(0).start>target.end || input.get(input.size()-1).end < target.start){ //no overlap
) w8 `* F; T9 r$ [4 A  F! B; j1 }2 F                input.add(target);7 L% ?% b) ^; I2 N
        }else{
6 I3 L2 r$ }+ I" S& v+ S+ r            int result = insertAndMerge2(input, 0, input.size() - 1, target);
; S+ F( J8 m, U+ M            if(result == -1){0 H. R7 E. [/ _' x
                input.add(target);" T& V+ e7 T- a5 s
            }5 E6 K0 K2 I2 y' h
        }  o% Z& b# y$ }8 W
        return input;8 Q* v9 O0 L5 _$ N% O, R
    }

1153

主题

172

精华

3562

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

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

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

本版积分规则

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