Arrays
Required: 2015 Free Response Question #1, Part A
(A) Write a static method arraySum that calculates and returns the sum of the entries in a specified one-dimensional array. The following example shows an array arr1 and the value returned by a call to arraySum.
public class ArrayPartA {
public static int arraySum(int[] arr) {
System.out.print("Original array elements: ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
}
return sum;
}
public static void main(String[] args) {
int[] array = {1, 2, 3, 3, 7};
System.out.println("Array Sum: " + arraySum(array));
}
}
ArrayPartA.main(null);
Original array elements: 1 2 3 3 7
Array Sum: 16
Optional: Demonstrating Common Errors
Off by One Error
public class OffbyOneError {
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5};
for (int i = 0; i <= array.length; i++) {
System.out.println(array[i]);
}
}
}
OffbyOneError.main(null);
1
2
3
4
5
---------------------------------------------------------------------------
java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5
at OffbyOneError.main(#22:6)
at .(#23:1)
EXPLANATION: The issue here is that we are iterating up to the array length by doing i <= array.length. It should be i < array.length. Java index starts at 0 and goes up to the length of the array - 1, not the actual length of the array. Therefore, we get an ArrayIndexOutofBoundsException.
Modifying Array Length
public class ModifyingArrayLength {
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
if (i == 2) {
array = new int[3];
}
}
}
}
ModifyingArrayLength.main(null);
1
2
3
EXPLANATION: Though this does not actually output a runtime error, this is still bad practice. When ‘i’ becomes 2, the code tries to modify the length of the array, which creates an error because the length of an array in Java can’t be changed after it is created.
ArrayLists
Popcorn Hacks
- ArrayLists are dynamic, meaning their size can grow or shrink as needed, but arrays are static in size.
-
ArrayList objects are created in the same fashion as other object classes. The primary difference with ArrayLists is that the element type of the ArrayList must be specified using angled brackets <>. In this example, E represents the data type that will be used in the ArrayList. This notation is called the generic type. This can be replaced by an object data type.
-
Create 2 ArrayLists, 1 called studentName and 1 called studentAge
import java.util.ArrayList;
public class Student {
public static void main(String[] args) {
ArrayList<String> studentName = new ArrayList<>();
ArrayList<Integer> studentAge = new ArrayList<>();
studentName.add("Rohin");
studentName.add("Vishnu");
studentName.add("Akshat");
studentAge.add(16);
studentAge.add(18);
studentAge.add(18);
System.out.println("Student Names: " + studentName);
System.out.println("Student Ages: " + studentAge);
}
}
Student.main(null);
Student Names: [Rohin, Vishnu, Akshat]
Student Ages: [16, 18, 18]
ArrayList<String> g = new ArrayList<>();
g.add("Hello");
g.add("Hello");
g.add("HeLLO");
g.add("Hello");
g.add(1, "Hola");
g.add(new String("Hello"));
System.out.println(g);
- Why does this code work?
ANSWER: The correct data type “String” is added into the ArrayList, which is why the code is printed correctly.
7.2 HACKS
- The learning objective is that “Students will be able to represent collections of related object reference data using ArrayList objects.” What does this mean to you?
ArrayLists are used to store collections of objects, where the objects are related in some way, such as being of the same type or representing similar objects in a system. ArrayLists hold references to objects rather than the objects themselves - this allows for the manipulation of objects through these references.
- Look back at Size of the ArrayList. What does the code output and why?
The code looks at the literal size of the list, which is how many elements are present in it.
- Look back at Adding items to an ArrayList. What does the code output and why? What type of function is void, and what will be the return value?
The code returns the arraylist with all of its elements that were previously added. A void function is void, it does not return anything.
- Look back at Example 1. What two lines did we remove? Why?
We removed the lines that were trying to add a double and boolean value to the ArrayList - these were removed because the only valid data type was a string.
- If an ArrayList is being used as a parameter, what are the only two methods I can use from it? What would happen if I tried to use any other methods?
Get and size are the only two methods that can be used. Any other methods will only update the local array and not the actual array.
import java.util.ArrayList;
public class HackHelper {
private String manipulateList(ArrayList<Integer> array) {
array.add(10);
array.add(20);
array.remove(1);
array.set(0,30);
int firstElement = array.get(0);
int lastElement = array.get(array.size() - 1);
return "Items added: 10, 20\nItem removed: 20\nItem replaced: 10 with 30\nFirst element: " + firstElement + "\nLast element: " + lastElement + "\nList size: " + array.size();
}
public static void main (String[] args) {
HackHelper helper = new HackHelper();
ArrayList<Integer> list = new ArrayList<>();
System.out.println(helper.manipulateList(list));
}
}
HackHelper.main(null);
Items added: 10, 20
Item removed: 20
Item replaced: 10 with 30
First element: 30
Last element: 30
List size: 1
7.3 Traversing ArrayLists
The indices of an ArrayList start at 0; if you try to use any value lower than 0, you will get an IndexOutOfBoundsException error.
7.4 Developing Algorithms Using ArrayLists
Based on the code, the algorithm is being developed to find the maximum value of the list.
- Look back at the examples. What’s similar? What’s different?
In the examples, multiple similar ArrayList methods are being used, such as .get. Each of the code blocks has a different function and is attempting to output a different value.
- Why do we use ArrayList? Why not just regular lists?
Regular lists have a fixed size in Java, while ArrayLists do not.
- Demonstrate at least two ArrayList methods that aren’t ArrayList<>.size() and ArrayList<>.get()
ArrayList.add and ArrayList.remove
- Write the method findSum() using the Hack Helper and incorporating ArrayList.
import java.util.ArrayList;
public class ArraySum {
private int findSum(ArrayList<Integer> values) {
int sum = 0;
for (int num : values) {
sum += num;
}
return sum;
}
public static void main(String[] args) {
ArrayList<Integer> nums = new ArrayList<>();
nums.add(0);
nums.add(1);
nums.add(2);
nums.add(300);
nums.add(5);
nums.add(8);
ArraySum sums = new ArraySum();
System.out.println(sums.findSum(nums));
}
}
ArraySum.main(null);
316
7.5-7.7 Hacks:
Write code to remove an element of an ArrayList moving from the first index to the last index, without skipping any like in the example. Then use an insertion sort algorithm to sort the ArrayList you created.
import java.util.ArrayList;
public class ArrayListManipulation {
// Method to remove elements from ArrayList without skipping any
private static void removeElementsSequentially(ArrayList<Integer> list) {
int size = list.size();
for (int i = 0; i < size; i++) {
list.remove(0); // Remove element at index 0
System.out.println("Removed element at index 0: " + list);
}
}
// insertion sort algo
private static void insertionSort(ArrayList<Integer> list) {
int n = list.size();
for (int i = 1; i < n; ++i) {
int key = list.get(i);
int j = i - 1;
while (j >= 0 && list.get(j) > key) {
list.set(j + 1, list.get(j));
j = j - 1;
}
list.set(j + 1, key);
}
}
public static void main(String[] args) {
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(5);
numbers.add(3);
numbers.add(7);
numbers.add(1);
numbers.add(9);
System.out.println("Original ArrayList: " + numbers);
removeElementsSequentially(numbers);
numbers.clear();
numbers.add(5);
numbers.add(3);
numbers.add(7);
numbers.add(1);
numbers.add(9);
insertionSort(numbers);
System.out.println("Sorted ArrayList: " + numbers);
}
}
ArrayListManipulation.main(null);
Original ArrayList: [5, 3, 7, 1, 9]
Removed element at index 0: [3, 7, 1, 9]
Removed element at index 0: [7, 1, 9]
Removed element at index 0: [1, 9]
Removed element at index 0: [9]
Removed element at index 0: []
Sorted ArrayList: [1, 3, 5, 7, 9]
2D Arrays
public class TrimesterGrades {
private int[][] trimesterGrades = {
{85, 90, 78, 92, 99}, // tri 1
{92, 88, 91, 97, 80}, // tri 2
{79, 85, 83, 95, 67} // tri 3
};
public void updateGradeFor3rdPeriod(int newGrade) {
// update grades
trimesterGrades[2][2] = newGrade;
}
public static void main(String[] args) {
TrimesterGrades grades = new TrimesterGrades();
int newGrade = 90;
grades.updateGradeFor3rdPeriod(newGrade);
// show updated grades
System.out.println("Updated Trimester Grades:");
for (int i = 0; i < grades.trimesterGrades.length; i++) {
System.out.print("Trimester " + (i + 1) + ": ");
for (int j = 0; j < grades.trimesterGrades[i].length; j++) {
System.out.print(grades.trimesterGrades[i][j] + " ");
}
System.out.println();
}
}
}
TrimesterGrades.main(null);
Updated Trimester Grades:
Trimester 1: 85 90 78 92 99
Trimester 2: 92 88 91 97 80
Trimester 3: 79 85 90 95 67
2019 FRQ 3
public ArrayList<String> getDelimitersList(String[] tokens) {
ArrayList<String> delimiters = new ArrayList<String>(); // Initialize an empty ArrayList to store delimiters
for (String str : tokens) { // Iterate over each token in the tokens array
if (str.equals(openDel) || str.equals(closeDel)) { // Check if the token is an open or close delimiter
delimiters.add(str); // If it is, add it to the delimiters ArrayList
}
}
return delimiters; // Return the list of delimiters
}
import java.util.ArrayList;
public class TrimesterGrades {
private String openDel = "{"; // storing open delimiter
private String closeDel = "}"; // storing closed delimiter
public boolean isBalanced(ArrayList<String> delimiters) {
int openCount = 0; // initialize a counter for open delimiters
int closeCount = 0; // initialize a counter for close delimiters
for (String str : delimiters) { // iterate over each delimiter in the ArrayList
if (str.equals(openDel)) { // check if the delimiter is an open delimiter
openCount++; // increment the open delimiter count
} else { // if it's not an open delimiter, it's a close delimiter
closeCount++; // increment the close delimiter count
}
if (closeCount > openCount) { // If there are more close delimiters than open delimiters encountered so far
return false; // The delimiters are unbalanced, return false
}
}
// Check if the number of open and close delimiters are equal
if (openCount == closeCount) {
return true; // Delimiters are balanced, return true
} else {
return false; // Delimiters are unbalanced, return false
}
}
public void testIsBalanced(ArrayList<String> delimiters) {
// Check if delimiters are balanced
if (isBalanced(delimiters)) {
System.out.println("Delimiters are balanced.");
} else {
System.out.println("Delimiters are unbalanced.");
}
}
// Example usage of the testIsBalanced method
public static void main(String[] args) {
// Example usage of the testIsBalanced method
ArrayList<String> delimiters = new ArrayList<>();
delimiters.add("{");
delimiters.add("[");
delimiters.add("]");
delimiters.add("}");
TrimesterGrades tester = new TrimesterGrades();
tester.testIsBalanced(delimiters);
}
}
TrimesterGrades.main(null);
Delimiters are unbalanced.
Searching
- Implement linear search for an array list of integers
import java.util.ArrayList;
public class LinearSearch {
public static int linearSearch(ArrayList<Integer> list, int target) {
// iterate through the list
for (int i = 0; i < list.size(); i++) {
// if current element = target, return index
if (list.get(i) == target) {
return i;
}
}
// if target is not found, return -1
return -1;
}
public static void main(String[] args) {
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(5);
numbers.add(8);
numbers.add(3);
numbers.add(1);
numbers.add(9);
int target = 3;
int index = linearSearch(numbers, target);
if (index != -1) {
System.out.println("Element " + target + " found at index " + index);
} else {
System.out.println("Element " + target + " not found in the list");
}
}
}
LinearSearch.main(null);
Element 3 found at index 2
- When is it preferred to use linear search over binary search?
Linear search is preferred over binary search for unsorted data, as it doesn’t need any data to be sorted beforehand. For smaller data sets, it is preferred to use a linear search, as it doesn’t need any sort of preprocessing. Furthermore, for binary searching, inserting and deleting elements a lot is not efficient.
What are some examples of algorithms that would be useful to have recursion?
Recursion can be used in sorting algorithms, where arrays are being divided into smaller subarrays, and then each subarray is sorted recursively. Search algorithms are also used recursively, searching through data structures such as trees.
public class BinarySearch {
static char[] arr = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};
public static String findMe(char target, int start, int end) {
if (start > end) {
return "Not Found";
}
// find middle number - java integer division automatically truncates
int middle = (start + end) / 2;
if (arr[middle] == target) {
return "Found it at index " + middle;
}
// recursion spotted - search lower section
if (arr[middle] > target) {
return findMe(target, start, middle - 1);
}
// recursion spotted part 2 - search higher section
if (arr[middle] < target) {
return findMe(target, middle + 1, end);
}
return "Not Found";
}
public static void main(String[] args) {
char target = 'f';
int start = 0;
int end = arr.length - 1;
System.out.println(findMe(target, start, end));
}
}
BinarySearch.main(null);
What iteration did it find f?
f is found in the second iteration. The algorithm starts with the entire range of the array from index 0 to index 7. Then the middle index is calculated using integer division, and the character at the middle index is compared with the target character. The process is repeated, and the ‘f’ character is found in the second interation at index 5.
Removing Car from Garage Method
import java.util.HashMap;
public abstract class Collectable implements Comparable <Collectable> {
public final String masterType = "Collectable";
private String type; // extender should define their data type
// enumerated interface
public interface KeyTypes {
String name();
}
protected abstract KeyTypes getKey(); // this method helps force usage of KeyTypes
// getter
public String getMasterType() {
return masterType;
}
// getter
public String getType() {
return type;
}
// setter
public void setType(String type) {
this.type = type;
}
// this method is used to establish key order
public abstract String toString();
// this method is used to compare toString of objects
public int compareTo(Collectable obj) {
return this.toString().compareTo(obj.toString());
}
// static print method used by extended classes
public static void print(Collectable[] objs) {
// print 'Object' properties
System.out.println(objs.getClass() + " " + objs.length);
// print 'Collectable' properties
if (objs.length > 0) {
Collectable obj = objs[0]; // Look at properties of 1st element
System.out.println(
obj.getMasterType() + ": " +
obj.getType() +
" listed by " +
obj.getKey());
}
// print "Collectable: Objects'
for(Object o : objs) // observe that type is Opaque
System.out.println(o);
System.out.println();
}
}
public class Car extends Collectable {
private String make;
private String model;
private int year;
public Car(String make, String model, int year) {
this.make = make;
this.model = model;
this.year = year;
}
@Override
protected KeyTypes getKey() {
return null;
}
public String getMake() {
return make;
}
public String getModel() {
return model;
}
public int getYear() {
return year;
}
public String toString() {
return year + " " + make + " " + model;
}
}
public class Garage {
private static HashMap<String, Car> garage = new HashMap<>();
public Garage() {
garage.put("Lambo", new Car("Lamborghini", "Aventador", 2021));
garage.put("Ferrari", new Car("Ferrari", "F8 Tributo", 2021));
garage.put("Porsche", new Car("Porsche", "911 Turbo S", 2021));
garage.put("McLaren", new Car("McLaren", "720S", 2021));
}
// Print what's in my garage
public void printGarage() {
for (String key : garage.keySet()) {
System.out.println(key + ": " + garage.get(key));
}
}
// Method to remove a car based on the key
public void removeCar(String key) {
Car removedCar = garage.remove(key);
if (removedCar == null) {
System.out.println(key + " not found in the garage");
} else {
System.out.println("Removed: " + key + ", " + removedCar);
}
}
public static void main(String[] args) {
Garage myGarage = new Garage();
myGarage.printGarage();
// Test removing a car from the garage
String keyToRemove = "Lambo";
myGarage.removeCar(keyToRemove);
myGarage.printGarage(); // Print garage after removal
}
}
Garage.main(null);
Ferrari: 2021 Ferrari F8 Tributo
Porsche: 2021 Porsche 911 Turbo S
Lambo: 2021 Lamborghini Aventador
McLaren: 2021 McLaren 720S
Removed: Lambo, 2021 Lamborghini Aventador
Ferrari: 2021 Ferrari F8 Tributo
Porsche: 2021 Porsche 911 Turbo S
McLaren: 2021 McLaren 720S
HACKS
- Is sequential/linear or binary more efficient? Why?
For sorted data sets, binary search is more efficient, as it repeatedly divides the sorted array in half until the target element is found. Sequential search efficiency is more suitable for unsorted data sets, and it is easy to implement when the data set is small.
- Why might you not always be able to use binary search?
Binary search requires the data to be sorted beforehand. If the data is not sorted, applying binary search would either require sorting the data first or would output incorrect results. Also, some data structures, such as linked lists, do not support efficient random access or indexing, which is needed for binary search.
- Which of the following implements a method named contains for searching an array sequentially, confirming whether or not the array contains a requested element?
Option 4 is the one that implements a method named contains for searching an array sequentially, confirming whether or not the array contains a requested element. The program iterates through the array ‘arr’ sequentially using a for loop, and inside the loop, it checks the current element arr[i] is equal to the requested value ‘val’. Based on whether or not a match is found, it returns either true or false.
public static int foo(int[] arr, int x) {
for(int i = 0; i < arr.length; i++) {
if(arr[i] == x) {
return i;
}
}
return -1;
}
int[] vals = {1,4,51,3,14,91,130,14};
for(int i = 0; i < 20; i++) {
if(foo(vals,i%4) < 0) {
System.out.println("Indubitably!");
}
}
Based on analyzing the values of i % 4 for each iteration of the loop, the word indubitably is printed out 10 times.