Computer Science A

Course Progress 0/0
Sprint View
Week 19 2016 FRQ 2

2016 FRQ 2

16 min read

AP Computer Science A 2016 Free-Response Question #2

Problem Description

This question involves two classes that are used to process log messages. A list of sample log messages is given below:

Code Runner Challenge

Part A

View IPYNB Source 
CLIENT3:security alert – repeated login failures
Webserver:disk offline
SERVER1:file not found
SERVER2:read error on disk DSK1
SERVER1:write error on disk DSK2
Webserver:error on /dev/disk
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Log messages have the format machineId:description, where machineId identifies the computer and description describes the event being logged. Exactly one colon (“:”) appears in a log message. There are no blanks either immediately before or immediately after the colon.

The LogMessage Class

Part (a)

Write the constructor for the LogMessage class. It must initialize the private data of the object so that getMachineId returns the machineId part of the message and getDescription returns the description part of the message.

Complete the LogMessage constructor below.

Code Runner Challenge

Part B

View IPYNB Source 
public class LogMessage
{
    private String machineId;
    private String description;
    
    /** Precondition: message is a valid log message. */
    public LogMessage(String message)
    { /* to be implemented in part (a) */ }
    
    /** Returns true if the description in this log message properly contains keyword;
     * false otherwise.
     */
    public boolean containsWord(String keyword)
    { /* to be implemented in part (b) */ }
    
    public String getMachineId()
    { return machineId; }
    
    public String getDescription()
    { return description; }
    
    // There may be instance variables, constructors, and methods that are not shown.
}
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

// CODE_RUNNER: <challenge text>

Code Runner Challenge

Part C

View IPYNB Source 
// CODE_RUNNER: Part A
class LogMessage
{
    private String machineId;
    private String description;

    public LogMessage(String message)
    {
        int colonIndex = message.indexOf(":");
        machineId = message.substring(0, colonIndex);
        description = message.substring(colonIndex + 1).trim();
    }

    public String getMachineId()
    {
        return machineId;
    }

    public String getDescription()
    {
        return description;
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Part (a) - LogMessage Constructor:");
        System.out.println("=====================================");

        String[] testMessages = {
            "SERVER1:item not found",
            "Webserver:disk offline",
            "CLIENT3:security alert – repeated login failures"
        };

        for (String msg : testMessages) {
            LogMessage logMsg = new LogMessage(msg);
            System.out.println("Original Message: " + msg);
            System.out.println("  Machine ID: " + logMsg.getMachineId());
            System.out.println("  Description: " + logMsg.getDescription());
            System.out.println();
        }
    }
}

Main.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Part (b)

Write the LogMessage method containsWord, which returns true if the description in the log message properly contains a given keyword and returns false otherwise.

A description properly contains a keyword if all three of the following conditions are true:

  • the keyword is a substring of the description;
  • the keyword is either at the beginning of the description or it is immediately preceded by a space;
  • the keyword is either at the end of the description or it is immediately followed by a space.

Examples

Descriptions that properly contain “disk”:

  • "disk"
  • "error on disk"
  • "error on /dev/disk disk"
  • "error on disk DSK1"

Descriptions that do NOT properly contain “disk”:

  • "DISK"
  • "error on disk3"
  • "error on /dev/disk"
  • "diskette"

Assume that the LogMessage constructor works as specified, regardless of what you wrote in part (a).

// CODE_RUNNER: <challenge text>

// CODE_RUNNER: Part B
class LogMessage {
    private String description;

    public LogMessage(String message) {
        int colonIndex = message.indexOf(":");
        description = message.substring(colonIndex + 1).trim();
    }

    public String getDescription() {
        return description;
    }

    public boolean containsWord(String keyword) {
        int index = 0;

        while ((index = description.indexOf(keyword, index)) != -1) {
            boolean validStart =
                (index == 0) || (description.charAt(index - 1) == ' ');

            int endIndex = index + keyword.length();
            boolean validEnd =
                (endIndex == description.length()) ||
                (description.charAt(endIndex) == ' ');

            if (validStart && validEnd) {
                return true;
            }

            index++;
        }

        return false;
    }
}

public class Main {
    public static void main(String[] args) {
        String[] testMessages = {
            "SERVER2:read error on disk DSK1",
            "Webserver:error on disk3",
            "Webserver:error on /dev/disk",
            "Webserver:disk offline",
            "Webserver:diskette drive"
        };

        String keyword = "disk";

        for (String msg : testMessages) {
            LogMessage logMsg = new LogMessage(msg);
            System.out.println(logMsg.getDescription() + " -> "
                               + logMsg.containsWord(keyword));
        }
    }
}

Main.main(null);

Part (c)

The SystemLog class represents a list of LogMessage objects and provides a method that removes and returns a list of all log messages (if any) that properly contain a given keyword. The messages in the returned list appear in the same order in which they originally appeared in the system log. If no message properly contains the keyword, an empty list is returned.

public class SystemLog
{
    /** Contains all the entries in this system log.
     * Guaranteed not to be null and to contain only non-null entries.
     */
    private List<LogMessage> messageList;
    
    /** Removes from the system log all entries whose descriptions properly contain keyword,
     * and returns a list (possibly empty) containing the removed entries.
     * Postcondition:
     * - Entries in the returned list properly contain keyword and
     *   are in the order in which they appeared in the system log.
     * - The remaining entries in the system log do not properly contain keyword and
     *   are in their original order.
     * - The returned list is empty if no messages properly contain keyword.
     */
    public List<LogMessage> removeMessages(String keyword)
    { /* to be implemented in part (c) */ }
    
    // There may be instance variables, constructors, and methods that are not shown.
}

Write the SystemLog method removeMessages, which removes from the system log all entries whose descriptions properly contain keyword and returns a list of the removed entries in their original order.

Example

Assume that theLog is a SystemLog object initially containing six LogMessage objects representing the following list of log messages:

CLIENT3:security alert – repeated login failures
Webserver:disk offline
SERVER1:file not found
SERVER2:read error on disk DSK1
SERVER1:write error on disk DSK2
Webserver:error on /dev/disk

The call theLog.removeMessages("disk") would return a list containing the LogMessage objects representing:

Webserver:disk offline
SERVER2:read error on disk DSK1
SERVER1:write error on disk DSK2

After the call, theLog would contain:

CLIENT3:security alert – repeated login failures
SERVER1:file not found
Webserver:error on /dev/disk

Assume that the LogMessage class works as specified, regardless of what you wrote in parts (a) and (b).

You must use containsWord appropriately to receive full credit.

// CODE_RUNNER: <challenge text>

// CODE_RUNNER: Part C
import java.util.*;

class LogMessage {
    private String machineId;
    private String description;

    public LogMessage(String message) {
        int colonIndex = message.indexOf(":");
        machineId = message.substring(0, colonIndex);
        description = message.substring(colonIndex + 1).trim();
    }

    public String getMachineId() {
        return machineId;
    }

    public String getDescription() {
        return description;
    }

    public boolean containsWord(String keyword) {
        int index = 0;

        while ((index = description.indexOf(keyword, index)) != -1) {
            boolean validStart =
                (index == 0) || (description.charAt(index - 1) == ' ');

            int endIndex = index + keyword.length();
            boolean validEnd =
                (endIndex == description.length()) ||
                (description.charAt(endIndex) == ' ');

            if (validStart && validEnd) {
                return true;
            }

            index++;
        }

        return false;
    }
}

class SystemLog {
    private List<LogMessage> messageList;

    public SystemLog() {
        messageList = new ArrayList<LogMessage>();
    }

    public void addMessage(LogMessage msg) {
        messageList.add(msg);
    }

    public List<LogMessage> removeMessages(String keyword) {
        List<LogMessage> removed = new ArrayList<LogMessage>();

        for (int i = 0; i < messageList.size(); i++) {
            if (messageList.get(i).containsWord(keyword)) {
                removed.add(messageList.remove(i));
                i--;
            }
        }

        return removed;
    }

    public void printMessages(String title) {
        System.out.println(title);
        for (LogMessage msg : messageList) {
            System.out.println("  " +
                msg.getMachineId() + ":" + msg.getDescription());
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Part (c) - removeMessages Method:");
        System.out.println("=====================================\n");

        SystemLog theLog = new SystemLog();
        theLog.addMessage(new LogMessage(
            "CLIENT3:security alert – repeated login failures"));
        theLog.addMessage(new LogMessage("Webserver:disk offline"));
        theLog.addMessage(new LogMessage("SERVER1:item not found"));
        theLog.addMessage(new LogMessage("SERVER2:read error on disk DSK1"));
        theLog.addMessage(new LogMessage("SERVER1:write error on disk DSK2"));
        theLog.addMessage(new LogMessage("Webserver:error on /dev/disk"));

        System.out.println("Calling: theLog.removeMessages('disk')");

        List<LogMessage> removed = theLog.removeMessages("disk");

        System.out.println("Removed Messages:");
        for (LogMessage msg : removed) {
            System.out.println("  " +
                msg.getMachineId() + ":" + msg.getDescription());
        }
        System.out.println();

        theLog.printMessages("Remaining Messages in System Log:");
    }
}

Main.main(null);

AP Computer Science A 2016 FRQ #2 - Answer Key

Part (a): LogMessage Constructor

What you need to do:

Split the message string at the colon (“:”) to separate the machineId from the description.

Step-by-step approach:

  1. Find the position of the colon using indexOf(":")
  2. Extract the machineId - everything before the colon
  3. Extract the description - everything after the colon
  4. Assign to instance variables

Solution:

/** Precondition: message is a valid log message. */
public LogMessage(String message)
{
    int colonIndex = message.indexOf(":");
    machineId = message.substring(0, colonIndex);
    description = message.substring(colonIndex + 1);
}

How it works:

  • message.indexOf(":") finds the position of the colon (returns the index)
  • message.substring(0, colonIndex) gets everything from position 0 up to (but not including) the colon
  • message.substring(colonIndex + 1) gets everything after the colon (skipping the colon itself)

Example:

For "SERVER1:file not found":

  • colonIndex = 7
  • machineId = "SERVER1" (characters 0-6)
  • description = "file not found" (characters 8 to end)

Part (b): containsWord Method

What you need to do:

Check if a keyword “properly contains” in the description, meaning:

  1. The keyword appears in the description
  2. It’s either at the start OR preceded by a space
  3. It’s either at the end OR followed by a space

Step-by-step approach:

  1. Find the keyword in the description using indexOf()
  2. If not found, return false
  3. Check if it starts at the beginning OR is preceded by a space
  4. Check if it ends at the end OR is followed by a space
  5. Return true only if both conditions are met

Solution (Method 1 - Using indexOf):

/** Returns true if the description in this log message properly contains keyword;
 * false otherwise.
 */
public boolean containsWord(String keyword)
{
    int index = description.indexOf(keyword);
    
    if (index == -1) {
        return false;  // keyword not found
    }
    
    // Check if preceded by space or at beginning
    boolean validStart = (index == 0) || (description.charAt(index - 1) == ' ');
    
    // Check if followed by space or at end
    int endIndex = index + keyword.length();
    boolean validEnd = (endIndex == description.length()) || 
                       (description.charAt(endIndex) == ' ');
    
    return validStart && validEnd;
}

Solution (Method 2 - College Board Canonical):

public boolean containsWord(String keyword)
{ 
    if (description.equals(keyword)) 
    { 
        return true; 
    } 
    
    if (description.indexOf(keyword + " ") == 0)
    { 
        return true; 
    } 
    
    if (description.indexOf(" " + keyword + " ") != -1)
    { 
        return true; 
    } 
    
    if (description.length() > keyword.length())
    { 
        if (description.substring(description.length() - keyword.length() - 1)
            .equals(" " + keyword))
        { 
            return true;
        } 
    } 
    
    return false; 
}

Comparison of Methods:

Method 1 (indexOf with charAt):

  • Finds keyword once, then checks boundaries
  • More efficient (only searches once)
  • Cleaner logic flow

Method 2 (College Board):

  • Checks each case separately
  • Case 1: Keyword is the entire description
  • Case 2: Keyword at start, followed by space
  • Case 3: Keyword in middle, surrounded by spaces
  • Case 4: Keyword at end, preceded by space
  • More explicit about each scenario ```

How Method 1 works:

Step 1: Find the keyword

  • description.indexOf(keyword) returns the starting position of the keyword
  • If it returns -1, the keyword isn’t in the description at all

Step 2: Check the character before the keyword

  • If index == 0, the keyword is at the beginning (valid)
  • Otherwise, check if description.charAt(index - 1) == ' ' (preceded by space)

Step 3: Check the character after the keyword

  • Calculate where the keyword ends: index + keyword.length()
  • If this equals the description length, keyword is at the end (valid)
  • Otherwise, check if description.charAt(endIndex) == ' ' (followed by space)

Step 4: Return true only if BOTH conditions are met

How Method 2 (College Board) works:

Case 1: description.equals(keyword)

  • Keyword IS the entire description (e.g., “disk” equals “disk”)

Case 2: description.indexOf(keyword + " ") == 0

  • Keyword at start, followed by space (e.g., “disk offline” starts with “disk “)

Case 3: description.indexOf(" " + keyword + " ") != -1

  • Keyword in middle, surrounded by spaces (e.g., “error on disk DSK1” contains “ disk “)

Case 4: description.substring(description.length() - keyword.length() - 1).equals(" " + keyword)

  • Keyword at end, preceded by space (e.g., “error on disk” ends with “ disk”)
  • Takes the last keyword.length() + 1 characters and checks if it equals “ “ + keyword

Examples:

Description Keyword Result Why?
"disk" "disk" true At beginning AND at end
"error on disk" "disk" true Preceded by space AND at end
"error on disk DSK1" "disk" true Preceded by space AND followed by space
"error on disk3" "disk" false Followed by ‘3’, not space
"diskette" "disk" false Followed by ‘e’, not space
"error on /dev/disk" "disk" false Preceded by ‘/’, not space

Part (c): removeMessages Method

What you need to do:

  1. Create a new empty list to store messages that match
  2. Loop through all messages in messageList
  3. For each message, check if it properly contains the keyword (using containsWord)
  4. If it matches, add it to the result list and remove it from messageList
  5. Return the result list

Step-by-step approach:

  1. Create an empty ArrayList to hold removed messages
  2. Use a loop to iterate through messageList
  3. Check each message using containsWord(keyword)
  4. If it matches:
    • Add to result list
    • Remove from messageList (be careful with indices!)
    • Adjust loop counter since list size changed
  5. Return the result list

Solution (Method 1 - Standard Approach):

public List<LogMessage> removeMessages(String keyword)
{
    List<LogMessage> result = new ArrayList<LogMessage>();
    
    for (int i = 0; i < messageList.size(); i++) {
        LogMessage msg = messageList.get(i);
        
        if (msg.containsWord(keyword)) {
            result.add(msg);
            messageList.remove(i);
            i--;  // Adjust index since we removed an element
        }
    }
    
    return result;
}

Solution (Method 2 - College Board Canonical):

public List<LogMessage> removeMessages(String keyword)
{ 
    List<LogMessage> removals = new ArrayList<LogMessage>();
    
    for (int i = 0; i < messageList.size(); i++)
    { 
        if (messageList.get(i).containsWord(keyword))
        { 
            removals.add(messageList.remove(i));
            i--; 
        } 
    } 
    
    return removals;
}

Comparison:

Method 1:

  • Stores message in a variable first
  • Adds to result, then removes from list
  • Two separate operations

Method 2 (College Board):

  • Combines operations: removals.add(messageList.remove(i))
  • messageList.remove(i) returns the removed element
  • That element is immediately added to the result list
  • More concise, same functionality ```

How it works:

Step 1: Create empty result list

  • List<LogMessage> result = new ArrayList<LogMessage>();

Step 2: Loop through each message

  • Start at index 0, go until messageList.size()
  • Get each message with messageList.get(i)

Step 3: Check if message matches

  • Use msg.containsWord(keyword) to check if description properly contains keyword

Step 4: If it matches:

  • result.add(msg) - add to result list (maintains order)
  • messageList.remove(i) - remove from original list
  • i-- - IMPORTANT! Decrement counter because removing shifts all elements down

Step 5: Return the result list

Why i-- is critical:

When you remove an element at index i:

  • Element at i+1 moves to position i
  • If you don’t decrement, you’ll skip checking that element on the next iteration

Example:

Before removal: [A, B, C, D]  (i=1, checking B)
After removing B: [A, C, D]   (C is now at i=1)
Without i--: next iteration checks i=2 (D), skipping C (bad)
With i--: i becomes 0, then increments to 1, checking C (correct)

Alternative Solution (Backwards Loop):

You can also loop backwards to avoid the index adjustment issue:

public List<LogMessage> removeMessages(String keyword)
{
    List<LogMessage> result = new ArrayList<LogMessage>();
    
    for (int i = messageList.size() - 1; i >= 0; i--) {
        if (messageList.get(i).containsWord(keyword)) {
            result.add(0, messageList.remove(i));  // Add at beginning to maintain order
        }
    }
    
    return result;
}

Example Walkthrough:

Initial messageList:

[0] CLIENT3:security alert – repeated login failures
[1] Webserver:disk offline
[2] SERVER1:file not found
[3] SERVER2:read error on disk DSK1
[4] SERVER1:write error on disk DSK2
[5] Webserver:error on /dev/disk

Call: removeMessages("disk")

Process:

  • i=0: “security alert…” - no “disk” properly contained (skip)
  • i=1: “disk offline” - “disk” at beginning (add to result, remove, i becomes 0)
  • i=1: “file not found” - no “disk” (skip)
  • i=2: “read error on disk DSK1” - “disk” preceded and followed by space (add, remove)
  • i=2: “write error on disk DSK2” - “disk” preceded and followed by space (add, remove)
  • i=2: “error on /dev/disk” - “disk” preceded by ‘/’, not space (skip)

Result list:

[0] Webserver:disk offline
[1] SERVER2:read error on disk DSK1
[2] SERVER1:write error on disk DSK2

Remaining messageList:

[0] CLIENT3:security alert – repeated login failures
[1] SERVER1:file not found
[2] Webserver:error on /dev/disk

Common Mistakes to Avoid

Part (a):

  • (X) Forgetting to add 1 when extracting description: substring(colonIndex) includes the colon
  • (correct) Use substring(colonIndex + 1) to skip the colon

Part (b):

  • (X) Only checking if keyword exists: description.contains(keyword)
  • (correct) Must check boundaries (spaces before/after)
  • (X) Not handling edge cases (keyword at beginning or end)
  • (correct) Use index == 0 and endIndex == description.length() checks

Part (c):

  • (X) Not using containsWord() method (required for full credit!)
  • (correct) Must call msg.containsWord(keyword)
  • (X) Forgetting to adjust index after removal: causes skipped elements
  • (correct) Use i-- or loop backwards
  • (X) Creating new list instead of modifying messageList
  • (correct) Must actually remove from messageList, not just add to result

Scoring Guidelines Summary

Part (a) - 3 points:

  • +1: Finds index of colon
  • +1: Correctly extracts machineId
  • +1: Correctly extracts description

Part (b) - 4 points:

  • +1: Finds keyword in description
  • +1: Checks if keyword at beginning OR preceded by space
  • +1: Checks if keyword at end OR followed by space
  • +1: Returns correct boolean value

Part (c) - 2 points:

  • +1: Properly uses containsWord method
  • +1: Correctly removes matching messages and maintains order

Total: 9 points

Course Timeline