Quesiton 3
Type: List/List Iteration
Blog This question taught me to review how classes worked with lists to manipulate data. In a sparse array, which is an efficient way to store and manipulate data with a significant number of zero or null values, I was tested on navigating and modifying a list of SparseArrayEntry objects to retrieve values and remove columns, showcasing the importance of list iteration and modification in data structure management. This ties back into list iteration because these list operations were simple, but they had to be executed through a variety of classes, increasing the complexity of the quesiton.
Part A
Value Retrieval - Iterate through a list of SparseArrayEntry objects to find the value at a specific row and column.
import java.util.ArrayList;
import java.util.List;
// Class to represent an entry in the sparse array
class SparseArrayEntry {
private int row;
private int col;
private int value;
public SparseArrayEntry(int row, int col, int value) {
this.row = row;
this.col = col;
this.value = value;
}
public int getRow() {
return row;
}
public int getCol() {
return col;
}
public int getValue() {
return value;
}
}
// Class to represent the sparse array
class SparseArray {
private List<SparseArrayEntry> entries;
private int numRows;
private int numCols;
public SparseArray(int numRows, int numCols) {
this.numRows = numRows;
this.numCols = numCols;
entries = new ArrayList<>();
}
public void addEntry(int row, int col, int value) {
entries.add(new SparseArrayEntry(row, col, value));
}
public int getValueAt(int row, int col) {
for (SparseArrayEntry e : entries) {
if (e.getRow() == row && e.getCol() == col) {
return e.getValue();
}
}
return 0;
}
public int getNumRows() {
return numRows;
}
public int getNumCols() {
return numCols;
}
}
// Example usage
public class Main {
public static void main(String[] args) {
SparseArray sparseArray = new SparseArray(5, 5); // 5x5 sparse array
sparseArray.addEntry(1, 2, 3); // Add an entry at row 1, column 2 with value 3
sparseArray.addEntry(3, 4, 5); // Add another entry at row 3, column 4 with value 5
System.out.println("Should print 3:");
System.out.println(sparseArray.getValueAt(1, 2)); // Should print 3
System.out.println("Should print 5:");
System.out.println(sparseArray.getValueAt(3, 4)); // Should print 5
System.out.println("Should print 0:");
System.out.println(sparseArray.getValueAt(0, 0)); // Should print 0 (default value)
}
}
Main.main(null);
Should print 3:
3
Should print 5:
5
Should print 0:
0
Part B
Column Removal - Modify the list of SparseArrayEntry objects to remove entries in a specific column and adjust the column indices of remaining entries.
import java.util.ArrayList;
import java.util.List;
class SparseArrayEntry {
private int row;
private int col;
private int value;
public SparseArrayEntry(int row, int col, int value) {
this.row = row;
this.col = col;
this.value = value;
}
public int getRow() {
return row;
}
public int getCol() {
return col;
}
public int getValue() {
return value;
}
}
class SparseArray {
private List<SparseArrayEntry> entries;
private int numRows;
private int numCols;
public SparseArray(int numRows, int numCols) {
this.numRows = numRows;
this.numCols = numCols;
entries = new ArrayList<>();
}
public void addEntry(int row, int col, int value) {
entries.add(new SparseArrayEntry(row, col, value));
}
public int getValueAt(int row, int col) {
for (SparseArrayEntry e : entries) {
if (e.getRow() == row && e.getCol() == col) {
return e.getValue();
}
}
return 0;
}
public void removeColumn(int col) { // new thingy
numCols--;
for (int i = entries.size() - 1; i >= 0; i--) {
if (entries.get(i).getCol() == col) {
entries.remove(i);
}
}
for (int i = 0; i < entries.size(); i++) {
if (entries.get(i).getCol() > col) {
SparseArrayEntry h = entries.get(i);
SparseArrayEntry e = new SparseArrayEntry(h.getRow(), (h.getCol() - 1), h.getValue());
entries.set(i, e);
}
}
}
public int getNumRows() {
return numRows;
}
public int getNumCols() {
return numCols;
}
}
// Testing
public class Main {
public static void main(String[] args) {
SparseArray sparseArray = new SparseArray(5, 5);
sparseArray.addEntry(1, 2, 3);
sparseArray.addEntry(3, 4, 5);
sparseArray.addEntry(2, 3, 7);
System.out.println("Original Array");
System.out.println("Should print 3:");
System.out.println(sparseArray.getValueAt(1, 2)); // Should print 3
System.out.println("Should print 5:");
System.out.println(sparseArray.getValueAt(3, 4)); // Should print 5
System.out.println("Should print 7:");
System.out.println(sparseArray.getValueAt(2, 3)); // Should print 7
System.out.println("");
sparseArray.removeColumn(3);
System.out.println("Shifted Array");
System.out.println("Should print 3:");
System.out.println(sparseArray.getValueAt(1, 2)); // Should print 3
System.out.println("Should print 5:");
System.out.println(sparseArray.getValueAt(3, 3)); // Should print 5 (shifted from column 4 to 3)
System.out.println("Should print 7:");
System.out.println(sparseArray.getValueAt(2, 2)); // Should print 7 (shifted from column 3 to 2)
}
}
Main.main(null);
Original Array
Should print 3:
3
Should print 5:
5
Should print 7:
7
Shifted Array
Should print 3:
3
Should print 5:
5
Should print 7:
0