naveentmani
BAN USER- 0of 0 votes
AnswersGive 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.
- naveentmani in United States for AWS
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)
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.
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)}| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures