The following are example questions that are similar to those that might appear on the midterm exam. Note that we would not expect you to complete all of these problems in a 60-minute period!
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)
There are varied correct solutions. Here is one approach:
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;
}
Here is another alternate solution
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;
}
Here is one final alternate solution:
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.
Possible test cases:
- Input starts and/or ends with run:
EXPECT_EQUAL(compress("bb or not bb"), "2b or not 2b"); - Empty string:
EXPECT_EQUAL(compress(""), "");
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).
- First line drawn: Center Vertical
- Last line drawn: South Horizontal
4) PrintBox
Write a function named printBox that accepts two parameters: a Vector<string> holding the lines of a file, and an int for a width. Your function should go through the lines and display them to the console with a 'box' border of ā#ā characters around them on all four sides. The second parameter to your function indicates the total width of the box including its border. You must also convert each line to "title case" by capitalizing the first letter of the line and lowercasing all subsequent letters. For example, suppose the file poem.txt contains the following text:
Your skin like dawn
Mine like musk
One paints the beginning
of a certain end.
The other, the end of a
sure beginning.
-Maya Angelou
Notice that the file might contain blank lines, which will be represented by the empty string. The passed in Vector of lines would look like this:
{"Your skin like dawn", "Mine like musk", "", "One paints the beginning", "of a certain end", "", "The other, the end of a", "sure beginning.", "", "-Maya Angelou"}
The following would be the outputs from two calls to your function:
printBox(lines, 26)
##########################
#Your skin like dawn #
#Mine like musk #
# #
#One paints the beginning#
#Of a certain end. #
# #
#The other, the end of a #
#Sure beginning. #
# #
#-maya angelou #
##########################
printBox(lines, 35)
###################################
#Your skin like dawn #
#Mine like musk #
# #
#One paints the beginning #
#Of a certain end. #
# #
#The other, the end of a #
#Sure beginning. #
# #
#-maya angelou #
###################################
You may assume that the width value passed is non-negative and that no line in the file is too wide to fit into a box of that width.
Fill in the function below:
void printBox(Vector<string> lines, int width) {
/* FILL ME IN */
}
void printPoundLine(int width) {
for (int i = 0; i < width; i++) {
cout << "#";
}
cout << endl;
}
void printBox(Vector<string> lines, int width) {
printPoundLine(width);
for (string line: lines) {
string output = "#";
if (line != ""){
output = output + toUpperCase(line.substr(0, 1)) + toLowerCase(line.substr(1));
}
while (output.length() < width - 1) {
output += " ";
}
cout << output << "#" << endl;
}
printPoundLine(width);
}
5) Interpreting Code
Part A: ADTs
Read through the following functions and note how they are similar and how they differ. Then, answer the following questions.
string maisie(string str) {
Stack<char> storage;
// Loop A
for (char ch: str) {
storage.push(ch);
}
// Loop B
string result;
while (!storage.isEmpty()) {
result += storage.pop();
}
return result;
}
string saki (string str) {
Vector<char> storage;
// Loop C
for (char ch: str) {
storage.add(ch);
}
// Loop D
string result;
while (!storage.isEmpty()) {
result += storage[0];
storage.remove(0);
}
return result;
}
- First, we will examine how each of these functions work.
- In one sentence, explain what the loop labeled Loop A accomplishes.
- In one sentence, explain what the loop labeled Loop B accomplishes.
- In one sentence, explain what the loop labeled Loop C accomplishes.
- In one sentence, explain what the loop labeled Loop D accomplishes.
- Now, let's put it all together: what is returned as a result of the function call
maisie("buster")? What is returned as a result of the function callsaki("buster")?
- What is the Big O of each function with respect to
nwherenis the length of the stringstr?
- Loop A adds each character in the original string to the Stack from the beginning of the string to the end of the string.
- Loop B puts each character that was in the original string
str(from end to beginning) into the result string since itās popping the letters off the stack. - Loop C adds each character in the original string to the Vector from the beginning of the string to the end of the string.
- Loop D puts each character that was in the original string
str(from beginning to end) into the result string by taking the first element in the storage Vector each time and then removing it. maisie("buster") = "retsub"andsaki("buster") = "buster"- First function is
O(n)and second function isO(n^2).
Part B: Recursion
Read through the following recursive function. Then, answer the questions that follow. Each question will ask you to trace through the output that is generated by a single recursive function call. Please include some record of the work that you did to generate each answer. This may include notes about the succession of recursive stack frames that you traced through, or other information about you kept track of the information stored at each level of the recursive process. Answers that do not include any record of work will be ineligible for any credit (even if they are correct).
void targaryen(int x, int y) {
if (y <= 0) {
cout << "0 ";
} else if (x > y) {
cout << x << " ";
targaryen(x - y, y);
} else {
targaryen(x, y - x);
cout << y << " ";
}
}
- What console output is produced by the function call
targaryen(4, 2)? - What console output is produced by the function call
targaryen(3, 4)? - What console output is produced by the function call
targaryen(16, 6)?
(We are lenient with spacing here as long as the numbers are correct and distinguishable)
- 4 0 2
- 3 2 0 1 4
- 16 10 4 0 2 6