Question

Here's the requirement. Write a client program Subset.java that takes a command-line integer k , reads in a sequence of strings from standard input using StdIn.readString() , and prints out exactly k of them, uniformly at random. Each item from the sequence can be printed out at most once. You may assume that 0 k N , where N is the number of string on standard input. The running time of the program must be linear in the size of the input. You may use only a constant amount of memory plus either one LinkedDeque or ResizingArrayRandomQueue object of maximum size at most N. For an extra challenge, limit the maximum size to k.

The sample output is $ java Subset 8
AA BB BB BB BB BB CC CC
<ctrl-d>
BB
CC
AA
BB
BB
BB

Here are code I have finished.

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

// Takes a command-line integer k; reads in a sequence of strings from
// standard input; and prints out exactly k of them, uniformly at random.
// Note that each item from the sequence is printed out at most once.
public class Subset {
    public static void main(String[] args) {
        //CODE HERE
        ResizingArrayRandomQueue<String> q = new ResizingArrayRandomQueue<String>();
        int k = Integer.parseInt(args[0]);

        while (!StdIn.isEmpty()){
            String item = StdIn.readString();
            q.enqueue(item);
        }
        while (k > 0) {
            StdOut.println(q.dequeue());
            k--;
        }
    }
}

and class ResizingArrayRandomQueue

public class ResizingArrayRandomQueue<Item> implements Iterable<Item> {
    //CODE HERE
    private Item[] q;
    private int N;

    // Construct an empty queue.
    public ResizingArrayRandomQueue() {
        //CODE HERE
        q = (Item[]) new Object[1];
        N = 0;
    }

    // Is the queue empty?
    public boolean isEmpty() {
        //CODE HERE
        return N == 0;
    }

    // The number of items on the queue.
    public int size() {
        //CODE HERE
        return N;
    }

    // Add item to the queue.
    public void enqueue(Item item) {
        //CODE HERE
        if (item == null)
            throw new IllegalArgumentException();
        q[N++] = item;
        if (N == q.length)
            resize(q.length * 2);
    }

    // Helper method for resizing the underlying array.
    private void resize(int max) {
        Item[] temp = (Item[]) new Object[max];
        for (int i = 0; i < N; i++) {
            if (q[i] != null) {
                temp[i] = q[i];
            }
        }
        q = temp;
    }

    // Remove and return a random item from the queue.
    public Item dequeue() {
        //CODE HERE
        if (isEmpty())
            throw new NoSuchElementException("Empty");
        int rand = StdRandom.uniform(0, N);
        N--;
        Item dItem = q[rand];
        q[rand] = q[N];
        q[N] = null;
        if (N > 0 && N == q.length/4)
            resize(q.length/2);
        return dItem;
    }

    // Return a random item from the queue, but do not remove it.
    public Item sample() {
        //CODE HERE
        if (isEmpty())
            throw new NoSuchElementException("Empty");
        int rand = StdRandom.uniform(0, N);
        Item item = q[rand];
        return  item;
    }

    // An independent iterator over items in the queue in random order.
    public Iterator<Item> iterator() {
        //CODE HERE
        return new RandomQueueIterator();
    }

    // An iterator, doesn't implement remove() since it's optional.
    private class RandomQueueIterator implements Iterator<Item> {
        //CODE HERE
        private int a = N;
        private Item[] b = (Item[]) new Object[q.length];

        RandomQueueIterator() {
            //CODE HERE
            for (int i = 0; i < q.length; i++) {
                b[i] = q[i];
            }
        }

        public boolean hasNext() {
            //CODE HERE
            return a > 0;
        }
        public void remove() {
            throw new UnsupportedOperationException();
        }

        public Item next() {
            //CODE HERE
            if (!hasNext()) {
                throw new NoSuchElementException("No more items");
            }
            int rand = StdRandom.uniform(0, a);
            a--;
            Item item = b[rand];
            b[rand] = b[a];
            b[a] = item;
            return item;
        }
    }

I successfully compiled Subset, however, when I ran it, it gives me this information:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
   at Subset.main(Subset.java:11)

Please correct any error in my code. Thx.

Answer 1

Instead of your Subset  try this one.....

Put that command line integer in try catch block....it will resolve you error.

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

// Takes a command-line integer k; reads in a sequence of strings from 
// standard input; and prints out exactly k of them, uniformly at random. 
// Note that each item from the sequence is printed out at most once.
public class Subset {
        public static void main(String[] args) {
                int k = 0;

                // If any arguments given, we try to parse it
                if (args.length > 0) {

                        try {
                                k = Integer.parseInt(args[0]);
                        } catch (NumberFormatException e) {
                                System.err.println("Argument" + args[0] + " must be an integer.");

                                // Program ends
                                System.exit(1);
                        }

                        ResizingArrayRandomQueue<String> q = new ResizingArrayRandomQueue<String>();
                        while (!StdIn.isEmpty()) {
                                q.enqueue(StdIn.readString());
                        }
                        for (int i = 0; i < k; i++) {
                                StdOut.println(q.dequeue());
                        }
                }
        }
}

I think you have posted incomplete Question... one or more class may be missing here

related to LinkedDeque...

I would have completed your question with output then..Anyway this try catch block will work fine...