StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POHow to partition bits in a bit array with less than linear time
text
Body
copied!<p>This is an interview question I faced recently.</p> <hr> <p>Given an array of 1 and 0, find a way to partition the bits <code>in place</code> so that 0's are grouped together, and 1's are grouped together. It does not matter whether 1's are ahead of 0's or 0's are ahead of 1's.</p> <p>An example input is <code>101010101</code>, and output is either <code>111110000</code> or <code>000011111</code>.</p> <p>Solve the problem in less than linear time.</p> <p>Make the problem simpler. The input is an integer array, with each element either 1 or 0. Output is the same integer array with integers partitioned well.</p> <hr> <p>To me, this is an easy question if it can be solved in <strong>O</strong>(N). My approach is to use two pointers, starting from both ends of the array. Increases and decreases each pointer; if it does not point to the correct integer, swap the two.</p> <pre> int * start = array; int * end = array + length - 1; while (start &lt end) { // Assume 0 always at the end if (*end == 0) { --end; continue; } // Assume 1 always at the beginning if (*start == 1) { ++start; continue; } swap(*start, *end); } </pre> <p>However, the interview insists there is a sub-linear solution. This makes me thinking hard but still not get an answer.</p> <p>Can anyone help on this interview question?</p> <p><strong>UPDATE</strong>: Seeing replies in SO stating that the problem cannot be solved in sub-linear time, I can confirm my original idea that there cannot be a solution of sub-linear. </p> <p>Is it possible the interviewer plays a trick?</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