找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

[Amazon] 亚麻SDE-2面经

[复制链接]

1127

主题

177

精华

3507

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

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

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

x
本帖最后由 Sophia 于 1-31-2017 12:38 PM 编辑 8 M$ b; A" A. @' `
% \: u8 w8 m5 J! Y) ]
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.
6 m8 M2 r$ B5 |/ O5 o. R  Y) M" J2 Z8 n4 d& H2 e; I
Eg. a 5 MB file receives delete requests for offsets (1, 100), (250, 550),(1000, 1200), (400, 600), (800, 900), (1100, 1150)
% O) j& O9 m! {+ z
4 W$ d! H# s# S" v6 A; pEffective delete requests - (1, 100) , (250, 600), (800, 900), (1000, 1200)
! P" C' d4 b/ W1 V0 T2 e6 _
* H1 }# ?% i1 s. I6 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." b8 r2 D) W* Y' D+ x- o& t

, Z- ]+ `) |1 w5 j# UWhat 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)}

1191

主题

191

精华

3779

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3779
发表于 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 b; `/ c( E' ^, {4 C0 x
6 x# M1 S6 I. Y# X# Z6 G
My below code is written using ArrayList and I am creating a result list every time when insert request comes which is not optimal. ; _, [, \, X# h8 P4 R% b
+ l. B$ d4 u( M# S1 ]& [) b' r9 ?1 W& r
Previously: 5 I. a% X1 J5 x, c% `: @
7 ]5 s X" V# Z+ C+ u, h% 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. 7 v W! q8 ]& H, V/ t' m
% C+ ^) w) Z6 W8 P
Possibility-2 : If the problem is to assume one interval comes at a time as input, then it is straight forward insert interval case.- }9 L3 c+ z2 I
3 d. O6 P! e, v% P' C, {* o \# @7 p$ O
Java Solution: 3 a3 U9 [4 f3 R: E
9 G1 i* d7 Y: x5 H
Interval object can be stored as below.

class Interval{
  I8 O5 I* E1 }8 z4 d: Y4 O& i	int start;
# q1 X; M3 ]5 `! _& X1 t	int end;
" w8 C; ~& p/ [2 r2 E( u2 t	public Interval(int start, int end){) J- ^9 |3 o# d' ?/ X$ W
		this.start = start;6 G. a* U. ^# t! L0 N
		this.end = end;
, l/ b3 K" @$ @2 I- l( m	}9 o4 H- V7 s: M
}

Key points: $ S9 k2 v( X9 L( o5 Z! p
1. As the question is not clear, if the intervals are sorted or not incase of more intervals as a preprocessing step.' k/ A% ?+ U) {: c |: o- S& }* o
We can take initial List of initial set of inputs and sort them and merge them and keep it ready. ( B8 s5 |' x9 N- u: x3 N8 w3 n
: G% ?+ T* o \4 F- R$ ?! f; h
This can be a preprocessor step. - \: e) O( Q( g1 O
5 q( ?; {! o6 g( l; f
Merge (preprocess step) can be like below

public List<Interval> merge(List<Interval> input){* I) I2 x* m+ z3 O! K+ {2 m
	List<Interval> results = new ArrayList<Interval>();
" i' {5 S$ ?. `# j% H  A* g        //sort the collection# ~: R5 _0 Y4 n- A5 F6 i
	Collections.sort(input,(i,j) -> (i.start = j.start ? (i.end.compareTo(j.end)) : i.start.compareTo(j.start) );( P  ^9 }. A5 G  Y

- V: b# Q! X) G9 M5 S- h	//Loop through sorted input and merge8 Q( n8 W7 P3 m$ ~0 R* g
	Interval previous = null;8 f6 H) x" Y& ^9 `* M! D' i% j, V
        for(Interval curr: input){
$ \4 v) R8 {( v/ h            if(previous == null || previous.end < curr.start){ //non-overlap case
# _2 S  T4 B" w' j. y                if(previous !=null){4 [: L( b5 A9 _( l
                    results.add(previous);  D5 D3 x( a% J; l& X# `
                }- ~* N/ [, V% g/ N& d
                previous = new Interval(curr.start, curr.end);
8 X3 M9 |% I1 }" I( O- O' V            }else{1 R/ {+ ~7 Q" r7 r* c* ]! }9 k6 K
                previous.start = Math.min(previous.start, curr.start);
( U. ]# Y! |- c                previous.end = Math.max(previous.end, curr.end);
% d5 A0 A. G& U7 j" c            }7 q1 k' q! _" v; ~
        }* |5 r8 A3 _- J
        //Very important to add below code to handle last previous interval
$ g  |6 G3 r% o( N+ G) L8 i        if(previous != null){8 [5 j! E) o7 D, ], k
            results.add(previous);
/ u' q$ B; y1 p! S        }2 O1 \) f2 S+ \" W+ ?
        return results;
- y4 ~/ k/ C# r0 ^+ R}

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){
, j; |& s% Z1 J& U0 z1 Z. h8 [
# G+ Y( ~3 t# ^) \3 Z        //handle single element cases here: B7 P- U* h7 `# I
        if(input.size()==0){
, G. W! S3 L, T7 H( z  k            return null;/ ^4 H. Z$ o! c7 @8 s& G
        }else if(input.get(0).start>target.end || input.get(input.size()-1).end < target.start){ //no overlap
6 I' M6 P. k: X                input.add(target);
. G) J# L, F% m- C" e        }else{; S# \3 L( Y3 Q) O% G
            int result = insertAndMerge2(input, 0, input.size() - 1, target);( x0 v+ c0 Y  P% ]
            if(result == -1){
- Y  h  {# H+ F6 k) f                input.add(target);
3 p0 L. ?7 C! @0 A5 E0 \            }! h( B7 Q3 p2 B9 C' I  N5 a
        }
" @# B+ _. q! B7 r2 U        return input;
  c) ?5 x, ~: M; m0 Q& u    }

回复 支持 反对

使用道具 举报

1149

主题

172

精华

3554

积分

神级会员

Rank: 7Rank: 7Rank: 7

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

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

回复 支持 反对

使用道具 举报

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

本版积分规则

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