亚麻SDE-2面经

PattyZhou

, n* |4 S1 r  D+ z4 @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)

Effective delete requests - (1, 100) , (250, 600), (800, 900), (1000, 1200)
" r; f/ s8 J+ O
7 [. U, Z- ^! R) A! ^The 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.
6 @7 u" }  |8 m, n" B" m- w( b* d" i( 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)}

刷题小白

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.

My below code is written using ArrayList and I am creating a result list every time when insert request comes which is not optimal. , l: W9 h* v/ W9 l5 H

Previously:
1 J, c4 K5 }- Q1 z+ n
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.

Possibility-2 : If the problem is to assume one interval comes at a time as input, then it is straight forward insert interval case.

Java Solution: 4 W7 M. `6 |: ~4 u. P3 Q

Interval object can be stored as below.

class Interval{
9 a$ w% T: K8 M, e5 ^" O" }+ S# l	int start;
7 q* r7 |" t; ^- P7 k6 M) S/ n  O	int end;
	public Interval(int start, int end){
+ y# v" e3 v. n5 d		this.start = start;
		this.end = end;
+ f/ Q) e# P4 \& _! }* `0 w! j	}
}

Key points: , B9 P3 r2 l% n7 z" `; B/ f0 B
1. As the question is not clear, if the intervals are sorted or not incase of more intervals as a preprocessing step. ; D7 J) w! L6 l# i& O- S) `
We can take initial List of initial set of inputs and sort them and merge them and keep it ready.

This can be a preprocessor step.
4 k& W1 x3 B: m$ }
Merge (preprocess step) can be like below

public List<Interval> merge(List<Interval> input){
	List<Interval> results = new ArrayList<Interval>();
7 `5 y4 d4 l- T" O3 D0 P        //sort the collection
	Collections.sort(input,(i,j) -> (i.start = j.start ? (i.end.compareTo(j.end)) : i.start.compareTo(j.start) );
; K( k# Y# a% ~$ Y- m5 {
	//Loop through sorted input and merge
	Interval previous = null;
        for(Interval curr: input){
- H% D/ H) J/ ~& [" k4 b3 g9 v            if(previous == null || previous.end < curr.start){ //non-overlap case
6 H& y: B9 e9 `; R7 y                if(previous !=null){
0 o7 @8 }! K& R& d1 B/ B                    results.add(previous);
9 e$ z; x# M' g( H2 m3 g# ~$ |                }
/ U. k" o1 d$ u" k+ u5 ^                previous = new Interval(curr.start, curr.end);
            }else{
                previous.start = Math.min(previous.start, curr.start);
                previous.end = Math.max(previous.end, curr.end);
            }
        }
        //Very important to add below code to handle last previous interval
        if(previous != null){
            results.add(previous);
+ M6 @0 R8 E" q1 F        }
        return results;
- [* H- e8 Z6 Q# f3 K9 u& }) l6 y; i}

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){
7 R  p$ d% t- q3 b: |
& Q; z% D  F1 t, g8 V3 _        //handle single element cases here
3 d" l6 ^% t0 `. K1 h5 D& F        if(input.size()==0){
            return null;
        }else if(input.get(0).start>target.end || input.get(input.size()-1).end < target.start){ //no overlap
) w8 `* F; T9 r$ [4 A  F! B; j1 }2 F                input.add(target);
        }else{
6 I3 L2 r$ }+ I" S& v+ S+ r            int result = insertAndMerge2(input, 0, input.size() - 1, target);
; S+ F( J8 m, U+ M            if(result == -1){
                input.add(target);
            }
        }
        return input;
    }

非丽丝

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