Skip to content

Instantly share code, notes, and snippets.

@Chayemor

Chayemor/Deque.java

Last active July 17, 2020 16:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Chayemor/15fc47e128b5797b30f92fa9e07c90ee to your computer and use it in GitHub Desktop.
Save Chayemor/15fc47e128b5797b30f92fa9e07c90ee to your computer and use it in GitHub Desktop.
Download ZIP
Deques and Randomized Queues - Coursera Algorithms Part 1
Raw
Deque.java
/* *****************************************************************************
* Name: Johanna Mesa Ramos
* Coursera User ID: c02b4bb527298de170192d644483baeb
* Course: Algorithms, Part I https://www.coursera.org/learn/algorithms-part1
**************************************************************************** */
import java.util.Iterator;
public class Deque<Item> implements Iterable<Item> {
private Node front, back;
private int count = 0;
private class Node {
Item item;
Node next = null;
Node prev = null;
}
public Deque() {
}
public boolean isEmpty() {
return count == 0;
}
public int size() {
return count;
}
public void addFirst(Item item) {
if (item == null)
throw new IllegalArgumentException("Argument can't be null");
count += 1;
Node old = front;
front = new Node();
front.next = old;
front.item = item;
if (size() == 1) {
back = front;
}
else {
old.prev = front;
}
}
public void addLast(Item item) {
if (item == null)
throw new IllegalArgumentException("Argument can't be null");
count += 1;
Node old = back;
back = new Node();
back.item = item;
back.prev = old;
if (size() == 1) {
front = back;
}
else {
old.next = back;
}
}
public Item removeFirst() {
if (size() == 0)
throw new java.util.NoSuchElementException("Deque is empty");
count -= 1;
Item item = front.item;
front = front.next;
if (count == 0) {
back = null;
}
return item;
}
public Item removeLast() {
if (size() == 0)
throw new java.util.NoSuchElementException("Deque is empty");
count -= 1;
Item item = back.item;
back = back.prev;
if (size() == 0)
front = null;
return item;
}
public Iterator<Item> iterator() {
return new DequeIterator();
}
private class DequeIterator implements Iterator<Item> {
private Node current = front;
public boolean hasNext() {
return current != null;
}
public void remove() {
throw new UnsupportedOperationException("Method not supported");
}
public Item next() {
if (current == null)
throw new java.util.NoSuchElementException("There is no next element");
Item item = current.item;
current = current.next;
return item;
}
}
public static void main(String[] args) {
Deque<Integer> quetack = new Deque<Integer>();
System.out.format("Size : %s%n", quetack.size());
System.out.format("Is empty: %s%n%n", quetack.isEmpty());
System.out.println("Adding 10 elements, using addFirst");
for (int i = 0; i < 10; ++i)
quetack.addFirst(i);
System.out.format("Size : %s%n", quetack.size());
System.out.format("Is empty: %s%n%n", quetack.isEmpty());
System.out.println("Printing Dequeue with iterator, numbers should appear from 9 to 0");
Deque.printIterator(quetack);
System.out.println("Printing Dequeue with removeFirst, numbers should appear from 9 to 0");
while (!quetack.isEmpty())
System.out.format("%s ", quetack.removeFirst());
System.out.format("%n%n");
System.out.format("Size : %s%n", quetack.size());
System.out.format("Is empty: %s%n%n", quetack.isEmpty());
System.out.println("Adding 10 elements, using addLast");
for (int i = 0; i < 10; ++i)
quetack.addLast(i);
System.out.format("Size : %s%n", quetack.size());
System.out.format("Is empty: %s%n%n", quetack.isEmpty());
System.out.println("Printing Dequeue with iterator, numbers should appear from 0 to 9");
Deque.printIterator(quetack);
System.out.println("Printing Dequeue with removeLast, numbers should appear from 9 to 0");
while (!quetack.isEmpty())
System.out.format("%s ", quetack.removeLast());
System.out.format("%n%n");
System.out.format("Size : %s%n", quetack.size());
System.out.format("Is empty: %s%n%n", quetack.isEmpty());
System.out.println("Adding 1 element, using addLast");
quetack.addLast(0);
System.out.format("Size : %s%n", quetack.size());
System.out.format("Is empty: %s%n%n", quetack.isEmpty());
System.out.println("Printing Dequeue with removeLast, numbers should appear to be 0");
System.out.format("%s ", quetack.removeLast());
System.out.format("Size : %s%n", quetack.size());
System.out.format("Is empty: %s%n%n", quetack.isEmpty());
System.out.println("Random operations");
quetack.addFirst(1);
quetack.addFirst(2);
System.out.format("Should be 1 ---> %s %n", quetack.removeLast());
System.out.format("Is empty: %s%n", quetack.isEmpty());
System.out.format("Should be 2 ---> %s %n", quetack.removeLast());
System.out.format("Is empty: %s%n", quetack.isEmpty());
}
private static void printIterator(Deque<Integer> q) {
for (Integer i : q)
System.out.format("%s ", i);
System.out.format("%n%n");
}
}
Raw
Permutation.java
/* *****************************************************************************
* Name: Johanna Mesa Ramos
* Coursera User ID: c02b4bb527298de170192d644483baeb
* Course: Algorithms, Part I https://www.coursera.org/learn/algorithms-part1
**************************************************************************** */
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class Permutation {
public static void main(String[] args) {
if (args.length == 0)
return;
int numToPrint;
try {
numToPrint = Integer.parseInt(args[0]);
}
catch (NumberFormatException nfe) {
return;
}
final RandomizedQueue<String> rndQueue = new RandomizedQueue<String>();
while (!StdIn.isEmpty()) {
rndQueue.enqueue(StdIn.readString());
}
while (numToPrint > 0) {
numToPrint -= 1;
StdOut.println(rndQueue.dequeue());
}
}
}
Raw
RandomizedQueue.java
/* *****************************************************************************
* Name: Johanna Mesa Ramos
* Coursera User ID: c02b4bb527298de170192d644483baeb
* Course: Algorithms, Part I https://www.coursera.org/learn/algorithms-part1
**************************************************************************** */
import edu.princeton.cs.algs4.StdRandom;
import java.util.Iterator;
public class RandomizedQueue<Item> implements Iterable<Item> {
private Node front, back;
private int count = 0;
private class Node {
Item item;
Node next = null;
Node prev = null;
}
public RandomizedQueue() {
}
public boolean isEmpty() {
return size() == 0;
}
public int size() {
return count;
}
public void enqueue(Item item) {
if (item == null)
throw new IllegalArgumentException("Argument can't be null");
count += 1;
Node old = back;
back = new Node();
back.item = item;
back.prev = old;
if (size() == 1) {
front = back;
}
else {
old.next = back;
}
}
/**
* Removes and returns a random item
**/
public Item dequeue() {
if (size() == 0)
throw new java.util.NoSuchElementException("RandomizedQueue is empty");
Node rndNode = getRandomNode(null);
count -= 1;
if (rndNode.prev == null) {
front = rndNode.next;
if (front != null)
front.prev = null;
else
back = front;
}
else if (rndNode.next == null) {
back = rndNode.prev;
back.next = null;
}
else {
rndNode.prev.next = rndNode.next;
rndNode.next.prev = rndNode.prev;
rndNode.prev = null;
rndNode.next = null;
}
return rndNode.item;
}
/**
* Return random item without removing
*/
public Item sample() {
if (size() == 0)
throw new java.util.NoSuchElementException("RandomizedQueue is empty");
return getRandomNode(null).item;
}
private Node getRandomNode(Integer chosen) {
chosen = chosen == null ? StdRandom.uniform(count) : chosen;
boolean firstHalf = chosen < (size() / 2);
Node random = firstHalf ? front : back;
int pos = firstHalf ? 0 : size() - 1;
while (pos != chosen) {
if (firstHalf) {
pos += 1;
random = random.next;
}
else {
pos -= 1;
random = random.prev;
}
}
return random;
}
public Iterator<Item> iterator() {
return new RandomizedIterator();
}
private class RandomizedIterator implements Iterator<Item> {
private boolean[] visited = new boolean[count];
private int visits = count;
public boolean hasNext() {
return visits > 0;
}
public void remove() {
throw new UnsupportedOperationException("This method is not supported");
}
public Item next() {
if (!hasNext())
throw new java.util.NoSuchElementException("There are no more elements to returns");
int rnd;
do {
rnd = StdRandom.uniform(count);
} while (visited[rnd]);
visited[rnd] = true;
visits -= 1;
return getRandomNode(rnd).item;
}
}
public static void main(String[] args) {
RandomizedQueue<Integer> rndQueue = new RandomizedQueue<Integer>();
System.out.format("Size : %s%n", rndQueue.size());
System.out.format("Is empty: %s%n%n", rndQueue.isEmpty());
System.out.println("Adding 10 elements, using enqueue");
for (int i = 0; i < 10; ++i)
rndQueue.enqueue(i);
System.out.format("Size : %s%n", rndQueue.size());
System.out.format("Is empty: %s%n%n", rndQueue.isEmpty());
System.out.println(
"Printing RandomizeQueue with iterator, 10 numbers should appear in random");
RandomizedQueue.printIterator(rndQueue);
System.out.println(
"Printing RandomizedQueue with dequeue, 10 numbers should appear in random order");
while (!rndQueue.isEmpty())
System.out.format("%s ", rndQueue.dequeue());
System.out.format("%nSize : %s%n", rndQueue.size());
System.out.format("Is empty: %s%n%n", rndQueue.isEmpty());
System.out.println("Adding 1 element, using enqueue");
rndQueue.enqueue(1);
System.out.println("Getting element, through sample");
System.out.format("%s %n", rndQueue.sample());
System.out.format("%nSize : %s%n", rndQueue.size());
System.out.format("Is empty: %s%n%n", rndQueue.isEmpty());
System.out.println("Getting element, through dequeue");
System.out.format("%s %n", rndQueue.dequeue());
System.out.format("%nSize : %s%n", rndQueue.size());
System.out.format("Is empty: %s%n%n", rndQueue.isEmpty());
System.out.println("Adding 10 elements, using enqueue");
for (int i = 0; i < 10; ++i)
rndQueue.enqueue(i);
System.out.println(
"Printing RandomizedQueue with sample, 10 numbers should appear in random order");
for (int i = 0; i < 10; ++i)
System.out.format("%s ", rndQueue.sample());
System.out.format("%nSize : %s%n", rndQueue.size());
System.out.format("Is empty: %s%n%n", rndQueue.isEmpty());
}
private static void printIterator(RandomizedQueue<Integer> q) {
for (Integer i : q)
System.out.format("%s ", i);
System.out.format("%n%n");
}
}
Raw
Z Results.txt
See the Assessment Guide for information on how to interpret this report.
ASSESSMENT SUMMARY
Compilation: PASSED
API: PASSED
Spotbugs: PASSED
PMD: PASSED
Checkstyle: PASSED
Correctness: 44/45 tests passed
Memory: 30/50 tests passed
Timing: 164/193 tests passed
Aggregate score: 91.66%
[Compilation: 5%, API: 5%, Spotbugs: 0%, PMD: 0%, Checkstyle: 0%, Correctness: 60%, Memory: 10%, Timing: 20%]
ASSESSMENT DETAILS
The following files were submitted:
----------------------------------
5.3K Jul 8 15:58 Deque.java
682 Jul 8 15:58 Permutation.java
5.6K Jul 8 15:58 RandomizedQueue.java
********************************************************************************
* COMPILING
********************************************************************************
% javac Deque.java
*-----------------------------------------------------------
% javac RandomizedQueue.java
*-----------------------------------------------------------
% javac Permutation.java
*-----------------------------------------------------------
================================================================
Checking the APIs of your programs.
*-----------------------------------------------------------
Deque:
RandomizedQueue:
Permutation:
================================================================
********************************************************************************
* CHECKING STYLE AND COMMON BUG PATTERNS
********************************************************************************
% spotbugs *.class
*-----------------------------------------------------------
M P BX_UNBOXING_IMMEDIATELY_REBOXED Bx: Unboxes and immediately reboxes a boxed value. At RandomizedQueue.java:[line 86]
================================================================
% pmd .
*-----------------------------------------------------------
================================================================
% checkstyle *.java
*-----------------------------------------------------------
% custom checkstyle checks for Deque.java
*-----------------------------------------------------------
% custom checkstyle checks for RandomizedQueue.java
*-----------------------------------------------------------
[INFO] RandomizedQueue.java:124: Using a loop in this method might be a performance bug. [Performance]
% custom checkstyle checks for Permutation.java
*-----------------------------------------------------------
================================================================
********************************************************************************
* TESTING CORRECTNESS
********************************************************************************
Testing correctness of Deque
*-----------------------------------------------------------
Running 17 total tests.
Tests 1-6 make random calls to addFirst(), addLast(), removeFirst(),
removeLast(), isEmpty(), and size(). The probabilities of each
operation are (p1, p2, p3, p4, p5, p6), respectively.
Test 1: check random calls to addFirst(), addLast(), and size()
* 5 random calls (0.4, 0.4, 0.0, 0.0, 0.0, 0.2)
* 50 random calls (0.4, 0.4, 0.0, 0.0, 0.0, 0.2)
* 500 random calls (0.4, 0.4, 0.0, 0.0, 0.0, 0.2)
* 1000 random calls (0.4, 0.4, 0.0, 0.0, 0.0, 0.2)
==> passed
Test 2: check random calls to addFirst(), removeFirst(), and isEmpty()
* 5 random calls (0.8, 0.0, 0.1, 0.0, 0.1, 0.0)
* 50 random calls (0.8, 0.0, 0.1, 0.0, 0.1, 0.0)
* 500 random calls (0.8, 0.0, 0.1, 0.0, 0.1, 0.0)
* 1000 random calls (0.8, 0.0, 0.1, 0.0, 0.1, 0.0)
* 5 random calls (0.1, 0.0, 0.8, 0.0, 0.1, 0.0)
* 50 random calls (0.1, 0.0, 0.8, 0.0, 0.1, 0.0)
* 500 random calls (0.1, 0.0, 0.8, 0.0, 0.1, 0.0)
* 1000 random calls (0.1, 0.0, 0.8, 0.0, 0.1, 0.0)
==> passed
Test 3: check random calls to addFirst(), removeLast(), and isEmpty()
* 5 random calls (0.8, 0.0, 0.0, 0.1, 0.1, 0.0)
* 50 random calls (0.8, 0.0, 0.0, 0.1, 0.1, 0.0)
* 500 random calls (0.8, 0.0, 0.0, 0.1, 0.1, 0.0)
* 1000 random calls (0.8, 0.0, 0.0, 0.1, 0.1, 0.0)
* 5 random calls (0.1, 0.0, 0.0, 0.8, 0.1, 0.0)
* 50 random calls (0.1, 0.0, 0.0, 0.8, 0.1, 0.0)
* 500 random calls (0.1, 0.0, 0.0, 0.8, 0.1, 0.0)
* 1000 random calls (0.1, 0.0, 0.0, 0.8, 0.1, 0.0)
==> passed
Test 4: check random calls to addLast(), removeLast(), and isEmpty()
* 5 random calls (0.0, 0.8, 0.0, 0.1, 0.1, 0.0)
* 50 random calls (0.0, 0.8, 0.0, 0.1, 0.1, 0.0)
* 500 random calls (0.0, 0.8, 0.0, 0.1, 0.1, 0.0)
* 1000 random calls (0.0, 0.8, 0.0, 0.1, 0.1, 0.0)
* 5 random calls (0.0, 0.1, 0.0, 0.8, 0.1, 0.0)
* 50 random calls (0.0, 0.1, 0.0, 0.8, 0.1, 0.0)
* 500 random calls (0.0, 0.1, 0.0, 0.8, 0.1, 0.0)
* 1000 random calls (0.0, 0.1, 0.0, 0.8, 0.1, 0.0)
==> passed
Test 5: check random calls to addLast(), removeFirst(), and isEmpty()
* 5 random calls (0.0, 0.8, 0.1, 0.0, 0.1, 0.0)
* 50 random calls (0.0, 0.8, 0.1, 0.0, 0.1, 0.0)
* 500 random calls (0.0, 0.8, 0.1, 0.0, 0.1, 0.0)
* 1000 random calls (0.0, 0.8, 0.1, 0.0, 0.1, 0.0)
* 5 random calls (0.0, 0.1, 0.8, 0.0, 0.1, 0.0)
* 50 random calls (0.0, 0.1, 0.8, 0.0, 0.1, 0.0)
* 500 random calls (0.0, 0.1, 0.8, 0.0, 0.1, 0.0)
* 1000 random calls (0.0, 0.1, 0.8, 0.0, 0.1, 0.0)
==> passed
Test 6: check random calls to addFirst(), addLast(), removeFirst(),
removeLast(), isEmpty(), and size()
* 5 random calls (0.3, 0.3, 0.1, 0.1, 0.1, 0.1)
* 50 random calls (0.3, 0.3, 0.1, 0.1, 0.1, 0.1)
* 500 random calls (0.3, 0.3, 0.1, 0.1, 0.1, 0.1)
* 1000 random calls (0.3, 0.3, 0.1, 0.1, 0.1, 0.1)
* 5 random calls (0.1, 0.1, 0.3, 0.3, 0.1, 0.1)
* 50 random calls (0.1, 0.1, 0.3, 0.3, 0.1, 0.1)
* 500 random calls (0.1, 0.1, 0.3, 0.3, 0.1, 0.1)
* 1000 random calls (0.1, 0.1, 0.3, 0.3, 0.1, 0.1)
==> passed
Test 7: check removeFirst() and removeLast() from an empty deque
* removeFirst()
* removeLast()
==> passed
Test 8: check whether two Deque objects can be created at the same time
* n = 10
* n = 1000
==> passed
Test 9: check iterator() after n calls to addFirst()
* n = 10
* n = 50
==> passed
Test 10: check iterator() after each of m intermixed calls to
addFirst(), addLast(), removeFirst(), and removeLast()
* m = 20
- number of student entries = 2
- number of reference entries = 1
- iterator() yields wrong entries after applying operation 3
- sequence of operations was:
Deque deque<Integer> = new Deque<Integer>()
deque.addFirst(1)
deque.addLast(2)
deque.removeLast() ==> 2
* m = 50
- number of student entries = 2
- number of reference entries = 1
- iterator() yields wrong entries after applying operation 17
* m = 100
- number of student entries = 4
- number of reference entries = 3
- iterator() yields wrong entries after applying operation 13
* m = 1000
- number of student entries = 6
- number of reference entries = 5
- iterator() yields wrong entries after applying operation 15
==> FAILED
Test 11: create two nested iterators to same deque
* n = 10
* n = 50
==> passed
Test 12: create two parallel iterators to same deque
==> passed
Test 13: create an iterator and check calls to next() and hasNext()
* 10 consecutive calls to hasNext() on a deque of size 10
* 10 consecutive calls to next() on a deque of size 10
* 50 random intermixed calls to next() and hasNext() on a deque of size 10
* 1000 random intermixed calls to next() and hasNext() on a deque of size 100
==> passed
Test 14: create Deque objects of different parameterized types
==> passed
Test 15: call addFirst() and addLast() with null argument
==> passed
Test 16: check that remove() and next() throw the specified exceptions in iterator()
==> passed
Test 17: call iterator() when the deque is empty
==> passed
Total: 16/17 tests passed!
================================================================
Testing correctness of RandomizedQueue
*-----------------------------------------------------------
Running 19 total tests.
Tests 1-4 make random calls to enqueue(), dequeue(), sample(),
isEmpty(), and size(). The probabilities of each operation are
(p1, p2, p3, p4, p5), respectively.
Test 1: check random calls to enqueue() and size()
* 5 random calls (0.8, 0.0, 0.0, 0.0, 0.2)
* 50 random calls (0.8, 0.0, 0.0, 0.0, 0.2)
* 500 random calls (0.8, 0.0, 0.0, 0.0, 0.2)
* 1000 random calls (0.8, 0.0, 0.0, 0.0, 0.2)
==> passed
Test 2: check random calls to enqueue() and dequeue()
* 5 random calls (0.7, 0.1, 0.0, 0.1, 0.1)
* 50 random calls (0.7, 0.1, 0.0, 0.1, 0.1)
* 500 random calls (0.7, 0.1, 0.0, 0.1, 0.1)
* 1000 random calls (0.7, 0.1, 0.0, 0.1, 0.1)
* 5 random calls (0.1, 0.7, 0.0, 0.1, 0.1)
* 50 random calls (0.1, 0.7, 0.0, 0.1, 0.1)
* 500 random calls (0.1, 0.7, 0.0, 0.1, 0.1)
* 1000 random calls (0.1, 0.7, 0.0, 0.1, 0.1)
==> passed
Test 3: check random calls to enqueue(), sample(), and size()
* 5 random calls (0.8, 0.0, 0.1, 0.0, 0.1)
* 50 random calls (0.8, 0.0, 0.1, 0.0, 0.1)
* 500 random calls (0.8, 0.0, 0.1, 0.0, 0.1)
* 1000 random calls (0.8, 0.0, 0.1, 0.0, 0.1)
* 5 random calls (0.1, 0.0, 0.8, 0.0, 0.1)
* 50 random calls (0.1, 0.0, 0.8, 0.0, 0.1)
* 500 random calls (0.1, 0.0, 0.8, 0.0, 0.1)
* 1000 random calls (0.1, 0.0, 0.8, 0.0, 0.1)
==> passed
Test 4: check random calls to enqueue(), dequeue(), sample(), isEmpty(), and size()
* 5 random calls (0.6, 0.1, 0.1, 0.1, 0.1)
* 50 random calls (0.6, 0.1, 0.1, 0.1, 0.1)
* 500 random calls (0.6, 0.1, 0.1, 0.1, 0.1)
* 1000 random calls (0.6, 0.1, 0.1, 0.1, 0.1)
* 5 random calls (0.1, 0.6, 0.1, 0.1, 0.1)
* 50 random calls (0.1, 0.6, 0.1, 0.1, 0.1)
* 500 random calls (0.1, 0.6, 0.1, 0.1, 0.1)
* 1000 random calls (0.1, 0.6, 0.1, 0.1, 0.1)
==> passed
Test 5: call dequeue() and sample() from an empty randomized queue
* dequeue()
* sample()
==> passed
Test 6: create multiple randomized queue objects at the same time
* n = 10
* n = 100
==> passed
Test 7: check that iterator() returns correct items after a sequence
of n enqueue() operations
* n = 10
* n = 50
==> passed
Test 8: check that iterator() returns correct items after sequence
of m enqueue() and dequeue() operations
* m = 10
* m = 1000
==> passed
Test 9: create two nested iterators over the same randomized queue
* n = 10
* n = 50
==> passed
Test 10: create two parallel iterators over the same randomized queue
* n = 10
* n = 50
==> passed
Test 11: create two iterators over different randomized queues
==> passed
Test 12: create an iterator and check calls to next() and hasNext()
* 10 consecutive calls to hasNext() on a deque of size 10
* 10 consecutive calls to next() on a deque of size 10
* 50 random intermixed calls to next() and hasNext() on a deque of size 10
* 1000 random intermixed calls to next() and hasNext() on a deque of size 100
==> passed
Test 13: create RandomizedQueue objects of different parameterized types
==> passed
Test 14: check randomness of sample() by enqueueing n items, repeatedly calling
sample(), and counting the frequency of each item
* n = 3, trials = 12000
* n = 5, trials = 12000
* n = 8, trials = 12000
* n = 10, trials = 12000
==> passed
Test 15: check randomness of dequeue() by enqueueing n items, dequeueing n items,
and seeing whether each of the n! permutations is equally likely
* n = 2, trials = 12000
* n = 3, trials = 12000
* n = 4, trials = 12000
* n = 5, trials = 12000
==> passed
Test 16: check randomness of iterator() by enqueueing n items, iterating over those
n items, and seeing whether each of the n! permutations is equally likely
* n = 2, trials = 12000
* n = 3, trials = 12000
* n = 4, trials = 12000
* n = 5, trials = 12000
==> passed
Test 17: call enqueue() with a null argument
==> passed
Test 18: check that remove() and next() throw the specified exceptions in iterator()
==> passed
Test 19: call iterator() when randomized queue is empty
==> passed
Total: 19/19 tests passed!
================================================================
********************************************************************************
* TESTING CORRECTNESS (substituting reference RandomizedQueue and Deque)
********************************************************************************
Testing correctness of Permutation
*-----------------------------------------------------------
Tests 1-5 call the main() function directly, resetting standard input
before each call.
Running 9 total tests.
Test 1a: check formatting for sample inputs from assignment specification
% java Permutation 3 < distinct.txt
E
D
I
% java Permutation 3 < distinct.txt
F
B
A
% java Permutation 8 < duplicates.txt
CC
BB
CC
AA
BB
BB
BB
BB
==> passed
Test 1b: check formatting for other inputs
% java Permutation 8 < mediumTale.txt
wisdom
it
best
of
of
foolishness
times
it
% java Permutation 0 < distinct.txt
[no output]
==> passed
Test 2: check that main() reads all data from standard input
* filename = distinct.txt, k = 3
* filename = distinct.txt, k = 3
* filename = duplicates.txt, k = 8
* filename = mediumTale.txt, k = 8
==> passed
Test 3a: check that main() prints each item from the sequence at most once
(for inputs with no duplicate strings)
* filename = distinct.txt, k = 3
* filename = distinct.txt, k = 1
* filename = distinct.txt, k = 9
* filename = permutation6.txt, k = 6
* filename = permutation10.txt, k = 10
==> passed
Test 3b: check that main() prints each item from the sequence at most once
(for inputs with duplicate strings)
* filename = duplicates.txt, k = 8
* filename = duplicates.txt, k = 3
* filename = permutation8.txt, k = 6
* filename = permutation8.txt, k = 2
* filename = tinyTale.txt, k = 10
==> passed
Test 3c: check that main() prints each item from the sequence at most once
(for inputs with newlines)
* filename = mediumTale.txt, k = 10
* filename = mediumTale.txt, k = 20
* filename = tale.txt, k = 10
* filename = tale.txt, k = 50
==> passed
Test 4: check main() when k = 0
* filename = distinct.txt, k = 0
* filename = distinct.txt, k = 0
==> passed
Test 5a: check that permutations are uniformly random
(for inputs with no duplicate strings)
* filename = permutation4.txt, k = 1
* filename = permutation4.txt, k = 2
* filename = permutation4.txt, k = 3
* filename = permutation4.txt, k = 4
* filename = permutation6.txt, k = 2
==> passed
Test 5b: check that permutations are uniformly random
(for inputs with duplicate strings)
* filename = permutation5.txt, k = 1
* filename = permutation5.txt, k = 2
* filename = permutation5.txt, k = 3
* filename = duplicates.txt, k = 3
* filename = permutation8.txt, k = 2
==> passed
Total: 9/9 tests passed!
================================================================
********************************************************************************
* TIMING (substituting reference RandomizedQueue and Deque)
********************************************************************************
Timing Permutation
*-----------------------------------------------------------
Running 23 total tests.
Test 1: count calls to methods in StdIn
* java Permutation 5 < distinct.txt
* java Permutation 10 < permutation10.txt
* java Permutation 1 < mediumTale.txt
* java Permutation 20 < tale.txt
* java Permutation 100 < tale.txt
* java Permutation 16412 < tale.txt
==> passed
Test 2: count calls to methods in Deque and RandomizedQueue
* java Permutation 5 < distinct.txt
* java Permutation 10 < permutation10.txt
* java Permutation 1 < mediumTale.txt
* java Permutation 20 < tale.txt
* java Permutation 100 < tale.txt
* java Permutation 16412 < tale.txt
==> passed
Test 3: count calls to methods in StdRandom
* java Permutation 5 < distinct.txt
* java Permutation 10 < permutation10.txt
* java Permutation 1 < mediumTale.txt
* java Permutation 20 < tale.txt
* java Permutation 100 < tale.txt
* java Permutation 16412 < tale.txt
==> passed
Test 4: Time main() with k = 5, for inputs containing n random strings
n seconds
------------------------------
=> passed 1000 0.00
=> passed 2000 0.00
=> passed 4000 0.00
=> passed 8000 0.00
=> passed 16000 0.01
=> passed 32000 0.01
=> passed 64000 0.03
=> passed 128000 0.05
=> passed 256000 0.08
=> passed 512000 0.17
==> 10/10 tests passed
Test 5: Time main() with k = 1000, for inputs containing n random strings
n seconds
------------------------------
=> passed 1000 0.00
=> passed 2000 0.00
=> passed 4000 0.00
=> passed 8000 0.00
=> passed 16000 0.01
=> passed 32000 0.01
=> passed 64000 0.02
=> passed 128000 0.04
=> passed 256000 0.08
=> passed 512000 0.20
==> 10/10 tests passed
Total: 23/23 tests passed!
================================================================
********************************************************************************
* MEMORY
********************************************************************************
Analyzing memory of Permutation
*-----------------------------------------------------------
Running 2 total tests.
Test 1: check that only one Deque or RandomizedQueue object is created
* filename = distinct.txt, n = 9, k = 1
* filename = distinct.txt, n = 9, k = 2
* filename = distinct.txt, n = 9, k = 4
* filename = tinyTale.txt, n = 12, k = 10
* filename = tale.txt, n = 138653, k = 50
==> passed
Test 2: check that the maximum size of any Deque or RandomizedQueue object
created is between k and n
* filename = distinct.txt, n = 9, k = 1
* filename = distinct.txt, n = 9, k = 2
* filename = distinct.txt, n = 9, k = 4
* filename = tinyTale.txt, n = 12, k = 10
* filename = tale.txt, n = 138653, k = 5
* filename = tale.txt, n = 138653, k = 50
* filename = tale.txt, n = 138653, k = 500
* filename = tale.txt, n = 138653, k = 5000
* filename = tale.txt, n = 138653, k = 50000
==> passed
Test 3 (bonus): check that maximum size of any or Deque or RandomizedQueue object
created is equal to k
* filename = tale.txt, n = 138653, k = 5
- max size of RandomizedQueue object = 138653
* filename = tale.txt, n = 138653, k = 50
- max size of RandomizedQueue object = 138653
* filename = tale.txt, n = 138653, k = 500
- max size of RandomizedQueue object = 138653
* filename = tale.txt, n = 138653, k = 5000
- max size of RandomizedQueue object = 138653
* filename = tale.txt, n = 138653, k = 50000
- max size of RandomizedQueue object = 138653
==> FAILED
Total: 2/2 tests passed!
================================================================
********************************************************************************
* MEMORY
********************************************************************************
Analyzing memory of Deque
*-----------------------------------------------------------
For tests 1-4, the maximum amount of memory allowed for a Deque
containing n items is 48n + 192.
Running 48 total tests.
Test 1a-1i: total memory usage after inserting n items,
where n is a power of 2
n bytes
----------------------------------------------------------
=> passed 32 1576
=> passed 64 3112
=> passed 128 6184
=> passed 256 12328
=> passed 512 24616
=> passed 1024 49192
=> passed 2048 98344
=> passed 4096 196648
=> passed 8192 393256
==> 9/9 tests passed
Memory: 48.00 n + 40.00 (R^2 = 1.000)
Test 2a-2i: Total memory usage after inserting n items,
when n is one more than a power of 2.
n bytes
----------------------------------------------------------
=> passed 33 1624
=> passed 65 3160
=> passed 129 6232
=> passed 257 12376
=> passed 513 24664
=> passed 1025 49240
=> passed 2049 98392
=> passed 4097 196696
=> passed 8193 393304
==> 9/9 tests passed
Memory: 48.00 n + 40.00 (R^2 = 1.000)
Test 3a-3i: Total memory usage after inserting 2n-1 items, and then
deleting n-1 items, when n is one more than a power of 2.
n bytes
----------------------------------------------------------
=> FAILED 33 3160 (1.8x)
=> FAILED 65 6232 (1.9x)
=> FAILED 129 12376 (1.9x)
=> FAILED 257 24664 (2.0x)
=> FAILED 513 49240 (2.0x)
=> FAILED 1025 98392 (2.0x)
=> FAILED 2049 196696 (2.0x)
=> FAILED 4097 393304 (2.0x)
=> FAILED 8193 786520 (2.0x)
==> 0/9 tests passed
Memory: 96.00 n - 8.00 (R^2 = 1.000)
Test 4a-4e: Total memory usage after inserting n items,
and then deleting all but one item
(should not grow with n or be too large of a constant).
n bytes
----------------------------------------------------------
=> FAILED 32 1576 (6.6x)
=> FAILED 64 3112 (13.0x)
=> FAILED 128 6184 (25.8x)
=> FAILED 256 12328 (51.4x)
=> FAILED 512 24616 (102.6x)
=> FAILED 1024 49192 (205.0x)
=> FAILED 2048 98344 (409.8x)
=> FAILED 4096 196648 (819.4x)
=> FAILED 8192 393256 (2e+03x)
==> 0/9 tests passed
Memory: 48.00 n + 40.00 (R^2 = 1.000)
Test 5a-5e: Total memory usage of iterator after inserting n items
(should not grow with n or be too large of a constant).
n bytes
----------------------------------------------------------
=> passed 32 32
=> passed 64 32
=> passed 128 32
=> passed 256 32
=> passed 512 32
=> passed 1024 32
=> passed 2048 32
=> passed 4096 32
=> passed 8192 32
==> 9/9 tests passed
Memory: 32.00 (R^2 = 1.000)
Test 6a: Insert n strings; delete them one at a time, checking for
loitering after each deletion. The probabilities of addFirst()
and addLast() are (p1, p2), respectively. The probabilities of
removeFirst() and removeLast() are (q1, q2), respectively.
* 100 random insertions (1.0, 0.0) and 100 random deletions (1.0, 0.0)
- loitering observed during 99 of 100 deletions
- maximum number of loitered objects at one time = 99
* 100 random insertions (1.0, 0.0) and 100 random deletions (0.0, 1.0)
- loitering observed during 99 of 100 deletions
- maximum number of loitered objects at one time = 99
* 100 random insertions (0.0, 1.0) and 100 random deletions (1.0, 0.0)
- loitering observed during 99 of 100 deletions
- maximum number of loitered objects at one time = 99
* 100 random insertions (0.0, 1.0) and 100 random deletions (0.0, 1.0)
- loitering observed during 99 of 100 deletions
- maximum number of loitered objects at one time = 99
* 100 random insertions (0.5, 0.5) and 100 random deletions (0.5, 0.5)
- loitering observed during 100 of 100 deletions
- maximum number of loitered objects at one time = 100
==> FAILED
Test 6b: Perform random operations, checking for loitering after
each operation. The probabilities of addFirst(), addLast(),
removeFirst(), and removeLast() are (p1, p2, p3, p4),
respectively.
* 100 random operations (0.8, 0.0, 0.2, 0.0)
- loitering detected after operation 8 of 100
- sequence of operations was:
deque.addFirst("FMBFPWBBCO")
deque.removeFirst() ==> FMBFPWBBCO
deque.addFirst("ZWRMOIKRIQ")
deque.addFirst("GPYDWDNAAX")
deque.addFirst("DEAJRXXZWQ")
deque.addFirst("KKIZCFTCBF")
deque.addFirst("OSBGOHRLKR")
deque.removeFirst() ==> OSBGOHRLKR
- loitered object(s):
OSBGOHRLKR
* 100 random operations (0.8, 0.0, 0.0, 0.2)
- loitering detected after operation 5 of 100
- sequence of operations was:
deque.addFirst("YXOTYWESGS")
deque.removeLast() ==> YXOTYWESGS
deque.addFirst("WXGLOOJFAO")
deque.addFirst("LJUWOHOQKG")
deque.removeLast() ==> WXGLOOJFAO
- loitered object(s):
WXGLOOJFAO
* 100 random operations (0.0, 0.8, 0.2, 0.0)
- loitering detected after operation 5 of 100
- sequence of operations was:
deque.addLast("GNOARDSLCA")
deque.addLast("AOXCLPDORI")
deque.addLast("DLRKERAOLO")
deque.addLast("ULCIWKQWIQ")
deque.removeFirst() ==> GNOARDSLCA
- loitered object(s):
GNOARDSLCA
* 100 random operations (0.0, 0.8, 0.0, 0.2)
- loitering detected after operation 31 of 100
* 100 random operations (0.4, 0.4, 0.1, 0.1)
- loitering detected after operation 14 of 100
* 100 random operations (0.2, 0.2, 0.3, 0.3)
- loitering detected after operation 27 of 100
==> FAILED
Test 7: worst-case constant memory allocated or de-allocated
per deque operation?
* 128 random operations
* 256 random operations
* 512 random operations
==> passed
Min observed memory for Deque: 48.00 n + 40.00 (R^2 = 1.000)
Max observed memory for Deque: 96.00 n - 8.00 (R^2 = 1.000)
Total: 28/48 tests passed!
================================================================
Analyzing memory of RandomizedQueue
*-----------------------------------------------------------
For Tests 1-5, the maximum amount of memory allowed for
a RandomizedQueue containing n items is 48n + 192.
For Test 6, the maximum amount of memory allowed for
a RandomizedQueue iterator over n items is 8n + 72.
Test 1a-1i: Total memory usage after inserting n items
when n is a power of 2.
n bytes
----------------------------------------------------------
=> passed 32 1576
=> passed 64 3112
=> passed 128 6184
=> passed 256 12328
=> passed 512 24616
=> passed 1024 49192
=> passed 2048 98344
=> passed 4096 196648
=> passed 8192 393256
==> 9/9 tests passed
Memory: 48.00 n + 40.00 (R^2 = 1.000)
Test 2a-2i: Total memory usage after inserting n items,
when n is one more than a power of 2.
n bytes
----------------------------------------------------------
=> passed 33 1624
=> passed 65 3160
=> passed 129 6232
=> passed 257 12376
=> passed 513 24664
=> passed 1025 49240
=> passed 2049 98392
=> passed 4097 196696
=> passed 8193 393304
==> 9/9 tests passed
Memory: 48.00 n + 40.00 (R^2 = 1.000)
Test 3a-3i: Total memory usage after inserting 2n-1 items, and then
deleting n-1 items, when n is one more than a power of 2.
n bytes
----------------------------------------------------------
=> passed 33 1624
=> passed 65 3160
=> passed 129 6232
=> passed 257 12376
=> passed 513 24664
=> passed 1025 49240
=> passed 2049 98392
=> passed 4097 196696
=> passed 8193 393304
==> 9/9 tests passed
Memory: 48.00 n + 40.00 (R^2 = 1.000)
Test 4a-4i: Total memory usage after inserting n items, deleting n items,
then inserting n times, when n is a power of 2.
n bytes
----------------------------------------------------------
=> passed 32 1576
=> passed 64 3112
=> passed 128 6184
=> passed 256 12328
=> passed 512 24616
=> passed 1024 49192
=> passed 2048 98344
=> passed 4096 196648
=> passed 8192 393256
==> 9/9 tests passed
Memory: 48.00 n + 40.00 (R^2 = 1.000)
Test 5a-5i: Total memory usage after inserting n items,
and then deleting all but one item.
n bytes
----------------------------------------------------------
=> passed 32 88
=> passed 64 88
=> passed 128 88
=> passed 256 88
=> passed 512 88
=> passed 1024 88
=> passed 2048 88
=> passed 4096 88
=> passed 8192 88
==> 9/9 tests passed
Memory: 88.00 (R^2 = 1.000)
Test 6a-6i: Total memory usage of iterator after inserting n items.
n bytes
----------------------------------------------------------
=> passed 32 96
=> passed 64 128
=> passed 128 192
=> passed 256 320
=> passed 512 576
=> passed 1024 1088
=> passed 2048 2112
=> passed 4096 4160
=> passed 8192 8256
==> 9/9 tests passed
Memory: 1.00 n + 64.00 (R^2 = 1.000)
Test 7a: Insert 100 strings; delete them one at a time, checking
for loitering after each deletion.
==> passed
Test 7b: Perform random operations, checking for loitering after
each operation. The probabilities of enqueue(), dequeue(),
and sample() are (p1, p2, p3), respectively.
* 200 random operations (0.8, 0.2, 0.0)
* 200 random operations (0.2, 0.8, 0.0)
* 200 random operations (0.6, 0.2, 0.2)
* 200 random operations (0.2, 0.4, 0.4)
==> passed
Test 8: Insert T items into queue; then iterate over queue and check
that worst-case constant memory is allocated or deallocated
per iterator operation.
* T = 64
* T = 128
* T = 256
==> passed
Test 9: Total memory usage after inserting n items, seeking to identify
values of n where memory usage is minimized as a function of n.
n bytes
----------------------------------------------------------
=> passed 8 424
=> passed 16 808
=> passed 32 1576
=> passed 64 3112
=> passed 128 6184
=> passed 256 12328
=> passed 512 24616
=> passed 1024 49192
=> passed 2048 98344
==> 9/9 tests passed
Memory: 48.00 n + 40.00 (R^2 = 1.000)
Test 10: Total memory usage after inserting 4096 items, then successively
deleting items, seeking values of n where memory usage is maximized
as a function of n
n bytes
----------------------------------------------------------
WARNING: the time limit of 60 seconds was exceeded, so not all tests could be completed.
This usually indicates a performance bug or an infinite loop.
================================================================
********************************************************************************
* TIMING
********************************************************************************
Timing Deque
*-----------------------------------------------------------
Running 103 total tests.
Test 1a-1k: make n calls to addFirst() followed by n calls to removeFirst()
n seconds
----------------------------------
=> passed 1024 0.00
=> passed 2048 0.00
=> passed 4096 0.00
=> passed 8192 0.00
=> passed 16384 0.00
=> passed 32768 0.00
=> passed 65536 0.00
=> passed 128000 0.00
=> passed 256000 0.00
=> passed 512000 0.01
=> passed 1024000 0.03
==> 11/11 tests passed
Test 2a-2k: make n calls to addLast() followed by n calls to removeLast()
n seconds
----------------------------------
=> passed 1024 0.00
=> passed 2048 0.00
=> passed 4096 0.00
=> passed 8192 0.00
=> passed 16384 0.00
=> passed 32768 0.00
=> passed 65536 0.00
=> passed 128000 0.00
=> passed 256000 0.01
=> passed 512000 0.01
=> passed 1024000 0.02
==> 11/11 tests passed
Test 3a-3k: make n calls to addFirst() followed by n calls to removeLast()
n seconds
----------------------------------
=> passed 1024 0.00
=> passed 2048 0.00
=> passed 4096 0.00
=> passed 8192 0.00
=> passed 16384 0.00
=> passed 32768 0.00
=> passed 65536 0.00
=> passed 128000 0.00
=> passed 256000 0.01
=> passed 512000 0.01
=> passed 1024000 0.02
==> 11/11 tests passed
Test 4a-4k: make n calls to addLast() followed by n calls to removeFirst()
n seconds
----------------------------------
=> passed 1024 0.00
=> passed 2048 0.00
=> passed 4096 0.00
=> passed 8192 0.00
=> passed 16384 0.00
=> passed 32768 0.00
=> passed 65536 0.00
=> passed 128000 0.00
=> passed 256000 0.01
=> passed 512000 0.01
=> passed 1024000 0.02
==> 11/11 tests passed
Test 5a-5g: make n random calls to addFirst(), removeFirst(), isEmpty(), and size()
with probabilities (0.7, 0.1, 0.1, 0.1)
n seconds
------------------------------
=> passed 1024 0.00
=> passed 2048 0.00
=> passed 4096 0.00
=> passed 8192 0.00
=> passed 16384 0.00
=> passed 32768 0.00
=> passed 65536 0.00
=> passed 128000 0.01
=> passed 256000 0.01
=> passed 512000 0.02
=> passed 1024000 0.04
=> passed 2048000 0.07
==> 12/12 tests passed
Test 6a-6g: make n random calls to addLast(), removeLast(), isEmpty(), and size(),
with probabilities (0.7, 0.1, 0.1, 0.1)
n seconds
------------------------------
=> passed 1024 0.00
=> passed 2048 0.00
=> passed 4096 0.00
=> passed 8192 0.00
=> passed 16384 0.00
=> passed 32768 0.00
=> passed 65536 0.00
=> passed 128000 0.01
=> passed 256000 0.01
=> passed 512000 0.02
=> passed 1024000 0.06
=> passed 2048000 0.06
==> 12/12 tests passed
Test 7a-7g: make n random calls to addFirst(), addLast(), removeFirst(), removeLast(),
isEmpty(), and size() with probabilities (0.3, 0.3, 0.1, 0.1, 0.1, 0.1)
n seconds
------------------------------
=> passed 1024 0.00
=> passed 2048 0.00
=> passed 4096 0.00
=> passed 8192 0.00
=> passed 16384 0.00
=> passed 32768 0.00
=> passed 65536 0.00
=> passed 128000 0.00
=> passed 256000 0.01
=> passed 512000 0.02
=> passed 1024000 0.04
=> passed 2048000 0.07
==> 12/12 tests passed
Test 8a-8g: make n calls to addFirst(); iterate over the n items by calling
next() and hasNext()
n seconds
------------------------------
=> passed 1024 0.00
=> passed 2048 0.00
=> passed 4096 0.00
=> passed 8192 0.00
=> passed 16384 0.00
=> passed 32768 0.00
=> passed 65536 0.00
=> passed 128000 0.00
=> passed 256000 0.01
=> passed 512000 0.01
=> passed 1024000 0.03
=> passed 2048000 0.05
==> 12/12 tests passed
Test 9a-9k: make n calls to addFirst()/addLast(); interleave n calls each to
removeFirst(), removeLast(), addFirst(), and addLast()
n seconds
----------------------------------
=> passed 1025 0.00
=> passed 2049 0.00
=> passed 4097 0.00
=> passed 8193 0.00
=> passed 16385 0.00
=> passed 32769 0.00
=> passed 65537 0.01
=> passed 128001 0.01
=> passed 256001 0.02
=> passed 512001 0.03
=> passed 1024001 0.06
==> 11/11 tests passed
Total: 103/103 tests passed!
================================================================
Timing RandomizedQueue
*-----------------------------------------------------------
Running 67 total tests.
Test 1: make n calls to enqueue() followed by n calls to dequeue();
count calls to StdRandom
* n = 10
* n = 100
* n = 1000
==> passed
Test 2: make n calls to enqueue() follwed by n calls to sample();
count calls to StdRandom
* n = 10
* n = 100
* n = 1000
==> passed
Test 3: make n calls to enqueue() and iterate over the n items;
count calls to StdRandom
* n = 10
- iteration should call StdRandom() at most once per item
- number of items = 10
- number of elementary StdRandom() operations = 41
* n = 100
- iteration should call StdRandom() at most once per item
- number of items = 100
- number of elementary StdRandom() operations = 419
* n = 1000
- iteration should call StdRandom() at most once per item
- number of items = 1000
- number of elementary StdRandom() operations = 6621
==> FAILED
Test 4a-k: make n calls to enqueue() followed by n calls to dequeue()
n seconds
----------------------------------
=> passed 1024 0.00
=> passed 2048 0.00
=> passed 4096 0.01
=> passed 8192 0.03
=> passed 16384 0.11
=> passed 32768 0.44
=> FAILED 65536 2.11
[ Most likely one of your operations is not constant time. ]
==> 6/11 tests passed
Test 5a-k: make n calls to enqueue() followed by n random calls to
enqueue(), sample(), dequeue(), isEmpty(), and size()
with probabilities (0.2, 0.2, 0.2, 0.2, 0.2)
n seconds
----------------------------------
=> passed 1024 0.00
=> passed 2048 0.00
=> passed 4096 0.01
=> passed 8192 0.02
=> passed 16384 0.08
=> passed 32768 0.30
=> FAILED 65536 1.35
[ Most likely one of your operations is not constant time. ]
==> 6/11 tests passed
Test 6a-k: make n calls to enqueue() followed by n random calls to
enqueue(), sample(), dequeue(), isEmpty(), and size()
with probabilities (0.6, 0.1, 0.1, 0.1, 0.1)
n seconds
----------------------------------
=> passed 1024 0.00
=> passed 2048 0.00
=> passed 4096 0.00
=> passed 8192 0.01
=> passed 16384 0.04
=> passed 32768 0.19
=> passed 65536 0.78
=> FAILED 128000 3.08
[ Most likely one of your operations is not constant time. ]
==> 7/11 tests passed
Test 7a-k: make n calls to enqueue() followed by n random calls to
enqueue(), sample(), dequeue(), isEmpty(), and size()
with probabilities (0.1, 0.1, 0.6, 0.1, 0.1)
n seconds
----------------------------------
=> passed 1024 0.00
=> passed 2048 0.00
=> passed 4096 0.01
=> passed 8192 0.03
=> passed 16384 0.12
=> passed 32768 0.55
=> FAILED 65536 2.55
[ Most likely one of your operations is not constant time. ]
==> 6/11 tests passed
Test 8a-k: make n calls to enqueue() followed by n calls each to
next() and hasNext().
n seconds
----------------------------------
=> passed 1024 0.00
=> passed 2048 0.00
=> passed 4096 0.01
=> passed 8192 0.04
=> passed 16384 0.16
=> passed 32768 0.66
=> FAILED 65536 2.77
[ Most likely one of your operations is not constant time. ]
==> 6/11 tests passed
Test 9a-i: make 100 calls to enqueue; 99 calls to dequeue;
n calls to enqueue(); then call dequeue() three times,
followed by enqueue() three times, and repeat n times.
n seconds
----------------------------------
=> passed 1024 0.00
=> passed 2048 0.01
=> passed 4096 0.05
=> passed 8192 0.18
=> passed 16384 0.91
=> FAILED 32768 5.57
[ Most likely one of your operations is not constant time. ]
==> 5/9 tests passed
Total: 38/67 tests passed!
================================================================
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment