Extra 106A Practice

Thanks to Ruchir Rastogi and Fanny Chen for writing some of these problems!

Trace problem

What does this code print?

 
10
1
private String name = "Ryan";
2
3
public void run() {
4
    doubleName("Chris");
5
    println(name);
6
}
7
8
private void doubleName(String name) {
9
    name = name + name;
10
}

What about this? (Note change in line 9)

 
10
1
private String name = "Ryan";
2
3
public void run() {
4
    doubleName("Chris");
5
    println(name);
6
}
7
8
private void doubleName(String name) {
9
    this.name = name + name;
10
}

What about this? (Note change in lines 4/5, 10)

 
11
1
private String name = "Ryan";
2
3
public void run() {
4
    String name = "Chris";
5
    doubleName(name);
6
    println(name);
7
}
8
9
private void doubleName(String name) {
10
    name = name + name;
11
}

Splitting arrays into balanced partitions

We want to write a method that takes an array of integers and returns whether it could be split into two arrays with equal sum, where each array has at least one element. This is best explained by example:

Implement the following method to tell whether an array can be balanced:

 
2
1
private boolean canBalance(int[] arr) {
2
}

Past tense counter

Write a method that takes a filename and returns the number of past-tense verbs in that file. For simplicity, we define a "past-tense verb" to be any word ending in "ed". (raced is a past-tense verb, but education is not.)

 
2
1
private int countNumPastTense(String filename) {
2
}

Implementing a library

Write a program that does the following:

You should also implement a getMostFrequentWord method in the Book class, which returns the most frequent word in the book.

A sample program run might look like this:

Enter a filename to add to the library: book1.txt
Enter a filename to add to the library: book2.txt
Enter a filename to add to the library:
Enter a title to look up: Journey to the Center of the Earth
Enter a title to look up: The Art and Science of Java
Enter a title to look up:
 
4
1
public class Library extends ConsoleProgram {
2
    public void run() {
3
    }
4
}
 
19
1
public class Book {
2
    public Book(String filename) {
3
    }
4
  
5
    public String getName() {
6
    }
7
  
8
    public int getYear() {
9
    }
10
  
11
    public void setYear(int year) {
12
    }
13
  
14
    public String getContents() {
15
    }
16
  
17
    public String getMostFrequentWord() {
18
    }
19
}

Solution: Trace problem

Note that this is absolutely awful code! This is why good style is important :)

Solution: Splitting arrays into balanced partitions

Make sure you have a high-level approach planned out before starting this problem; you won't be able to code your way through it if you don't already know exactly what you want to do. Here's one approach: Let's try creating all possible partitions and check if they are balanced. If one of them is balanced, we can return true; otherwise, we return false. In order to create all possible partitions, we'll move a "pointer" through the array from left to right and say, if we were to split it here, what partitions would we get?

  [1, 5, 1, 5]
    ^			    Splitting here yields [1] [5, 1, 5]
ptr = 1

  [1, 5, 1, 5]
       ^		    Splitting here yields [1, 5] [1, 5]
   ptr = 2

  [1, 5, 1, 5]
          ^		    Splitting here yields [1, 5, 1] [5]
      ptr = 3

On each step, we can sum the values to the left of the pointer and sum the values to the right of the pointer. If the sums are equal, then the partitions would be balanced if we split at this point, so we can return true. If we get to the very end and haven't found a valid partition, we return false.

 
17
1
private boolean canBalance(int[] arr) {
2
    for (int pointer = 1; pointer < arr.length; pointer++) {
3
        int leftSum = 0;
4
        int rightSum = 0;
5
        for (int i = 0; i < pointer; i++) {
6
            leftSum += arr[i];
7
        }
8
        for (int i = pointer; i < arr.length; i++) {
9
            rightSum += arr[i];
10
        }
11
12
        if (leftSum == rightSum) {
13
            return true;
14
        }
15
    }
16
    return false;
17
}

Solution: Past tense counter

High-level approach:

 
25
1
private int countNumPastTense(String filename) {
2
    int counter = 0;
3
    try {
4
        BufferedReader br = new BufferedReader(new FileReader(filename));
5
        String line = br.readline();
6
        while (line != null) {
7
            String[] words = line.split(" ");
8
            for (String word : words) {
9
                int length = word.length;
10
                if (length >= 2) {  // Make sure we don't try doing charAt if the word
11
                                   // is too short! Otherwise it'd crash here
12
                    if (word.charAt(length - 1) == 'd' &&
13
                        word.charAt(length - 2) == 'e') {
14
                            counter++;
15
                    }
16
                }
17
            }
18
        }
19
        br.close();
20
    } catch (IOException e) {
21
        println("There's an error.");
22
    }
23
24
    return counter;
25
}

