MT 1 Solution CS 455

Fall 2022 [Bono]

CS 455 Midterm 1 Solutions

Problem 1

position < word.length() && !found

Problem 2

Part A.

Part B.

[0, 0, 0]

Problem 3
Part A. Solution in bold.

//   VendingMachine models the inventory inside a candy machine. 
//   interface invariant: the amount of each kind of candy in the machine
//                        is always non-negative
public class VendingMachine {
   public static final int HERSHEYS = 0; 
   public static final int M_AND_MS = 1; 
   public static final int STARBURST = 2; 
   public static final int NUM_KINDS = 3; 

   private int[] amounts;

   // Creates an empty vending machine object 
   public VendingMachine () {

      amounts = new int[NUM_KINDS];

   }


   // PRECONDITION for parameters to get, buy, and supply methods:
   // -- kind is one of HERSHEYS, M_AND_MS, and STARBURST
   // -- quantity > 0   [applies to buy and supply only]


   // Returns the amount in this machine of the kind of candy specified
   // PRECONDITION: see above
    public int get(int kind) { 

      return amounts[kind];

   }

   //  Adds to this vending machine the given quantity of the kind of candy
   //     specified.
   // PRECONDITION: see above
   public void supply(int kind, int quantity) {

      amounts[kind] += quantity;

   }

   // Attempts to buy the given quantity of the kind of candy specified
   // from this vending machine.  Returns the actual number of pieces      
   // given out, based on the current inventory (i.e., it can't give out
   // more than is currently in the machine); updates inventory accordingly.
   // PRECONDITION: see above
   public int buy(int kind, int quantity) { 

      if (quantity > amounts[kind]) {  // >= works too
         quantity = amounts[kind];
         amounts[kind] = 0;
      }
      else {
         amounts[kind] -= quantity;
      }
      return quantity;

   }
}

Part B. Correct answer depended on implementation of Part A.
Used a single array instance variable: circle only

b. constant definitions

If student used three separate ints in part A, the correct answer for B was to circle everything -- although constructor optional because of default initialization.

Part C. Note: I reduced this part to be out of 5 points instead of the original 6.
Correct answer depends on implementation of Part A.
For an array in part A:

amounts.length = NUM_KINDS
amounts[i] >= 0 for all valid i
the amount for a particular kind (i.e., any one of the three candy type constants) is in amounts[KIND]

You could get full credit for the above solution but you could also get a point for saying:

valid range for candy-kind constants is [0, NUM_KINDS-1]

and 1/2 point for saying:

amounts array reference cannot be null

For three variables in part A (e.g., amountHersheys, amountMandMs, and amountStarburst

amountHersheys >= 0
amountMandMs >= 0
amountStarburst >= 0
amountHersheys stores the amount of candy indicated by constant HERSHEYS
amountMandMs stores the amount of candy indicated by constant M_AND_MS
amountStarburst stores the amount of candy indicated by constant STARBURST

Part D.

ArrayList<VendingMachine> machines;

Alternate solution:

VendingMachine[] machines;

Part E. Goes with first solution to part D, above:

machines = new ArrayList<>();
for (int i = 0; i < 10; i++) {
   machines.add(new VendingMachine());
}

Goes with alternate solution to part D:

machines = new VendingMachine[10];
for (int i = 0; i < 10; i++) {
   machines[i] = new VendingMachine();
}

Problem 4. Several correct solutions. Here are two:

cp $ASNLIB/public/08-28/* .

cp $ASNLIB/public/08-28/* ~

Problem 5 The best approach to solve it with the given constraints is shown in the solution below.

Some students, instead, tried to copy the original array, and then shift elements just one position at a time. I don't know if any of those ended up with full credit since the code is somewhat trickier. It's also slower (O(n²)), and takes more space than necessary because it would involve a third array of the correct size for the final answer.

public static int[] zeroesRemoved(int[] nums) {

   int numNonZeros = 0;
                              // figure out the length of the result array
   for (int i = 0; i < nums.length; i++) {

      if (nums[i] != 0) {
         numNonZeros++;
      }

   }

   int[] result = new int[numNonZeros];
 
   int resultIndex = 0;
                            // copy only non-zeroes into the result array
   for (int i = 0; i < nums.length; i++) {

      if (nums[i] != 0) {
         result[resultIndex] = nums[i];
         resultIndex++;
      }

   }

   return result;

}