亚麻SDE-2面经

PattyZhou

0 A0 R4 F* n! j0 \
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.

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)

  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
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)}

刷题小白

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.
. q3 f' t0 ` Y+ d
Previously:
# |# 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:

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){
		this.start = start;
		this.end = end;
	}
3 r2 C3 `7 h9 U5 e& ~9 H0 K# j}

Key points:
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

This can be a preprocessor step. * n; O% }# U9 Y5 V! U( H

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 collection
	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
	//Loop through sorted input and merge
	Interval previous = null;
        for(Interval curr: input){
            if(previous == null || previous.end < curr.start){ //non-overlap case
                if(previous !=null){
                    results.add(previous);
                }
                previous = new Interval(curr.start, curr.end);
            }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        }
        //Very important to add below code to handle last previous interval
        if(previous != null){
            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
                input.add(target);
0 {4 L+ \& O3 }        }else{
8 G4 o: q9 E) e: \            int result = insertAndMerge2(input, 0, input.size() - 1, target);
            if(result == -1){
                input.add(target);
            }
" o/ q, l% a. L) s+ m        }
        return input;
    }

非丽丝

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