Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>As @j_random_hacker pointed out, this is quite similar to <a href="https://stackoverflow.com/q/5739024/134633"><em>Finding duplicates in O(n) time and O(1) space</em></a>, and an adaptation of my answer there works here too.</p> <p>Assuming that the "bag" is represented by a 1-based array <code>A[]</code> of size <code>N - k</code>, we can solve Qk in <code>O(N)</code> time and <code>O(k)</code> additional space.</p> <p>First, we extend our array <code>A[]</code> by <code>k</code> elements, so that it is now of size <code>N</code>. This is the <code>O(k)</code> additional space. We then run the following pseudo-code algorithm:</p> <pre><code>for i := n - k + 1 to n A[i] := A[1] end for for i := 1 to n - k while A[A[i]] != A[i] swap(A[i], A[A[i]]) end while end for for i := 1 to n if A[i] != i then print i end if end for </code></pre> <p>The first loop initialises the <code>k</code> extra entries to the same as the first entry in the array (this is just a convenient value that we know is already present in the array - after this step, any entries that were missing in the initial array of size <code>N-k</code> are still missing in the extended array).</p> <p>The second loop permutes the extended array so that if element <code>x</code> is present at least once, then one of those entries will be at position <code>A[x]</code>.</p> <p>Note that although it has a nested loop, it still runs in <code>O(N)</code> time - a swap only occurs if there is an <code>i</code> such that <code>A[i] != i</code>, and each swap sets at least one element such that <code>A[i] == i</code>, where that wasn't true before. This means that the total number of swaps (and thus the total number of executions of the <code>while</code> loop body) is at most <code>N-1</code>.</p> <p>The third loop prints those indexes of the array <code>i</code> that are not occupied by the value <code>i</code> - this means that <code>i</code> must have been missing.</p>
    singulars
    1. This table or related slice is empty.
    1. POEasy interview question got harder: given numbers 1..100, find the missing number(s)
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. UScaf
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI wonder why so few people vote this answer up and even did not mark it as a correct answer. Here is the code in Python. It runs in O(n) time and need extra space O(k). http://pastebin.com/9jZqnTzV
      singulars
      1. PO
      1. USwall-e
    2. CO@wall-e: Well, I *was* several months late to this party.
      singulars
      1. PO
      1. UScaf
    3. CO@caf this is quite similar to setting the bits and counting the places where the bit is 0. And I think as you are creating an integer array more memory is occupied.
      singulars
      1. PO
      1. USFox
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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