找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

[Amazon] 亚麻SDE-2面经

[复制链接]

1120

主题

177

精华

3493

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

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

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

x
本帖最后由 Sophia 于 1-31-2017 12:38 PM 编辑 ' `# m! M) o. _/ ?! Q# Y% |

" ~4 \: r3 C# Z1 i- B, ^) ]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.
. K9 S" X' @7 L" _8 C- a$ V/ [/ E. q/ n. }8 }
Eg. a 5 MB file receives delete requests for offsets (1, 100), (250, 550),(1000, 1200), (400, 600), (800, 900), (1100, 1150)' Q8 r2 |+ l) G2 @) [* R

' w2 ~, O; U9 `5 c* YEffective delete requests - (1, 100) , (250, 600), (800, 900), (1000, 1200)% ]6 R& G7 x0 o! p  h. x

' f* o$ {) f' Y! ?# h5 `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.# ]+ s, i! J& G& D5 q2 _5 Q# T
  D* B& U, P, `
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)}

1184

主题

190

精华

3750

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3750
发表于 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. & p p% i# V4 B$ r& J2 i6 G8 Z* a
) E/ A" s, q; x x/ t
My below code is written using ArrayList and I am creating a result list every time when insert request comes which is not optimal. . u' D: X' ? g- f6 N: E
; a: l& ^5 G, T4 v7 U
Previously: 5 G0 r: X, I/ h( Z
8 N4 g) B6 y! Z/ z8 o2 H6 d
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. # t- ?+ j& i$ W8 b b$ u7 V
" z' y$ M6 C# E' r2 P ?- i
Possibility-2 : If the problem is to assume one interval comes at a time as input, then it is straight forward insert interval case. . j3 q! o; s6 S, J! I; k
5 }6 x/ X5 Y1 R& M$ K3 { d! e
Java Solution: + g, K+ V2 K( A( @& d
8 `, G7 K8 G Y
Interval object can be stored as below.

class Interval{' j& [0 Q) V" n9 c3 ^( c
	int start;* j. l0 J* I6 T" g: E! a/ A6 ~
	int end;# I8 o4 t) ]& _2 L- d) M! ^
	public Interval(int start, int end){) {3 I: ]/ i6 U. _& @* ]# h
		this.start = start;
1 m5 ~2 W0 U! r. s1 d		this.end = end;
! ^* q7 K+ o( D8 J1 U' p6 Q! z$ L	}
: S) A) R5 P4 d0 S9 F$ ?}

Key points:7 ]) m0 T. [) M, D5 u; d4 o
1. As the question is not clear, if the intervals are sorted or not incase of more intervals as a preprocessing step.1 \$ K# N: h4 @4 S* z% K
We can take initial List of initial set of inputs and sort them and merge them and keep it ready. $ K- }' l J# n! O/ ?
! j; f& B6 s9 b1 w) A/ h- G
This can be a preprocessor step.: U- l6 D V7 U) O. G K
- y$ [+ q- e; }& I1 Q) O
Merge (preprocess step) can be like below

public List<Interval> merge(List<Interval> input){
1 C% I5 _3 F  E* z2 Y	List<Interval> results = new ArrayList<Interval>();: ?9 v0 b3 ~+ q: `# ^+ v
        //sort the collection
% B' V( c0 [  m- j+ A9 i1 U- m, N	Collections.sort(input,(i,j) -> (i.start = j.start ? (i.end.compareTo(j.end)) : i.start.compareTo(j.start) );2 J4 d0 o0 @. L5 q) Q7 r! y
  S$ Q) a* U2 P- s2 `4 O3 N9 N
	//Loop through sorted input and merge$ D  D/ v, }9 y: j" B  E* Y) C  B
	Interval previous = null;
2 l9 o2 o. G' e& v* x. p8 }5 E4 Q        for(Interval curr: input){
. d9 s/ B, F) c            if(previous == null || previous.end < curr.start){ //non-overlap case
6 }7 W# K' v9 i% q                if(previous !=null){
! N. Z1 r6 ~  k$ M' T( ]  M                    results.add(previous);
) q: Y* n8 L  _6 G+ f                }5 b) c* P; M0 Q, V
                previous = new Interval(curr.start, curr.end);
* m: o6 }, v0 W            }else{9 M/ Z# X0 R/ z% |) ~
                previous.start = Math.min(previous.start, curr.start);! E/ M+ R& A% w( s
                previous.end = Math.max(previous.end, curr.end);
* f% ~' l# l- Q1 d! N2 i+ Z% }2 O            }, J" S3 P7 j6 D- `: \* u; w+ ]
        }" r- \6 ~. ?9 g' o# g
        //Very important to add below code to handle last previous interval
7 f/ B& R# A; D' }5 F        if(previous != null){, x8 }) z4 R7 G/ [4 S
            results.add(previous);
( s5 p2 M9 N, j4 O7 Y3 k        }$ O- v" R- \7 Q# R, ]
        return results;
! z( T5 m6 U( e}

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){/ y3 j4 \( j6 n2 _) ]8 W
* ]  [0 [6 h2 N) L5 T
        //handle single element cases here! c2 ]) H+ i6 G3 a
        if(input.size()==0){0 {) ]: W0 m: E  H6 `7 c
            return null;
& H1 w0 h0 P9 e! X) ?: x- q        }else if(input.get(0).start>target.end || input.get(input.size()-1).end < target.start){ //no overlap4 h; {$ B1 s9 _; X1 U; R
                input.add(target);9 j6 C9 J2 K2 X
        }else{; V. \. @  ?+ G) \7 ?
            int result = insertAndMerge2(input, 0, input.size() - 1, target);
- M% J# w2 B# I) M, g$ ]% B            if(result == -1){
" A$ }) P1 ^. @7 F  k( A3 a                input.add(target);
; w# Q, \/ t% l8 C* ?# z+ ?            }- i, J- {. }3 R( x8 s
        }0 `$ w7 e7 Z6 k. J
        return input;
6 ?) Q# R/ m! ~8 _: M2 I    }

回复 支持 反对

使用道具 举报

1135

主题

171

精华

3495

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

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

回复 支持 反对

使用道具 举报

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

本版积分规则

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