-
Notifications
You must be signed in to change notification settings - Fork 6
CS 31 (Spring '17)
Contributed by Srivishnu Ramamurthi. Solution previously had running out of bounds problems, corrected by Colin Yang.
The following function eliminates duplicate characters that are next to each other in a string.
If a is equal to "aabbacc" and n is equal to 7, the function would turn a into "abac123" and would return 4. What character do variables 1, 2, and 3 correspond to?
int eliminateDuplicates(char *a, int n) {
if (n < 0)
return -1;
for (int i = 0; i < n; i++) {
if (i + 1 < n && a[i] == a[i + 1]) {
for (int j = i; j < n - 1; j++)
a[j] = a[j + 1];
i--;
n--;
}
}
return n;
}Variables 1, 2, and 3 would all correspond to character c. This is due to the fact that when a character is supposed to be deleted, the function shifts over the array from right to left. Due to this, the garbage value will always be the value of the character at the largest index in the array.
Contributed by Jamie Yu.
Takes in a character array and a character to search for. Return the number of instances the character appears in the array.
input: char foo[10] = {'u','c','l','a','b','r','u','i','n','s'};
calculatetotal(foo,'u') should return 2
//
// findtotal.cpp
//
// Created by Jamie Yu on 5/26/17.
// Copyright © 2017 Jamie Yu. All rights reserved.
//
#include <iostream>
using namespace std;
int calculatetotal(const char* str, char chr) {
int total = 0;
while (*str != 0) {
if (*str == chr) {
total++;
}
str++;
}
return total;
}
int main(){
char foo[10] = {'u','c','l','a','b','r','u','i','n','s'};
cout << calculatetotal(foo,'u') << endl;
return 0;
}Contributed by Timothy Margono.
Consider the following array declaration int foo[10]; that has been initialized with 10 random int values.
Write a function int sum(int foo[]) that takes as input the 10 element array foo and outputs the sum of all its elements.
Use only pointers to traverse the array and access its elements.
If foo is declared to be int foo[10] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; then int sum(int foo[]) outputs 10.
#include <iostream>
int count(int foo[]) {
int count = 0;
for (int* i = foo; i != foo + 10; i++) {
count += (*i);
}
return count;
}
int main() {
int foo[10] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
std::cout << count(foo) << std::endl;
return 0;
}Contributed by Koyoshi Shindo.
Implement the method hasDuplicate(int array[], int n) that checks whether array has duplicate elements or not. n is always the size of the array.
int foo[5] = {16, 2, 3, 4, 5};
int bar[5] = {4, 1, 3, 15, 1};
hasDuplicate(foo, 5); // returns false because foo does not have duplicates
hasDuplicate(bar, 5); // returns true because bar has two "1" in itbool hasDuplicate(int array[], int n) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (array[i] == array[j]) return true;
}
}
return false;
}Contributed by Jonathan Chon.
Asks students to (a) write a function that returns a bool and accepts an int that checks whether the input is a prime number. Remember, 1 is not a prime number. (b) Write a main function that uses part a to print out the first 100 prime numbers
#include <iostream>
using namespace std;
bool isPrime(int x) {
if (x < 2)
return false;
for (int i = 2; i < x; i++) {
if (x % i == 0)
return false;
}
return true;
}
//Lists first 100 print numbers using isPrime() function
int main() {
int i = 0;
int j = 0;
while (i < 100) {
if (isPrime(j)) {
i++;
cout << j << endl;
}
j++;
}
}Contributed by Dharma Naidu.
Given an array of integers, its size, and a specified element, find the index of the specified element closest to the center. This item is guaranteed to be in the array, and if two are equidistant, you may return either.
#include <stdio.h>
#include <iostream>
using namespace std;
int find_int(int find_this, int array[], int size) {
int searchingHere = size / 2;
int previousSearchCounter = 0;
if (size <= 2) {
if (array[0] == find_this) {
return 0;
}
return 1;
}
while (true) {
if (array[searchingHere] == find_this) {
return searchingHere;
}
if (previousSearchCounter < 0)
previousSearchCounter = -1 * (previousSearchCounter) + 1;
else
previousSearchCounter = -1 * (previousSearchCounter) - 1;
searchingHere += previousSearchCounter;
}
}
int main() {
int foo[10] = {4, 1, 1, 1, 1, 1, 1, 4, 1, 1};
cout << find_int(4, foo, 10) << endl; //should print 7
return 0;
}
Contributed by Brian Raymond.
You have been given a pointer to a cstring which is made up of multiple words, a word being any sequence of alphabetical characters. Your employer wants to know the size of the longest of these words in this string. Create a function which as its single input takes a pointer to a cstring and outputs the length of the longest word or words within or -1 if no words exist within the string.
char[] str1 = "How long would the longest word be if the longest word could string loooongier words?";
Input: &str1
Output: 10
char[] str2 = "^&)%^&Testing&%^)& if sp3cial char@cters count";
Input: &str2
Output: 7
char[] str3 = "^&)3%!$@#^#4%&%@3@%^&2";
Input: &str3
Output: -1
char[] str4 = "Words of Equal Sizes";
Input: &str4
Output: 5
#include <iostream>
#include <cctype>
using namespace std;
int longestWord(char* cstring) {
char* pos = cstring;
int record = -1, curLen = 0;
while (*pos != '\0') { // while end of string not reached
if (!isalpha(*pos)) { // if char is not letter, new word starts
curLen = 0;
} else { // word continues
curLen++;
if (curLen > record) // check if current word is now longest
record = curLen;
}
pos++;
}
return record;
}Contributed by Artiom Arutiunov.
The problem asks you to analyze the function numbersinString and find what the output would be.
#include <iostream>
#include <string>
using namespace std;
string numbersInString(string word) {
string returnString;
for (int i = 0; i < word.size(); i++) {
switch (word[i]) {
case '1':
returnString += "1";
break;
case '2':
returnString += "2";
break;
case '3':
returnString += "3";
break;
case '4':
returnString += "4";
break;
case '5':
case '6':
case '7':
returnString += "7";
break;
case '8':
returnString += "8";
break;
case '9':
returnString += "9";
break;
default:
break;
}
}
return returnString;
}
int main(int argc, const char * argv[]) {
string input1 = "Artiom123456789";
string input2 = "5556677";
string input3 = "0Artiom0";
string result;
result = numbersInString(input1);
cout << result << endl;
result = numbersInString(input2);
cout << result << endl;
result = numbersInString(input3);
cout << result << endl;
}Input 1: Artiom123456789
Corresponding output: 123477789
Input 2: 5556677
Corresponding output: 7777777
Input 3: 0Artiom0
Corresponding output:
Contributed by Austin Guo.
Remove all the a's (case insensitive) in a fixed size 10 character array arr. You are not required to consider efficiency in your final solution. Return the pointer to the beginning of the input character array.
#include <string>
using namespace std;
char* removeA(char* arr, int size) {
int size = 10;
for (int i = 0; i < size; i++) {
if (arr[i] == 'a' || arr[i] == 'A') {
int k = i;
while (k < size - 1) {
arr[k] = arr[k+1];
k++;
}
arr[k] = '\0'; // end the C-string
size--;
}
}
return arr;
}Contributed by Cian Costello.
Create a struct that will hold the 4 doubles in a 2 by 2 matrix:
| a b |
| c d |
Then write a function that will invert this matrix and return the inverted struct. Finally, in the main function, assign the inverted matrix into a 2D array and print out the values of the inverted matrix using for-loops while printing the numbers with exactly 2 digits after the decimal place.
Print outputs should include the "|" to delineate the array as shown above.
#include <iomanip>
#include <iostream>
#include <string>
using namespace std;
struct Matrix2 {
double a;
double b;
double c;
double d;
};
Matrix2 invert_struct(Matrix2 &input) { // invert struct matrix
double det = (input.a * input.d) - (input.b * input.c); // calculate the determinant
Matrix2 output;
output.a = input.d/det;
output.d = input.a/det;
output.b = input.b/det*-1;
output.c = input.c/det*-1;
return output;
}
int main() {
Matrix2 inverted, in_m;
// hard coded initial values for the matrix
in_m.a = 3;
in_m.b = 1;
in_m.c = 5;
in_m.d = 8;
inverted = invert_struct(in_m);
double matrix_2[2][2];
matrix_2[0][0] = inverted.a;
matrix_2[1][0] = inverted.b;
matrix_2[0][1] = inverted.c;
matrix_2[1][1] = inverted.d;
for (int i = 0; i < 2; i++) {
cout << "|";
for (int j = 0; j < 2; j++) {
cout << setprecision(2) << fixed << matrix_2[j][i] << " ";
}
cout << "|" << endl;
}
}Contributed by Zhouheng Sun.
Consider the following problems regarding C-string and C++ string:
-
Does the following code compile?
char bar1[4] = "foo\0";
-
What's the output of the following?
char bar2[] = "foo\0"; cout << strlen(bar) << endl;
-
What's the output of the following?
string bar3 = "foo"; bar3 += "\0"; cout << bar3.size() << endl;
-
Does the following two blocks of code compile (independent of each other)?
// block 1
string bar4 ;
bar4 = bar4 + "foo" + "bar";
// block 2
string bar5;
bar5 += "foo" + "bar";-
No. The literal is seen as "foo\0\0" so the compiler expects bar1's type to be char[N], where N is at least 5.
-
The answer is 3. Strlen stop counting at the first zero byte.
-
The answer is 3. Notice "\0" is a c-string literal and it by design can't store zero byte, so it will be taken as empty when passed to the c++ string bar3's + operator. Note that C++ string is able to store zero bytes but you must do it without using c-string literals.
-
Yes and No. Notice that the expression is evaluated from left to right, meaning that bar4 + "foo" will be evaluated first returning a C++ string. Therefore
bar4 + "foo" + "bar"is simply(bar4 + "foo") + "bar", i.e. a "C++ string plus const char*" operation, which is valid. For similar reasons, in bar5"foo" + "bar"is evaluated first but failed because by C++ standard it doesn't make sense to add two const char pointers together."
Contributed by Vince Wu.
Write a constructor and a destructor for the class bug that satisfy the following requirements:
- The member variables m_capacity and m_memory are initialized by the constructor arguments.
- the main function does not cause a memory leak.
#include <iostream>
#include <string>
#include <cctype>
using namespace std;
class bug {
public:
bug(int capacity, char mem[]) {
//write your code here
}
~bug() {
//write your code here
}
private:
int m_capcity;
char* m_memory;
};
int main() {
char mem[6] = "hello";
bug buggy(5, mem);
}
#include <iostream>
#include <string>
#include <cctype>
using namespace std;
class bug {
public:
bug(int capacity, char mem[]) {
m_capcity = capacity;
m_memory = new char[m_capcity];
snprintf(m_memory, capacity, mem);
}
~bug() {
delete m_memory;
}
private:
int m_capcity;
char* m_memory;
};
int main() {
char mem[6] = "hello";
bug buggy(5, mem);
}Contributed by Jennifer Xu.
Given an integer, produce another integer by reversing the digits.
Input: 123456789
Output: 987654321
This solution works because of integer truncation.
#include <iostream>
using namespace std;
// Reverse the digits of an integer
int main() {
int forwards = 12345;
int backwards = 0;
while (forwards > 0) {
backwards *= 10;
backwards += forwards % 10;
forwards /= 10;
}
cout << backwards << endl; // should print out 54321
}Contributed by Zhiyuan Yang.
Determine the output of the following code.
#include <iostream>
using namespace std;
void mystery(int& a, int* b, int c) {
a++;
c += a;
*b -= a;
}
int main()
{
int a = 1, b_val = 2, c = 3;
int *b = &b_val;
mystery(c, b, a);
cout << a << ' ' << *b << ' ' << c;
}The output should be: 1 -2 4
Contributed by Andrew Chen.
Write a function that takes a single string input containing a time in 12-hour (AM/PM) format and converts it to military time (24-hour). Note that midnight is 12:00:00AM on a 12-hour clock and 00:00:00 on a 24 hour clock.
The input will be a string containing time in proper 12-hour format (hh:mm:ssAM or hh:mm:ssPM).
Sample input:08:30:11PM
The return value should be a string with the corresponding 24-hour time (hh:mm:ss, without AM or PM).
Sample output: 13:52:20
The function can look something like this:
string convertTime(string time) {
string output;
//code here
return output
}This solution takes advantage of the specific input format to extract the hour digits as integers, which may need to be changed. The hour is incremented by 12 if the time is 1pm or later, and converted back to a string to be returned. The output does not need AM or PM, so the final string is effectively truncated.
string convertTime(string time) {
int hour = (time[0] - '0')*10 + (time[1] - '0');
if (hour < 12 && time[8] == 'P')
hour += 12;
if (hour == 12 && time[8] == 'A')
hour = 0;
char tens = (hour / 10) + '0';
char ones = (hour % 10) + '0';
string output = time.substr(0, 8);
output[0] = tens;
output[1] = ones;
return output;
}Contributed by Colin Yang.
What will the following program output? Notice the difference between character pointer and character array. Also remember sizeof operator finds the size of variable represented in memory. You can assume this program runs on a 64-bit machine, where the size of a pointer is 8.
const char *charPtr = "hello world";
cout << sizeof(charPtr) << endl;
cout << strlen(charPtr) << endl;const char charArr[] = "hello world";
cout << sizeof(charArr) << endl;
cout << strlen(charArr) << endl;8
11
12
11
Explanation: charPtr points to the string literal in data segment of the program, while charArr stores the string on the stack.
- size of a pointer is 8
-
strlenfinds the length of a null terminated string - char array also stores the null character
- same as previous
strlen
Contributed by Manav Maroli.
Sort an array using bubble sort.
int a[] = {0, 6, 7 , 10, 2, 5};
bubblesort(a, 6);
for (int i = 0; i < 6; i++) {// Testing bubblesort function
std::cout << a[i] << std::endl;
}
// Print out 0, 2, 5, 6, 7, 10#include <iostream>
void bubblesort(int arr[], int size);
int main() {
int a[] = {0, 6, 7 , 10, 2, 5};
bubblesort(a, 6);
/*
for (int i = 0; i < 6; i++) {// Testing bubblesort function
std::cout << a[i] << std::endl;}
*/
}
void bubblesort(int arr[], int size) {
int i = 0;
int j = 0;
for (; i < size; i++) {
for (j = i + 1; j < size; j++) {
if (arr[j] < arr[i]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}Contributed by Hiu Man Yeung.
Write a function that takes a c string as the parameter and eliminates all duplicate alphabets in the c string. Assume all alphabets in the c string are lower cases.
Example 1: input: bbbbac output: bac Example 2: input: abbacd output: abcd
void delDuplicates(char a[]) {
int b[26];
for (int i = 0; i < 26; i++) {
b[i] = 0;
}
for (int i = 0; a[i] != '\0'; i++) {
if (!b[a[i]-'a']) {
b[a[i]-'a'] = 1;
} else {
for (int j = i; a[j] != '\0'; j++) {
a[j] = a[j+1];
}
i--;
}
}
} Contributed by Qianmeng Chen.
Given two integer arrays sorted by ascending order, write a function to merge them and put the result in a given array. The lengths of arrays are given and you can assume the array used to store the results is large enough. Also, you can assume the result array is neither of the two input arrays.
The function interface is given below:
void mergeSorted(int arr1[], int arr2[], int len1, int len2, int result[]);int a1[] = {6, 8, 9, 10};
int a2[] = {4,7};
int a3[6];
mergeSorted(a1, a2, 4, 2, a3);
//now a3 == {4, 6, 7, 8, 9, 10}void mergeSorted(int arr1[], int arr2[], int len1, int len2, int result[]) {
int length = len1 + len2;
for (int i = 0; i < length; i++) {
if (len1 <= 0) {
result[i] = *arr2;
arr2++;
len2--;
} else if (len2 <= 0) {
result[i] = *arr1;
arr1++;
len1--;
} else if (*arr1 < *arr2) {
result[i] = *arr1;
arr1++;
len1--;
} else {
result[i] = *arr2;
arr2++;
len2--;
}
}
}Contributed by Stephanie Tran
Given the following main function, please implement the ‘multiplier’ function, which takes in 3 arguments and returns an int. The multiplier function takes in int x and int n, returning the integer that results from the expression, x^n. It also determines if the result is an even or odd value, and assigns the corresponding answer to the evenOrOdd string.
using namespace std;
int main() {
int x, n, result;
string evenOrOdd;
cout << "Please enter a value for x: " << endl;
cin >> x;
cout << "Please enter a value for n: " << endl;
cin >> n;
result = multiplier(x, n, evenOrOdd);
cout << "The resulting value of " << result << " is " << evenOrOdd << endl;
}If x is 4 and n is 2, the output should be: “The resulting value of 16 is even”
To implement the multiplier function, we must remember that evenOrOdd can only be updated with either “even” or “odd” if it’s passed in by reference. Otherwise, the changes made in multiplier only exist locally within the function and will have no effect on the evenOrOdd string in main once it returns. This means the declaration for multiplier is: int multiplier(int x, int n, string &evenOrOdd); Furthermore, we need to create two local variables within multiplier. The first is int accumulator, which gets multiplied to int x during each iteration. An accumulator is necessary to constantly update the resulting value from each multiplication operation without changing the original value of x. The second local variable we need is int counter. Counter gets incremented during each iteration of the while loop. It serves as the test condition for the loop since the loop only breaks once counter exceeds the value of n. When counter > n, we’ve successfully calculated x^n. To determine whether the result is even or odd, we simply use the modulo operator to find the remainder. If result modulo 2 has no remainder, then it is even because it was able to be divided by 2 perfectly.
int multiplier(int x, int n, string &evenOrOdd) {
int accumulator = 1;
int counter = 1;
while (counter <= n) {
accumulator = accumulator * x;
counter++;
}
if (accumulator %2 == 0)
evenOrOdd = "even";
else
evenOrOdd = "odd";
return accumulator;
}Contributed by Xiang (Allan) Chen.
Write a function that checkIP that, given a single input C-string s, checks whether s is a valid IP address. A real world IP address has many representations, but for the purposes of this problem, a valid IP address has the form x.x.x.x, where each x is a number between 0 and 255, inclusive. Note that this means x can contain anywhere between 1 and 3 digits.
In your implementation, you may NOT use the C++ string class or any library functions EXCEPT isdigit() and strlen().
The function prototype is as follows:
bool isValidIP(const char* s);The following driver routine shows examples of valid and invalid addresses. After you implement the function above, you may prepend it to the following code and compile the resulting file for testing.
int main() {
assert(isValidIP("8.8.8.8"));
assert(isValidIP("192.168.1.1"));
assert(isValidIP("1.2.3.40"));
assert(isValidIP("101.23.94.113"));
assert(isValidIP("000.0.010.1")); // leading zeros are allowed
assert(!isValidIP("100.212.999.2")); // the third group (999) is larger than 255
assert(!isValidIP("a.330.292.1")); // the first group contains a letter
assert(!isValidIP("342.92.30.29'")); // the first group (342) is larger than 255
assert(!isValidIP("203.2929222")); // only 2 groups, 2nd group too large
assert(!isValidIP("the earth is flat")); // absolute nonsense
assert(!isValidIP("10.67.3233.220")); // third group has too many digits
assert(!isValidIP("10.67.33.")); // missing last group
assert(!isValidIP("10.67.2.256")); // last group too large
assert(!isValidIP("10.67.3")); // missing last group
assert(!isValidIP(".10.67.3")); // missing first group
std::cout << "ALL TESTS PASSED" << std::endl;
}#include <cassert>
#include <cstring>
#include <cctype>
#include <iostream>
bool isValidIP(const char* s) {
int numGroups = 0;
for (size_t i = 0; i < strlen(s); i++) {
int accumulator = 0;
int numDigits = 0;
while (i < strlen(s)) {
if (isdigit(s[i]) && numDigits < 4) {
accumulator += accumulator*10 + s[i] - '0';
} else if (s[i] == '.' && numDigits > 0) {
break;
} else {
return false;
}
i++;
numDigits++;
}
numGroups++;
if (numGroups > 4 || accumulator < 0 || accumulator > 255) {
return false;
}
}
return numGroups == 4;
}
int main() {
assert(isValidIP("8.8.8.8"));
assert(isValidIP("192.168.1.1"));
assert(isValidIP("1.2.3.40"));
assert(isValidIP("101.23.94.113"));
assert(isValidIP("000.0.010.1"));
assert(!isValidIP("100.212.999.2"));
assert(!isValidIP("a.330.292.1"));
assert(!isValidIP("342.92.30.29'"));
assert(!isValidIP("203.2929222"));
assert(!isValidIP("the earth is flat"));
assert(!isValidIP("10.67.3233.220"));
assert(!isValidIP("10.67.33."));
assert(!isValidIP("10.67.2.256"));
assert(!isValidIP("10.67.3"));
std::cout << "ALL TESTS PASSED" << std::endl;
}Contributed by Michelle Duan.
This problem challenges students to add to a given C++ class by writing definitions for various public member functions. A class skeleton with function declarations and descriptions of the intended behavior of these functions is given; students must then write working definitions for these functions outside of the class.
Students must take care to use the proper syntax for defining a class (e.g. placing the class name and scope resolution operator prior to a member function name if it is defined outside of a class) and must also apply previously learned C++ constructs (such as if-else branches) to correctly complete certain public member functions.
/*
Suppose you are given the following partially completed code
for the Flashlight class.
Members of a Flashlight object include an integer representing
the number of batteries in the Flashlight and a string that
represents the current status of the Flashlight (on or off).
Users of a Flashlight object can check the flashlight's
current status (on or off), create a new Flashlight with
a given status and number of batteries, check the number of
batteries in the Flashlight, or use up energy from the
batteries for a given integer amount of time.
*/
#include <string>
using namespace std;
class Flashlight {
public:
Flashlight(string initialStatus, int initialBatteries);
/*
Returns "on" if the Flashlight is currently on,
"off" otherwise
*/
string checkStatus() const;
/*
Returns the current number of full/partially full batteries
in the flashlight
*/
int getNumBatteries() const;
/*
If the flashlight is currently off, do nothing and
immediately return.
Otherwise, use up energy for mins minutes where each
minute consumes 2 batteries. If all batteries have
been depleted, do nothing. If the amount of energy
to be used up is greater than the amount currently
stored int the Flashlight, use up as much energy as
possible and set the Flashlight's number of batteries
to zero.
Return true if the number of batteries has been modified,
false otherwise.
*/
bool useEnergy(int mins);
private:
// Status indicator of Flashlight--"on" if the flashlight
// is on, "off" otherwise
string m_status;
// Number of batteries in the Flashlight
int m_batteries;
};
/*
1.) Write the definition of the checkStatus() function so that it matches the given declaration.
2.) Write the definition of the getNumBatteries() function so that it matches the given declaration.
3.) Write the definition of the useEnergy() function so that it matches the given declaration. You may assume that m_status will always be either "on" or "off" and that mins will always be a whole, nonnegative integer. You may also assume that a Flashlight object is always initialized with a whole, nonnegative number of full batteries.
*/
int main() {
}These are some possible code solutions to the three-part question. Slight variants of these solutions may also be correct.
1.)
string Flashlight::checkStatus() const
{
return m_status;
}
2.)
int Flashlight::getNumBatteries() const
{
return m_batteries;
}
3.)
bool Flashlight::useEnergy(int mins)
{
if(m_status == "off" || m_batteries <= 0)
return false;
int numBatteriesToUse = mins * 2;
if(numBatteriesToUse > m_batteries)
m_batteries = 0;
else
m_batteries = m_batteries - numBatteriesToUse;
return true;
}
Contributed by Nicole Wong.
Given two arrays of doubles, x and px, where the the probability of x[i] is px[i], and the length of both arrays, n. Implement a function to return the expected value (average) of the data.
The formula for expected value is the sum of all possible values each multiplied by the probability of its occurrence.
Calculating the expected value of a dice roll:
Input:
double x[] = {1, 2, 3, 4, 5, 6}double px[] = {1.0 / 6, 1.0 / 6, 1.0 / 6, 1.0 / 6, 1.0 / 6, 1.0 / 6};int n = 6
Output:
- Function should return 3.5
// Given an array of values x and an array of probabilities px where
// the probability of x[i] is px[i], return the expected value
// of x. The length of both arrays is n.
//
// The formula for expected value (aka average) is the sum of all
// possible values each multiplied by the probability of its occurrence.
double expected_value(double x[], double px[], int n) {
double answer = 0;
for (int i = 0; i < n; i++) {
answer += x[i] * px[i];
}
return answer;
}
Contributed by Nicole Wong.
In computer networking, link layer data framing with the HDLC byte stuffing protocol uses a special byte, 01111110, to mark the beginning of a data frame. In order to avoid having this special byte appear in the data, we need to pad the data by inserting a zero after each set of five ones. These extra zeroes are considered overhead.
Write a function to recursively count the number of five consecutive 1's in a string, not including overlapping strings of ones.
count_five_ones("01111110") returns 1
using namespace std;
int count_five_ones(string s) {
if (s.length() < 5) {
return 0;
} else {
if (s[0] == '1' && s[1] == '1' && s[2] == '1' && s[3] == '1' && s[4] == '1') {
if (s.length() > 5)
return 1 + count_five_ones(s.substr(5));
else
return 1;
} else {
return count_five_ones(s.substr(1));
}
}
}
Contributed by Anthony Xue.
Implement the function isAlphabetical that takes a string and will return true if the words of the string are in alphabetical ordering. The words in the string will be considered in alphabetical ordering if the first word starts with A or a, the second with B or b, the third with C or c, and so on. You can assume that the strings we are testing only have 26 words as most, so valid strings will have a word that starts with A or a and end with a word that starts with Z or z.
isAlphabetical("Apples Beach car dinner elephant Fish") will return true
isAlphabetical("Aloha bees joe bruin ucla") will return false
In order to determine whether or not our words are in alphabetical ordering, we must check the first letter of each word with the next in order letter. We know that the first letter we need to check for is "A" or "a", and we can keep track of when we hit the first letter of a word either by seeing if its the first character in the string or if it follows a space. If the first letter of the word is not the expected letter, we simply return false. If we succeed in looping through the string, we know it is in alphabetical ordering, and we return true.
bool isAlphabetical(const string input) {
char next_upper = 'A', next_lower = 'a';
bool first = true;
for (int i = 0; i < input.size(); i++) {
if (input[i] == ' ') {
first = true;
} else if (first) {
if (input[i] != next_upper && input[i] != next_lower) {
return false;
}
first = false;
next_upper++;
next_lower++;
}
}
return true;
}Contributed by Yun Xu.
Write the function isPermutation that takes two string argument and checks if they are permutation of each other
The strings "dog" and "god" should return true.
#include <iostream>
#include <string>
using namespace std;
bool isPermutation(string str1, string s) {
}
int main() {
string str1 = "god";
string str2 = "dog";
if (isPermutation(str1, str2))
cout << "True" << endl;
else
cout << "False" << endl;
// should return true
return 0
}bool isPermutation(string str1, string s {
// if two strings have different length, they can't be permutation of each other
if (str1.length() != str2.length()) {
return false;
}
// create an array that keeps count of how frequent the characters appear
int charFreq[12] = { 0 }; // assumption: ASCII
for (int i = 0; i < str1.length(); i++) {
// increment count for characters that str1 has
charFreq[str1.at(i)]++;
}
for (int i = 0; i < str2.length(); i++) {
// decrement count if character shows up in str2
charFreq[str2.at(i)]--;
// if any count happen to be negative, that means it's a character that only exist in str2
// hence it's for sure not a permutation, so can immediately return false
if (charFreq[str2.at(i)] < 0) {
return false;
}
}
for (int i = 0; i < str1.length(); i++) {
// if the two strings are permutation, the counts that incremented in
// the first for loop should have all
// decremented back to 0 after the second for loop for str2
// if any of the count is not 0, return false
if (charFreq[str1.at(1)] != 0)
return false;
}
return true;
}Contributed by Xuening Wang.
#include <iostream>
using namespace std;
int main(){
char s1[] = "I love UCLA";
char *s2 = s1;
s2 += 2;
s2[4] = '\0';
cout << "s1 = " << s1 << endl;
cout << "s2 = " << s2 << endl;
return 0;
}s1 = I love
s2 = loveContributed by Vishesh Sharma.
Write a function int* findDiffs(char str1[], char str2[]) that takes two C-strings str1 and str2, and returns an integer array containing the indices at which these two strings differ (i.e. have a different character) up to the length of the shortest string. Note that your implementation must be case sensitive and you are not allowed to make any assumptions about the lengths of the two strings. The array returned by your function must end with -1, which denotes the end of the array.
Example 1:
- Input:
str1 = "UCLA is the best!", str2 = "Is UCLA the best?" - Returned array:
0, 1, 2, 3, 4, 5, 6, 16, -1
Example 2:
- Input:
str1 = "CS31 is easy!", str2 = "CS31 is easy!" - Returned array:
-1
#include <iostream>
using namespace std;
int* findDiffs(char str1[], char str2[]) {
int shorter_len;
int str1_len = strlen(str1);
int str2_len = strlen(str2);
if (str1_len < str2_len) {
shorter_len = str1_len;
} else {
shorter_len = str2_len;
}
int* diff_indices = new int[shorter_len + 1]; // 1 extra place to keep track
// of end of array using -1
int j = 0; // keeps track of next available
// index in diff_indices
for (int i = 0; i < shorter_len; i++) {
if (str1[i] != str2[i]) {
diff_indices[j] = i;
j++;
}
}
diff_indices[j] = -1;
return diff_indices;
}
void main() {
// A simple test of the function
char str1[] = "UCLA is the best!";
char str2[] = "Is UCLA the best?";
int* diffs = findDiffs(str1, str2);
for (int i = 0; diffs[i] != -1; i++) {
cout << diffs[i] << endl;
}
getchar();
}Contributed by Ernest Cheng
Write a switch statement that takes in an integer of the day number (Monday = 1, Tuesday = 2, etc.) and outputs “This is a weekday” and “This is a weekend day” depending on what day it is.
Input = 5, Prints "This is a weekday"
#include <iostream>
int main() {
int day = 5;
switch (day) {
case 6 :
case 7 : cout << "This is a weekend day";
break;
case 1 :
case 2 :
case 3 :
case 4 :
case 5 : cout << "This is a weekday";
break;
default : cout << "Not a legal day";
break;
}
}Contributed by Danlin Xie.
Return the position of a string in the array such that that string is <= every string in the array (lexicographic order). If there is more than one such string, return the smallest position of such a string. Return −1 if the array has no elements.
string people[5] = { "malory", "lana", "sterling", "cheryl", "cyril" };
int j = locationOfMin(people, 5); // returns 3, since cheryl is earliest
// in alphabetic order
#include <string>
using namespace std;
int locationOfMin(const string a[], int n) {
if (n <= 0)
return -1;
int minPos = 0; // assume to start that min is at position 0
for (int k = 1; k < n; k++)
if (a[k] < a[minPos])
minPos = k;
return minPos;
}Contributed by Nathan Smith.
Temperatures in Farenheit can be converted to celsius with the following formula: T(°C) = (T(°F) - 32) × 5/9. (Celsius to Farenheit is computed in a similar way: T(°F) = T(°C) × 9/5 + 32). Write a function to convert Farenheit to Celsius and Celsius to Farenheit given a double temp, and 2 characters to represent the unit to convert from and to, respectively ('f' or 'c'). If a unit is not supported, simply return the value of temp.
double convert(52, 'f', 'c') -> 11.1111
double convert(52, 'c', 'f') -> 125.6
double convert(30, 'f', 'f') -> 30
double convert(30, 'c', 'x') -> 30
double convert(double temp, char inputUnit, char outputUnit) {
double converted;
if (inputUnit == 'f' && outputUnit == 'c') {
converted = (temp - 32) * (5.0 / 9.0);
} else if (inputUnit == 'c' && outputUnit == 'f') {
converted = temp * (9.0 / 5.0) + 32;
} else {
converted = temp;
}
return converted;
}
Contributed by Aaron Chi.
What does the following code output?
int foo(int x, int &y) {
int a = 2 * y;
y = a + 2;
x = a - 2;
return a * x;
}
int bar(int *x, int y) {
*x += 5;
y = y + *x;
return y / *x;
}
int main() {
int a = 3;
int b = 5;
int c = foo(a, b);
int d = bar(&b, c);
cout << a << endl << b << endl << c << endl << d << endl;
}Let us analyze the result of int c = foo(a, b). a is passed by value while b is passed by reference. In function foo, a is set to 2 * 5, which is 10. y is set to 12, which changes the original parameter b to 12 and x is set to 8. The return value is 80, stored into c. At this point, a has value 3, b has value 12, and c has value 80.
In the function bar, the address of b is passed as parameter x. b is set to 17 by the line *x += 5;. y is set to 17+80, which is 97. The return value is truncated to 5.
The resulting output is:
3
17
80
5
Contributed by Anthony Nguyen.
Given the function prototype 'int findMaxSum(int arr[], int n, int* pos1, int* pos2);' write the code to complete the function. The function should find the maximum value of the sum between any two elements of the array. Then set pointers 'pos1' and 'pos2' to the address of those elements. 'int n' is the number of elements in the array.
// What is the output of the following code:
#include <cstring>
#include <iostream>
using namespace std;
int findMaxSum(int arr[], int n, int* pos1, int* pos2) {
int maxSum = INT_MIN;
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n; j++)
if (arr[i] + arr[j] > maxSum) {
maxSum = (arr[i] + arr[j]);
pos1 = &arr[i];
pos2 = &arr[j];
}
}
return maxSum;
}
Contributed by Jingtao Wang.
implement a function nonRep which takes in a string and turn the first non-repeating character in the string if there is none, return "\0"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
char nonRep(string s) {
int t = s.size();
int count[256] = {0}; // 256 possible characters
for (int i=0; i < t; i++)
count[s[i]]++;
for (int i = 0; i < t; ++i) {
if (count[s[i]] == 1) {
return s[i];
}
}
return 0;
}
Contributed by Emily Chen.
Pascal triangle is a triangilar array of binomial coefficient starting at n = 0 and r = 0; Each entry is seperated by two tabs so that the output has a pyrmid shape like the following. Not: The rows of Pascal's triangle are conventionally enumerated starting with row n = 0. level 0 is just a single number 1.
if pass in 3, output should be:
1 // --- level 0
1 1 // --- level 1
1 2 1 // --- level 2
1 3 3 1 // --- level 3
Similarly, if pass in 5, output will be
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
#include <iostream>
using namespace std;
int factorial(int n) {
int result = 1;
for (int i = n; i > 0; i-- )
result *= i;
return result;
}
int entry(int n , int r) {
if (n < r) return -1;
return (factorial(n)/(factorial(r)*factorial(n-r)));
}
void pascalTriangel(int n) {
// check if n is valid
if (n < 0) {return;}
// iterate through each level
for (int i =0; i <= n; i ++) {
// to produce the tab in front of each level. There are n-1 tabs
for (int k = 0; k < n-i; k++) {
cout << "\t";
}
// Iterate through each entry except for the last one. there are n entries on nth level
for (int j = 0; j < i ; j++) {
cout << entry(i, j) << "\t\t";
}
// there are no tabs after the last entry so we print this seperately.
// There is a newline after the last entry
cout << entry(n, n) << endl;
}
}Contributed by Hiromu Ikeda.
Using the last digit of your ID number for int i, write the output of the following C++ program.
#include <iostream>
#include <string>
using namespace std;
int main() {
int i;
cin >> i;
// the value of int i is equal to the last digit of your ID number.
// you may assume that int i is between 0~9.
if (i % 2 == 0) {
cout << "a" << endl;
}
if (i == 1 || i == 3) {
cout << "b" << endl;
}
if (i % 2 == 1) {
cout << "c" << endl;
}
}
Followup: Write a C++ code with the same functionality, but using case-switch statements instead.
#include <iostream>
#include <string>
using namespace std;
int main(){
int i;
cin >> i;
switch(i){
case 0: case 2: case 4: case 6: case 8:
cout << "a" << endl;
break;
case 1: case 3:
cout << "b" << endl;
break;
case 5: case 7: case 9:
cout << "c" << endl;
break;
}
}
© 2017 UCLA UPE Tutoring Committee.