You're asked to implement a data structure called ordered linked list with capacity limit. Make sure you name your implementation class as OrderedListImpl.
The following interface lists all the methods that should be implemented.
interface OrderedList {
int getMin();
int getMax();
int getMedian();
int add(int val);
OrderedList merge(OrderedList other);
remove(int val);
removeAll(int cap);
String toString();
boolean equals(Object o);
boolean isEmpty();
int size();
OrderedList intersection(OrderedList other);
//static OrderedList sort(LinkedList< Integer> other);
}
This interface above is for description purpose only. The actual interface file you should use has been provided separately. Don't modify the interface file.
The ordered linked list is different from ordinary linked list in that 1) the integer numbers in the ordered linked list are linked together in nondecreasing order; 2) it has a length limit.
Problem 1: It exposes two methods called getMin() and getMax(), which will return the minimum and the maximum number in the list. A more interesting method is called getMedian() which will return the median of all the numbers in the list. They throw the IllegalStateException exception if the ordered list is empty.
According to https://en.wikipedia.org/wiki/Median#Finite_data_set_of_numbers, median is defined as:
The median of a finite list of numbers is the "middle" number, when those numbers are listed in order from smallest to greatest.
If there is an odd number of numbers, the middle one is picked. For example, consider the list of numbers
1, 3, 3, 6, 7, 8, 9
This list contains seven numbers. The median is the fourth of them, which is 6. If there is an even number of observations, then there is no single middle value; the median is then usually defined to be the mean of the two middle values. For example, in the data set
1, 2, 3, 4, 5, 6, 8, 9
the median is the mean of the middle two numbers: this is (4+5)/2, which is 4.5.
Problem 2: The ordered linked list exposes a method called add(int val) that lets the caller add a number to the list. Note that the list has a capacity limit that is specified at construction time. When the caller tries to add a number while the list has already reached its capacity limit, there will be two cases:
1.If the number to be added is larger than the current minimum number in the list, the new number gets added to the list. And at the same time, in order to make sure the capacity limit doesn't get exceeded, the current minimum number should be removed from the list.
2.If the number to be added is smaller than or equal to the current minimum number in the list, the new number will not be added to the list.
On a different note, the constructor should throw IllegalArgumentException if the specified cap is less than or equal to 0.
Problem 3: The ordered linked list also exposes a method called merge(OrderedList other) that lets the caller merge two ordered linked lists. After merging, a new ordered linked list will be returned and the two original ones should remain unchanged. The new ordered list should have a capacity that equals the sum of the capacities of the two original lists. The new list also has all the numbers from the two original lists, linked in nondecreasing order.
Problem 4: The ordered linked list also exposes a method called remove(int val) which removes one occurrence of the specified val from the list. It also provides removeAll(int v) that removes all the numbers that are larger than or equal to `v` from the list.
Problem 5: Basic methods supported by the ordered linked list includes: toString(), equals(Object o), isEmtpy() and size():
toString() should convert the list to a string in the following format: [num1 num2 num3 ? ? ?] (brackets are needed, elements separated by one space)
The question marks represent the unused capacity. For example, an ordered linked list with capacity 7 and internal numbers 3->89->1289 will be printed as: [3 89 1289 ? ? ? ?]
equals(Object o) checks whether two lists are equal. Two lists are only considered equal if they have the same capacity and the same elements.
isEmpty() simply checks whether there is any number within the list.
size() simply returns the count of numbers in the list.
Problem 6: intersection(OrderedList other) returns all the common elements between this and another given ordered linked list. For example, the returned list should be 1->5->7 if this list is 1->2->5->6->7 and the other one is 1->3->4->5->7.
Problem 7: static OrderedList sort(LinkedList