Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I think there is a solution with <code>O(1)</code> for all operations.</p> <p>You need a deque, and two hashtables. </p> <p>The first one is a linked hashtable, where for each <code>element</code> you store its <code>count</code>, the <code>next</code> element in count order and a <code>previous</code> element in count order. Then you can look the next and previous element's entries in that hashtable in a constant time. For this hashtable you also keep and update the element with the largest count. (<code>element -&gt; count, next_element, previous_element</code>)</p> <p>In the second hashtable for each distinct number of elements, you store the elements with that count in the start and in the end of the range in the first hashtable. Note that the size of this hashtable will be less than <code>n</code> (it's <code>O(sqrt(n))</code>, I think). (<code>count -&gt; (first_element, last_element)</code>)</p> <p>Basically, when you add an element to or remove an element from the deque, you can find its new position in the first hashtable by analyzing its <code>next</code> and <code>previous</code> elements, and the values for the old and new count in the second hashtable in constant time. You can remove and add elements in the first hashtable in constant time, using algorithms for linked lists. You can also update the second hashtable and the element with the maximum count in constant time as well.</p> <p>I'll try writing pseudocode if needed, but it seems to be quite complex with many special cases.</p>
    singulars
    1. This table or related slice is empty.
    1. POData Structure that supports queue like operations and mode finding
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USKolmar
    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
    1. COI agree with this answer because this is the one I proposed to my interviewer and it comes more naturally. However you have said the same thing my interviewer also said that is "it is difficult to code this and there *might* be some corner cases where it might not work". Hence I thought of this easier to implement albeit slower solution.
      singulars
      1. PO
      1. USrajaditya_m
    2. COI think it _will_ work in all cases, but, yes, it may be really tricky to code and thus it should be tested very thoroughly.
      singulars
      1. PO
      1. USKolmar
    3. COI don't get it: when a value occurs multiple times, does it occur once or multiple times in your first hash table? I would think multiple times because next and previous are different for different copies, but then you have to update the counts of all copies when a new one is added, which is potentially O(N).
      singulars
      1. PO
      1. USErik P.
 

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