Databases
StackOverflow2013
Postsdbo
POMissing number(s) Interview Question Redux
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POMissing number(s) Interview Question Redux
    primarykey
    data
    text
    <p>The common interview problem of determining the missing value in a range from 1 to N has been done a thousand times over. Variations include 2 missing values up to K missing values.</p> <p>Example problem: Range [1,10] (1 2 4 5 7 8 9 10) = {3,6}</p> <p>Here is an example of the various solutions:</p> <p><a href="https://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-number">Easy interview question got harder: given numbers 1..100, find the missing number(s)</a></p> <p>My question is that seeing as the simple case of one missing value is of O(n) complexity and that the complexity of the larger cases converge at roughly something larger than O(nlogn):</p> <p>Couldn't it just be easier to answer the question by saying sort <em>(mergesort)</em> the range and iterate over it observing the missing elements? </p> <p>This solution should take no more than <b>O(nlogn)</b> and is capable of solving the problem for ranges other than 1-to-N such as 10-to-1000 or -100 to +100 etc... </p> <p>Is there any reason to believe that the given solutions in the above SO link will be better than the sorting based solution for larger number of missing values?</p> <p><em>Note: It seems a lot of the common solutions to this problem, assume an only number theoretic approach. If one is being asked such a question in an S/E interview wouldn't it be prudent to use a more computer science/algorithmic approach, assuming the approach is on par with the number theoretic solution's complexity...</em></p> <p>More related links:</p> <ul> <li><a href="https://mathoverflow.net/questions/25374/duplicate-detection-problem">https://mathoverflow.net/questions/25374/duplicate-detection-problem</a></li> <li><a href="https://stackoverflow.com/questions/2872959/algorithm-how-to-tell-if-an-array-is-a-permutation-in-on">How to tell if an array is a permutation in O(n)?</a></li> </ul>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. This table or related slice is empty.
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    3. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POMissing number(s) Interview Question Redux
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POMissing number(s) Interview Question Redux
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POMissing number(s) Interview Question Redux
      1. This table or related slice is empty.
      1. VTUpMod
    1. COSorting or using BitSets are perfectly valid solutions unless the interviewer explicitly specifies that he is looking for a streaming algorithm or that the set requires too much memory.
      singulars
      1. POMissing number(s) Interview Question Redux
      1. USabc
    2. COWhat if you don't even have O(N) memory available? What if you have to implement this on an embedded device with very limited resources, and the input comes in the form of a stream with no random access?
      singulars
      1. POMissing number(s) Interview Question Redux
      1. USgcbenison
 

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