Databases
StackOverflow2013
Postsdbo
POAlgorithmic riddle: sequence with random access, insertion and remotion
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POAlgorithmic riddle: sequence with random access, insertion and remotion
    text
    copied!<p>Describe a data structure where:</p> <ul> <li><strong>Any item is indexed by an integral value like in an array</strong> <ul> <li>an integer can index a single value</li> <li>integers used to index items are <em>contiguous</em>: they go from 1 to <code>n</code> without holes</li> </ul></li> <li><strong>Getting the item at position <code>i</code> (ie: the item associated to the integer <code>i</code>) should be as fast as possible</strong> <ul> <li>random access</li> </ul></li> <li><strong>Inserting a new item at position <code>i</code> should be as fast as possible</strong> <ul> <li>this will right-shift any item from <code>i</code> onwards</li> </ul></li> <li><strong>Removing an item at position <code>i</code> should also be as fast as possible</strong> <ul> <li>this will left-shift any item from <code>i+1</code> onwards</li> </ul></li> </ul> <p>EDIT: a little thing I forgot about: item indices can only be shifted when adding/removing one, they cannot be randomly swapped.</p> <p>In this description <code>n</code> is the size of the structure (ie: how many items it contains), and <code>i</code> is a generic integer (1 &lt;= <code>i</code> &lt;= <code>n</code>), of course.</p> <hr> <p>I heard this from a guy I met in my faculty. Don't know if it's an interview question, an exam question, just a riddle or what, but I guess it could be everything.</p> <p>If I recall correctly (but hey, it was before December 24th) he said such a data structure could be implemented either with <code>O(sqrt n)</code> insertion/remotion and <code>O(1)</code> access time, or with <code>O(log n)</code> for any operation.</p> <hr> <p>EDIT: Some right answers have been given. Read it if you don't want to think any more about this problem.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload