title: Java interview question: get entry by two fields in O(log(n)) time
body: <p>Hi had an interview task, the idea is to store elements with fields: <code>id</code>, <code>name</code>, <code>updateTime</code>;</p>
  
  <p>There should be methods <code>add(Element)</code>, <code>getElement(id)</code>, <code>getLastUpdatedElements()</code></p>
  
  <p><strong>Requirements:</strong></p>
  
  <ul>
  <li>code should be on Java </li>
  <li>Should be thread safe</li>
  <li>Upper bound of computational complexiy for <strong>all these methods</strong> should be O(log(n))  </li>
  </ul>
  
  <p><strong>Notes</strong></p>
  
  <ul>
  <li>Update time of any element can be changed in runtime</li>
  <li>getLastUpdatedElements - returns updated last minute elements</li>
  </ul>
  
  <p><strong>My thoughts</strong></p>
  
  <p>I can not use <code>CopyOnWriteArrayList</code> because it will take O(N) to find last updated elements if the key is <code>id</code>, what breaks the requirement.</p>
  
  <p>To fit O(log(N)) complexity with <code>getLastUpdatedElements()</code> I can use <code>ConcurrentSkipListSet</code> with comparator by <code>updateTime</code> but in that case it will take O(N) to get element by ID. (Please note that in this case <code>add(Element)</code> is O(log(N)) since we know updateTime for newly created elements) </p>
  
  <p>I can use two trees, first one with comparator by id, second - with comparator by <code>updateTime</code>, but all access methods I should make synchronize what makes my programm single threaded </p>
  
  <p>I think I'm close, just need to find how to get element with O(log(N)) but my thoughts are running out.</p>