FIFO Queue with random deletion

By : Rebecca
Source: Stackoverflow.com
Question!

Implement a data type that supports insert an item, delete the item added least recently, and delete a random item. Each operation should take constant expected amortized time per operation and should use space (at most) proportional to the number of items in the data structure.

eg. 1 2 3 4 5 6 -> 1 2 4 5 6

I have already implemented the queue as below, but now I do not know how the delete a random item with amortized time, should I rearrange the array every time when there is a random remove like moving number after the random removed number one slot forward in array? is it a really bad practice? or should I implement the Queue using linked list? but my gut feeling tells me linked list also need average O(n) to reach the random node from the head of the linked list.

public class RandomQueue<Item> implements Iterable<Item> {
Item[] items;
int N;
int first;
int last;

public RandomQueue() {
    items = (Item[]) new Object[2];
    N = 0;
    first = last = 0;
}

public static void main(String[] args) {
    RandomQueue<Integer> rd = new RandomQueue<>();
}

public boolean isEmpty() {
    return N == 0;
}

public String toString() {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < N; i++) {
        sb.append(items[(first + i) % items.length]).append(" ");
    }
    return sb.toString();
}

private void resize(int length) {
    Item[] temp = (Item[]) new Object[length];
    for (int i = 0; i < N; i++) {
        temp[i] = items[(first + i) % items.length];
    }
    items = temp;
    first = 0;
    last = N;
}

public void enqueue(Item item) {
    if (N == items.length)
        resize(items.length * 2);
    items[last++] = item;
    if (last == items.length)
        last = 0;
    N++;
}

public Item dequeue() {
    if (isEmpty())
        throw new NoSuchElementException("Queue is empty");
    Item first = items[first];
    items[first] = null;
    N--;

    if (first == items.length)
        first = 0;
    else
        first++;
    if (N > 0 && N == items.length / 4)
        resize(items.length / 2);
    return first;
}
}
By : Rebecca


Answers

The key to this problem is that you are not removing a random item from the queue you are creating a queue that excludes a random item. You should have a function in your program that accepts a queue as input and does the following:

  1. Create a second queue that will exclude the random deleted item.
  2. Generate a random number less than or equal to the total length of the first queue.
  3. Create a loop that will remove items from the first queue and add them to the second queue.
  4. If the counter in your loop equals the random number, do not add it to the second queue.
  5. Delete the first queue and return the second queue.
By : PrestonM


To make sure all fields are filled before submission of the form:

<input type="radio" required>

The ' required ' attribute makes sure all fields are filled before the form can be submitted.



I don't have the privalage to comment but you can use the required field as follows

 <input type="radio" name="question-1-answers" id="question-1-answers-A" value="A" required=true />

using this way the user will have to click all the required fields before submitting a form.



This video can help you solving your question :)
By: admin