Implementing String Algorithms: Practice Questions (Computer Science A 2.10)

Answer: (A). The characters of “computer” are c(0) o(1) m(2) p(3) u(4) t(5) e(6) r(7). substring(3, 6) takes indexes 3, 4 and 5: “put”. The length is 8.

• (B) starts one index too early.
• (C) gets the substring right but treats the last index (7) as the length.
• (D) includes the end index 6.

Answer: (B). The letter “a” is at indexes 1, 3 and 5, so count is 3.

• (A) misses one occurrence.
• (C) is the length of the String, the number of loop passes.
• (D) would be the result if no letter matched, but “a” occurs three times.

Answer: (B). Each new letter goes in front: “a”, then “ba”, then “cba”.

• (A) would be the result of appending (r = r + ...).
• (C) comes from an incorrect mix of prepending and appending.
• (D) keeps only the last letter, as if r were replaced each pass without keeping the previous text.

Answer: (C). “river” has length 5, so the end index of a substring can be at most 5. substring(2, 6) uses 6, which is out of range.

• (A) is valid: it returns the whole String.
• (B) is valid: a start equal to the length returns the empty String.
• (D) is valid: the start equals the end, so it returns the empty String.

Answer: (C). The call s.substring(1, 3) returns “un” but its result is not stored, and Strings are immutable, so s is still “sunny”. Then “!” is added.

• (A) assumes s became “un”.
• (B) assumes s was shortened to “unny”.
• (D) assumes s became “sun”.

Answer: (C). On the last pass i is s.length() - 1, so the window is substring(length - 1, length + 1), whose end index is beyond the length. That throws StringIndexOutOfBoundsException for every String of length 1 or more. (Even "ab" fails: the second pass uses substring(1, 3).) The loop should stop at i <= s.length() - 2.

• (A) is wrong: an empty String never enters the loop, so it does not throw.
• (B) is wrong: the problem is the loop bound, not what the String contains.
• (D) is wrong: the length of the String does not matter; the last window is always out of range.

Model answer.

public static int countVowels(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        String letter = s.substring(i, i + 1);
        if ("aeiou".indexOf(letter) >= 0) {
            count++;
        }
    }
    return count;
}

“education” has the letters e, d, u, c, a, t, i, o, n. The vowels are e, u, a, i, o: 5.

Suggested Marlbridge rubric (6 marks).

Model answer.

public static boolean isPalindrome(String s) {
    String rev = "";
    for (int i = 0; i < s.length(); i++) {
        rev = s.substring(i, i + 1) + rev;
    }
    return s.equals(rev);
}

An alternative with no new string compares the first and last characters moving inward:

public static boolean isPalindrome(String s) {
    for (int i = 0; i < s.length() / 2; i++) {
        String front = s.substring(i, i + 1);
        String back = s.substring(s.length() - 1 - i, s.length() - i);
        if (!front.equals(back)) {
            return false;
        }
    }
    return true;
}

Suggested Marlbridge rubric (6 marks).

The loop runs for i from 0 to 4 (s.length() - 2 is 4). The output is 2 to.

Suggested Marlbridge rubric (6 marks). 1 mark for each of the five rows (correct pair, decision, count and t), and 1 mark for the correct output.

(a) The String has length 6, so the loop runs for i < 3, that is i = 0, 1, 2. The windows are “xyz” (i = 0, a match), “yzx” (i = 1) and “zxy” (i = 2). The count is 1, but “xyz” also occurs at index 3, so the correct answer is 2.

(b) The loop test is off by one: the last window starts at s.length() - 3, which is 3, but i < s.length() - 3 stops one position too soon, so the last window is never examined.

(c) for (int i = 0; i <= s.length() - 3; i++)

(d) If s.length() - 3 is negative (length under 3), the test 0 <= negative number is false at once, so the loop does not run and the method returns 0, with no exception.

Suggested Marlbridge rubric (6 marks).