Databases
StackOverflow2013
Postsdbo
POFinding lowest number with a run-time of O(1) - java
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POFinding lowest number with a run-time of O(1) - java
    primarykey
    data
    text
    <p>I'm in a need to create a data-structure based on Linked list, Array, And constant memory usage.</p> <p>As an input i get two numbers: N and M.</p> <p>N represents maximum capacity of a disk-on-key, M represents maximum capacity of a computer hard-drive, So that M>N.</p> <p>So i need to create a program that 'moves' information from the hard-drive to the disk-on-key, That program needs to implements the following methods:</p> <ol> <li>Insert(data) - Inserts the data into the disk-on-key, If its full it removes the data least important(*): worst case run-time O(1).</li> <li>delete(data) - deletes the given data from the disk-on-key - O(1)</li> </ol> <p>(*) the user can change the file importance.</p> <p>Maximum amount of memory usage is O(M)</p> <p>What i did so far:</p> <p>I've created an array [1...M] which will 'hold' the computer data, I've created a doubly linked list which will hold the disk-on-key data. [The idea is: each time a data is added to the disk-on-key it will be added to the linked list, and i can go directly to the data using the array as a index(/key) storage.]</p> <p>My computer data fields:</p> <pre><code>node firstNode; node currentNode; node[] dataCollection; // Will hold computer hard-drive data </code></pre> <p>So i wanted to create method replacing the least important data with data i want to add [so i'll be able to use in Insert], My code for replace:</p> <pre><code>public void replace(int leastImportantdata, int insertData){ node leastImportant = dataCollection[leastImportantdata]; if (leastImportant.prev!=null) leastImportant.prev.next=dataCollection[insertData-1]; if (leastImportant.next!=null) leastImportant.next.prev=dataCollection[insertData-1]; numOfReplacements++; </code></pre> <p>So, my main problem is finding the least important data given those two 'combined' data structures and still keeping a run-time of O(1), Especially when the user decides to change the files importance.</p> <ul> <li>Say that we start with {4,3,2,1} (numbers represents importance) the least important data would be 1.Suddenly, the user decided to change the last file importance to 5, we get {4,3,2,5} and least important data is 2.</li> </ul> <p>Any idea?</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USassylias
    1. USStationaryTraveller
    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. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POFinding lowest number with a run-time of O(1) - java
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POFinding lowest number with a run-time of O(1) - java
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POFinding lowest number with a run-time of O(1) - java
      1. This table or related slice is empty.
      1. VTUpMod
    1. COWhat is the range of "Importance"? That is, what is the highest and lowest Importance that can be assigned to a datum?
      singulars
      1. POFinding lowest number with a run-time of O(1) - java
      1. USRBarryYoung
    2. COWhy do you feel you need O(1), when O(log N) is almost certainly adequate and doing better than that is virtually impossible?
      singulars
      1. POFinding lowest number with a run-time of O(1) - java
      1. USHot Licks
    3. COThese questions may not be necessary if he paid more attention to his design. Using a SkipList can help produce a very simple and clean solution for this problem.
      singulars
      1. POFinding lowest number with a run-time of O(1) - java
      1. USIgwe Kalu
 

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