Solution: Implementing a library

 
36
1
public class Library extends ConsoleProgram {
2
    // Note: the choice of a HashMap is important here. Using an ArrayList
3
    // probably would not lead to full points.
4
    HashMap<String, Book> books = new HashMap<String, Book>();
5
6
    public void run() {
7
        populateLibrary();
8
        printBooks();
9
    }
10
  
11
    public void populateLibrary() {
12
        while (true) {
13
            String line = readLine();
14
            if (line.equals("")) {
15
                break;
16
            }
17
            Book book = new Book(line);
18
            books.put(book.getName(), book);
19
        }
20
    }
21
  
22
    public void printBooks() {
23
        while (true) {
24
            String name = readLine();
25
            if (name.equals("")) {
26
                break;
27
            }
28
            Book book = books.get(name);
29
            if (book == null) {
30
                println("404, book not found");
31
            } else {
32
                println(book.getContents());
33
            }
34
        }
35
    }
36
}
 
82
1
public class Book {
2
    String name;
3
    int year;
4
    String contents;
5
    String mostFrequentWord;
6
7
    public Book(String filename) {
8
        try {
9
            BufferedReader br = new BufferedReader(new FileReader(filename));
10
            // Read the first two lines
11
            name = br.readline();
12
            year = Integer.parseInt(br.readline());
13
            // Read the rest of the file
14
            contents = "";
15
            while (true) {
16
                String line = br.readline();
17
                if (line == null) {
18
                    break;
19
                }
20
                contents += line + " ";
21
            }
22
        } catch (IOException e) {
23
            println("Error reading " + filename);
24
            // NOTE: If this were a real program, this exception handling wouldn't
25
            // quite cut it, because this would end up returning a Book object that
26
            // hasn't been fully set up (since we weren't able to read any info
27
            // about it). However, for the purposes of this example, this is good
28
            // enough.
29
        }
30
      
31
        // At this point, `contents` is populated, so we can figure out what the
32
        // most frequent word is
33
        mostFrequentWord = findMostFrequentWord();
34
    }
35
  
36
    private String findMostFrequentWord() {
37
        // Populate a histogram for the words. (The choice of HashMap is important
38
        // here as well)
39
        HashMap<String, Integer> wordFrequencies = new HashMap<String, Integer>();
40
        String[] allWords = contents.split(" ");
41
        for (String word : allWords) {
42
            if (!wordFrequencies.containsKey(word)) {
43
                wordFrequencies.put(word, 1);
44
            } else {
45
                int existingFrequency = wordFrequencies.get(word);
46
                // Overwrite the frequencies map to have the existing freq + 1
47
                wordFrequencies.put(word, existingFrequency + 1);
48
            }
49
        }
50
      
51
        // Now that we have the histogram, find the most popular word
52
        String mostFrequentWord;
53
        int highestFrequency = 0;   // haven't seen anything yet
54
        for (String word : wordFrequencies.keySet()) {
55
            if (wordFrequencies.get(word) > highestFrequency) {
56
                mostFrequentWord = word;
57
                highestFrequency = wordFrequencies.get(word);
58
            }
59
        }
60
        return mostFrequentWord;
61
    }
62
  
63
    public String getName() {
64
        return name;
65
    }
66
  
67
    public int getYear() {
68
        return year;
69
    }
70
  
71
    public void setYear(int year) {
72
        this.year = year;
73
    }
74
  
75
    public String getContents() {
76
        return contents;
77
    }
78
  
79
    public String getMostFrequentWord() {
80
        return mostFrequentWord;
81
    }
82
}

This solution definitely isn't perfect (there are a few issues that prevent it from being robust and able to handle lots of kinds of input files). However, we aren't too interested in the details; the most important things here are your ability to understand/implement/use classes, and your understanding of data structures and ability to select the correct data structure for the correct situation.

Also, this is a pretty long problem. On the final, we won't ask you to write something this huge; however, any small component from this problem is probably fair game.