找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 6732|回复: 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 编辑
% V7 n7 {: O* R% f
$ L2 D3 \$ K/ _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.. _# \8 E( h, R# V2 o7 r% V

$ _# Y. m! Z& A# p0 g/ j6 y2 C+ JEg. a 5 MB file receives delete requests for offsets (1, 100), (250, 550),(1000, 1200), (400, 600), (800, 900), (1100, 1150)
- _: T% u% v' k1 ^- Q7 N
! W: Z2 c5 N* N, h8 n' {% bEffective delete requests - (1, 100) , (250, 600), (800, 900), (1000, 1200)
( |1 [) _2 ?" Z" c1 f9 `4 I  m
; |  J- }$ h  S. {5 Q1 W( J8 lThe 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.
( V% K5 Y4 s" ~7 e) p. U+ i4 k" @9 p9 L) q* 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)}

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. 4 h$ k! A& _; M6 m7 c% a; f
( C) S! m2 p* j a6 C9 A
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 M8 \1 @! z
5 I( }/ k7 P3 [! u: g0 \
Previously: ! i* ?1 d5 `0 Y3 l
1 c) f# q9 i# G5 e
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.$ P. i- \* o( S, U% f9 Q
5 R/ v7 {6 d% q) g
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 d: J, T* W8 h4 s7 `% q: `
G& x) f7 C" @- O3 ?" w e
Java Solution:* f$ b+ n1 @9 h2 j" f0 O
8 ?4 ]# S- e, y# L8 e
Interval object can be stored as below.

class Interval{
5 m+ ?( B5 E' \3 a	int start;4 Z& Q3 ?. ?4 v1 c
	int end;
1 l+ E/ K( T) g; X) h8 S	public Interval(int start, int end){* i$ x" x1 a' C/ F. W3 p
		this.start = start;9 P2 K/ l1 m3 F* J( l4 |5 C
		this.end = end;( F/ p( l( I+ \5 d1 o
	}, ^' o6 k; Q" G5 Z2 }" m9 Y' x% n
}

Key points:) w, P' H& U* Y, a2 G [
1. As the question is not clear, if the intervals are sorted or not incase of more intervals as a preprocessing step.3 y3 E: m& D3 W |6 {5 H% J; K6 E
We can take initial List of initial set of inputs and sort them and merge them and keep it ready. 3 p. m1 P3 \( R0 W" f# T; j4 U3 |7 G7 B9 l
/ L9 m3 c5 m* h9 d$ r6 }
This can be a preprocessor step. ! j6 U" G4 z$ k( m
0 i. [# L7 W& B! y& g& h6 S
Merge (preprocess step) can be like below

public List<Interval> merge(List<Interval> input){6 ?: b* t: ~1 p- a( ]& d# b
	List<Interval> results = new ArrayList<Interval>();
9 x- `8 f. y8 B/ E8 g! `/ x        //sort the collection+ q( _$ \4 I' O7 d7 F( c
	Collections.sort(input,(i,j) -> (i.start = j.start ? (i.end.compareTo(j.end)) : i.start.compareTo(j.start) );7 o. r0 t6 T) d4 W0 Q! u
5 D" R/ J! _" `7 b9 F
	//Loop through sorted input and merge
7 |2 w! h7 @+ ]) s% Y7 D	Interval previous = null;4 x* q& F- H  }5 r9 D8 u
        for(Interval curr: input){  S6 Y8 o1 z7 f, `) h8 e) ]. X
            if(previous == null || previous.end < curr.start){ //non-overlap case
% ~+ s& Q' x. R, h                if(previous !=null){
. x  X3 \6 A, [5 X5 P                    results.add(previous);# O2 @. m0 ]8 e# ^/ k
                }
! u6 ?: G' [2 `! a( Q, X6 `                previous = new Interval(curr.start, curr.end);  s. V3 k+ |0 M5 o
            }else{' {3 c& A3 R4 w
                previous.start = Math.min(previous.start, curr.start);1 M, i, B& k2 U9 n
                previous.end = Math.max(previous.end, curr.end);
7 u* @' z' K, ~$ k6 N) Z# i! z            }4 L+ X  R" ?+ T5 Y7 F! ?$ W: C
        }
; E# K; A$ g! M9 k$ }# u        //Very important to add below code to handle last previous interval. a; _% n& E. W% g2 C+ }5 m6 ^
        if(previous != null){
# a& |3 V# X" e9 [' Q0 x: U! y            results.add(previous);% S/ o( \0 t( v7 Y6 D4 n  W, M
        }; C1 Z5 x% ?* i0 i
        return results;8 S# S5 @7 ?: R- Z) `: j: A
}

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){; ~: O  p0 u: u( c

8 q" b) k/ [5 C) U+ ]# E        //handle single element cases here
1 e  s5 u" B, e$ _1 v. s2 M        if(input.size()==0){$ R1 ^! Q% f9 ^. c2 U% w8 o8 F
            return null;$ W: ?, z! a) ?3 w6 T# J
        }else if(input.get(0).start>target.end || input.get(input.size()-1).end < target.start){ //no overlap
% Z" U7 k8 r8 B" W                input.add(target);( p: a2 l( p3 l+ E. r
        }else{
* i# K6 N7 r/ j7 F            int result = insertAndMerge2(input, 0, input.size() - 1, target);
0 L& v0 W6 H" d            if(result == -1){
$ t! I$ a) s7 b) X8 I                input.add(target);3 ?; n# |% f# a7 \
            }  ?) f* L" \( [
        }
6 ^8 r: X8 G- Y. Q3 W2 N! m        return input;. j1 [3 M9 |  X- k
    }

回复 支持 反对

使用道具 举报

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

回复 支持 反对

使用道具 举报

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

本版积分规则

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