Description
Problem 1 (25 points): Squeeze an array:
Implement the squeeze() method in the provided ArraySqueeze class so that it performs as
indicated in the comment. The main() method in this class runs some test cases on squeeze(). You
should also add a few nontrivial and interesting test cases of your own at the end of main().
Problem 2 (35 points): Longest plateau:
Consider a non-empty int array ints. A contiguous subarray ints[ start .. start + len -1 ] (with
starting index start and length len) is called a flat if all elements of that subarray are equal.
Furthermore, such a subarray is called a plateau if it is flat and each of the elements ints[start -1]
and ints[start + len] that immediately proceed/succeed the subarray are either nonexistent (i.e.,
out of array’s index range) or are strictly smaller than the elements of the subarray. Your task
includes the design of a public static method longestPlateau(int[] ints) that returns (a compact
description of) the longest plateau of the input array ints. You may break ties arbitrarily if ints has
more than one longest plateau. The return type should be a 3-element array representing { value ,
start , len } : The first indicates common element value ints[start] of the plateau, the second its
starting index, the third its length.
Implement the longestPlateau() method in the provided ArrayLongestPlateau class so that it
performs as indicated. The main() method in this class runs some test cases on longestPlateau().
You should also add a few nontrivial and interesting test cases of your own at the end of main().
2
Problem 3 (40 points): Overlap/enclosure counts of windows:
Given an array of windows in the plane, we want to count how many overlapping and how many
enclosing pairs of windows there are (without double counting).
A window is the region of the plane enclosed by a rectangle with sides parallel to the x and y axes.
A window can be abstracted as an object with the 4 fields of doubles: (left, right, bottom, top).
These fields should satisfy the invariant: left < right and bottom < top. The window is the
Cartesian product of the x-interval [left, right] and the y-interval [bottom, top], i.e., the set of
points (x,y) in the plane such that left < x < right
and bottom < y < top .
Consider a pair of windows w0
and w1
. We say these two windows overlap if they have a common
interior point (just touching boundaries is not enough). We say w0
encloses w1
if no part of w1
is
outside w0
. (Note that the first relationship is symmetric but the second is anti-symmetric.)
Design a class called Window with the following fields and methods:
(Note: you should not confuse this with the Java API class java.awt.Window.)
• Protected fields left, right, bottom, top.
• A constructor that throws an exception named InvalidWindowException if the given 4 fields do
not satisfy the above invariant.
• Public getters and setters for these fields. The setters also throw InvalidWindowException if
invalid field value is attempted to be set.
• Boolean instance method encloses(Window w) returns true if and only if the instance window
encloses the argument window w.
• Boolean instance method overlaps(Window w) returns true if and only if the instance window
overlaps the argument window w.
• Static method overlapCount(Window[] windows) returns the number of (unordered)
overlapping pairs of windows in the input array windows.
• Static method enclosureCount(Window[] windows) returns the number of (ordered)
enclosing pairs of windows in the input array windows.
• main() method runs some interesting test cases of the above methods.
