Practice Midterm Questions 2

The following are example questions that are similar to those that might appear on the midterm exam.

1) Compress

The compress function forms a compressed string by replacing each sequence of consecutive identical characters by the count and character.

Here are test cases that indicate the desired behavior for the compress function:

PROVIDED_TEST("Test compress")
{
    EXPECT_EQUAL(compress("banana"), "banana");
    EXPECT_EQUAL(compress("bookkeeper"), "b2o2k2eper");
    EXPECT_EQUAL(compress("Oooga boooga boooga"), 
                          "O2oga b3oga b3oga");
}

Part A

Write the compress function. Your solution is free to use any string functions from the C++ standard and/or Stanford libraries.

string compress(string str)

string compress(string str){
    string result = "";
    for (int i = 0; i < str.length(); i++){
        int count = 1;
        int j = i + 1;  
        while (j < str.length() && str[i] == str[j]){
            count += 1;
            j++;
        }
        if (count >= 2) {
            result += integerToString(count) + str[i];
            i = j - 1; // note: j - 1 because of loop control i++
        } else {
            result += str[i]; // char for singleton as own case
        }
    }
    return result;
}

string compress(string str){
    string result = "";
    int count = 1;
    for (int i = 0; i < str.length() - 1; i++){
        if (str[i] == str[i+1]){
            count++;
        } else {
            if (count >= 2){
                result += integerToString(count);
            }
            result += str[i]; // append char for either run or singleton
            count = 1;
        }
    }
    /* Handle end of string case */
    if (count >= 2){
        result += integerToString(count);
    }
    result += str[str.length() - 1];
    return result;
}

string compress(string str){
    for (int i = 0; i < str.length(); i++){
        int count = 1;
        int j = i + 1;
        while (j < str.length() && str[i] == str[j]){
            count += 1;
            j++;
        }
        if (count >= 2) { // e.g. edit result to replace run AAAA with 4A
            str = str.substr(0, i) + integerToString(count) + str.substr(j-1);
           // or possibly str.replace(i, count-1, integerToString(count));
            i += integerToString(count).length(); // Note: because of loop control i++
        }
    }
    return str;
}

Part B

Add two student test cases of your own that augment the provided test cases. Briefly explain why you chose these test cases and how each adds coverage that is distinct from the other tests.

2) BuildTeam

For this problem, you are writing code to help staff campus jobs.

A student who wishes to be considered submits a resume of their skills to the campus resume book. A resume is stored as a Set<string> which each skill is represented as a string, e.g. "marketing" or "construction". The resume book is of type Map<string, Set<string>>. This map associates a person's name (key) with their resume (value).

Here is an example campus resume book:

"Elmo"   ->  { "tickling", "giggling" }
"Kermit" ->  { "juggling", "singing", "problem solving" }
"Zoe"    ->  { "drumming", "counting" }
"Snuffy" ->  { "sleeping" }

The hiring manager identifies a set of desired skills for a team. Interested candidates submit their resume to the campus resume book and add their names to the applicant queue. You will write code to review the resumes of the applicants in the queue and choose which students to hire for the team.

Here are the steps to build a team (make sure to follow these steps when implementing the function!):

• Start with an empty team
• Consider each applicant in order that the application was received
• If the applicant has something to offer (that is, applicant's resume has skills that are desired and currently lacking in your team), add to the team
  • Hint: The higher-level set operations will be handy here
• Continue until the team contains all desired skills or you run out of applicants

Note that this approach does not find the smallest team – instead it gives preference to earlier applicants and may build a larger team than optimal. This is totally fine and as expected. You are not searching for the optimally smallest team, you are to exactly follow the team-building algorithm as described above.

Write the function buildTeam. The three arguments to the function are the set of desired skills for the team, the queue of applicant names, and the campus resume book. The function returns a vector of names to hire for the team, chosen using the process outlined above.

Vector<string> buildTeam(Set<string>& desired, 
                          Queue<string> applicants, 
                          Map<string, Set<string>>& resumeBook)

Vector<string> buildTeam(Set<string>& desired, 
                         Queue<string> applicants, 
                         Map<string, Set<string>>& resumeBook) {
 
    Vector<string> team;
    while (!applicants.isEmpty() && !desired.isEmpty()) {
         string curApplicant = applicants.dequeue();
         Set<string> neededSkills = resumeBook[curApplicant] * desired;
         if (!neededSkills.isEmpty()){
            team.add(curApplicant);
            desired -= neededSkills;
        }
    }
    return team;
}

3) Plus Fractal

The recursive "plus-fractal" is defined as follows:

The leftmost image is a level 1 plus-fractal. It is a single plus, with four line ends.

The second image is a level 2 plus-fractal, with a half-sized plus drawn on each end of the level 1 plus-fractal.

The third image is a level 3 plus-fractal, with a quarter-sized plus drawn on each end of the level 2 plus-fractal.

The final image is a level 4 plus-fractal, with a 1/8th-sized plus drawn on each end of the level 3 plus-fractal.

The fractal can, of course, continue with an infinite number of levels.

You are given this helper function that draws a single plus in a GWindow at location middle with length lineLength:

/* Function: drawPlus
 * ------------------
 * Draws a "plus" symbol that crosses at the middle
 */
void drawPlus(GWindow& window, GPoint middle, int lineLength) {
    window.drawLine({middle.x, middle.y - lineLength},
                    {middle.x, middle.y + lineLength});
    window.drawLine({middle.x - lineLength, middle.y},
                    {middle.x + lineLength, middle.y});
}

Part A

Write the drawPlusFractal function that draws a plus-fractal with level levels:

/* Function: drawPlusFractal
 * -------------------------
 * A recursive function that draws a plus on all end points
 * The fractal will have level number of "levels"
 */
void drawPlusFractal(GWindow& window, int level, GPoint middle, int lineLength) {
    // YOUR CODE HERE
}

Your solution can draw plusses on top of other lines that have previously been drawn through the recursion (i.e., you do not have to worry about overlapping parts of the fractal).

void drawPlusFractal(GWindow &window, int level, GPoint middle, int lineLength) {
    if (level == 0) { // base case
        return;
    }
    drawPlus(window, middle, lineLength); // draw center, then recurse
    drawPlusFractal(window, level - 1, {middle.x - lineLength, middle.y},
                    lineLength / 2.0);       // West
    drawPlusFractal(window, level - 1, {middle.x + lineLength, middle.y},
                    lineLength / 2.0);       // East
    drawPlusFractal(window, level - 1, {middle.x, middle.y - lineLength},
                    lineLength / 2.0);       // North
    drawPlusFractal(window, level - 1, {middle.x, middle.y + lineLength},
                    lineLength / 2.0);      // South
}

Part B

Based on your code, which is the first line drawn in a level 2 fractal, and which is the last line drawn? Use the diagram below to answer, referring to the line by its quadrant (North, West, South, East, or Center) and its orientation (Horizontal or Vertical).