Problems

1. (10 points) Design the <T> List<T> take(List<T> l, int n) method that returns a list with the first \( n \) elements of the given list \( l \). If \( |l| \le n \), return all elements of the list, but don't return the list itself.

   Files to Submit: Problem1.java, Problem1Test.java

2. (10 points) Design the <T> boolean isPalinList(List<T> ls) method that, when given a List<T>, returns whether the list is palindromic.

   Files to Submit: Problem2.java, Problem2Test.java

3. (16 points) Design the <T> List<List<T>> cartesianProduct(List<List<T>> ls) method that, when given a list of lists, returns the cartesian product of each list. That is, if \( ls \) contains lists \( l_1, l_2, ..., l_n \), you should construct and return \( l_1 \times l_2 \times \cdots \times l_n \). The cartesian product of two lists \( X \times Y \) is \( (x_1, y_1), (x_1, y_2), ..., (x_1, y_n), ..., (x_n, y_n) \), but generalizing this to \( n \) lists is more difficult.

   One way to solve this problem is to design a method that computes the cartesian product of only two lists. Then, write a method that computes the cartesian product of a list of lists plus a second list of values. This then generalizes to any number of lists via a case analysis of having 0, 1, 2, or greater than 2 lists to compute the cartesian product of.

   Another way is to use a recursive approach:

   1. If the list is empty, return the empty list.
   2. If the list contains only one list inside, return a list where the elements are singletons. For example, [[1, 2]] returns [[1], [2]].
   3. Otherwise, split the list into two parts: call the first element \( \mathit{xs} \) and the rest \( \mathit{yss} \). Instantiate a "result list" \( R \). Recursively call the method on \( \mathit{ys} \). Then, for every element \( x \in \mathit{xs} \), for every element \( \mathit{ys} \in \mathit{yss} \), create a new list \( l \). Add to it \( x \) and all of the elements from \( \mathit{ys} \). Then, add \( l \) to \( R \).

   Files to Submit: Problem3.java, Problem3Test.java

4. (16 points) Design the <T> List<T> interleave(List<T> l1, List<T> l2, int m, int n) method that, when given two lists \( l_1, l_2 \) and two integers \( m, n \), returns a new list with the first \( m \) elements of \( l_1 \), then the first \( n \) elements of \( l_2 \), then the next \( m \) elements of \( l_1 \), and so forth. If there are less than \( m \) elements left to take from \( l_1 \) or there are less than \( n \) elements left to take from \( l_2 \), take the rest of the lists. You may assume that \( m, n \geq 1 \). We provide an example below.

   interleave(List.of("a", "b", "c", "d", "e", "f", "g", "h", "i", "j"),
              List.of("10", "20", "30", "40", "50"),
              3,
              2)
      => List.of("a", "b", "c", "10", "20", "d", "e", "f", "30", "40", 
                 "g", "h", "i", "50", "j")
   

   Files to Submit: Problem4.java, Problem4Test.java

5. (8 points) Design the boolean containsHigh(List<List<Integer>> lop) method that, when given a list of two-element arrays representing \( x, y \) coordinate pairs, returns whether or not any of the \( y \)-coordinates are greater than \( 450 \). You must use only the Stream API.

   Files to Submit: Problem5.java, Problem5Test.java

6. (8 points) Design the List<Integer> sqAddFiveOmit(List<Integer> lon) that receives a list of numbers, returns a list of those numbers squared and adds five to the result, omitting any of the resulting numbers that end in \( 5 \) or \( 6 \). You must use only the Stream API.

   Files to Submit: Problem6.java, Problem6Test.java

7. (8 points) Design the List<String> removeLonger(List<String> los, int n) method that receives a list of strings, and removes all strings that contain more characters than a given integer \( n \). Return this result as a list. You must use only the Stream API.

   Files to Submit: Problem7.java, Problem7Test.java

8. (8 points) Design the int filterSumChars(String s) method that, when given a string \( s \), removes all non-alphanumeric characters, converts all letters to uppercase, and computes the sum of the ASCII values of the letters. Digits should also be added, but use the digit itself and not its ASCII value. You must use only the Stream API.

   Files to Submit: Problem8.java, Problem8Test.java

9. (8 points) Design the int productOdds(int n) method that returns the product of all of the odd integers from \( 1 \) to \( n \), inclusive. You should use an IntStream to generate the appropriate range. You must use only the Stream API.

   Files to Submit: Problem9.java, Problem9Test.java

10. (8 points) Design the int keyLength(Map<String, Set<String>> M, int n) that, when given a map \( M \) of strings to sets of strings and a length \( n \), returns the total length of the keys that map to a set of size at most \( n \). You must use only the Stream API.

    Files to Submit: Problem10.java, Problem10Test.java