All of the code for this project is in the cse143review/src folder. Inside, we have two packages: a datastructures package containing a basic linked list and binary tree implementation, and a problems package with a bunch of method stubs and TODOs.

For this project, you will design and implement each of the TODOs listed in the problems package. We also recommend taking a look at the files in the datastructures package as you go through the TODOs to get a better understanding of the data structures used for each problem.

Array Problems

For each of the array problems, you’ll be taking an array as a parameter.

For each of the array problems, do not,

  • add any additional imports,
  • or create new int[] objects for toString or rotateRight.

toString

Implement a method that returns a String representation of the contents of the input int[]. The String representation of the int[] should begin with “[” and end with “]”. Each pair of integers in the String representation should be separated by a comma and a space.

For example, if a variable named array refers to the array:

{5, 10, 15}

Then toString(array) should return the String:

"[5, 10, 15]"

On the other hand if the input array was:

{1}

Then toString(array) should return the String:

"[1]"

reverse

Implement a method that returns a new int[] containing the input int[]‘s elements in reverse order. The method should not modify the input array.

For example, if a variable named array refers to an array containing the values:

{1, 2, 3, 4, 5, 6, 7, 8, 9}

The call to reverse(array) should return an array containing the values:

{9, 8, 7, 6, 5, 4, 3, 2, 1}

rotateRight

Implement a method that rotates the values in the input int[] to the right (i.e., forward in position) by one. Each element moves right by one, except the last element, which moves to the front.

For example, if a variable named array refers to an array containing the values:

{3, 8, 19, 7}

The call of rotateRight(array) should modify it to store:

{7, 3, 8, 19}

A subsequent call of rotateRight(array) would leave the array as follows:

{19, 7, 3, 8}

Map Problems

For each of the Map problems, you’ll be taking a Map as a parameter (even if it doesn’t show up in the method signature).

contains3

Implement a method that returns true if any string occurs at least 3 times in the input list, and false otherwise. Use a map as auxiliary storage. For example, consider the following list:

["373", "is", "fun", "HI", "fun", "fun"]

contains3 should return true given this input because “fun” shows up at least 3 times.

intersect

Implement a method that takes as input two maps from Strings to Integers and returns a new map whose contents are the intersection of the two. The intersection of two maps is defined here as the set of keys-value pairs that exist in both maps. If some key K maps to value V in both the first and second map, include it in your result. If K does not exist as a key in both maps, or if K does not map to the same value V in both maps, exclude that pair from your result.

For example, consider the following two maps:

map1: {Janet=87, Logan=62, Whitaker=46, Alyssa=100, Stefanie=80, Jeff=88, Kim=52, Sylvia=95}
map2: {Logan=62, Kim=52, Whitaker=52, Jeff=88, Stefanie=80, Brian=60, Lisa=83, Sylvia=87}

Calling intersect(map1, map2) would return the following new map (the order of the key-value pairs does not matter):

{Logan=62, Stefanie=80, Jeff=88, Kim=52}

LinkedIntList problems

For each of the LinkedIntList problems, you’ll be taking a list as a parameter and then directly modifying the links between the nodes (the public fields) by using the ListNode class defined in LinkedIntList. You are allowed to have as many ListNode variables as you want (except when told explicitly).

For each of the LinkedIntList problems, do not,

  • call any methods on the LinkedIntList objects,
  • construct any new ListNode objects for reverse3 or firstToLast,
  • use other data structures such as arrays, lists, queues, etc.,
  • or mutate the data of any nodes.

reverse3

Implement a method to change the following LinkedIntList (you may assume it has these exact 3 elements):

front → 5 → 4 → 3 → /

Into this sequence of ListNode objects:

front → 3 → 4 → 5 → /

This is intended to be a warm-up to the other LinkedIntList problems, so you don’t need to generalize your solution to work for different lists.

firstToLast

Implement a method that moves the first element of the input LinkedIntList to the back end of the list.

Suppose a LinkedIntList variable named list stores the following elements from front (left) to back (right):

front → 18 → 4 → 27 → 9 → 54 → 5 → 63 → /

If you call firstToLast(list), the list would then store the elements in this order:

front → 4 → 27 → 9 → 54 → 5 → 63 → 18 → /

If the list is empty or has just one element, its contents should not be modified.

concatenate

Implement a method which takes two LinkedIntLists as input and returns a new list containing all the items of the first followed by all the items of the second. Don’t modify the input lists; use the new keyword to create new objects instead. Your implementation should run in linear time i.e. without the use of nested for-loops.

list1: front → 1 → 2 → 3 → /
list2: front → 4 → 5 → 6 → /

If you made the call concatenate(list1, list2), then it should return a new list:

return: front → 1 → 2 → 3 → 4 → 5 → 6 → /

and list1 and list2 would remain unchanged:

list1: front → 1 → 2 → 3 → /
list2: front → 4 → 5 → 6 → /

IntTree Problems

For each of the IntTree problems, you’ll be taking a tree as a parameter and then directly modifying the links between the nodes (the public fields) by using the IntTreeNode class defined in IntTree. You are allowed to have as many IntTreeNode variables as you want (except when told explicitly).

For each IntTree problems, do not,

  • call any methods on the IntTree objects,
  • construct any new IntTreeNode objects,
  • use other data structures such as arrays, lists, queues, etc.,
  • or mutate the data of any node.

depthSum

Implement a method that returns the sum of the values stored in a binary tree of integers weighted by the depth of each value.

You should return the value at the overallRoot, plus 2 times the values stored at the next level of the tree, plus 3 times the values stored at the next level of the tree, and so on. For example, in the tree below:

Example depthSum tree

The sum would be computed as:

9+2(7+6)+3(3+2+4)+4(5+2)=90 9 + 2 \cdot (7+6) + 3 \cdot (3+2+4) + 4 \cdot (5+2) = 90

removeLeaves

Implement a method that removes the leaf nodes from an IntTree. (Remember that a leaf node is one that has empty left and right subtrees.) If a variable tree refers to the first tree below, the removeLeaves(tree) should remove the four leaves from the tree (the nodes with data values 1, 4, 6, and 0) leaving the next tree below.

A second call on the method would eliminate the two leaves in this tree (the nodes with data values 3 and 8), shown in the third tree below.

A third call would eliminate the one leaf with data value 9, and a fourth call would leave an empty tree because the previous tree was exactly one leaf node.

If your method is called on an empty tree, the method does not change the tree because there are no nodes of any kind (leaf or not).

Example removeLeaves tree

trim

Implement a method that accepts parameters for an IntTree and minimum and maximum integer values, and removes from the tree any elements that are not within that range (inclusive).

For this method, you should assume that your tree is a binary search tree (BST), so its elements are in valid BST order. Your method should maintain the BST ordering property of the tree.

For example, suppose a variable of type IntTree called tree stores the following elements:

Example trim tree1

The table below shows what the state of the tree would be if various trim calls were made. The calls shown are separate; they are not a chain of sequential calls. You may assume that the minimum is less than or equal to the maximum.

Example trim tree2

Hint
The BST ordering property is important for solving this problem. If a node’s data value is too large or too small to fit within the range, this may also tell you something about whether that node’s left or right subtree elements can be within the range. Taking advantage of such information makes it more feasible to remove the correct nodes.

Testing and Submitting

For this project, we’ve provided tests inside the cse143review/test module for you to check your work. Run them as you go through each problem. Review the testing page for more info.

Once you have successfully passed all the tests, visit the Commit & Submit page for instructions on saving your work and submitting it for grading.