跳转至

2024.S1

Question 1

A palindrome is a string that is the same backwards as forwards. For example, "racecar" is a palindrome, because after reversing the characters it still reads "racecar" whereas "word" is not because after reversing the characters it becomes a different string, "drow".

A substring of a string is any chunk of characters starting at some index and running for some length. For example, "TS20" is a substring of "CITS2005" starting at index 2 and of length 4.

Write a class PalindromeCounter. The class should have a static method int numPals(String string, int length) that returns the number of substrings of string of length length that are palindromes. The class should have an overload of numPals that takes only the String parameter and returns the number of substrings of length greater than 1 that are palindromes. The efficiency of your algorithm is not important, but for full marks, you should avoid repeating code unnecessarily.

For example, numPals("banana", 3) should return 3, since "ana", "nan", and "ana" are all palindromes of length 3, and numPals("racecar") should return 3 because "cec", "aceca", and "racecar" are all palindromes.

Hint: Recall that String has a .charAt(i) method that gets the character at a specific index, and that it also has a .length() method that returns the number of characters in the string.

Answer:

class PalindromeCounter {
    private static boolean isPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) 
                return false;
            start++;
            end--;
        }
        return true;
    }

    public static int numPals(String str, int len) {
        int count = 0;
        for (int i = 0; i <= str.length() - len; i++) {
            if (isPalindrome(str, i, i + len - 1)) {
                count++;
            }
        }
        return count;
    }

    public static int numPals(String str) {
        int total = 0;
        for (int len = 2; len <= str.length(); len++) {
            total += numPals(str, len);
        }
        return total;
    }
}

Explanation: A palindrome is a string that reads the same forward and backward. The solution uses:

  1. isPalindrome helper method that checks characters from both ends moving inward
  2. numPals(String, int) counts palindromic substrings of given length by sliding a window
  3. numPals(String) sums counts for all lengths ≥2 by calling the first method The algorithm efficiently reuses code and handles all cases correctly.

Question 2

Give a brief description of what abstract classes are and how they relate to the concept of inheritance in Java. Provide a short (≤ 20 lines) code example showing a use of one or more abstract classes where it would not be possible to use interfaces instead, and explain why.

Answer: Abstract classes:

  • Define common structure/behavior for subclasses
  • Can contain abstract methods (no implementation) and concrete methods
  • Support code reuse through inheritance
  • Cannot be instantiated directly

Example: 

abstract class Animal {
    private String name;
    public Animal(String name) { this.name = name; }
    public abstract void makeSound();
    public String getName() { return name; }
}

class Dog extends Animal {
    public Dog(String name) { super(name); }
    public void makeSound() { System.out.println("Woof"); }
}

Explanation: Abstract classes are needed when: 1. Requiring fields (like name) 2. Needing constructors to initialize state 3. Sharing common implementation (like getName()) Interfaces can't have instance fields or constructors, making abstract classes essential for stateful hierarchies.

Question 3

Give a brief description of what interfaces are and how they relate to the concept of polymorphism in Java. Provide a short (≤ 20 lines) code example showing a use of one or more interfaces where it would not be possible to use abstract classes instead, and explain why.

Answer: Interfaces:

  • Define contracts (method signatures) without implementation
  • Enable polymorphism - different classes can be treated uniformly
  • Support multiple inheritance of types

Example: 

interface Drawable {
    void draw();
}

class Circle implements Drawable {
    public void draw() { /* draw circle */ }
}

class Square implements Drawable {
    public void draw() { /* draw square */ }
}

Explanation: Interfaces are essential when: 1. Unrelated classes need to share behavior 2. Multiple behaviors need to be combined 3. Decoupling implementation from contract Abstract classes can't support multiple inheritance, while interfaces allow classes to implement multiple interfaces.

Question 4

Recall that Java Strings are immutable, meaning their values cannot change. Explain how, then, the following method is able to modify the contents of the words array such that the contents of words is different when it is returned from when it was constructed.

public static String[] mystery() {
    String[] words = {"these", "words", "change"};
    words[2] = words[0] + words[1];
    words[1] = words[0];
    return words;
}

