India’s Best Job Seekers and Training Platform Forums Data Structure Give a large multi MB byte file in memory, a system handles …

  • Give a large multi MB byte file in memory, a system handles …

     Akash  updated 11 months, 2 weeks ago 1 Member · 1 Post
  • Akash 

    Administrator
    at

    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)

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

Log in to reply.

Original Post
0 of 0 posts June 2018
Now
KodNest Training New Batch is starting on 19th October 2020. Attend one week free demo classes.Register Now

New Report

Close