The Problem & First Impressions

• The SparseArray class, employing concepts of object-oriented programming in Java, manages a sparse array by utilizing SparseArrayEntry objects. The getValueAt method, leveraging concepts of data encapsulation and iteration, retrieves the value at a specified row and column by searching the entries list. Utilizing control structures such as conditionals, it returns either the associated value or 0 if no matching entry is found. The removeColumn method, also employing iteration and conditional logic, efficiently removes a specified column, adjusting the entries list and updating the total column count. This solution effectively demonstrates the use of object-oriented principles, data encapsulation, iteration, and control structures in Java for managing sparse arrays in a memory-efficient manner.

Part A

• Task: Create a static method named getValueAt in the SparseArray class.
• Purpose: Calculate and return the value of the sparse array element at a specified row and column.
• Example: Given a SparseArray object sparse, demonstrate the result obtained by calling sparse.getValueAt(3, 1) and sparse.getValueAt(3, 3).
• Outcome: The method should check if the list entries contains an entry with the specified row and column. If found, return the associated value; otherwise, return 0. In the provided example, the call sparse.getValueAt(3, 1) should return -9, and sparse.getValueAt(3, 3) should return 0.

My Solution:

• For each entry, it checks if the row and column match the specified row and col parameters.
• If a matching entry is found, the method returns the associated value using getValue() from the SparseArrayEntry.
• If no matching entry is found after iterating through the list, the method returns 0, indicating that there is no entry at the specified row and column in the sparse array.
• For instance, calling getValueAt(3, 1) would return the value associated with the entry at row 3, column 1, if such an entry exists. If not, it returns 0.
• This method allows retrieval of the value of a sparse array element based on its row and column indexes.

public class SparseArrayEntry {
  private int col;
  private int row;
  private int value;

  public SparseArrayEntry(int r, int c, int v) {
      this.row = r;
      this.col = c;
      this.value = v;
  }

  public int getRow() {
      return this.row;
  }

  public int getCol() {
      return this.col;
  }

  public int getValue() {
      return this.value;
  }
}

public class SparseArray {
  private int numRows;
  private int numCols;

  private List<SparseArrayEntry> entries;

  public SparseArray() {
      this.entries = new ArrayList<SparseArrayEntry>();
  }

  public int getNumRows() {
      return numRows;
  }

  public int getNumCols() {
      return numCols;
  }

  public List<SparseArrayEntry> getEntries() {
      return entries;
  }

  public int getValueAt(int row, int col) {
      for (int i = 0; i < this.entries.size(); i++) {
          if (this.entries.get(i).getRow() == row && this.entries.get(i).getCol() == col) {
              return this.entries.get(i).getValue();
          }
      }
      return 0;
  }
}

SparseArray test = new SparseArray();
test.getEntries().add(new SparseArrayEntry(1,1,5));
test.getEntries().add(new SparseArrayEntry(1,4,4));
test.getEntries().add(new SparseArrayEntry(2,0,1));
test.getEntries().add(new SparseArrayEntry(3,1,-9));
System.out.println("Number of rows: " + test.getNumRows() + " Number of columns: " + test.getNumCols());
System.out.println("Value at row = 1, col = 1: " + test.getValueAt(1,1));
System.out.println("Value at row = 1, col = 4: " + test.getValueAt(1,4));
System.out.println("Value at row = 2, col = 0: " + test.getValueAt(2,0));
System.out.println("Value at row = 3, col = 1: " + test.getValueAt(3,1));

Number of rows: 0 Number of columns: 0
Value at row = 1, col = 1: 5
Value at row = 1, col = 4: 4
Value at row = 2, col = 0: 1
Value at row = 3, col = 1: -9

Part B

• Task: Implement the removeColumn method in the SparseArray class.
• Purpose: Remove a specified column from the sparse array and adjust the entries list and column count accordingly.
• Example: Given a SparseArray object sparse with a specific state, demonstrate the result obtained by calling sparse.removeColumn(1).
• Outcome:
  • Remove all entries in the entries list with column indexes matching the specified column.
  • Replace entries in the entries list with column indexes greater than the specified column by decrementing their column indexes by one (moving one column to the left).
  • Adjust the number of columns in the sparse array (numCols) to reflect the removed column.
  • The order of entries in the entries list may change, as it is in no particular order.
  • Example outcome:
    • numRows: 6
    • numCols: 4
    • entries:
      • row: 1, col: 3, value: 4
      • row: 2, col: 0, value: 1

