| Home |
| Expertise |
| Pricing |
| Examples |
| FAQ |
| Contact |
| Bookmark Us |
2. Circular List in Java (cost: $40)
1. Making Change in C
(Cost: $18)
Write a C program that given coins of 5, 10 and
25 cents will find all the possible combinations
to make change for a given amount of money. For
example the amount of 35 cents can be changed in
6 different ways:
35 = 25 + 10
35 = 25 + 5 + 5
35 = 10 + 10 + 10 + 5
35 = 10 + 10 + 5 + 5 + 5
35 = 10 + 5 + 5 + 5 + 5 + 5
35 = 5 + 5 + 5 + 5 + 5 + 5 + 5
Solution
file: change.c
#include <stdio.h> #include <stdlib.h> /* Disperses remainingSum into all possible combinations */ void disperseRemainingSum( int remainingSum, int *noOfSolutions, int coins[], int coinCount, int coinPiece[], int currCoinPiece ); int main(int argc, char *argv[]) { int coins[1000]; int coinPiece[3] = { 25, 10, 5 }; int noOfSolutions = 0; int amount; if (argc == 2) amount = atoi(argv[1]); else { printf( "Enter amount to be changed: " ); scanf( "%d", &amount ); } disperseRemainingSum( amount, &noOfSolutions, coins, 0, coinPiece, 0); if ( noOfSolutions == 0 ) printf( "%d can't be changed.\n", amount ); system("PAUSE"); return EXIT_SUCCESS; } void disperseRemainingSum( int remainingSum, int *noOfSolutions, int coins[], int coinCount, int coinPiece[], int currCoinPiece ) { int i; /* If already dispersed, print results and return */ if ( remainingSum == 0 ) { int i; ++(*noOfSolutions); for ( i = 0; i < coinCount; ++i ) printf( "%d ", coins[i] ); printf( "\n" ); return; } /* Disperse the remaining with each possible coin */ for ( i = currCoinPiece; i < 3; ++i ) { int newRemainingSum = remainingSum - coinPiece[i]; if ( newRemainingSum >= 0 ) { coins[coinCount] = coinPiece[i]; disperseRemainingSum( newRemainingSum, noOfSolutions, coins, coinCount + 1, coinPiece, i ); } } }
2. Circular List in Java
(Cost: $40)
Implement a PriorityQueue using a circular double linked list. Your class should implement the Java API Queue interface except that the iterator() method may throw the UnsupportedOperationException. There should only be one reference to the circular linked list, this is the current smallest (highest priority) item. When a new item is inserted, it is linked next to the current smallest. If it is smaller, it then becomes the new smallest. Thus insertion is O(1). When the smallest item is removed, you have to search for the next smallest; thus remove/pop is O(n). The priority queue will only hold Comparable objects. You will need to define a static inner class (also called a nested class) to represent the nodes. You should submit the class as the file CircularListPriorityQueue.java as follows:
import java.util.AbstractQueue;
import java.util.Iterator;
/** The CircularListPriorityQueue implements the Queue interface
* by building a circular linked list. The contract for the
* peek and poll methods differs from the normal Queue contract
* in that the smallest item in the queue is returned/removed.
* This implementation only store Comparable items. Attempt
* to store non-Comparable items will result in a
* ClassCastException.
*/
public class CircularListPriorityQueue<E> extends AbstractQueue<E>
{
/** Insert an item into the queue based on its
* priority
* @pre The item to be inserted implements the
* Comparable interface.
* @post The item is in the priority queue.
* @param item The Object to be inserted.
* @return true To indicate insertion was sucessful.
* @throws ClassCastException If no Comparator is
* specified and the item inserted does not implement
* the Comparable interface.
* @throws NullPointerException if the item to be inserted
* is null.
*/
public boolean offer(E item)
{
/* Insert implementation here */
return true;
}
/** Peek at the first item in the queue.
* @post The priority queue remains unchanged
* @return The item with the smallest priority value
* or null if the queue is empty.
*/
public E peek()
{
/* Insert implementation here */
return null;
}
/** Remove the first item in the queue.
* @post The item is no longer in the queue.
* @return The item with the smallest priority value
* or null if the queue is empty.
*/
public E poll()
{
/* Insert implementation here */
return null;
}
/** Return the size of the priority queue
* @return The size of the queue
*/
public int size()
{
/* Insert implementation here */
return 0;
}
/** Return true if the queue is empty
* @return true if empty
*/
public boolean isEmpty()
{
return size() == 0;
}
/** Return an Iterator to the elements in the PriorityQueue.
* This method always throws the UnsupportedOperationException
* @throws UnsupportedOperationException
*/
public Iterator<E> iterator()
{
throw new UnsupportedOperationException( "iterator not supported");
}
}
Solution
file: CircularListPriorityQueue.java
import java.util.AbstractQueue;
import java.util.Iterator;
import java.util.Comparator;
/**
* The CircularListPriorityQueue implements the Queue interface
* by building a circular linked list. The contract for the
* peek and poll methods differs from the normal Queue contract
* in that the smallest item in the queue is returned/removed.
* This implementation only store Comparable items. Attempt
* to store non-Comparable items will result in a
* ClassCastException.
*/
public class CircularListPriorityQueue<E> extends
AbstractQueue<E>
{
private static class Node<E>
{
public E value;
public Node next;
Node(E value)
{
this.value = value;
}
}
private Node<E> smallestNode;
private int count;
/** Insert an item into the queue based on its
* priority
* @pre The item to be inserted implements the
* Comparable interface.
* @post The item is in the priority queue.
* @param item The Object to be inserted.
* @return true To indicate insertion was sucessful.
* @throws ClassCastException If no Comparator is
* specified and the item inserted does not implement
* the Comparable interface.
* @throws NullPointerException if the item to be inserted
* is null.
*/
public boolean offer(E item)
{
if (item == null)
throw new NullPointerException();
if ((item instanceof Comparable) == false)
throw new ClassCastException();
// If no items yet
if (smallestNode == null)
{
smallestNode = new Node(item);
smallestNode.next = smallestNode;
}
// If at least one item inside already
else
{
// First add it as next
Node newNode = new Node(item);
newNode.next = smallestNode.next;
smallestNode.next = newNode;
// If newly inserted is smallest, then correct smallestNode
// to point to newly inserted
if (((Comparable)smallestNode.value).
compareTo(smallestNode.next.value) > 0)
smallestNode = smallestNode.next;
}
++count;
return true;
}
/** Peek at the first item in the queue.
* @post The priority queue remains unchanged
* @return The item with the smallest priority value
* or null if the queue is empty.
*/
public E peek()
{
return smallestNode.value;
}
/** Remove the first item in the queue.
* @post The item is no longer in the queue.
* @return The item with the smallest priority value
* or null if the queue is empty.
*/
public E poll()
{
// If no elements
if (smallestNode == null)
return null;
// If only one element
if (smallestNode.next == smallestNode)
{
E e = smallestNode.value;
smallestNode = null;
--count;
return e;
}
// If more than one element
Node<E> n = smallestNode;
Node<E> secondSmallestNode = n.next;
// n will iterate until it comes right before smallestNode;
do
{
n = n.next;
if ( ((Comparable)secondSmallestNode.value).compareTo(n.value) > 0 )
{
secondSmallestNode = n;
}
} while (n.next != smallestNode);
// Remove smallestNode from the circle
n.next = smallestNode.next;
E e = smallestNode.value;
smallestNode = secondSmallestNode;
--count;
return e;
}
/** Return the size of the priority queue
* @return The size of the queue
*/
public int size()
{
return count;
}
/** Return true if the queue is empty
* @return true if empty
*/
public boolean isEmpty()
{
return size() == 0;
}
/** Return an Iterator to the elements in the PriorityQueue.
* This method always throws the UnsupportedOperationException
* @throws UnsupportedOperationException
*/
public Iterator<E> iterator()
{
throw new UnsupportedOperationException(
"iterator not supported");
}
}
file: Tester.java
public class Tester
{
public static void main(String[] args)
{
CircularListPriorityQueue pq = new CircularListPriorityQueue<Integer>();
System.out.println("Created an empty queue");
System.out.println("Que size is " + pq.size());
System.out.println("Will add 5 to the queue");
pq.add(5);
System.out.println("Assumed internal order: (5)");
System.out.println("Will add 8 to the queue");
pq.add(8);
System.out.println("Assumed internal order: (5) 8");
System.out.println("Will add 3 to the queue");
pq.add(3);
System.out.println("Assumed internal order: (3) 5 8");
System.out.println("Will add 9 to the queue");
pq.add(9);
System.out.println("Assumed internal order: (3) 9 5 8");
System.out.println("Que size is " + pq.size());
System.out.println("\nWill remove elements from the queue");
System.out.println("Removed: " + pq.poll());
System.out.println("Assumed internal order: 9 (5) 8");
System.out.println("Removed: " + pq.poll());
System.out.println("Assumed internal order: 9 (8)");
System.out.println("Removed: " + pq.poll());
System.out.println("Assumed internal order: (9)");
System.out.println("Removed: " + pq.poll());
System.out.println("Que size is " + pq.size());
}
}
