Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Here's my initial algorithm:</p> <pre><code>create array of size 100 [0..99]. read first 100 numbers and put into array. sort array in ascending order. while more numbers in file: get next number N. if N &gt; array[0]: if N &gt; array[99]: shift array[1..99] to array[0..98]. set array[99] to N. else find, using binary search, first index i where N &lt;= array[i]. shift array[1..i-1] to array[0..i-2]. set array[i-1] to N. endif endif endwhile </code></pre> <p>This has the (very slight) advantage is that there's no O(n^2) shuffling for the first 100 elements, just an O(n log n) sort and that you very quickly identify and throw away those that are too small. It also uses a binary search (7 comparisons max) to find the correct insertion point rather than 50 (on average) for a simplistic linear search (not that I'm suggesting anyone else proffered such a solution, just that it may impress the interviewer).</p> <p>You may even get bonus points for suggesting the use of optimised <code>shift</code> operations like <code>memcpy</code> in C provided you can be sure the overlap isn't a problem.</p> <hr> <p>One other possibility you may want to consider is to maintain three lists (of up to 100 integers each):</p> <pre><code>read first hundred numbers into array 1 and sort them descending. while more numbers: read up to next hundred numbers into array 2 and sort them descending. merge-sort lists 1 and 2 into list 3 (only first (largest) 100 numbers). if more numbers: read up to next hundred numbers into array 2 and sort them descending. merge-sort lists 3 and 2 into list 1 (only first (largest) 100 numbers). else copy list 3 to list 1. endif endwhile </code></pre> <p>I'm not sure, but that may end up being more efficient than the continual shuffling.</p> <p>The merge-sort is a simple selection along the lines of (for merge-sorting lists 1 and 2 into 3):</p> <pre><code>list3.clear() while list3.size() &lt; 100: while list1.peek() &gt;= list2.peek(): list3.add(list1.pop()) endwhile while list2.peek() &gt;= list1.peek(): list3.add(list2.pop()) endwhile endwhile </code></pre> <p>Simply put, pulling the top 100 values out of the combined list by virtue of the fact they're already sorted in descending order. I haven't checked in detail whether that would be more efficient, I'm just offering it as a possibility.</p> <p>I suspect the interviewers would be impressed with the potential for "out of the box" thinking and the fact that you'd stated that it should be evaluated for performance.</p> <p>As with most interviews, technical skill is <em>one</em> of the the things they're looking at.</p>
    singulars
    1. This table or related slice is empty.
    1. POFinding the hundred largest numbers in a file of a billion
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USpaxdiablo
    1. USpaxdiablo
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POFinding the hundred largest numbers in a file of a billion
      singulars
      1. PTQuestion
    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. COWouldn't the constant sorting be an unnecessary task? Why bother sorting when all you have to do is a simple comparison. The best case scenario for any sort is O(n) right? Which is when the set is already sorted. But a comparison of each element, remember the lowest value of the highest values, would be O(n-1).
      singulars
      1. PO
      1. This table or related slice is empty.
    2. COYou may be right, @Pickle, that's why I stated I hadn't done a proper analysis - you have to compare the operations rather than the big-O properties, it may be that 10 million of the sort and merge operations is more efficient that a potential 10 million 100-value shuffles involved in my original answer. By the way, if you _find_ an O(n) sort, let me know, I'll buy the rights off you :-)
      singulars
      1. PO
      1. USpaxdiablo
    3. COI wrote out some of the logic and it looks like you have to at least do a bubble sort on the 100 (assuming they're sorted) after seeing if a number is larger than your smallest largest number. You pop your buffer of 100 then do a bubble sort to find the appropriate position for the new number.
      singulars
      1. PO
      1. This table or related slice is empty.
 

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