My Solution:

• Initializes an ArrayList indicesToRemove to keep track of indices to be removed from the entries list.
• Iterates through the entries list:
  • If an entry has the specified column index (col), adds its index to indicesToRemove.
  • If an entry has a column index greater than col, updates the entry by decrementing its column index by one.
• Adjusts the indices in indicesToRemove to account for the removal of entries during the iteration.
• Removes entries from the entries list based on the indices stored in indicesToRemove.
• Decrements the total number of columns in the sparse array (numCols).
• Given a SparseArray object test with specific entries and dimensions, calling test.removeColumn(1) would:
  • Remove entries with column index 1.
  • Update entries with column index greater than 1 by decrementing their column index by one.
  • Adjust the total number of columns (numCols) to reflect the removal.
• The resulting state of the SparseArray would be printed using the subsequent println statements.

public class SparseArray {
  private int numRows;
  private int numCols;

  private List<SparseArrayEntry> entries;

  public SparseArray(int rows, int cols) {
      this.entries = new ArrayList<SparseArrayEntry>();
      this.numRows = rows;
      this.numCols = cols;
  }

  public int getNumRows() {
      return numRows;
  }

  public int getNumCols() {
      return numCols;
  }

  public List<SparseArrayEntry> getEntries() {
      return entries;
  }

  public int getValueAt(int row, int col) {
      for (int i = 0; i < this.entries.size(); i++) {
          if (this.entries.get(i).getRow() == row && this.entries.get(i).getCol() == col) {
              return this.entries.get(i).getValue();
          }
      }
      return 0;
  }

  public void removeColumn(int col) {
      ArrayList<Integer> indicesToRemove = new ArrayList<Integer>();
      for (int i = 0; i < this.entries.size(); i++) {
          if (this.entries.get(i).getCol() == col) {
              indicesToRemove.add(i);
          } else if (this.entries.get(i).getCol() > col) {
              int newRow = this.entries.get(i).getRow();
              int newCol = this.entries.get(i).getCol()-1;
              int newValue = this.entries.get(i).getValue();
              this.entries.set(i, new SparseArrayEntry(newRow, newCol, newValue));
          }
      }
      for (int i = 0; i < indicesToRemove.size(); i++) {
          indicesToRemove.set(i, indicesToRemove.get(i) - i);
      }

      for (int i = 0; i < indicesToRemove.size(); i++) {
          this.entries.remove((int) indicesToRemove.get(i));
      }
      this.numCols--;
  }
}

SparseArray test = new SparseArray(6,5);
test.getEntries().add(new SparseArrayEntry(1,1,5));
test.getEntries().add(new SparseArrayEntry(1,4,4));
test.getEntries().add(new SparseArrayEntry(2,0,1)); 
test.getEntries().add(new SparseArrayEntry(3,1,-9));
System.out.println("Number of rows: " + test.getNumRows() + " Number of columns: " + test.getNumCols());
System.out.println("Value at row = 1, col = 1: " + test.getValueAt(1,1));
System.out.println("Value at row = 1, col = 4: " + test.getValueAt(1,4));
System.out.println("Value at row = 2, col = 0: " + test.getValueAt(2,0));
System.out.println("Value at row = 3, col = 1: " + test.getValueAt(3,1));
test.removeColumn(1);
System.out.println("Number of rows: " + test.getNumRows() + " Number of columns: " + test.getNumCols());
System.out.println("Value at row = 1, col = 1: " + test.getValueAt(1,1));
System.out.println("Value at row = 1, col = 3: " + test.getValueAt(1,3));
System.out.println("Value at row = 2, col = 0: " + test.getValueAt(2,0));
System.out.println("Value at row = 3, col = 1: " + test.getValueAt(3,1));

Number of rows: 6 Number of columns: 5
Value at row = 1, col = 1: 5
Value at row = 1, col = 4: 4
Value at row = 2, col = 0: 1
Value at row = 3, col = 1: -9
Number of rows: 6 Number of columns: 4
Value at row = 1, col = 1: 0
Value at row = 1, col = 3: 4
Value at row = 2, col = 0: 1
Value at row = 3, col = 1: 0