找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

[Amazon] 亚麻SDE-2面经

[复制链接]

1128

主题

177

精华

3509

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

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

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

x
本帖最后由 Sophia 于 1-31-2017 12:38 PM 编辑
. P9 `: ?# {# R
+ |( n0 Q" v1 T* q5 aGive 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.
* U, A- ?& o9 j+ X/ R7 K# \
( |9 n7 I7 k3 ?Eg. a 5 MB file receives delete requests for offsets (1, 100), (250, 550),(1000, 1200), (400, 600), (800, 900), (1100, 1150)- s: p. ~4 _! d" ^  x' w

8 v8 A& \  |: K% A' n1 c* J) C& eEffective delete requests - (1, 100) , (250, 600), (800, 900), (1000, 1200)/ ]1 N: s% k; N4 l3 N# T6 @# B

! [0 q( C+ b8 _: Q! p. P& C* yThe 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.' U7 M/ D1 }' T+ f$ f

: F& g1 u" [, H; G4 ~- yWhat 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. ( Z( l, j/ h6 W1 ]. x1 I3 t
+ e% }( ^2 t8 g1 x
My below code is written using ArrayList and I am creating a result list every time when insert request comes which is not optimal. 5 y/ p9 R# Q1 I
, L1 n8 O. o- @; C
Previously:, e1 r7 C6 _& t2 C! `. I
, a: O- \* H/ a+ H6 ?8 O5 U
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.3 e" ?. P) A2 S+ M C) K
% d, A8 C( ?3 f7 {1 m4 @' h
Possibility-2 : If the problem is to assume one interval comes at a time as input, then it is straight forward insert interval case. + k( ^3 P4 L8 C* \) T( A8 ~
- @$ M: T3 Y" k7 j) L
Java Solution:2 g! z2 N' v6 ^, E
( g: V. n3 g( c( o& }
Interval object can be stored as below.

class Interval{2 y- E6 G% Z( G- A0 C
	int start;( U; g2 ]9 S9 t. A/ S% f9 U1 X: L
	int end;6 M! k5 H! }' a' \3 ^
	public Interval(int start, int end){( s+ i# ?9 o7 |0 \+ Y' [, y1 e& O' V
		this.start = start;
9 P5 b3 L; _: e		this.end = end;+ _1 U7 k. g. ^1 F/ [' w
	}) i/ _7 O, e9 \
}

Key points: * d: Y# g$ X0 R" ]! T; x
1. As the question is not clear, if the intervals are sorted or not incase of more intervals as a preprocessing step.* P0 U8 D9 V6 p8 o$ D$ L t! y
We can take initial List of initial set of inputs and sort them and merge them and keep it ready. 2 o8 c5 o2 i2 R) L$ N2 n {& z9 h
- y) a2 U, W1 c0 s
This can be a preprocessor step.8 T) Z% e! E" e
% R2 }+ v3 l" P+ D- X2 B2 [1 m
Merge (preprocess step) can be like below

public List<Interval> merge(List<Interval> input){
; Z; N: `) b+ s# Z' H9 E" j& c5 N	List<Interval> results = new ArrayList<Interval>();$ ^( |$ F# w% M/ F
        //sort the collection, {' z2 H, G5 W5 D9 Q9 b- j4 t+ d
	Collections.sort(input,(i,j) -> (i.start = j.start ? (i.end.compareTo(j.end)) : i.start.compareTo(j.start) );& x6 G3 Y. l9 f! ]
0 Y7 u* M) [6 h$ e  w2 E) t
	//Loop through sorted input and merge
7 e: s/ u" D$ ~9 n" X	Interval previous = null;
( o0 x( F2 S- P! i  W& ]8 Y6 O        for(Interval curr: input){8 k: T6 g6 L9 n: B7 O2 I8 i  l% O. ^
            if(previous == null || previous.end < curr.start){ //non-overlap case
" f$ }+ J8 b( Y" U- y                if(previous !=null){
* J6 }/ N; d3 y0 R9 T, p3 k% M                    results.add(previous);. {/ j( j4 k0 w
                }8 y0 u% u4 ^$ b* V' U- {7 I
                previous = new Interval(curr.start, curr.end);# ~; J  D0 Z( M5 g; q9 ~
            }else{
% I; b& w  R/ ^                previous.start = Math.min(previous.start, curr.start);
9 B7 r( o1 g: ?/ v1 ?$ V# b                previous.end = Math.max(previous.end, curr.end);
( z2 S1 v' N% e. b' r- ?' B            }* U4 o! @7 a9 J/ o0 p
        }
, Q, e: F- f& ^4 ^' x  l        //Very important to add below code to handle last previous interval& g* e7 ^4 A( j
        if(previous != null){
0 }7 W5 {6 {3 M3 m8 L0 j  ?* ~# m            results.add(previous);
0 N; @# C: j0 f* r' [* ~1 g        }
, ~0 E. K3 ]5 ~' x, p2 `4 L1 x        return results;8 D8 J  a' j6 j; L& s5 K2 C) n! Y, 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){
1 ~8 ^! p$ P: Q3 c" q% y8 T) R+ N9 p/ L! _/ `5 M  T
        //handle single element cases here/ I; x$ l5 O4 C, Z  w( z8 o2 a
        if(input.size()==0){6 F$ N. F) S: p1 o2 r/ n9 v
            return null;1 O; P8 i( R/ Z4 |5 ?5 Z4 R
        }else if(input.get(0).start>target.end || input.get(input.size()-1).end < target.start){ //no overlap
6 Y/ V. k# h& a7 D+ s; K# M( k                input.add(target);$ I) B: X2 ?- b8 g: P* ?1 H
        }else{
: v0 @% I2 A$ [% T. x- A$ f3 f            int result = insertAndMerge2(input, 0, input.size() - 1, target);
& B  A$ B% T& w% ^6 c- y            if(result == -1){
; y5 l, [: r, y+ |* `0 R                input.add(target);
; u' \9 J' b+ B  A/ d# P5 }; [! k; H            }
* A9 p  X/ x: I, E( X8 a+ {        }
; O. y1 U* b6 b* b; m9 J# X        return input;/ a1 e8 Q- `8 t% @
    }

回复 支持 反对

使用道具 举报

1152

主题

172

精华

3560

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

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

回复 支持 反对

使用道具 举报

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

本版积分规则

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