找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 7591|回复: 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 编辑 + {: C& n" J$ @3 F

" @/ m, K4 i$ g. BGive 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.+ n3 \4 m! w; N1 T, y" X$ u

: u: O) s2 F/ X6 w) DEg. a 5 MB file receives delete requests for offsets (1, 100), (250, 550),(1000, 1200), (400, 600), (800, 900), (1100, 1150)
+ d: a' _% _) U# u" {# L9 E1 m6 a9 z0 g% O+ _# I* u( A
Effective delete requests - (1, 100) , (250, 600), (800, 900), (1000, 1200)+ O8 Z! a( g  W0 m6 L

3 z# n0 Y8 R( X7 q3 T1 Y  P0 TThe 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.
1 b: M  I% v4 ?6 ~/ U! _/ W6 d
. R# v6 U6 X( [3 vWhat 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. ! `, e1 R N6 H8 B5 F! X$ q
' ]( B5 Y3 X6 [' E5 W) ?" u
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; M' I$ X5 w2 H
( Y0 ~' v/ s4 N8 E) Z
Previously:$ F2 L) t3 [ d5 s! H6 [) _! q
k8 @5 \& [2 Q1 m8 R) L
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. + s+ M8 k2 @8 I1 { s/ t( l
; J) d4 R& d# F0 S' I% q; z
Possibility-2 : If the problem is to assume one interval comes at a time as input, then it is straight forward insert interval case. - G% {( v* w, u9 o* I
+ A4 B3 x- L5 K# S: G. m
Java Solution:9 l9 T4 d0 e! s0 H8 X/ a
$ G3 i, _ E6 o# A
Interval object can be stored as below.

class Interval{
: Q0 Y3 F0 D# r1 r	int start;
2 {9 O, M+ H2 d5 A	int end;
$ K. H# s. b' |+ @- i, P	public Interval(int start, int end){1 A: N( v& w6 d; z7 L" s. T
		this.start = start;
( R0 z. O  C, R% |4 F" q		this.end = end;
9 ~4 ?4 T9 V/ K# s' ?1 v+ a	}
. K/ q, _0 b# |+ ?}

Key points: 7 v" y1 Z' q& p
1. As the question is not clear, if the intervals are sorted or not incase of more intervals as a preprocessing step." t+ u+ R# ^" u3 ]' ]- I
We can take initial List of initial set of inputs and sort them and merge them and keep it ready. ' f1 ]. ]8 ?/ X) K, Y& U
/ O+ b( j! Y9 ^8 V4 S" E! p
This can be a preprocessor step.1 f6 _: d$ M( v
9 f9 C; A* R1 }4 \) N8 M% u) C
Merge (preprocess step) can be like below

public List<Interval> merge(List<Interval> input){
8 d8 j0 T- I$ m  M3 v	List<Interval> results = new ArrayList<Interval>();1 J" K% f0 D! G& Y  ?
        //sort the collection
9 _" a* g% t8 j+ ]7 ^; x' }+ h	Collections.sort(input,(i,j) -> (i.start = j.start ? (i.end.compareTo(j.end)) : i.start.compareTo(j.start) );* g' C. }% l  R+ g
  }* D: w. i' d( M. S
	//Loop through sorted input and merge4 v# Q) g- }: k
	Interval previous = null;
$ C% G9 C( [( S- ]5 |0 C        for(Interval curr: input){
9 }7 g* f6 p: T7 a  @6 T# d5 _            if(previous == null || previous.end < curr.start){ //non-overlap case
' P5 |5 A# |8 e4 D1 g* |                if(previous !=null){8 z8 l$ w$ [1 e6 g  I& p- o# n
                    results.add(previous);" a+ C) ?1 R; l* {
                }) Z# \2 f3 I1 r7 D) A4 r) Y, H' T) }
                previous = new Interval(curr.start, curr.end);; G' \( ^4 E1 m6 a9 i. L+ d4 }" `/ C
            }else{  }- I# O; i1 i, H5 d% A1 T
                previous.start = Math.min(previous.start, curr.start);4 r/ a7 B' [* |9 C: }
                previous.end = Math.max(previous.end, curr.end);4 w4 j0 e. v; \  W# |- {  q. n
            }1 h& \: @" _1 L2 c
        }
6 g9 y, W6 |; m( I        //Very important to add below code to handle last previous interval
  I6 G( T8 ^3 Q! a1 ~        if(previous != null){3 o9 Q* H1 F. }* N8 }
            results.add(previous);
' M% q) \  G3 ]" T6 n* V! P        }- ?" C* w8 A1 n8 M
        return results;& ?/ L' p( ^0 e9 U5 y
}

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){: c& A! B; X4 a0 [( F% O. w( k
6 \% S* U, y5 I( G
        //handle single element cases here
' e2 t* t7 K- A( Z4 x; i8 x. U        if(input.size()==0){- j: C* `1 x5 h: E$ ^# k0 }
            return null;$ N: t! V7 e7 D- m. G  @/ T2 c! A
        }else if(input.get(0).start>target.end || input.get(input.size()-1).end < target.start){ //no overlap
; s; E1 H/ E& K$ w" C2 k$ ~" c! F                input.add(target);
- g0 g" P1 r. @        }else{
5 V# R3 A1 W* z# Y- j            int result = insertAndMerge2(input, 0, input.size() - 1, target);$ P  @3 l9 j1 h  c' w9 a6 ?8 `, w  j
            if(result == -1){
1 {- y; W9 y! \' W9 |$ |, x, |                input.add(target);* Y$ d  L, \; I( K. h; t
            }; p$ N( V1 I  O) N. u* c
        }2 N) f* y  ]5 E5 M- C& I0 P
        return input;& y* G3 H: O0 D7 u' \  Y6 w% \( J# F
    }

回复 支持 反对

使用道具 举报

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

回复 支持 反对

使用道具 举报

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

本版积分规则

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