找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 10302|回复: 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 A0 R4 F* n! j0 \* e' o7 d) u( o& a
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.0 m6 |& @/ h( |' S) o
! J* T" f8 e& Z
Eg. a 5 MB file receives delete requests for offsets (1, 100), (250, 550),(1000, 1200), (400, 600), (800, 900), (1100, 1150)
* x- x2 k- o# F0 N: \
! F: @. t2 v. t3 ]- D8 d2 ]Effective delete requests - (1, 100) , (250, 600), (800, 900), (1000, 1200)6 K* ]/ w6 f. ?9 D

  X0 R" O, [# X- p2 CThe 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.
9 {7 {0 k$ o( s$ W4 V# Z/ ]2 R- g/ b8 b3 O6 {! B* A) f
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. - j) ]& B5 M$ V" a Q' s5 g
4 q& H$ P% F Z2 C& l
My below code is written using ArrayList and I am creating a result list every time when insert request comes which is not optimal. 7 q1 A5 {' B6 x4 O+ ]8 i
. q3 f' t0 ` Y+ d
Previously:2 K8 Z3 R" v6 B" N% x2 X
# |# H! O' t. x0 z
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. 8 n* i h; f# ]1 R m3 x
5 i# m' _) `4 k/ w- Y9 V' \$ A0 \( a
Possibility-2 : If the problem is to assume one interval comes at a time as input, then it is straight forward insert interval case. 8 n- F* |, L. S- C
: q& m5 K: W$ [% X8 V
Java Solution:' b2 v9 p) T8 k+ v) x) x2 z6 S6 y
( A7 H" s8 a; Z
Interval object can be stored as below.

class Interval{
/ p+ T5 t0 J$ Q	int start;
! r8 O' T9 q) _: L+ V7 I	int end;
0 @- I0 F/ h$ d7 y* t6 R	public Interval(int start, int end){# G1 K% T) P6 w
		this.start = start;3 ^1 b0 y  p) Q6 P2 Q
		this.end = end;6 m7 m8 O, u! r% o% E
	}
3 r2 C3 `7 h9 U5 e& ~9 H0 K# j}

Key points:! Y9 J2 B# u. w) ~9 m
1. As the question is not clear, if the intervals are sorted or not incase of more intervals as a preprocessing step. : c6 E4 @% H' V1 K: E
We can take initial List of initial set of inputs and sort them and merge them and keep it ready. - K0 G: o1 w9 A# j e0 z
( b% G: _4 L: O7 G
This can be a preprocessor step. * n; O% }# U9 Y5 V! U( H
- `/ Z% T& _' Q+ e* M, H* o) f
Merge (preprocess step) can be like below

public List<Interval> merge(List<Interval> input){
* }3 z2 ~, _$ W; m4 ^! r  r" a! ?	List<Interval> results = new ArrayList<Interval>();
9 }: X! E+ n& W! h3 H, ^* O        //sort the collection6 r- A" |9 ]: x$ r5 I* M* @5 M8 c
	Collections.sort(input,(i,j) -> (i.start = j.start ? (i.end.compareTo(j.end)) : i.start.compareTo(j.start) );
' L9 T! n+ d# }# p" J2 z5 O$ V) V5 |4 d. D3 O. j
	//Loop through sorted input and merge2 A& v1 |7 h7 d8 k( u3 ^5 C. Z
	Interval previous = null;; T. g0 w+ I! u# ?8 v5 u
        for(Interval curr: input){9 P7 Q4 ~6 B2 H7 \$ _  Y: S: H; J
            if(previous == null || previous.end < curr.start){ //non-overlap case7 ?9 t+ T# A# b5 A+ Y
                if(previous !=null){7 k5 g5 E7 `' C/ ~  a
                    results.add(previous);( N5 i- u. r6 X7 S' E
                }; |: `4 h8 J( Z* ~
                previous = new Interval(curr.start, curr.end);1 S. [2 Q) U- y) Q+ L4 \
            }else{
  s" N! j8 |+ H$ t4 t3 }8 b                previous.start = Math.min(previous.start, curr.start);
  F+ b$ d" b; R& U8 _4 j                previous.end = Math.max(previous.end, curr.end);
8 V3 S; \3 Q$ _% `2 g5 B            }
6 P* x: s+ c, S$ \: g        }! _6 K* N1 x; A) k5 [6 J$ o
        //Very important to add below code to handle last previous interval+ T2 b" T; R2 T( Y  Z
        if(previous != null){" J, z( m6 G5 q* z2 O/ K, n' o
            results.add(previous);
6 O5 C0 N3 o4 c# G5 T+ P        }
! L! ]; ?% W. I+ w8 c        return results;
  X0 f) Z; c& K}

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){
/ z$ F3 a( |# W
8 B) C& O5 v( Q1 i        //handle single element cases here
2 |5 g2 P. k+ X0 R: O$ X! c& x7 h# P        if(input.size()==0){
' Q# o$ r; p( Q0 F; X* \            return null;
  e' {0 ]5 q' c6 n5 J# j( b4 i        }else if(input.get(0).start>target.end || input.get(input.size()-1).end < target.start){ //no overlap) ]) g  s4 a" w( k/ h
                input.add(target);
0 {4 L+ \& O3 }        }else{
8 G4 o: q9 E) e: \            int result = insertAndMerge2(input, 0, input.size() - 1, target);4 o. j+ V% u) l6 l4 Q$ L
            if(result == -1){3 x( v  ?( Z, }, j' h
                input.add(target);7 [. ?5 V9 w0 b! ?
            }
" o/ q, l% a. L) s+ m        }" W9 x" m" Z3 ~1 P9 F1 |
        return input;& H) w1 I( {  t$ [* X* ^
    }

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

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

本版积分规则

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