Answer: The method modifies the array's element references, not the String contents. Specifically:

  1. words[2] = words[0] + words[1] creates a new String and changes array reference
  2. words[1] = words[0] copies reference to first element
  3. Strings themselves remain immutable - only references change

Explanation: Java Strings are immutable, meaning their character data can't change after creation. However: - Array elements are references to objects - Reassigning array elements changes what objects they reference - The original Strings "words" and "change" remain unmodified

Question 5

The DigitHistogram class below stores a count of how many copies it "contains" of each digit 0 through 9. It provides methods for inserting or deleting one digit at a time. Overload the delete method in the DigitHistogram class to take an array of ints as a parameter instead of a single int. The new method, when called as hist.delete(arr), should delete from hist each digit that appears in arr. If the same digit appears multiple times in the array, one copy of it should be deleted for each time it appears (without taking the count below zero). The method should return the number of elements successfully deleted. If any of the elements in the array are not a valid digit, the method should throw an IllegalArgumentException and not modify the contents of the histogram.

public class DigitHistogram {
    private int[] counts;

    public DigitHistogram() {
        counts = new int[10];
    }

    public void insert(int digit) throws IllegalArgumentException {
        if (digit < 0 || 9 < digit) {
            throw new IllegalArgumentException();
        }
        counts[digit] += 1;
    }

    // Returns true if the digit existed and was
    // successfully removed and false otherwise
    public boolean delete(int digit) throws IllegalArgumentException {
        if (digit < 0 || 9 < digit) {
            throw new IllegalArgumentException();
        }
        if (counts[digit] > 0) {
            counts[digit] -= 1;
            return true;
        }
        return false;
    }
}

Answer:

public int delete(int[] digits) throws IllegalArgumentException {
    // Validate all digits first
    for (int digit : digits) {
        if (digit < 0 || digit > 9) {
            throw new IllegalArgumentException();
        }
    }

    int count = 0;
    for (int digit : digits) {
        if (counts[digit] > 0) {
            counts[digit]--;
            count++;
        }
    }
    return count;
}

Explanation: 1. First validate all digits - throw if any invalid 2. Iterate through digits array: - For each digit, decrement count if >0 - Track successful deletions 3. Return total successful deletions Key points: - Validation before modification ensures atomicity - No count goes below zero - Returns actual number of deletions

Question 6

Describe the concept of deadlock and explain how the behaviour of the synchronized keyword in Java could lead to a deadlock. Your answer does not need to include example code, but may if you think it helps communicate the idea.

Answer: Deadlock occurs when threads wait indefinitely for resources held by each other. Synchronized keyword can cause deadlock by:

  1. Requiring threads to acquire locks on objects
  2. Creating circular wait dependencies between threads Example: Thread1 locks A then needs B, while Thread2 locks B then needs A.

Explanation: Synchronized blocks/methods: - Provide mutual exclusion for shared resources - Can lead to deadlock when: a) Threads acquire locks in different orders b) No preemption of locks c) Circular wait conditions form Prevention: always acquire locks in consistent order.

Question 7

The following interface represents any type that can be incremented. For example, integers can be incremented by adding 1, such that incrementing 4 gives 5. In this question, assume that to increment something is to increase it by the smallest amount possible. Create an EvenInteger class that can only be used to hold non-negative (≥ 0) even integers. This class should implement Incrementable. It should have a constructor that initializes the value to zero, and a public getter method to retrieve the value. Incrementing an even number should increase it to the next largest even number.

interface Incrementable {
    void increment();
}

Answer:

class EvenInteger implements Incrementable {
    private int value;

    public EvenInteger() {
        value = 0;
    }

    public int getValue() {
        return value;
    }

    public void increment() {
        // Ensure non-negative and even
        if (value < 0 || value % 2 != 0) {
            throw new IllegalStateException();
        }
        // Handle overflow
        if (value > Integer.MAX_VALUE - 2) {
            throw new ArithmeticException("Overflow");
        }
        value += 2;
    }
}

Explanation: The EvenInteger class: 1. Starts at 0 (even, non-negative)

  1. Only allows even values via controlled increment (+2)

  2. Prevents negative values and overflow

  3. Implements Incrementable interface

Key points: - Constructor ensures valid initial state - Increment maintains evenness - Validation prevents invalid states