找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 6415|回复: 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 编辑
& j" W7 g9 Z: b  L
8 |5 R/ N, S+ o; q+ q! N9 g( _- b; e2 {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.. }! g6 Z; _) `

; |  W) F2 d; S6 n+ ~. g! D2 `Eg. a 5 MB file receives delete requests for offsets (1, 100), (250, 550),(1000, 1200), (400, 600), (800, 900), (1100, 1150)$ ~9 {( c: B2 q  y8 ?8 j

: F# N/ B0 m9 q4 ~( _# hEffective delete requests - (1, 100) , (250, 600), (800, 900), (1000, 1200)
& e# h  n- F# u7 T0 r2 H& h
  u, {: g& g, h. qThe 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." O3 i3 v# V+ n; }
& K3 p  R$ A9 |. {% T
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. 0 e, {/ v- I7 J4 o) j
" M. ~( l3 S6 o8 O: \ @
My below code is written using ArrayList and I am creating a result list every time when insert request comes which is not optimal. " j5 f- \3 A4 ^3 L A1 k0 b
6 @' W( v' Z4 b. I5 n
Previously: 4 C; D( G; ]* m- R+ `2 _+ v
. J3 e& N; W9 H" C
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. . j/ A! P7 r+ i+ F
: Z9 w ?/ [# r1 n* {6 K% S4 u
Possibility-2 : If the problem is to assume one interval comes at a time as input, then it is straight forward insert interval case. * F F+ _; y) v/ H9 e
; m0 o* Y- t. q# C- B
Java Solution: ) O: H- Z/ n' P' Y& O5 C% K# @
6 p9 V: `0 g+ L }
Interval object can be stored as below.

class Interval{% l5 O9 p% d  s8 `8 `. ~
	int start;
! P, r) L: S4 }5 q- ^( J+ y	int end;
( O3 n- G: I% E2 T	public Interval(int start, int end){6 b2 l. \4 `8 Y- d' G
		this.start = start;9 e# a- l% Q8 z6 G( q& |& Z6 _
		this.end = end;8 Y- S" Z; r( h: H8 F8 a
	}
) u1 i7 ]$ R. K5 r}

Key points: , r& i/ W s' {# k4 `) n
1. As the question is not clear, if the intervals are sorted or not incase of more intervals as a preprocessing step.% }& c7 q/ m+ Z/ L' c
We can take initial List of initial set of inputs and sort them and merge them and keep it ready.5 j, y- G! ?' N0 ~9 ^2 `4 J2 K b
) F; V; A q* k1 X. u2 l9 \" a
This can be a preprocessor step. * T) Q- k ~; ?1 i
! D: u3 A/ G {2 y4 b* R1 G" I
Merge (preprocess step) can be like below

public List<Interval> merge(List<Interval> input){
8 l# L9 j. i& s$ @	List<Interval> results = new ArrayList<Interval>();4 k% M1 M. Q# p4 E. t, z: [& \# K$ ~7 w- ?
        //sort the collection
* T. c7 {5 H. l' b. k	Collections.sort(input,(i,j) -> (i.start = j.start ? (i.end.compareTo(j.end)) : i.start.compareTo(j.start) );5 d5 o& P5 g  I+ D- H

1 q% z5 b# ^; \8 _	//Loop through sorted input and merge
# D, v% E8 F1 m5 j$ b8 h	Interval previous = null;
$ q  u6 D1 U+ a  i9 x. G: n        for(Interval curr: input){
) c4 x/ g. w+ u# ~- Z$ G            if(previous == null || previous.end < curr.start){ //non-overlap case
* |- _3 d- N. W/ H6 B                if(previous !=null){
1 l& I( V% P  w, g6 L7 F8 j. F+ c' U                    results.add(previous);+ N& k) C9 W  ~, o
                }5 l% T& J. H! n
                previous = new Interval(curr.start, curr.end);
% f+ I7 ~% A, q7 {            }else{
, p. c7 H" Y1 Q* }7 c) M                previous.start = Math.min(previous.start, curr.start);. Y! r, \: K6 c( J4 U- j% r; X
                previous.end = Math.max(previous.end, curr.end);( `0 P$ Y8 R- P9 [3 I" p
            }
- x, H4 p# I# _2 y& i1 m8 D) Y% Z        }
- U" q- j& {5 S3 E        //Very important to add below code to handle last previous interval7 Z1 Y- D; t0 l! ^+ [& h6 }
        if(previous != null){
2 U" B8 X3 z2 Q) P            results.add(previous);
. G  Q2 s- V$ D5 c6 C. I        }0 V# L+ i2 v" ?4 G9 R; g& d' [
        return results;
5 i; Q, ~9 D6 d  ?2 ]}

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){
; I- H- ^$ y" g/ I
- B, D7 g8 V- t( ?' X3 Q& J( J        //handle single element cases here
8 ~( J9 j0 @0 C0 L        if(input.size()==0){
0 h4 K. M' S! c- j: h2 m8 g            return null;  ]4 |; z  {- F, T2 Q& k" l$ X2 s/ w
        }else if(input.get(0).start>target.end || input.get(input.size()-1).end < target.start){ //no overlap  F7 m3 }6 D; t3 K0 V4 @
                input.add(target);
  k% q$ ], S) @% u( H8 k        }else{! \! I5 B: R' F( E. f4 W
            int result = insertAndMerge2(input, 0, input.size() - 1, target);0 B+ V1 c. f, ~6 R  v4 g
            if(result == -1){
" i  F. G) `  j. |( x* c7 j0 N                input.add(target);
0 C0 H$ O7 k% A8 M, |# |1 F" l            }! r) H# l7 A! d7 F$ ]
        }8 {6 b0 E) U# ^$ g  A
        return input;
. E+ ^2 }& _4 F7 e( V; 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....

回复 支持 反对

使用道具 举报

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

本版积分规则

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