<p>Many of the solutions are great, but <strong>None of them mentioned the <a href="https://medium.com/p/2ab4c0335e8b" rel="nofollow noreferrer">state-of-the-art</a> one</strong>.</p>
<p>It has <strong>O(1) worst-time</strong> complexity for the <code>fill(v), read(i), write(i, v)</code> operations<br>
(calling <em>fill(v)</em> sets all the values in the array to v, and <em>read</em>/<em>write</em> are self explanatory),<br>
While taking only <strong>1 bit of extra space</strong> besides the array. Yep.</p>
<p>So an int32_t array of size 1,000,000 will take O(1) worst-time to be initialized (and filled),<br>
and will take only 32,000,001 bits of memory.</p>
<p>It is mentioned in the <a href="https://arxiv.org/abs/1709.08900" rel="nofollow noreferrer">In-Place Initializable Arrays</a> paper,<br>and explained in an <a href="https://medium.com/p/2ab4c0335e8b" rel="nofollow noreferrer">Article</a> I've written about the subject.</p>
<p>I wrote a C++ header-only library called <a href="https://github.com/tomhea/farray" rel="nofollow noreferrer">Farray</a> that features the <strong>F</strong>illable <strong>Array</strong>,<br>
which is a templated implementation of the paper above.</p>
Interview question: data structure to set all values in O(1)
<p>I encountered the following interview question on the Internet.</p>

<p><strong>Describe a data structure for which getValue(int index), setValue(int index, int value), and setAllValues(int value) are all O(1).</strong></p>

<p>Though array is good enough for the first and second operations to be performed in O(1), what can be proposed for the third (setAllValues)?</p>