Practice Midterm 1 Solutions

Q1) C++ Fundamentals

bool findFreeBlock(Grid<string>& seatGrid, int k, GridLocation& loc) {
    for (int r = 0; r < seatGrid.numRows(); r++) {
        int count = 0; // count of num consecutive empty seats in current row
        for (int c = 0; c < seatGrid.numCols(); c++) {
            if (seatGrid[r][c].empty()) {
                count++;
                if (count == k) {
                    loc = { r, c - k + 1 };
                    return true;
                }
            } else {
                count = 0;
            }
        }
    }
    return false;
}

Q2) ADTS

int reseatGroup(Grid<string>& seatGrid, Map<string, Set<GridLocation>>& reservationDB, string groupCode) {
    // Start by "unlocking" the seat assignments from existing reservation
    Set<GridLocation> oldSeats = reservationDB[groupCode];
    int k = oldSeats.size();
    for (GridLocation seat : oldSeats) {
        seatGrid[seat] = "";
    }

    GridLocation loc;
    if (findFreeBlock(seatGrid, k, loc)) {
        // Update reservationDB with new block of seats
        reservationDB[groupCode] = getSeatsForBlock(loc, k);
    }

    // mark seat assignments (will restore old or set new)
    for (GridLocation seat : reservationDB[groupCode]) {
        seatGrid[seat] = groupCode;
    }

    // Take a set difference between seatsNow and oldSeats.
    // Elements that are in both will be removed.
    Set<GridLocation> changedSeats = oldSeats.difference(reservationDB[groupCode]);
    return changedSeats.size();
}

Q3) Code study: ADTs and Big-O

a) O(N2)

b)

Input vector   Expected result    Actual result
------------------------------------------------
 {4, 4, 5}           {5}            {4, 5}

c) O(N)

d)

Input queue     Expected result    Actual result
------------------------------------------------
 {4, 1, 4}            {1}           {1}

e) None

f)

Input stack   Expected result    Actual result
------------------------------------------------
{7, 4, 4}          {7}               {7}

g)

Input stack   Expected result    Actual result
------------------------------------------------
{4, 7, 4}           {7}           {4, 7}

Q4 Recursion Mystery

a)

Call                            Return value
----------------------------------------------------
recursionMystery1(10,4)         2
recursionMystery1(3,7)          3
recursionMystery1(15,5)         0

b) Remainder of a / b.

c)

Call                            Printed value
----------------------------------------------------
recursionMystery2(5, 'f')       fgOfgOf
                                RRR

recursionMystery2(4, 'i')       iOhiOh
                                RR

Q5 Recursive Functions

Count 11

int count11(string s) {
    if (str.length() <= 1) {
        return 0;
    }
    if (str[0] == '1' && str[1] == '1') {
        return 1 + count11(str.substring(2));
    }
    return count11(str.substring(1));
}

ChangeXY

string changeXY(string s) {
    if (s.length() == 0) {
        return "";
    }
    if (s[0] == 'x') {
        return 'y' + changeXY(s.substr(1));
    }
    return s[0] + changeXY(s.substr(1));
}