Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Doesn't this work?:</p> <p>You can compute the rank of a number in linear time as long as <code>A</code> and <code>B</code> are sorted. The technique you use for computing the rank can also be used to find all things in <code>A+B</code> that are between some lower bound and some upper bound in time linear the size of the output plus <code>|A|+|B|</code>.</p> <p>Randomly sample <code>n</code> things from <code>A+B</code>. Take the median, say <code>foo</code>. Compute the rank of <code>foo</code>. With constant probability, <code>foo</code>'s rank is within <code>n</code> of the median's rank. Keep doing this (an expected constant number of times) until you have lower and upper bounds on the median that are within <code>2n</code> of each other. (This whole process takes expected linear time, but it's obviously slow.)</p> <p>All you have to do now is enumerate everything between the bounds and do a linear-time selection on a linear-sized list.</p> <p>(Unrelatedly, I wouldn't excuse the interviewer for asking such an obviously crappy interview question. Stuff like this in no way indicates your ability to code.)</p> <p><strong>EDIT</strong>: You can compute the rank of a number <code>x</code> by doing something like this:</p> <pre><code>Set i = j = 0. While j &lt; |B| and A[i] + B[j] &lt;= x, j++. While i &lt; |A| { While A[i] + B[j] &gt; x and j &gt;= 0, j--. If j &lt; 0, break. rank += j+1. i++. } </code></pre> <p><strong>FURTHER EDIT</strong>: Actually, the above trick only narrows down the candidate space to about n log(n) members of <code>A+B</code>. Then you have a general selection problem within a universe of size n log(n); you can do basically the same trick one more time and find a range of size proportional to sqrt(n) log(n) where you do selection.</p> <p>Here's why: If you sample k things from an n-set and take the median, then the sample median's order is between the (1/2 - sqrt(log(n) / k))th and the (1/2 + sqrt(log(n) / k))th elements with at least constant probability. When n = |A+B|, we'll want to take k = sqrt(n) and we get a range of about sqrt(n log n) elements --- that's about |A| log |A|. But then you do it again and you get a range on the order of sqrt(n) polylog(n).</p>
    singulars
    1. This table or related slice is empty.
    1. POFind the median of the sum of the arrays
      singulars
      1. PTQuestion
    1. PTAnswer
    1. UStmyklebu
    1. UStmyklebu
    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. This table or related slice is empty.
    1. COSo the rank takes higher than linear (nested for loop) solution is not linear
      singulars
      1. PO
      1. USaaronman
    2. COAnything that says "randomly" usually has worst case complexity infinity.
      singulars
      1. PO
      1. USaschepler
    3. CONo, the rank computation is obviously linear. And this is called a "Las Vegas" algorithm; it always returns the correct answer and its expected runtime is nice.
      singulars
      1. PO
      1. UStmyklebu
 

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