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:

You could get full credit for the above solution but you could also get a point for saying: and 1/2 point for saying: For three variables in part A (e.g., amountHersheys, amountMandMs, and amountStarburst


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(n2)), 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;

}