Lists Of Integers JUnit: P2J4Test.java This fourth transition lab from Python to Java contains four more interesting problems taken from the graded labs of the instructor's Python course. The four static methods to write here now deal with List data type of Java standard library (remember to put the necessary imports to the top of the source code of your class) whose behaviour and operations are essentially identical to those of ordinary Python lists of integers, except with a way more annoying syntax. public static List runningMedianOfThree(List items) Create and return a new List instance (use any concrete subtype of List of your choice) whose first two elements are the same as that of original items, after which each element equals the median of the three elements in the original list ending in that position. For example, when called with a list that prints out as [5, 2, 9, 1, 7, 4, 6, 3, 8], this method would return an object of type List that prints out as [5, 2, 5, 2, 7, 4, 6, 4, 6]. public static int firstMissingPositive(List items) Given a list whose each element is a positive integer, return the first positive integer missing from this list. For example, given a list [7, 5, 2, 3, 10, 2, 9999999, 4, 6, 3, 1, 9, 2], this method should return 8. Given one of the lists [], [6, 2, 12345678] or [42], this method should return 1. Since the pigeonhole principle dictates that the first missing positive integer of an n-element list must necessarily be less than or equal to n+1, a boolean array of that many elements can conveniently be used to keep track of which numbers you have seen to solve this problem efficiently in both time and space with two consecutive for-loops. public static void sortByElementFrequency(List items) Sort the elements of the given list in decreasing order of frequency, that is, how many times each element appears in this list. If two elements have the same frequency in the parameter list, those elements should end up in ascending order of values, the same way as we do in ordinary sorting of lists of integers. Note that this method does not return anything, but modifies items in place. For example, given a list object that prints out as [4, 99999, 2, 2, 99999, 4, 4, 4], after calling this method that list object would print out as [4, 4, 4, 4, 2, 2, 99999, 99999]. The return type of this method is void, because this method rearranges the elements of items in place instead of creating and returning a separate result list. As in all computer programming, you should allow the language and its standard library do your work for you instead of rolling your own logic. The method Collections.sort can be given a Comparator strategy object that compares two integers for their ordering. Start by building a local counter map of type Map used to keep track of how many times each value that you see appears inside the list. Next, define a local class that implements Comparator and whose compare method performs integer order comparisons by consulting this map for the counts of those elements to compute the answer, reverting to ordinary integer order comparison only in the case where these counts are equal. public static List factorFactorial(int n) Compute and return the list of prime factors of the factorial of n (that is, the product of all positive integers up to n), with those prime factors sorted in ascending order and with each factor appearing in this list exactly as many times as it would appear in the prime factorization of that factorial. For example, when called with n=10, this method would create and return a list of prime factors that prints out as [2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 5, 5, 7]. Multiplying together all those itty bitty prime numbers would produce the result of 3,628,800, which equals the product of the first ten positive integers. Remember that when n equals zero or one, its factorial equals one and therefore has no prime factors. The expected answer for these small but all the more important special cases is then an empty list. The factorial n! grows exponentially, so when n goes up to not just mere eleven but even past that mythical barrier, these factorials would no longer be representable inside the 32 bits used to house the primitive int type of Java. Since this method must be able to work for values of n that are in the thousands and their factorials consist of tens of thousands of digits, you should not first compute that entire factorial of n and only then start breaking the resulting behemoth down to its prime factors. Instead, you need to build up the list of prime factors as you go, by appending the prime factors of the integer that you are currently multiplying into the factorial. When you have done this for all integers up to n, sort the result list in ascending order before returning it.
Lists Of Integers
JUnit: P2J4Test.java
This fourth transition lab from Python to Java contains four more interesting problems taken from
the graded labs of the instructor's Python course. The four static methods to write here now deal
with List<Integer> data type of Java standard library (remember to put the necessary imports
to the top of the source code of your class) whose behaviour and operations are essentially identical
to those of ordinary Python lists of integers, except with a way more annoying syntax.
public static List<Integer> runningMedianOfThree(List<Integer> items)
Create and return a new List<Integer> instance (use any concrete subtype of List of your
choice) whose first two elements are the same as that of original items, after which each element
equals the median of the three elements in the original list ending in that position. For example,
when called with a list that prints out as [5, 2, 9, 1, 7, 4, 6, 3, 8], this method would
return an object of type List<Integer> that prints out as [5, 2, 5, 2, 7, 4, 6, 4, 6].
public static int firstMissingPositive(List<Integer> items)
Given a list whose each element is a positive integer, return the first positive integer missing from
this list. For example, given a list [7, 5, 2, 3, 10, 2, 9999999, 4, 6, 3, 1, 9, 2],
this method should return 8. Given one of the lists [], [6, 2, 12345678] or [42], this method
should return 1.
Since the pigeonhole principle dictates that the first missing positive integer of an n-element list
must necessarily be less than or equal to n+1, a boolean array of that many elements can
conveniently be used to keep track of which numbers you have seen to solve this problem efficiently
in both time and space with two consecutive for-loops.
public static void sortByElementFrequency(List<Integer> items)
Sort the elements of the given list in decreasing order of frequency, that is, how many times each
element appears in this list. If two elements have the same frequency in the parameter list, those
elements should end up in ascending order of values, the same way as we do in ordinary sorting
of lists of integers. Note that this method does not return anything, but modifies items in place.
For example, given a list object that prints out as [4, 99999, 2, 2, 99999, 4, 4, 4], after
calling this method that list object would print out as [4, 4, 4, 4, 2, 2, 99999, 99999].
The return type of this method is void, because this method rearranges the elements of items in
place instead of creating and returning a separate result list.
As in all computer programming, you should allow the language and its standard library do your
work for you instead of rolling your own logic. The method Collections.sort can be given a
Comparator<Integer> strategy object that compares two integers for their ordering. Start by
building a local counter map of type Map<Integer,Integer> used to keep track of how many
times each value that you see appears inside the list. Next, define a local class that implements
Comparator<Integer> and whose compare method performs integer order comparisons by
consulting this map for the counts of those elements to compute the answer, reverting to ordinary
integer order comparison only in the case where these counts are equal.
public static List<Integer> factorFactorial(int n)
Compute and return the list of prime factors of the factorial of n (that is, the product of all positive
integers up to n), with those prime factors sorted in ascending order and with each factor appearing
in this list exactly as many times as it would appear in the prime factorization of that factorial. For
example, when called with n=10, this method would create and return a list of prime factors that
prints out as [2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 5, 5, 7]. Multiplying together
all those itty bitty prime numbers would produce the result of 3,628,800, which equals the product
of the first ten positive integers. Remember that when n equals zero or one, its factorial equals one
and therefore has no prime factors. The expected answer for these small but all the more important
special cases is then an empty list.
The factorial n! grows exponentially, so when n goes up to not just mere eleven but even past that
mythical barrier, these factorials would no longer be representable inside the 32 bits used to house
the primitive int type of Java. Since this method must be able to work for values of n that are in the
thousands and their factorials consist of tens of thousands of digits, you should not first compute
that entire factorial of n and only then start breaking the resulting behemoth down to its prime
factors. Instead, you need to build up the list of prime factors as you go, by appending the prime
factors of the integer that you are currently multiplying into the factorial. When you have done this
for all integers up to n, sort the result list in ascending order before returning it.
Step by step
Solved in 2 steps with 3 images
