Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>This algorithm is O(1) space (with some cheating), O(n) time (average), needs the source array to be non-const and destroys it at the end. Also it limits possible values in the array (three bits of each value should be reserved for the algorithm).</p> <p>Half of the answer is already in the question. Use hashmap. If a number is hit twice, use index difference, update the best so far result and remove this number from the hashmap to free space . To make it O(1) space, just reuse the source array. Convert the array to hashmap in-place.</p> <p>Before turning an array element to the hashmap cell, remember its value and position. After this it may be safely overwritten. Then use this value to calculate a new position in the hashmap and overwrite it. Elements are shuffled this way until an empty cell is found. To continue, select any element, that is not already reordered. When everything is reordered, every int pair is definitely hit twice, here we have an empty hashmap and an updated best result value.</p> <p>One reserved bit is used while converting array elements to the hashmap cells. At the beginning it is cleared. When a value is reordered to the hashmap cell, this bit is set. If this bit is not set for overwritten element, this element is just taken to be processed next. If this bit is set for element to be overwritten, there is a conflict here, pick first unused element (with this bit not set) and overwrite it instead.</p> <p>2 more reserved bits are used to chain conflicting values. They encode positions where the chain is started/ended/continued. (It may be possible to optimize this algorithm so that only 2 reserved bits are needed...)</p> <p>A hashmap cell should contain these 3 reserved bits, original value index, and some information to uniquely identify this element. To make this possible, a hash function should be reversible so that part of the value may be restored given its position in the table. In simplest case, hash function is just <code>ceil(log(n))</code> least significant bits. Value in the table consists of 3 fields:</p> <ul> <li><code>3</code> reserved bits</li> <li><code>32 - 3 - (ceil(log(n)))</code> high-order bits from the original value</li> <li><code>ceil(log(n))</code> bits for element's position in the original array</li> </ul> <p>Time complexity is O(n) only on average; worst case complexity is O(n^2).</p> <p>Other variant of this algorithm is to transform the array to hashmap sequentially: on each step <code>m</code> having <code>2^m</code> first elements of the array converted to hashmap. Some constant-sized array may be interleaved with the hashmap to improve performance when <code>m</code> is low. When <code>m</code> is high, there should be enough int pairs, which are already processed, and do not need space anymore.</p>
    singulars
    1. This table or related slice is empty.
    1. POFind the element with the longest distance in a given array where each element appears twice?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USEvgeny Kluev
    1. USEvgeny Kluev
    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. COthanks for your detailed analysis, but how to keep the hash ksys ? because you have to use hash key to search in the hash table to check whether a new element is hitted twice ?
      singulars
      1. PO
      1. USuser1002288
    2. COHalf of the hash key is stored in the hash table (high-order bits). Other half is restored from position in the hash table (because hash function is reversible). For example, table size is 32, and you search for a number 33. Take the low-order bits (1), so index in the table is 1. Compare the high-order bits in this table element with the high-order bits of the number (32). If there is no match, follow the chain of conflicting values. If 32 is found somewhere in the chain, this element is hit twice. If not found, add it to the hashmap.
      singulars
      1. PO
      1. USEvgeny Kluev
    3. COIn other words, part of the hash key is used to find proper hashmap entry (and not stored anywhere because it is not needed to resolve collisions). Other part of the hash key is used to resolve possible collisions (and stored in every hashmap entry).
      singulars
      1. PO
      1. USEvgeny Kluev
 

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