找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 7098|回复: 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 编辑
0 e! s" I, x7 {( E, c
* _- y, `0 P: z5 fGive 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.
- `# l2 R8 I, k7 J% m7 l8 c$ ]6 t' u
4 c. P" p; i; b/ LEg. a 5 MB file receives delete requests for offsets (1, 100), (250, 550),(1000, 1200), (400, 600), (800, 900), (1100, 1150)4 d: X6 ^* B9 n7 l4 Z5 m/ G
, J( T9 H/ u2 J! t
Effective delete requests - (1, 100) , (250, 600), (800, 900), (1000, 1200); s+ J: n8 N# z! E2 L. l: b

) `( T5 A. {. z4 W+ y& oThe 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.
! S0 u( @& i* D, o9 y' [$ Y' d9 C0 m! Q" I9 }
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. , S2 a. D1 Z6 i8 Z# A% W+ L
' M* i$ M: d7 a: m- W3 z* 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. 4 [+ \5 |* ]( B1 U. D
r- ^! W4 x5 H1 W# h
Previously:5 B V& u/ K) h* R6 t, ~2 J
% d& f4 G4 y' B& L; \6 M
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.+ d" X- B3 `0 g' D2 H2 V7 ?* V8 c
/ x5 g: }0 d/ k# |; H4 \
Possibility-2 : If the problem is to assume one interval comes at a time as input, then it is straight forward insert interval case. ) w& h( J' ?1 r+ s- N- W
W* A( D/ O7 {& L; {) }
Java Solution: 4 @. \8 U% Z3 w( Q% g. v" e6 ?* N( L
' h- I: b" x, C9 a7 I T$ \+ _
Interval object can be stored as below.

class Interval{
! q: g$ S0 }! C# W; Z	int start;
  |% W% H; ?* j	int end;
! I: c6 c$ z6 [, P4 x; g& E0 F	public Interval(int start, int end){8 {2 B2 q1 F0 h; I) q/ w% V
		this.start = start;
. B" r- M% @8 i9 B/ b' J- x: N, ~		this.end = end;7 _7 }( s- w3 a8 C2 _3 p3 O0 a8 [
	}$ d" t2 y. f" y0 Q, H! j* |+ W
}

Key points:/ c! n6 v. N/ r% A- m3 _, K( O
1. As the question is not clear, if the intervals are sorted or not incase of more intervals as a preprocessing step. 4 A: o' Q6 T* @/ I4 V
We can take initial List of initial set of inputs and sort them and merge them and keep it ready. 8 ^# `1 z& Y2 D8 n( A# J) _% q
5 X8 e3 C+ G' K3 s
This can be a preprocessor step.* I4 B4 |1 X- b! @9 q
) z' P4 K4 Y- L3 g( A `
Merge (preprocess step) can be like below

public List<Interval> merge(List<Interval> input){$ B2 T. d3 I; m+ t' E
	List<Interval> results = new ArrayList<Interval>();
& I' j2 X  i6 M0 ~0 w        //sort the collection
6 b8 Z( t$ z6 W3 |4 m: ]2 ~: P7 P	Collections.sort(input,(i,j) -> (i.start = j.start ? (i.end.compareTo(j.end)) : i.start.compareTo(j.start) );3 b8 d# n5 W$ V8 f" y7 [
) ]# g/ \) ?7 ?2 _% m
	//Loop through sorted input and merge
$ {9 c0 ?2 f% U2 V. l* W	Interval previous = null;$ t+ U8 \- O) m
        for(Interval curr: input){
& A& M+ N& _0 V: U# z            if(previous == null || previous.end < curr.start){ //non-overlap case
# g# x+ l% ?7 l$ t9 K                if(previous !=null){
9 x. A1 A& c4 C( z4 l                    results.add(previous);  p' P0 |/ V2 h* O7 ]9 n& ^
                }
& I6 |( B. i! V: |                previous = new Interval(curr.start, curr.end);8 Q1 }: M0 R7 Y1 Z  Z! T$ t3 x$ F
            }else{/ K8 `) e8 @5 Y, W5 a; R7 K5 }( D
                previous.start = Math.min(previous.start, curr.start);& o8 F4 f4 y; J+ O5 r: u
                previous.end = Math.max(previous.end, curr.end);- q/ k( ]5 X  Q7 ]
            }4 D4 p! a* `  [7 X9 b' x) O' k1 [
        }
2 \  l- s' L& I" l+ S        //Very important to add below code to handle last previous interval; V/ h2 a+ ?7 S& v7 w* k; N
        if(previous != null){
9 M, o% h& K+ E& ]8 h            results.add(previous);8 o+ I" {) E2 U1 ~1 r; b
        }
, c: h8 z" Z3 g* E        return results;$ k3 ~2 A% F$ e! {9 b  e3 ~! J& v; g
}

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){' |8 }6 }/ g/ G$ W
# R7 n8 U4 {; Q2 H9 h& `  s
        //handle single element cases here3 P6 H+ S2 q% r
        if(input.size()==0){
2 s7 w! i) X1 n3 i            return null;( g, }( L9 x6 ~
        }else if(input.get(0).start>target.end || input.get(input.size()-1).end < target.start){ //no overlap9 E7 s% @! ~6 a$ y
                input.add(target);
  m& z0 W% |2 M5 E. a+ Q& f        }else{. {* }: A" X9 P  b$ L0 i
            int result = insertAndMerge2(input, 0, input.size() - 1, target);0 E! e2 w3 c" y% H" r  J
            if(result == -1){7 |" m4 N- B" `! ?, e+ ]- I  b6 B
                input.add(target);9 f" U8 O; S2 _. B; a
            }
4 K" a$ A3 I* N4 U% q        }& R, w/ s+ i* a# x0 V& ^; E
        return input;5 O4 a% J9 Y+ U# M- i
    }

回复 支持 反对

使用道具 举报

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....

回复 支持 反对

使用道具 举报

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

本版积分规则

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