title: Algorithm to find record in a log structured file system
body: <p>I have a log of records. Each record has a ID and Timestamp. New records get appended to the log with monotonically increasing ID, even though there can be deletion of the records in between.</p>
  
  <p>The problem is - If you are given a timestamp T1, provide an efficient algorithm to determine the log record which has timestamp = Ceil(T1). </p>
  
  <p>Points to note. Log can be very big with millions of records. There can be missing records because of record deletion. </p>
  
  <p>Example: If log record = (ID, Timestamp), then log can be shown like this:</p>
  
  <p>(1, 10), (2, 11), (5, 15), (8,18), (9, 19), (10, 20)</p>
  
  <p>Find ID of the record with min timestamp greater or equal to 17.</p>
  
  <p>Answer is 8.</p>
  
  <p>Find ID of the record with min timestamp greater or equal to 11.</p>
  
  <p>Answer is 2.</p>
  
  <p>Find ID of the record with min timestamp greater or equal to 22.</p>
  
  <p>Answer is Nil</p>
  
  <p>Find ID of the record with min timestamp greater or equal to 5.</p>
  
  <p>Answer is 1</p>
  
  <p>I have come up with simple data-structures to solve this problem.</p>
  
  <p><div class="snippet" data-lang="js" data-hide="false">
  <div class="snippet-code">
  <pre class="snippet-code-html lang-html prettyprint-override"><code>/* index:    0  1   2   3   4  5  6   7   8  9  10   11   12  */
  
  int ids[]=     {1,  2,            6,  7,        10,  11,  12};
  int map[]=  {0, 1,  1,  0,  0, 0, 1,  1,  0, 0, 1,   1,   1};
  int time[]= {0, 10, 20, 0,  0, 0, 60, 70, 0, 0, 100, 110, 120};
  int start= 1, end = 12;  // this is known to us.</code></pre>
  </div>
  </div>
  </p>
  
  <p>ids[] is list of all the IDs. Given that this list can be millions, we cannot index this list in an array. So in the above example, IDs 3, 4, 5, 8, 9 are missing. But the list is in increasing order.</p>
  
  <p>map[] is the bitmap which can tell you if given ID is present or not. It is a cheap operation.</p>
  
  <p>time[] is the timestamp array for each of the IDs present. Remember to assume that getting timestamp is actually expensive operation. </p>
  
  <p>Also there is no co-relation between ID's and timestamp value. Instead of 10, 20, etc it could be anything like 1133, 2987..and so on. but in increasing order.</p>
  
  <p>You need to fill up this function:</p>
  
  <p><div class="snippet" data-lang="js" data-hide="false">
  <div class="snippet-code">
  <pre class="snippet-code-html lang-html prettyprint-override"><code>int
  find_ceil_id(int timestamp) 
  {
    .....
    ....
    return(id)
  }</code></pre>
  </div>
  </div>
  </p>