Set intersection
Back to JHAVEPOP exercises
Linked list representation of a set
For this exercise, each set is represented by a linked list. A
set is a collection of elements (in this case, characters) that
never contains more than one occurrence of each element. Even though a
linked list imposes an order on its elements, this order is not
relevant when the collection is treated as a set. Therefore, the
linked lists in this exercise are not ordered in any way. For example,
the set {1, 2} may be represented with the linked list 1 -> 2, or
by the linked list 2 -> 1. An empty linked list represents the
empty set.
Problem statement
Write a Java program that, given two sets s1 and s2, modifies s1 to
represent the intersection of s1 and s2 and leaves s2 unchanged, where
the intersection of two sets is the set containing all the
elements that are common to both sets.
As shown in the test cases below, your code may assume that the two
sets s1 and s2 are given as linked lists and that three additional
reference variables p1, p2, and prev1 are declared. For this exercise, you may
not declare any additional variables.
Make sure that your code works with all possible sets. The following
10 test cases are provided to help you test your code.
Test case #1
Description: s1 is the empty set.
Initial setup:
Final configuration:
Ready to test your program?
Test case #2
Description: s2 is the empty set.
Initial setup:
Final configuration:
Ready to test your program?
Test case #3
Description: Both sets s1 and s2 are empty.
Initial setup:
Final configuration:
Ready to test your program?
Test case #4
Description: Set s1 contains only one element, and this element
is also in s2.
Initial setup:
Final configuration:
Ready to test your program?
Test case #5
Description: Set s1 contains only one element, and this element
is not in s2.
Initial setup:
Final configuration:
Ready to test your program?
Test case #6
Description: Sets s1 and s2 have no elements in common; that is, the intersection is the empty set.
Initial setup:
Final configuration:
Ready to test your program?
Test case #7
Description: The sets s1 and s2 are equal.
Initial setup:
Final configuration:
Ready to test your program?
Test case #8
Description: The first element in set s1 is in the intersection but its last element is not.
Initial setup:
Final configuration:
Ready to test your program?
Test case #9
Description: The last element in set s1 is in the intersection but its first element is not.
Initial setup:
Final configuration:
Ready to test your program?
Test case #10
Description: Random general case.
Initial setup:
Final configuration:
Ready to test your program?
Back to JHAVEPOP exercises
