-
Notifications
You must be signed in to change notification settings - Fork 6
CS 31 (Fall '16)
Contributed by Katie Luangkote.
This function takes as input a C-string containing a number and the number of characters in the array (not including 0 byte). It outputs an integer representation of that number.
Input: char number[] = [1, 2, 3, 4];
Return: 1234
int convertStringToInt(char number[], int len) {
int rtrn = 0;
int multiplier = 1;
for (int i = len-1; i >= 0; i--) {
rtrn += (number[i]-'0')*multiplier;
multiplier *= 10;
}
return rtrn;
}
Contributed by Rahul Salvi.
Most palindromes consider only one character at a time. A common example would be 'racecar'. Checking if a word is a palindrome like this is quite easy -- just check that the first character matches the last, the second character matches the second-to-last, and so on. However, lets define a palindrome to have an order, which is the number of characters to compare in a block. For example, 'racecar' has an order of 1. On the other hand, 'abcdcdab' is a palindrome of order 2, since the first 'ab' matches the 'ab' at the end, and the first 'cd' can be matched against the second 'cd'. For this problem, create a function isPalindrome that takes three arguments in order: an input string (const char*), the length of the string (int), and the order to check (int). isPalindrome should return true if the input string is a palindrome of the correct order, and false if it is not. You may assume that the string length will always be a multiple of the order.
'a' is a palindrome of order 1
'abcddcba' is a palindrome of order 1
'xyzabcxyz' is a palindrome of order 3
'hello world world hello ' is a palindrome of order 6 (be careful about the trailing space)
'' (an empty string) is a palindrome of any order
The only really tricky part of this question is determining the right array indices to check against each other. We can split the string into blocks of size 'order'. From there, we compare blocks at the beginning to blocks at the end. If any comparisons fail, we know the string is not a palindrome.
bool isPalindrome(const char* str, int len, int order) {
int blocks = ((len / order) / 2);
for (int i = 0; i < blocks; i++) {
for (int j = 0; j < order; j++) {
int index1 = ((i * order) + j);
int index2 = (len - ((i + 1) * order)) + j;
if (str[index1] != str[index2]) {
return false;
}
}
}
return true;
}Contributed by Frank Fu.
Write a void function called multiplicationTable that takes two int arguments, rowMax and columnMax, in order to print out a rowMax by columnMax multiplication table. Output an error message instead of the table when either rowMax or columnMax that the user entered is negative. In addition, if rowMax or columnMax exceeds 9, set them to 9 and print out the table as if the user entered 9 as an input instead of the larger value. Make sure each column is separated by a tab, and each row starts at a new line. Also, be sure to write a main function that prompts the user to enter the number of rows (rowMax) and the number of columns (columnMax) before calling the multiplicationTable function in the main function to produce the output.
Example 1:
Please enter the number of rows: 9
Please enter the number of columns: 9
1*1=1 2*1=2 3*1=3 4*1=4 5*1=5 6*1=6 7*1=7 8*1=8 9*1=9
1*2=2 2*2=4 3*2=6 4*2=8 5*2=10 6*2=12 7*2=14 8*2=16 9*2=18
1*3=3 2*3=6 3*3=9 4*3=12 5*3=15 6*3=18 7*3=21 8*3=24 9*3=27
1*4=4 2*4=8 3*4=12 4*4=16 5*4=20 6*4=24 7*4=28 8*4=32 9*4=36
1*5=5 2*5=10 3*5=15 4*5=20 5*5=25 6*5=30 7*5=35 8*5=40 9*5=45
1*6=6 2*6=12 3*6=18 4*6=24 5*6=30 6*6=36 7*6=42 8*6=48 9*6=54
1*7=7 2*7=14 3*7=21 4*7=28 5*7=35 6*7=42 7*7=49 8*7=56 9*7=63
1*8=8 2*8=16 3*8=24 4*8=32 5*8=40 6*8=48 7*8=56 8*8=64 9*8=72
1*9=9 2*9=18 3*9=27 4*9=36 5*9=45 6*9=54 7*9=63 8*9=72 9*9=81
Example 2:
Please enter the number of rows: 7
Please enter the number of columns: 10
Sorry, the maximum number of columns we can have is 9! (Note: This line/output is optional.)
1*1=1 2*1=2 3*1=3 4*1=4 5*1=5 6*1=6 7*1=7 8*1=8 9*1=9
1*2=2 2*2=4 3*2=6 4*2=8 5*2=10 6*2=12 7*2=14 8*2=16 9*2=18
1*3=3 2*3=6 3*3=9 4*3=12 5*3=15 6*3=18 7*3=21 8*3=24 9*3=27
1*4=4 2*4=8 3*4=12 4*4=16 5*4=20 6*4=24 7*4=28 8*4=32 9*4=36
1*5=5 2*5=10 3*5=15 4*5=20 5*5=25 6*5=30 7*5=35 8*5=40 9*5=45
1*6=6 2*6=12 3*6=18 4*6=24 5*6=30 6*6=36 7*6=42 8*6=48 9*6=54
1*7=7 2*7=14 3*7=21 4*7=28 5*7=35 6*7=42 7*7=49 8*7=56 9*7=63
Example 3:
Please enter the number of rows: 0
Please enter the number of columns: 0
(Note: There is no output in this case!)
Example 4:
Please enter the number of rows: -2
Please enter the number of columns: 1
ERROR! We can't have negative rows or negative columns!
#include <iostream>
using namespace std;
void multiplicationTable(int rowMax, int columnMax) {
int i, j;
if (rowMax < 0 || columnMax < 0) {
cout << "ERROR! We can't have negative rows or negative columns! \n";
return;
}
if (rowMax > 9) {
cout << "Sorry, the maximum number of rows we can have is 9! \n";
rowMax = 9;
}
if (columnMax > 9) {
cout << "Sorry, the maximum number of columns we can have is 9! \n";
columnMax = 9;
}
for (i = 1; i <= rowMax; i++) {
for (j = 1; j <= columnMax; j++)
cout << j << "*" << i << "=" << j*i << "\t";
cout << "\n";
}
}
int main() {
int r, c;
cout << "Please enter the number of rows: ";
cin >> r;
cout << "Please enter the number of columns: ";
cin >> c;
multiplicationTable(r, c);
return 0;
}Contributed by Jason Yee.
Write a function, countUniquePrimes, that accepts both an array of ints and the size of said array and returns the number of UNIQUE prime numbers in that array. You may assume that the passed size does not exceed the actual size of the array. Should, however, the parameters passed to the function be nonsensical (e.g. a negative integer passed for the array size) the function should return -1. It is recommended that you write two helper functions for this problem.
/*We'll declare the headers of these helper functions ahead of time so we can use
them now, and implement them for real afterward.
Writing the helper functions before the function of countUniquePrimes is
acceptable as well.*/
bool hasAppearedBefore(int*, int);
bool isPrime(int);
int countUniquePrimes(int* numList, int size) {
if (numList == nullptr || size < 0) /*Catch nonsensical parameters*/
return -1;
int numPrimes = 0;
for (int i = 0; i < size; i++) {
/*Two conditions: hasn't been seen before in the list,
and is prime. Each time we meet a number that meets those
conditions, increment numPrimes as a counter.
We'll use the helper functions above to make this code clean.*/
if (hasAppearedBefore(numList, i) == false && isPrime(numList[i]) == true) {
numPrimes++;
}
}
return numPrimes;
}
/*Given pointer to stary of array of ints and an index in that array,
returns true if element at passed index appears at any previous indeces
i.e. is a repeat and not unique*/
bool hasAppearedBefore(int* numList, int index) {
int number = numList[index];
for (int j = 0; j < index; j++) { /*All indeces that come before index i*/
if (numList[j] == number) /*Has appeared before in the list*/
return true;
}
/*No duplicates found in previous indeces*/
return false;
}
/*Given a positive integer, returns if it is prime.*/
bool isPrime(int num) {
for (int j = 2; j < num; j++) { /*For all possible primes under num*/
if (num % j == 0) /*Found a divisor for num*/
return false;
}
/*No divisors found*/
return true;
}Contributed by Ryan Lo.
Your job is to write a function called toInt() that takes a string containing only numerical characters as input and returns an integer of the actual number the string represents
For instance: toInt("123") should return the integer: 123
#include <iostream>
using namespace std;
#include <string>
#include <cassert>
int toInt(string s) {
int res = 0;
int size = s.size();
for (int i = 0; i < size; i ++) {
res = res * 10 + (s[i] - '0');
}
return res;
}
int main() {
/*Write a function called "toInt" that converts a string consisting of only numerical
characters to an integer and returns the result.
For instance: toInt("123") should return the integer: 123
*/
assert(toInt("123") == 123);
assert(toInt("921340") == 921340);
cout << "All cases worked!" << endl;
}
Contributed by John Stucky.
What is the output of the following code?
#include <iostream>
using namespace std;
int main() {
int a[10];
int* b = a;
*a = 5;
*(a+1)=(*a)+1;
cout << (*(++b))+(*(b--)) << endl;
char s[5] = { 'C', 'S', '3', '1', '\0' };
char* t = &s[s[3]-'0'];
t[*(t+1)-'1'] = '\0';
cout << s << endl;
int x[5] = { 1, 2, 3, 4, 5 };
int* y[5];
for (int i = 0; i < 5; i++) {
y[4-i]= &x[i];
}
y[2]--;
x[2]++;
(*y[x[1]])--;
for (int i = 0; i < 5; i++) {
cout << x[i];
}
cout << endl;
}The code outputs
12
CS3
11445
For the first output, a is initialized to be an array of size 10. In the next line, b is an integer pointer pointing at the first index of a. The line *a = 5 sets a[0] = 5. *(a+1) = (*a)+1 is equivalent to a[1]=a[0]+1, so a[1] now equals 6. b is currently pointing to the contents at a[0], so pre-incrementing it before dereferencing it returns the contents at a[1], a value of 6. Note that *(b--) also returns the contests at a[1], so the printed statement is equivalent to a[1]+a[1], or 6+6, so 12 is printed.
For the second output, s is a pointer to a character array of size 5. Recall that characters in C++ are represented by integers, and that the integers used for the integer characters (e.g., '0', '1') are consecutive. This means that s[3]-'0' equals '1'-'0', equals 1. t is assigned to &s[s[3]-'0'], or '&s[1]', so t is a pointer to the contents of s[1]. In the assignment t[*(t+1)-'1']='\0', *(t+1) refers to t[1] or equivalently s[2], with contents of '3'. *(t+1)-'1' is '3'-'1' is 2, so t[2] is assigned the null character '\0'. When the c-string s is printed, characters up until the first \0 are printed, so the resulting printout is CS3.
For the third printout, without loss of generality, imagine that array x is stored starting at memory address 1000 and let the size of an int be 4. Then the array of int pointers y will have values 1016, 1012, 1008, 1004, 1000.
|index| 0 | 1 | 2 | 3 | 4 |
|-----|----|----|----|----|----|
| x | 1 | 2 | 3 | 4 | 5 |
| y |1016|1012|1008|1004|1000|
y[2]-- will update y[2] to 1004 (remember that in pointer arithmetic, pointers are increased or decreased by the size of the object to which they point). x[2]++ will increment the contents of x[2] to 4. Going into the next line of code, the array contents are:
|index| 0 | 1 | 2 | 3 | 4 |
|-----|----|----|----|----|----|
| x | 1 | 2 | 4 | 4 | 5 |
| y |1016|1012|1004|1004|1000|
y[x[1]] is easy to determine from the above table. x[1] is 2, so y[x[1]] is y[2] is 1004, the address where x[1] is stored. When this address is dereferenced and decremented, x[1] is updated to 1. The final printout is therefore 11445.
Contributed by Stephanie Lam.
Find the output produced by this code.
#include <iostream>
using namespace std;
int main() {
int arr[5] = {9, 3, 1, 7, 2};
int n = 3;
while (n >= 0) {
arr[n] += (n * n);
--n;
}
while (n < 4)
++n;
cout << n << endl;
for (int i = 0; i < 5; i++)
cout << arr[i] + n << "" "";
cout << endl;
return 0;
}Output:
4
13 8 9 20 6
Contributed by Yiyin Jin.
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory.
Given input array nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.
Since the array is already sorted, we can keep two pointers i and j, where i is the slow-runner while j is the fast-runner. As long as nums[i] = nums[j], we increment j to skip the duplicate.
When we encounter nums[j]≠nums[i], the duplicate run has ended so we must copy its value to nums[i+1]. ii is then incremented and we repeat the same process again until j reaches the end of array.
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int i = 0;
for (int j = 1; j < nums.length; j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
Contributed by Jason Wong.
Warm up to main problem: Write a function to reverse a string; can you do this without creating a new string?
Main problem: Write a recursive function to reverse a string. This recursive function must only take a single parameter, the string that is to be reversed. No global variables allowed.
Function skeletons below:
// Warm up
string reverse(string s) {
}
// Main problem
string reverseRecursive(string s) {
}
#include <string>
using namespace std;
string reverse(string s) {
// Pay attention to where we must stop.
// Verify that s.size()/2 works for both even and odd lengths
for (int i = 0; i < s.size() / 2; i++) {
// Compute index from end of string
int lastIndex = s.size() - 1 - i;
// Swap
char tmp = s[lastIndex];
s[lastIndex] = s[i];
s[i] = tmp;
}
return s;
}
string reverseRecursive(string s) {
// Base case: an empty string, or a string of size 1 is already "reversed"
if (s.size() == 0 || s.size() == 1) {
return s;
}
// Our reversed string is formed by the following:
// last character
// reversed version of string without first and last character
// first character
return s[s.size() - 1] + reverseRecursive(s.substr(1, s.size() - 2)) + s[0];
}Contributed by Jennifer Tan.
Write a function, isSubstring, that takes in two strings and returns true if one string is an exact substring (capitalization counts) of the other. The empty string is always a substring of another string.
input 1: 'apple', 'pineapple'
output 1: true
input 2: 'pineapple', 'Apple'
output2: false
#include <string>
using namespace::std;
bool isSubstring(string a, string b) {
string shorter = a;
string longer = b;
if (a.length() > b.length()) {
shorter = b;
longer = a;
}
if (shorter == "")
return true;
int i = 0;
while (i < longer.length() && (i + shorter.length()) <= longer.length()) {
if (longer[i] == shorter[0]) {
int l_i = i + 1;
int s_i = 1;
bool foundSubString = true;
while (l_i < longer.length() && s_i < shorter.length()) {
if (longer[l_i] != shorter[s_i]) {
foundSubString = false;
break;
}
l_i++;
s_i++;
}
if (foundSubString == true) {
return true;
}
}
i++;
}
return false;
}
Contributed by Chaoran Lin.
Write a function that takes a positive integer and converts it to its binary representation.
Input: 2 Output: 10 Input: 5 Output: 101 Input: 10 Output: 1010
The solution is to convert int to binary by dividing num until it reaches 0, and multiplying the remainder of every division by an incrementing exponent of 10, and then return the sum of those multiplication results.
#include <iostream>
#include <math.h>
using namespace std;
/**
* FUNCTION SIGNATURE: int convert(int num)
* PURPOSE: convert int to binary by dividing num until it reaches 0, and multiplying the remainder of every division
* by an incrementing exponent of 10, and then return the sum of those multiplication results.
* PARAMETER:
* num, the user-inputed integer
* RETURN VALUE:
* num converted to a binary
*/
int convert(int num) {
int binary = 0;
int remainder = 0;
int i = 0;
while (num != 0) {
remainder = num % 2;
num = num / 2;
binary += (remainder * pow(10.0, i));
i++;
}
return binary;
}
Contributed by Neda Vesselinova.
Given a three digit number, increment each of its digits and return the resulting number.
incrementDigits(123) should return 234.
incrementDigits(906) should return 1017.
To get the hundreds component, subtract the number in the tens and ones places from the number. To get the tens component, subtract the number in the ones place from the number in the tens and ones place. To get the ones component, get the number in the ones place. To increment the digits, add 100 to the hundreds, 10 to the tens, and 1 to the ones. Add each of the components to get the resulting number.
int incrementDigits(int num) {
int hundreds = num - (num % 100);
int tens = (num % 100) - (num % 10);
int ones = num % 10;
hundreds += 100;
tens += 10;
ones += 1;
return hundreds + tens + ones;
}Contributed by Omar Ozgur.
Write a function zigZagSequence that takes an array of integers and its
length, and tells if the array is in "zig-zag" form, such that
n1 < n2 > n3 < n4 etc.
int b[6] = {1, 3, -5, 4, 1, 0};
zigZagSequence(b, 5) => true
zigZagSequence(b, 6) => false
#include <cassert>
bool zigZagSequence(int seq[], int n) {
for (int i = 1; i < n; i++) {
if (i % 2 == 1) {
if (seq[i] <= seq[i - 1])
return false;
} else {
if (seq[i] >= seq[i - 1])
return false;
}
}
return true;
}
int main() {
int a[0] = {};
int b[6] = {1, 3, -5, 4, 1, 0};
int c[4] = {3, 2, 4, 1};
assert(zigZagSequence(a, 0) == true);
assert(zigZagSequence(b, 5) == true);
assert(zigZagSequence(b, 6) == false);
assert(zigZagSequence(c, 4) == false);
}
Contributed by Matthew Wong.
Write a function that prints a pyramid of $'s. The function should take a single integer parameter n to determine the size of the pyramid. Also, the pyramid should be right-aligned, so you will need to print spaces to correctly align the $'s.
For example, if the function was called with n = 3, the output would be:
$
$$
$$$
If it was called with n = 5, the output would be:
$
$$
$$$
$$$$
$$$$$
We are going to use a loop to print out the rows of the pyramid. Each iteration of this loop will print a single row. Within the loop will be two nested loops that will be responsible for printing the spaces and $'s of each row.
#include <iostream>
using namespace std;
void pyramidOfMoney(int n) {
// there will be n rows in the pyramid
// the nth row will have n dollar signs
for (int i = 1; i <= n; i++) {
// print the spaces preceding the dollar signs
for (int spaces = 0; spaces < n - i; spaces++)
cout << "" "";
// print the dollar signs for the row
for (int money = 0; money < i; money++)
cout << ""$"";
cout << endl;
}
}Contributed by Jason Xu.
Given a sorted 2D array of integers (ascending left to right, top to bottom), write a function that returns the number of integers in the array that appear more than once. Width and height of array will also be given as parameters.
Input: nums = { {1, 1, 2, 3}, {3, 3, 100, 100}, {101, 101, 102, 103} }
(height = 3, width = 4)
Output: func(nums, height, width) = 4
//
// testing.cpp
// for CS31
//
int countDups(int ** arr, int height, int width) {
if (width < 1 || height < 1)
return 0;
int last = 0;
if (arr[0][0] == 0)
last = -1;
int count = 0;
bool onDup = false;
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
if (arr[i][j] == last) {
if (!onDup) {
count++;
onDup = true;
}
} else {
last = arr[i][j];
onDup = false;
}
}
}
return count;
}
Contributed by Yi Peng
rotate("abcde",1) returns "eabcd".
rotate("abcde",2) returns "deabc".
rotate("abcde",3) returns "cdeab".
#include <iostream>
using namespace std;
string rotate(string s, int k) {
if (k < 0 || s.empty()) {
return s;
}
int toRotate = k % s.size();
return s.substr(s.size() - toRotate) + s.substr(0, s.size() - toRotate);
}Contributed by Bowei Wang.
Given the following code, predict the output.
void mystery(int *a, int b, int *c) {
a = b + c;
b = a + c;
c = a + b;
}
int main() {
int a, b, c;
a = 1;
b = 2;
c = 3;
mystery(b, c, a);
cout << a << "" "" << b << "" "" << c << endl;
}After calling mystery:
In main:
a:1 b:2 c:3
In mystery:
&a:b b:3 &c:a
After the line: a = b + c;
In main:
a:1 b:4 c:3
In mystery:
&a:b b:3 &c:a
After the line: b = a + c;
In main:
a:1 b:4 c:3
In mystery:
&a:b b:5 &c:a
After the line: c = a + b;
In main:
a:9 b:4 c:3
In mystery:
&a:b b:5 &c:a
After mystery returns:
In main:
a:9 b:4 c:3
Output:
9 4 3
Contributed by Jeffrey Jiang.
Consider the following code:
#include <string>
using namespace std;
class Name {
public:
Name(string first, string last) {
m_first = first;
m_last = last;
}
private:
string m_first;
string m_last;
}
class Person {
public:
Person(string first, string last, int age, Person best_friend) {
m_name(first, last);
m_age = age;
m_bestie = best_friend;
}
private:
Name m_name;
int m_age;
Person m_bestie;
}a. Does this code compile? If not, change the code so that it does compile.
b. Let's say that John Smith, who is age 20, has David Smallberg as his best friend, and Person a contains John Smith's information. Write the code that can retrieve the first name of David Smallberg's best friend, assuming that everything is defined (nothing null or missing) and all fields are made public.
c. Does Person need a non-default destructor to avoid memory leaks?
a. Here is the full code that is required to have it compile. Of course there are a couple different ways you can write it.
#include <string>
using namespace std;
class Name {
public:
Name(string first, string last) {
m_first = first;
m_last = last;
}
private:
string m_first;
string m_last;
};
class Person {
public:
Person(string first, string last, int age, Person* best_friend)
: m_name(first, last), m_age(age), m_bestie(best_friend) {}
private:
Name m_name;
int m_age;
Person* m_bestie;
};a. List of errors in the problem code: 1. Missing semicolons at the end of the class declaration. 2. Since Name has no default constructor, we must have m_name defined in a initializer list. 3. Person cannot be a member of its own definition. However, we can have a pointer to Person declared.
b. ((a.m_bestie)->m_bestie)->m_first
c. No. Since no pointer is dynamically allocated in Person, but only passed, there is no need to destruct this class by deleting a pointer. One additional point to bring up is that given this strict definition, there must be one Person with NULL as a best friend, since we don't have a way of setting it after construction.
Contributed by Prathyush Katukojwala.
String str contains an integer in string form.
Convert it to an integer without using the standard library stoi or any equivalent library function.
int out = stoi("150");
// out will contain the integer 150// str contains only an integer in string form and nothing else
int stoi(string str) {
int num = 0;
for (int i = 0; i < str.size(); i++) {
num *= 10; // shift all digits to the left one place
num += str[i] - '0'; // add the latest number
}
return num;
}Contributed by Christian Warloe.
Write a function that takes a string argument and returns the length of the longest substring with repeating characters.
The string "abcdef" should return 1. The string "abbccdef" should return 2. The string "aaabbcdeff" should return 3. The string "abbbcccdddd" should return 4.
int longest_repeating_substr(string mystr) {
int currlen = 1;
int maxlen = 0;
if (mystr.size() < 1) {
return 0;
}
char curr = mystr[0];
for (int i = 1; i < mystr.size(); i++) {
if (mystr[i] == curr) {
currlen++;
}
else {
if (currlen > maxlen)
maxlen = currlen;
currlen = 1;
curr = mystr[i];
}
}
return maxlen;
}Contributed by Hongyi Zhang.
Given a string, rotate the string to the right by k steps (e.g., ("abc", 1) → "cab"). Think of a solution to do this without using an additional array!
("abcdef", 3) -> ("defabc")
("defabc", 6) -> ("defabc")
("defabc", 1) -> ("efabcd")
("efabcd", 5) -> ("defabc")
#include <iostream>
#include <string>
#include <algorithm>
#include <assert.h>
using namespace std;
// using O(n) additional space
void rotateString(string* str, int k) {
string shift = """";
// temporarily store values to be shifted
int ka = k % str->size();
for (int i = 0; i < ka; i++) {
shift += (*str)[i];
}
// rotate the rest of the string
for (int i = 0; i < str->size() - ka; i++) {
(*str)[i] = (*str)[i + ka];
}
// append our stored values
for (int i = 0; i < shift.size(); i++) {
(*str)[str->size() - ka + i] = shift[i];
}
}
// How about doing this in place? :)
void rotateStringInPlace(string* str, int k) {
// str.begin() is a pointer to the first element
// str.end() is a pointer to the first element past the last element (i.e. str[str.size()])
// This is just how the C++ standard library works!
// Try implementing your own reverse function - `reverse(string& str, int start, int end)`
int ka = k % str->length();
// flip the entire string
// abcd -> dcba
reverse(str->begin(), str->end());
// flip the last k characters
// dcba -> dcab
reverse(str->end() - ka, str->end());
// flip the rest of the string
// dcab -> cdab
reverse(str->begin(), str->end() - ka);
// think about why this works! :)
}
int main() {
string test = "abcdef";
rotateString(&test, 3);
assert(test == "defabc");
rotateString(&test, 6);
assert(test == "defabc");
rotateString(&test, 1);
assert(test == "efabcd");
rotateString(&test, 5);
assert(test == "defabc");
test = "abcdef";
rotateStringInPlace(&test, 3);
assert(test == "defabc");
rotateStringInPlace(&test, 6);
assert(test == "defabc");
rotateStringInPlace(&test, 1);
assert(test == "efabcd");
rotateStringInPlace(&test, 5);
assert(test == "defabc");
}
Contributed by Jeffrey Chan.
Implement a function called sumOfIndexes that takes in an array of integers
and the size of the array, and returns the sum of the indexes of the first two integers
within the array that are equivalent. If there are no equivalent integers, return -1.
You do not have to worry about being passed any invalid arguments such as a negative size
argument.
Function signature: int sumOfIndexes(int arr[], int size)
int nums[5] = {1, 2, 3, 3, 2};
int x = sumOfIndexes(nums, 5);
// x = 5 because nums[1] = 2, nums[4] = 2,
// therefore 1 + 4 = 5
#include <iostream>
using namespace std;
int sumOfIndexes(int arr[], int size) {
for (int k = 0; k < size; k++) {
for (int j = k + 1; j < size; j++) {
if (arr[k] == arr[j])
return k + j;
}
}
return -1;
}Contributed by Jeremiah Fan.
Given an integer, write a function that prints out its digits in reverse order. Make sure that negative signs are preserved.
Function signature: void printReverse(int num);
printReverse(500) -> 005
printReverse(-436) -> -634
printReverse(0) -> 0
printReverse(0010) -> 01
#include <iostream>
using namespace std;
void printReverse(int num) {
if (num == 0) {
cout << num << endl;
return;
}
if (num < 0) {
cout << ""-"";
num *= -1;
}
while (num > 0) {
cout << num % 10;
num /= 10;
}
cout << endl;
}Contributed by Adam Romayor.
Write a function romanToInt that takes a single string of roman numerals as input
and returns the corresponding integer value. If the input is invalid return -1.
Roman Numerals and their values: I = 1 V = 5 X = 10 L = 50 C = 100 D = 500 M = 1000
Function signature: int romanToInt (string s);
romanToInt("X") -> 1
romanToInt("IV") -> 4
romanToInt("LDDMXIII") -> 963
romantToInt("wrong") -> -1
This solution maintains the value of the previous Roman Numeral. That way,
if the previous roman numeral is less than the current one, subtract off
2*prev. We multiply prev by 2 before subtracting, since we have already added the
previous roman numeral and must account for that.
int romanToInt(string s) {
int sum = 0;
int prev = 0;
for (int i = 0; i < size; i++) {
switch (s[i]) {
case 'M':
sum += 1000;
if (prev < 1000)
sum -= 2*prev;
prev = 1000;
break;
case 'D':
sum += 500;
if (prev < 500)
sum -= 2*prev;
prev = 500;
break;
case 'C':
sum += 100;
if (prev < 100)
sum -= 2*prev;
prev = 100;
break;
case 'L':
sum += 50;
if (prev < 50)
sum -= 2*prev;
prev = 50;
break;
case 'X':
sum += 10;
if (prev < 10)
sum -= 2*prev;
prev = 10;
break;
case 'V':
sum += 5;
if (prev < 5)
sum -= 2*prev;
prev = 5;
break;
case 'I':
sum += 1;
prev = 1;
break;
default:
return -1;
}
}
return sum;
}Contributed by Ramya Satish.
Given an array, return whether the array is sorted in ascending order and update the values at the pointers pointing to the min and max. You may assume that the array will not be of a size less than or equal to zero, and that min and max are not null pointers.
bool inOrder(int arr[], int size, int *min, int *max) {
int tempMin = arr[0];
int tempMax = arr[0];
bool order = true;
for (int i = 1; i < size; i++) {
if (arr[i] < tempMin) {
tempMin = arr[i];
}
if (arr[i] > tempMax) {
tempMax = arr[i];
}
if (arr[i] < arr[i - 1]) {
order = false;
}
}
*min = tempMin;
*max = tempMax;
return order;
}
Contributed by Alex Wu.
What does the following code output? What is the functionality of mystery (what does it return, given n)?
#include <iostream>
using namespace std;
int mystery(int n) {
if (n == 1)
return 0;
return 1 + mystery(n / 2);
}
int main() {
cout << mystery(5) << endl;
cout << mystery(10) << endl;
cout << mystery(100) << endl;
}The correct output is as follows: 2 3 6
Mystery returns log2(n) rounded down to the nearest integer.
Contributed by: Matt Fabius
Create a program that checks the strength of a user entered password. If the password contains a letter, a digit, and a special character and is longer than 8 characters, it is considered strong.
Bonus: Take in a username and verify that the password doesn't contain the username as well.
A good password: MargaretThatcheris110%cool
#include <iostream>
#include <string>
using namespace std;
/*
Create a password checker that outputs whether or not your password is good.
*/
int main() {
bool containsDigit = false;
bool containsLetter = false;
bool containsSpecial = false;
string password;
getline(cin, password);
for (int i = 0; i < password.length(); i++) {
if (isalpha(password[i]))
containsLetter = true;
else if (isdigit(password[i]))
containsDigit = true;
else
containsSpecial = true;
}
if (containsDigit && containsLetter && containsSpecial && password.length() > 8)
cout << "Good password" <<endl;
}
Contributed by Michael Li.
Given a C string, replace multiple consecutive whitespace characters with only one space character. Also, delete leading and ending whitespace. Do this in-place—i.e., don't use an extra array.
If the input is " Hello world, it's C++! ", the array should be changed to "Hello world, it's C++!".
Keep a pointer to the front and a pointer to the current character that needs to be moved if there's extra whitespace. To determine if there's extra whitespace, count the number of consecutive space characters and see if it's greater than 1 if it's in the middle; if it's at the start of the string, all whitespace is extra. If there's extra whitespace, copy characters to earlier in the array.
void trim(char* s) {
char* front = s;
unsigned spaceCount = 0, charCount = 0;
bool totalExtraSpaces = false;
while (true) {
while (*s == ' ') {
spaceCount++;
s++;
}
totalExtraSpaces = totalExtraSpaces || (charCount != 0 ? spaceCount - 1 : spaceCount);
if (*s == '\0') {
front[charCount] = '\0';
return;
}
if (charCount != 0) {
front[charCount] = ' ';
charCount++;
}
while (*s != ' ') {
if (totalExtraSpaces) {
front[charCount] = *s;
}
charCount++;
if (*s == '\0') {
return;
}
s++;
}
spaceCount = 0;
}
}
Contributed by Aniqa Kamal.
Write a function to find an element in a sorted array that has been rotated by some integer value. Return the index of the element and -1 if the element is not in the array.
Input: arr = [3, 5, 6, 0, 2], key = 0
Output: 3
int findPivot(int arr[], int start, int end) {
if (start == end)
return start;
if (start > end)
return -1;
int mid = (start + end) / 2;
if (mid < end && arr[mid] > arr[mid+1])
return mid;
if (mid > start && arr[mid] < arr[mid-1])
return mid-1;
if (arr[start] >= arr[mid])
return findPivot(arr, start, mid-1);
return findPivot(arr, mid+1, end);
}
int binarySearch(int arr[], int start, int end, int key) {
if (start > end)
return -1;
int mid = (end + start) / 2;
if (arr[mid] == key)
return mid;
if (arr[mid] > key)
return binarySearch(arr, start, mid-1, key);
return binarySearch(arr, mid+1, end, key);
}
int pivotedBinarySearch(int arr[], int n, int key) {
int pivot = findPivot(arr, 0, n-1);
if (pivot == -1)
return binarySearch(arr, 0, n-1, key);
if (arr[pivot] == key)
return pivot;
if (arr[0] <= key)
return binarySearch(arr, 0, pivot-1, key);
return binarySearch(arr, pivot+1, n-1, key);
}
struct Node {
int val;
Node* left, *right;
};
// Find the lowest common ancestor to two nodes in a binary tree.
Node* findLowestCommonAncestor(Node* root, Node* a, Node* b) {
if (!root || !a || !b)
return nullptr;
if (a->val == root->val || b->val == root->val)
return root;
Node* left = findLowestCommonAncestor(root->left, a, b);
Node* right = findLowestCommonAncestor(root->right, a, b);
if (left && right)
return root;
else if (left)
return left;
return right;
}Contributed by Aditya Padmakumar.
What is the output of the following program?
#include <iostream>
using namespace std;
int x = 5;
int &f() {
return x;
}
int main() {
f() = 10;
cout << x;
}A. 5 B. Address of ‘x’ C. Compile error D. 10 E. None of the above
D. f returns a reference, hence it can appear on the left hand side of the assignment operator.
Contributed by Brendon Daugherty.
Without creating any local variables, and only iterating over the array once, write a function is_alternation that has the following signature, taking two char* pointers as parameters and returning a bool value. The function is_alternation should return true if and only if the given c-string alternates between two characters. Iterate through the c-string using only pointers, without using array index access syntax ([ ]).
bool is_alternation(char* startOfWord, char* endOfWord);
You may assume that all C strings end in the null byte /0, and that startOfWord and endOfWord do in fact exist, and also point to the same string of interest.
The following code should output the string “All Good Fam”, without any errors.
int main()
{
char h[6] = "H";
char haha[5] = "haha";
char hahah[6] = "hahah";
char ha[3] = "ha";
assert(is_alternation(haha, haha+5));
assert(is_alternation(hahah, hahah + 6));
assert(is_alternation(ha, ha + 3));
assert(!is_alternation(h, h + 1));
std::cout << "All Good Fam" << std::endl;
}bool is_alternation(char *startOfWord, char* endOfWord) {
// This protects against null pointers
if ( !startOfWord || !endOfWord )
return false;
// You can use pointer arithmetic to get the size of your word!
if ( endOfWord - startOfWord < 2 ) {
return false;
}
// Because we no longer need the pointer to the end of the word, we can use endOfWord
// to iterate through our string!
endOfWord = startOfWord;
// All c-strings end in the nullbyte
while ( *endOfWord != '\0' ) {
// If the current char we look at is
// odd, check to see if it is the same as the second letter of
// the string
if ( ( (endOfWord - startOfWord) % 2 ) && *endOfWord != *(startOfWord + 1) )
return false;
// If the current char we look at is even,
// check to see if it is the same as the first letter of
// the string
else if ( (!(endOfWord - startOfWord) %2) && *endOfWord != *(startOfWord) )
return false;
// Don't forget to increment!
endOfWord += 1;
}
// Return true, if none of our tests came back false.
return true;
}Contributed by Tyler Carson.
Using what you know about overloaded functions, interpret function main() below. Transcribe what is printed to the console by main().
#include <iostream>
int foo() {
std::cout << "foo: void" << std::endl;
return 3;
}
int foo(int x) {
if (x < 0) {
std::cout << "foo: " << x << " squared" << std::endl;
return x*x;
} else {
std::cout << "foo: " << x << " + 1" << std::endl;
return x+1;
}
}
void bar() {
std::cout << "bar: void" << std::endl;
}
void bar(int x) {
while (x > 0) {
std::cout << "bar: " << x << std::endl;
x--;
}
}
int main() {
int x = 2, y = -1;
bar();
bar(x);
foo(y);
bar(foo());
}bar: void
bar: 2
bar: 1
foo: -1 squared
foo: void
bar: 3
bar: 2
bar: 1
Contributed by Xiaoxu Wu.
Given an array of integers and the size of the array, write a function firstRepeat that returns the index of the first repeated element. You may assume that there will be at least one duplicate element in the array.
Input: int arr[] = {1, 2, 3, 2, 4}; int size = 5;
Output: 3
Intput: int arr[] = {1, 2, 3, 7, 0, 2, 7, 3, 1}; int size = 9;
Output: 5
We use two for loops to check every character. Once we find a repeated character, we update the index only if it is less than minIndex, which is initiated to the value n - 1 which is the largest possible value.
int firstRepeat(int arr[], int n) {
int minIndex = n - 1;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] == arr[j] && j < minIndex)
minIndex = j;
return minIndex;
}
Contributed by Allison Ko.
Implement the power function:
float pow(float x, int y) {
// your code here
}Assume all inputs are valid. You don't have to check for errors.
pow(2, 5) // returns 32
pow(12, -2) // returns -144
pow(0.5, 2) // returns 0.25float pow(float x, int y) {
float result = 1;
if (y < 0) {
for (int i = 0; i > y; i--) {
result = result * (1.0/x);
}
} else {
for (int k = 0; k < y; k++) {
result = result * x;
}
}
return result;
}Contributed by Kelvin Wong.
After this program is run, what is inside the array foo?
'int main() { int foo[10]; for (int x = 0; x < 10; x++) { foo[x] = x; } for (int y = 0; y < 5; y++) { foo[y + 5] = foo[y] + y; } } '
foo = {0,1,2,3,4,0,2,4,6,8}
int main() {
int foo[10];
for (int x = 0; x < 10; x++) {
foo[x] = x; // makes foo = {0,1,2,3,4,5,6,7,8,9}
}
for (int y = 0; y < 5; y++) {
foo[y + 5] = foo[y] + y; // changes foo to {0,1,2,3,4,0,2,4,6,8}
}
}Contributed by Henry Yang.
Find the number of unique numbers in an integer array. Function declaration: int numUnique(int a[], int size)
//int test[10] = {1, 2, 3, 4, 5, 6, 7, 8, 8, 8}; //numUnique(test) should return 8!
//This solution specifically works for array size 10 (because of picky markup rules needing a compile time constant). The heart of the function works for arbitrary size!
#include <iostream>
using namespace std;
const int kArraySize = 10;
int numUnique(int a[]) {
// maintain a set of unique numbers
int set[kArraySize];
// maintain a count of unique numbers (also our return value)
int ans = 0;
for (int i = 0; i < kArraySize; i++) {
bool repeat = false;
for (int j = 0; j < ans; j++) {
if (set[j] == a[i]) {
repeat = true;
j = ans;
}
}
if (repeat) {
// move on
} else {
set[ans] = a[i];
ans++;
}
}
return ans;
}
Contributed by Michael Evangelista.
Write a function that takes an array of integers and orders the first n elements so that all even numbers are found before all odd numbers. Assume all arrays will have at most 20 elements.
Given an array with the following elements: 1, 2, 3, 4, if sorting the first 6 elements, the function can return any of the following lines:
2, 4, 1, 3
4, 2, 1, 3
2, 4, 3, 1
4, 2, 3, 1
The important thing is that all even numbers are found before all odd numbers; the order of the even or odd numbers doesn't matter.
void arraySort(int arr[], int nElements) {
int temp[SIZE]; // New array of max size
int tempSize = 0;
int odd[SIZE]; // Temp array for odds
int oddSize = 0;
for (int i = 0; i < nElements; i++) {
if (arr[i] % 2 == 0) { // If number is even
temp[tempSize] = arr[i]; // Insert number to temp
tempSize++; // Increment tempsize
} else { // Number is off
odd[oddSize] = arr[i];
oddSize++;
}
}
for (int j = 0; j < oddSize; j++) {
temp[tempSize] = odd[j];
tempSize++;
}
for (int k = 0; k < nElements; k++) {
arr[k] = temp[k]; // Set values of arr to new values
}
}Contributed by Xueyang Feng.
Write a function rotate that takes in a string s and “rotates” the string to the right k times.
rotate(“abcde”, 1) returns “eabcd” rotate(“abcde”, 2) returns “deabc” rotate(“abcde”, 3) returns “cdeab” rotate(“abcde”, 7) returns “deabc”
#include <iostream>
#include <string>
using namespace std;
string rotate(string s, int k) {
if (k < 0 || s.empty())
return s;
int toRotate = k % s.size();
return s.substr(s.size() - toRotate) +
s.substr(0, s.size() - toRotate);
}
int main() {
string s = "abcde";
rotate(s, 1);
string s2 = "eabcd";
if (s == s2)
cout << "good";
}
Contributed by Wandi Liu
Given two strings, trace the function chef() to find the output of main().
void chef(string &s1, string s2) {
int m = s1.size();
int n = s2.size();
for (int i = 1; i <= min(m, n); i++) {
// iterate the length of the shorter string
if (s1[m-i] < s2[n-i]) {
s1 = s1.substr(m-i+1);
s2 = s2.substr(n-i+1);
cout << i/2 << endl;
break;
} else if (s1[m-i] > s2[n-i]) { // Hint: you'll break here!
s1 = s1.substr(0, m-i+1);
s2 = s2.substr(0, n-i+1);
cout << i%2 << endl;
break;
} else { // Hint: you'll hit this first!
continue;
}
}
}
int main() {
string s1 = "smoburger";
string s2 = "nachoburger";
chef(s1, s2);
cout << s1 << endl << s2;
}Answer:
>> 0
>> sm
>> nachoburger
chef() will only permanently modify one of the parameters - s1 - which is passed by reference. The other, which is passed by value, will not be modified
A good understanding of for loops is needed because you will have to realize that the for loop is examining the two strings backwards (from index n-1 to 0)
The student should also understand the meaning of % (mod), this needs to be paired with the knowledge that that calling a function will executing its output statements
Contributed by Taoran Liu.
Given two positive integers, passed in as strings, return the sum of the two integers as a string.
You may not assume that the strings are the same length or that the sum will be less than
INT_MAX.
You may assume that only the characters 0-9 will be in the string.
Neither number will contain any leading zeros.
stringSum("111", "111")
"222"
stringSum("999","91")
"1090"
stringSum("2147483647", "1")
"2147483648"
#include <iostream>
using namespace std;
// cs31 practice problem. given two strings, convert them into integers and add them
string stringSum(string num1, string num2) {
string out = "";
int i = 1;
bool carry = false;
while (num1.size() != num2.size()) {
if (num2.size() > num1.size())
num1 = '0'+num1;
if (num1.size() > num2.size())
num2 = '0'+num2;
}
for (;;) {
int d1 = num1[num1.size()-i]-48, d2 = num2[num2.size()-i]-48;
int tot = (d1+d2);
if (carry) {
tot++;
carry = false;
}
char sum = tot%10 + 48;
carry = tot/10;
out = sum + out;
i++;
if (i > num1.size()) {
if (carry) out = '1'+out;
break;
}
}
return out;
}
int main() {
cout << stringSum("", "900");
return 0;
}
Contributed by Sahil Gandhi.
You are given an array of size 999 with the numbers 1-1000 in unsorted order. There are NO duplicates in this array. Your task is to find the one missing number in this array. Challenge: Can you do this without a secondary array?
int missingNumber(int size, int arr[]) {
int expectedSum = (size)*(size+1)/2;
int totalSum = 0;
for (int i = 0; i < size; i++) {
totalSum += arr[i];
}
return expectedSum - totalSum;
}Contributed by Yaacov Tarko.
Create a struct Student that stores the student's name as a string as the student's grade as an integer. Create a class Course that stores a string containing the course name (ex: "CS 31") and an array of Students. Course can have additional member variables as needed. Course name should be specified as an argument to the Course constructor, and should never change. Students should be added individually by a member function of Course, addStudent, that takes user input with cin and cout and returns 0 if it succeeds. A class can have up to 128 students, and if it has more than addStudent should return 1, output an error message, and not add the student. Now, write a function printStudents() that prints the names of students to the console in the order of their grades, from highest to lowest.
//
// main.cpp
// UPE CS31 problem
//
// Created by Yaacov Tarko on 11/3/16.
// Copyright © 2016 Yaacov Tarko. All rights reserved.
//
#include <iostream>
#include <string>
struct Student{
std::string name;
int grade;
};
class Course{
public:
// Don't worry about the 'explicit' keyword
// I'm only using it in order to conform to Google's style guide
// Your solution would be correct without it
explicit Course(std::string course_name);
int addStudent();
int printStudents();
private:
std::string course_name;
Student* students[128];
int num_students;
};
Course::Course(std::string course_name) {
this-> course_name = course_name;
this-> num_students = 0;
}
int Course::addStudent() {
// if there are too many students, don't add more
if (num_students >= 128) {
std::cout <<
""The course is already full. Please try to enroll next quarter"";
return 1;
}
std::string student_name;
int student_grade;
std::cout << ""Please enter the student's name:"";
std::cin >> student_name;
std::cout << ""Please enter the student's grade"";
std::cin >> student_grade;
// make sure you use the new keyword to create this object!
Student* new_student = new Student;
new_student->name = student_name;
new_student->grade = student_grade;
students[num_students] = new_student;
num_students++;
return 0;
}
/*
There are lots of ways you could implement this function.
This one is very inefficient but it's easy to write quickly on an exam.
It iterates through the whole array and sorts it (using an algorithm called selection sort),
and then iterates through the sorted array and prints it with cout.
*/
int Course::printStudents() {
// the location of the highest score in the unsorted part of the list.
int maximum = 0;
for (int i = 0; i < num_students-1; i++) {
// start by assuming the first unsorted student has the highest score
maximum = i;
for (int j = i; j < num_students; j++) {
if (students[j]->grade > students[maximum]->grade) {
maximum = j;
}
}
// swap the highest scoring student with the next unsorted one
Student *swap = students[maximum];
students[maximum] = students[i];
students[i]= swap;
}
// print the students' names and grades
for (int i = 0; i < num_students; i++) {
std::cout << students[i]->name << " " << students[i]->grade << "\n";
}
return 0;
}
// This is a tester. You wouldn't need to write it on the exam.
// I used it to make sure my code works properly.
int main(int argc, const char * argv[]) {
Course CS31("CS31");
for (int i = 0; i < 10; i++) {
CS31.addStudent();
}
CS31.printStudents();
return 0;
}
Kyle Liang.
Consider a number n. Find the sum of all prime numbers less than or equal to n.
sumOfPrimes(2) = 2; sumOfPrimes(5) = 10; sumOfPrimes(12) = 28;
2 for loops. One to iterate numbers i to n, one to check if that number i is prime.
There is an optimization for one for loop (see if you can find it).
#include <iostream>
using namespace std;
int sumOfPrimes(int x) {
bool isPrime = true;
int total = 0;
for (int i = 2; i <= x; i++) { // check all numbers up to n
// check if number i is prime
isPrime = true;
for (int j = 2; j < i; j++) {
if (i % j == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
total += i;
}
}
return total;
}
int main() {
cout << sumOfPrimes(12) << endl;
}Contributed by Vincent Cheng.
Write a function countInversions that takes in as parameters an array of numbers and the size of that array. This function should return the number of inversions in the array, or in other words, the number of times that, for two elements of different indexes, the element of greater index has a lesser value than the element of lesser index.
Array: 1, 3, 2
Size: 3
Inversions: 1
Array: 2, 3, 1, 5, 4
Size: 5
Inversions: 3
When two element have an inversion, that means that a[i] < a[j] when i > j for some array a. So it suffices to check for this condition for every element in the array; this can be accomplished with an outer loop through the elements of the array and an inner loop through the elements after the outer loop's element.
int countInversions(int* numArr, int size) {
int totalInversions = 0;
for (int x = 0; x < size; x++) {
for (int y = x + 1; y < size; y++) {
if (numArr[y] < numArr[x]) {
totalInversions++;
}
}
}
return totalInversions;
}Contributed by Jiaming Zheng.
Write a function changeMachine(int cents) which, given an amount of money in cents, it will tell you how many coin of each type (quarter, dime, nickel or penny).
void changeMachine(int cents){
}`changeMachine(78) prints "3 quarter(s) 3 penny(s)" `
`changeMachine(15) prints "1 dime(s) 1 nickel(s)" `
#include <iostream>
using namespace std;
void changeMachine(int cents) {
int quarters = 0, dimes = 0, nickels = 0, pennies = 0;
while (cents > 0) {
if (cents >= 25) {
cents -= 25;
quarters++;
} else if (cents >= 10) {
cents -= 10;
dimes++;
} else if (cents >= 5) {
cents -= 5;
nickels++;
} else {
cents -= 1;
pennies++;
}
}
if (quarters > 0)
cout << quarters << " quarter(s) ";
if (dimes > 0)
cout << dimes << " dime(s) ";
if (nickels > 0)
cout << nickels << " nickel(s) ";
if (pennies > 0)
cout << pennies << " cent(s) ";
}
int main() {
}Contributed by Luke Moore.
#include <iostream>
using namespace std;
int main() {
int numbers[9];
int * p;
p = numbers;
*p = 1;
*(p+3) = 2;
p++;
*p = 3;
p = &numbers[5];
*(p--) = 4;
p = p + 4;
*p = 5;
*(--p) = 6;
p = numbers + 2;
*(p++) = 7;
*(++p) = 8;
numbers[6] = 9;
for (int n = 0; n < 9; n++) {
cout << numbers[n] << endl;
}
return 0;
}
1
3
7
2
8
4
9
6
5
Contributed by Shannon Tom.
Does this program successfully compile? If so, what is the output? If not, explain why. Assume all necessary headers are included.
void add(int x, int y) {
x += y;
}
int main() {
int arr[5] = {5, 1, 7, 2, 9};
int a;
int *p, *b;
a = arr[1];
p = arr + a;
b = p;
a++;
b++;
*b = 3;
cout << *(p+a) << endl;
cout << *arr << endl;
add(*(p+a), *arr);
cout << *(p+a) << endl;
cout << *arr << endl;
cout << a << *p << *b << endl;
}
Correct Output: 2 5 2 5 213
For the correct output, trace through the code as follows:
void add(int x, int y) {
// x = 2, y = 5
x += y; // x = 2 + 5 = 7
}
int main() {
int arr[5] = {5, 1, 7, 2, 9};
int a;
int *p, *b;
a = arr[1]; // a = 1
p = arr + a; // p = &arr[1]. p points to arr[1]
b = p; // b points to arr[1]
a++; // a = 2. Add one to a
b++; // b = &arr[2]. b points to arr[2]
*b = 3; // the int of arr[2] is now 3
cout << *(p+a) << endl; // *arr[3] = 2
cout << *arr << endl; // *arr = 5
add(*(p+a), *arr); // Arguments are passed by value.
// original values are not altered
cout << *(p+a) << endl; // *arr[3] = 2 (same as previous values)
cout << *arr << endl; // *arr = 5 (same as previous values)
cout << a << *p << *b << endl; // a = 2, *p = 1, *b = 3
}Contributed by James Mullen.
Given a positive integer, write a method convert_to_digit_array that returns an array of 10 integers. Each value in the array should correspond to the count of that digit in the given integer.
1 -> [0, 1, 0, 0, 0, 0, 0, 0, 0, 0] 1357924680 -> [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 4844 -> [0, 0, 0, 0, 3, 0, 0, 0, 1, 0]
int[] convert_to_digit_array(int i) {
int[10] digits;
for (int j = 0; j < 10; j++) {
digits[j] = 0;
}
while (i > 0) {
int digit = i % 10;
digits[digit]++;
i = i/10;
}
return digits;
}
Contributed by Yuhuang Chen.
Create a dynamically allocated n x n identity matrix (a two dimensional array with n rows and n columns). Initialize the elements on the main diagonal to 1, and others to 0. Parameters: a int type to indicate matrix size Return type: a double pointer of int type
If n = 2, the matrix should look like 10 01
If n = 3, the matrix should look like 100 010 001
/*
Create a dynamically allocated n x n identity matrix (a two dimensional array with n rows and n columns). Initialize the elements on the main diagonal to 1, and others to 0.
*/
int** creat_identity_matrix(int n) {
int** ret;
ret = new int* [n];
for (int i = 0; i < n; i++)
ret[i] = new int[n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j)
ret[i][j] = 1;
else
ret[i][j] = 0;
}
}
return ret;
}
Jun Kai Ong.
Write a function isPalindromicNum that returns whether a given positive integer is a palindromic number sequence. (A palindromic number sequence is a number that reads the same backwards as forwards.)
int n = 123;
cout << isPalindromicNum(n); // outputs falseint n = 1;
cout << isPalindromicNum(n); // outputs true; int n = 1221;
cout << isPalindromicNum(n); // outputs true; bool isPalindromicNum(int num) {
int n = num;
int backwards = 0;
while (n != 0) {
backwards += n % 10;
n /= 10;
if (n == 0)
break;
backwards *= 10;
}
if (backwards != num)
return false;
else
return true;
}Contributed by Eric Kong.
Suppose you're writing a message to your secret lover. Suppose, in fact, that its contents are so mind-bogglingly embarrassing (if not incriminating) that dire consequences threaten to befall you both were it to fall into the wrong hands. It would be wise, therefore, to conceal the message in such a way that only your paramour could read it. Hence the basic motivation for the wondrous field of encryption, the secure transmission of confidential information to entrusted recipients only. From forbidden lovers to government agents, resistance operatives, and beyond, encryption makes the world go 'round.
More abstractly, we concern ourselves with the following problem. Given a raw specimen of text, or plaintext, to be encrypted, and an encryption key, we wish to produce an encrypted text, or ciphertext. (The converse problem, deducing a plaintext from a ciphertext given a key, is called, funnily enough, decryption.) A mechanism for performing encryption or decryption is called a cipher. One simple example of a cipher is the Caesar cipher: given a plaintext and a number x from 0 to 25, shift every letter in the plaintext by x places in the alphabet.
Naturally, some ciphers are stronger than others. In fact, cryptanalysts concern themselves wih the problem of breaking ciphers, or extracting the plaintext from the ciphertext without a key. The Caesar cipher is, alas, easily broken. So is its cousin the substitution cipher (replace every instance of a letter with another letter), stymied by simple letter frequency analysis. Hence these are seldom used in contemporary private correspondence.
The Vigenère cipher is a simple yet relatively strong cipher, considered nigh unbreakable for three centuries. Perhaps it is best illustrated through example. Suppose we have the plaintext ILOVEYOUSMALLBERG. Let's encrypt it with the key CAREY in the following manner. First, we extend the key by repetition to the length of the plaintext:
ILOVEYOUSMALLBERG
CAREYCAREYCAREYCA
Now let's establish an alphanumeric correspondence: A corresponds to 0, B to 1, and so on and so forth, and Z to 25. Consider the first character of the plaintext, I, and that of the key, C. I corresponds to 8, and C to 2. We add the numbers (modulo 26) to obtain 10, which corresponds to K. Thus the first letter of the ciphertext is K. We proceed similarly for every letter in the plaintext. The full ciphertext thus produced by the operation is KLFZCAOLWKCLCFCTG, as below:
ILOVEYOUSMALLBERG
CAREYCAREYCAREYCA
-----------------
KLFZCAOLWKCLCFCTG
Implement a function vigenere which takes two string arguments, plaintext and key, and applies the Vigenère cipher to obtain a ciphertext, which it should return as an uppercase string. Because we are nice, you may assume that plaintext and key consist solely of uppercase letters 'A'-'Z', that key is nonempty, and that you are working in ASCII. Friendly hint: In ASCII, the characters 'A' through 'Z' occur contiguously and in order.
We graciously provide you a function prototype for vigenere below.
string vigenere(string plaintext, string key);
The function call vigenere(""ILOVEYOUSMALLBERG"", ""CAREY"") shall return the string ""KLFZCAOLWKCLCFCTG"", as per the above example.
In our solution, we iterate through the plaintext letter by letter. A few items of note:
- To simulate the key being repeated as long as is necessary, we apply the modulus operator
%to the counteriso that it cycles within the key's length. - We establish the aforementioned alphanumeric correspondence by subtracting
'A'from the relevant character. Recall that characters are essentially integers, and in character arithmetic,'A' - 'A' = 0,'B' - 'A' = 1, and so on and so forth, and'Z' - 'A' = 25. (Note that this only works in nice encoding scheme like ASCII, where'A'-'Z'are contiguous. Things would go awry, for example, if we worked with that curious dinosaur of an encoding protocol, EBCDIC.) - Similarly, to reconstruct the character in the ciphertext,
cipherChar, we add an integer from0to25back to'A'. - It's necessary to apply the
% 26operation, as the addition may overflow25. - The cleverer of you problem-solvers may observe that the contents of the for-loop can be compressed into one line. We believe that in well-written code, readability trumps compactness, and accordingly we separate our steps in the calculation.
#include <string>
using namespace std;
string vigenere(string plaintext, string key) {
string ciphertext;
for (size_t i = 0; i < plaintext.length(); i++) {
char plainChar = plaintext[i];
char keyChar = key[i % key.length()];
char cipherChar = 'A' + (((plainChar - 'A') + (keyChar - 'A')) % 26);
ciphertext += cipherChar;
}
return ciphertext;
}Contributed by Yujing Fan.
Below is a code segment for the class Student, fill in the blank of functions Student (int ID, int grade, string name, Student* nextStudent); getgrade(); get_nextGrade(); updateGrade(int score);!
// write the code for the blank function
#include<stdio.h>
#include<iostream>
#include<string>
using namespace std;
class Student {
public:
Student() {
Student_ID = 0;
Student_grade = 0;
Student_name = """";
next_Student = nullptr;
}
Student(int ID, int grade, string name, Student* nextStudent);
int getID() {
return Student_ID;
}/*return the ID of current student*/
int getgrade() {
return Student_grade;
}/*return the grade of current student*/
string getname() {
return Student_name;
}/*return the name of current student*/
Student* getNextstudent() {
return next_Student;
}/*return the pointer that points to the next student*/
int updateGrade(int score) {
Student_grade = score;
} // update the current grade with new score
int get_nextGrade() {
return next_Student->getgrade();
} // return the grade of next student
private:
int Student_ID;
int Student_grade;
string Student_name;
Student* next_Student;
};
Student::Student(int ID, int grade, string name, Student* nextStudent) {
Student_ID = ID;
Student_grade = grade;
Student_name = name;
next_Student = nextStudent;
}
Contributed by Miranda Ku.
The following code is supposed to print the numbers from 0 to 5, as follows:
0
1
2
3
4
5However, it does not. Identify the problems in the code below. You need not make actual fixes (the code is too flawed). You should be able to identify two major problems.
(Note that this code is unreasonably convoluted. The problem is simply meant to help you identify code problems, so just roll with it.)
#include <iostream>
#include <stdlib.h>
#include <time.h>
int* badFunc() {
int x, y[6];
x = 0;
for (; x < 6; x++) {
y[x] = x;
}
int *copy = y;
for (; x < 5; x++) {
std::cout << *copy << std::endl;
copy++;
}
return copy;
}
void trample() {
unsigned int seed = time(NULL);
int x[100000];
for (int i = 0; i < 100000; i++)
x[i] = rand_r(&seed);
}
int main() {
int* ret = badFunc();
trample();
std::cout << *ret << std::endl;
}
The first problem is that the second loop is never being entered because x's value is 6. Thus it will never be less than 5 and the printing loop is never entered.
Secondly, the function returns a local address which is then freed for the computer to be able to reuse, which the function trample() aids with.
Thus printing this address is erroneous. Fixing this problem with this current code structure seems to be a useless exercise, as there are simply much better ways to write a program that does the same thing, so don't worry about it.
Contributed by Tyler Lindberg.
Given an array of characters, return the sum of their indices in the alphabet. The indexing will begin from 0, so a = 0, b = 1, c = 2, ..., z = 25. Both uppercase and lowercase letters should be mapped to the same index. If there are any non-alphabetical characters in the array, return -1.
Given Code:
#include <iostream>
int alphaSum(int a[], int size);Input : a, d, f, b
Answer: 0 + 3 + 5 + 1 = 9
Output: 9
int alphaSum(int a[], int size) {
int sum = 0;
// Store int value of a, since we want to count up from there
int aIndex = static_cast<int>('a');
for (int i = 0; i < size; i++) {
// Check if a[i] is a letter
if (!isalpha(a[i]))
return -1;
// Add on the ASCII value of the current char minus the ASCII value of 'a'
// This results in 'a' having an index of zero and 'z' having an index of 25
// Note that a[i] is converted to lower case using tolower first
sum += static_cast<int>(tolower(a[i])) - aIndex;
}
return sum;
}
Contributed by Ayush Rath.
Trace through main() and determine the output
#include <iostream>
using namespace std;
void convolve(int* a, int* b, int* c, int na, int nb, int nc) {
int tmp[7];
for (int* i = a; i < a + na; i++) {
int index = i - a;
tmp[na - index - 1] = *i;
}
for (int i = 0; i < nc; i++) {
int k = i;
int val = 0;
for (int j = 0; j < nb; j++) {
if (k >= 0 && k < na) {
val += (a[k] * b[j]);
}
k--;
c[i] = val;
}
}
}
int main() {
int a[7] = { 0, 0, 0, 1, 1, 1, 1 };
int b[7] = { 0, 0, 0, 8, 4, 2, 1 };
int c[13];
convolve(a, b, c, 7, 7, 13);
for (int i = 0; i < 13; i++) {
cout << c[i];
if (i % 2 == 0) {
cout << endl;
} else {
cout << "" "";
}
}
return 0;
}In convolve() the first for loop reverses a and stores it in tmp.
The second for loop determines what values are stored in c. Run through a few iterations to determine what is happening.
First iteration:
The first element of b is multiplied by the last element of a, the result is stored in c[0]
Second Iteration:
The first two elements of b are multiplied by the last two elements of a, the sum of the products is stored in c[0].
Take note of the pattern and extrapolate:
1:
*******
*******
2:
*******
*******
3
*******
*******
...
13:
*******
*******
When the contents of c are printed, there is a line break after every even indexed element, note that arrays in C++ start with an index of 0.
So the solution is:
0
0 0
0 0
0 8
12 14
15 7
3 1
Contributed by Ginny Wang.
Given an input string, reverse the string word by word (separated by space).
Input: "the brown fox"
Output: "eht nworb xof"
#include <string>
#include <algorithm>
using namespace std;
// you can also implement your own reverse function
string reverseWords(string s) {
string str = "";
int l = s.size();
if (!l)
return;
reverse(s.begin(), s.end());
int index = 0;
for (int i = 0; i < l; i++) {
if (s[i] != ' ') {
if (index != 0)
s[index++] = ' ';
int j = i;
for (j = i; j < l && s[j] != ' '; j++) {
s[index] = s[j];
index++;
}
reverse(s.begin()+index-(j-i), s.begin()+index);
i = j;
}
}
s.erase(s.begin()+index, s.end());
return s;
}
Contributed by Kaitlyn Cason.
One simple way to encrypt text is to write all of the even-index (starting at 0)
characters, followed by all of the odd index characters, ignoring punctuation and
whitespace. For example, we might encode "I love CS133" as "IoeS3lvC13". Write a
method called encrypt that takes a String as a parameter and returns a new String object
that represents the result of encrypting the parameter String. Complete the method
signature and the body of the method below::
Input: "I love CS31"
Output: "IoeS3lvC13"
Input: ""
Output: ""
Input: "look!at!this!encryption!"
Output: "loatiecytookthsnrpin"
#include <iostream>
#include <stdio.h>
using namespace std;
string encrypt(string source) {
// Initialize strings for odds and evens
string odds = "";
string evens = "";
// Since we index at 0, isEvens starts off TRUE
bool isEvens = true;
for (int i = 0; i < source.length(); i++) {
char c = source[i];
// Ignore whitespace and punctuation
if (isalpha(c) || isdigit(c)) {
if (isEvens) {
evens += c;
} else {
odds += c;
}
// Keep track of index (odd/even)
isEvens = !isEvens;
}
}
return evens + odds;
}Contributed by Jerry Liu.
Given a string, write a function that returns a compressed string. Assume an empty string returns empty string.
You are allowed to use the built-in to_string function.
Given "aaaaabbbc", the function should return "5a4b1c".
Given "1", the function should return "11".
The only tricky part is the line right before return result, which includes the last set of characters and corresponding count. The code inside the for loop does not take care of the last set of characters. During an exam, make sure you go through your code with some input!
#include <iostream>
#include <string>
using namespace std;
string compress(const string& s) {
if (s.empty())
return s;
string result;
char prev = s[0];
int count = 1;
for (int i = 1; i < s.size(); i++) {
if (prev == s[i]) {
count++;
} else {
result += to_string(count) + prev;
prev = s[i];
count = 1;
}
}
result += to_string(count) + prev;
return result;
}
int main() {
string s = "aaaaabbbc";
cout << compress(s) << endl;
s = "c";
cout << compress(s) << endl;
}Contributed by Regan Hsu.
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0]
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void moveZeroes(vector<int> nums) {
int j = 0, i = 0;
for (; i < nums.size(); i++, j++) {
if (nums[i] == 0) {
while (i < nums.size()-1 && nums[i] == 0) {
i++;
}
}
nums[j] = nums[i];
}
while (j < i) {
nums[j] = 0;
j++;
}
}Contributed by Changfei Shi.
Given two non-negative numbers num1 and num2 represented as strings, return the sum of num1 and num2.
Note:
- Both
num1andnum2contains only digits 0-9. - Both
num1andnum2do not contain any leading zero. - You cannot use the function
atoior otherwise directly convert string to integer or vice versa.
string addStrings(string num1, string num2) {
int i = 0;
int carry = 0;
string sum = """";
while (i < num1.size() || i < num2.size()) {
int a, b;
// Convert both of the values to their integer representations
if (i < num1.size())
a = (num1[num1.size() - 1 - i]) - '0';
else
a = 0;
if (i < num2.size())
b = (num2[num2.size() - 1 - i]) - '0';
else
b = 0;
// Check for the sum of the two values + the carry value
sum = static_cast<char>((a + b + carry) % 10 + '0') + sum;
if ((a + b + carry) >= 10)
carry = 1;
else
carry = 0;
i++;
}
if (carry == 1) {
sum = '1' + sum;
}
return sum;
}Contributed by Your Gabriel Zhou.
You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called "bulls") and how many digits match the secret number but locate in the wrong position (called "cows"). Your friend will use successive guesses and hints to eventually derive the secret number.
Secret number: "1807"
Friend's guess: "7810"
Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)
Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and B to indicate the cows. In the above example, your function should return "1A3B".
Please note that both secret number and friend's guess may contain duplicate digits, for example:
Secret number: "1123"
Friend's guess: "0111"
In this case, the 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return "1A1B".
You may assume that the secret number and your friend's guess only contain digits, and their lengths are always equal.
string getHint(string secret, string guess) {
int len = secret.size();
int bnum = 0, cnum = 0; // bnum: number of bulls, cnum: number of cows
vector<int> cnt1(10, 0), cnt2(10, 0);
for (int i = 0; i < len; i++) {
int n1 = secret[i] - '0', n2 = guess[i] - '0';
if (n1 == n2) {
bnum++;
}
else {
if (cnt2[n1]) {
cnum++;
cnt2[n1]--;
}
else {
cnt1[n1]++;
}
if (cnt1[n2]) {
cnum++;
cnt1[n2]--;
}
else {
cnt2[n2]++;
}
}
}
return to_string(bnum) + "A" + to_string(cnum) + "B";
}
Contributed by Robert Zalog
Implement the function provided by the following function header:
void removeCharacter(char *cstring, char c);,
which removes the character c from the C-string cstring. There is guaranteed to be only one instance of the character c in cstring.
Example function call:
// cstring defined as "hello world"
removeCharacter(cstring, 'w');
// cstring is now "hello orld"An example of invalid input:
// cstring defined as "hello world"
removeCharacter(cstring, 'l');
// invalid output, more than one instance of 'l' in cstringvoid removeCharacter(char *cstring, char c)
{
char *temp;
for ( ; *cstring != '\0'; cstring++) {
if (*cstring == c) {
temp = cstring+1;
while (*cstring != '\0') {
*cstring = temp;
cstring++;
}
}
}
}Shaan Mathur.
Given a string, can you determine if we can form a palindrome using those letters? Don't worry about actually rearranging the letters, we just want to see if it's possible.
Write a function possiblePalindrome that takes a string as an argument and returns a bool. This function should return true if the letters in the string can be rearranged such that a palindrome can be formed. If not, it should return false.
racecar -> true
racecra -> true
rcaearc -> true
racecara -> false
#include <string>
using namespace std;
// We want to determine whether the given string can be rearranged to form
// a palindrome. In other words, there should be an even amount of letters of each type.
// NOTE: This is a CS31 approach to the problem. In CS32, you will learn approaches that are
// even cooler, faster, and more interesting than this approach.
bool possiblePalindrome(string word) {
char foundOdd = '\0';
for (int i = 0; i < word.size(); i++) {
int count = 0; // number of instances of word[i]
for (int j = 0; j < word.size(); j++) {
if (word[i] == word[j])
count++;
}
// If there is an even amount, then there should be a way to rearrange the
// characters so that we can form a palindrome (since we can divide them
// and place each half on each side of our palindrome.
// If there is an odd amount, then that is acceptable if word is of odd size
// (one character in the middle will have no matching pair) and there an odd
// amount occurs only once (only ONEcharacter has no matching pair).
if (count % 2 == 1) {
// count is odd so we have one unmatched pair
if (word.size() % 2 == 1 && (foundOdd == '\0' || foundOdd == word[i])) {
// word size is odd and we hadn't found an unmatched pair before (or
// we did, but for this letter), so it's okay
foundOdd = word[i];
continue;
} else {
// word size is even OR we already found an unmatched pair before.
// Either way, this doesn't work
return false;
}
}
}
return true; // We were able to check every letter successfully! We CAN form a palindrome!
}
/* Closing thoughts...
Is there a case where this function wouldn't work? It's subtle, but possible. Think about it...
(And an optional hint to motivate CS32)
Is there anything about this implementation that seems unnecessary? If the string was of length
10, how many times would we check if word[i] == word[j]? How about 100? 1000? How about for
arbitrary N?
Believe it or not, if you take CS32 you'll figure out how to do this with only one for loop... :)
*/© 2017 UCLA UPE Tutoring Committee.