-
Notifications
You must be signed in to change notification settings - Fork 6
CS 32 (Fall '16)
Contributed by Gopi Suresh.
Given an vector of integers, every element appears twice except for one. Find that single one. Write a function singleNumbers(const vector<int> &vec) that solves this problem in O(n) time complexity.
int main() {
int nums[] = {1, 3, 2, 1, 2};
vector<int> n(nums, nums + sizeof(nums) / sizeof(int));
cout << singleNumber(n)<< endl;
}The above code prints out 3.
For a challenge, think of a way to solve this without using extra memory.
#include <unordered_set>
#include <vector>
#include <iostream>
using namespace std;
int singleNumber(const vector<int> &vec) {
unordered_set<int> s;
for (int i = 0; i < vec.size(); i++) {
if (s.find(vec[i]) != s.end()) {
s.erase(vec[i]);
} else {
s.insert(vec[i]);
}
}
return *s.begin();
}
int main() {
int nums[] = {1, 3, 2, 1, 2};
vector<int> n(nums, nums + sizeof(nums) / sizeof(int));
cout << singleNumber(n);
}Contributed by Robert Zalog
Implement the function provided by the following function header:
int findNum(int *nums, int n, int num);,
which returns the index of a given number num in a sorted (in ascending order) array nums of length n. Your function must not use a for loop and must utilize a recursive function call. In addition, your algorithm must run in O(log n) time complexity. You can assume that the specified value will always be found in the array (e.g., function caller will not ask you to look for 3 in an array that does not contain a 3).
Hint:
You might want to use a helper function that takes a start and an end parameter instead of just n.
Example function call:
int nums[6] = {1, 2, 4, 8, 10, 18};
findNum(nums, 0, 8); // returns 3int findNumHelper(int *, int, int, int);
int findNum(int *nums, int n, int num)
{
return findNumHelper(nums, 0, n, num);
}
int findNumHelper(int *nums, int start, int end, int num)
{
int test = start + (end - start) / 2;
if (nums[test] == num) {
return test;
}
if (nums[test] > num) {
return findNumHelper(nums, start, test, num);
}
if (nums[test] < num) {
return findNumHelper(nums, test+1, end, num);
}
}Contributed by Shaan Mathur.
Assume you have a struct defined as below:
struct Tree {
int data;
std::vector<Tree*> children;
};Write a function int countLeaves(Tree* head) that counts the number of leaves in a tree. HINT: Recursion and Trees tend to go very well together.
Head
N1 N2
N3 N4 N5 N6 N7
This tree has FIVE leaves.
[nullptr]
This "tree" has no leaves.
#include <vector>
struct Tree {
int data;
std::vector<Tree*> children;
};
int countLeaves(Tree* head) {
/* BASE CASES */
// head is an empty tree, in case there are no leaves. Thus return 0.
if (head == nullptr)
return 0;
// The node has no children, which is by definition a leaf. Thus return 1.
if (head->children.size() == 0)
return 1;
/* RECURSION */
// The node has children, so let's count them and return the total count.
int count = 0;
for (int i = 0; i < head->children.size(); i++) {
count += countLeaves(head->children[i]);
}
return count;
}Contributed by Gabriel Zhou.
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is: [ "((()))", "(()())", "(())()", "()(())", "()()()" ]
vector<string> generateParenthesis(int n) {
vector<string> res;
addingpar(res, "", n, 0);
return res;
}
void addingpar(const vector<string>& v, string str, int n, int m) {
if (n == 0 && m == 0) {
v.push_back(str);
return;
}
if (m > 0) { addingpar(v, str+")", n, m-1); }
if (n > 0) { addingpar(v, str+"(", n-1, m+1); }
}Contributed by Katie Luangkote.
Write nodeCount, a recursive function that counts the number of nodes in a tree rooted at node. This is a general tree, where a node can have a variable number of children.
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int val;
vector<Node *> children;
};
int nodeCount(Node *node) {
int count = 1;
for (int i = 0; i < node->children.size(); i++)
count += nodeCount(node->children[i]);
return count;
}
Contributed by Rahul Salvi.
For this question, create a function 'printReversed' that takes a single input std::string and prints it out with the words inside reversed. A word is a sequence of characters followed by a space or newline. The input string will be terminated by a newline character. 'printReversed' should not return anything. 'printReversed' may output an extra trailing space. You may create a single helper function that takes an optional int argument. You may use a loop inside each function call to find a word. There will never be consecutive space characters.
"this is a string\n" --> "string a is this " (with or without the trailing space)
"abcd\n" --> "abcd " (with or without the trailing space)
Two solutions are provided. They are both very similar except in the way that they call themselves to continue the recursion. To find a word, they iterate by characters until a space is found, appending to a temporary string. At this point, they print and return if a newline is found. Otherwise, the function is called again to find another word. Finally, the words are printed out in reverse similar to a post-order tree traversal. These solutions do print out a trailing space.
The first solution uses a helper function that tracks the index to begin looking for a word and passes it to the next call.
void printReversedHelper(std::string str, int index) {
std::string s = "";
int i = index;
while (str[i] != ' ') {
if (str[i] == '\n') {
std::cout << s << " ";
return;
}
s += str[i];
i++;
}
printReversedHelper(str, i+1);
std::cout << s << " ";
}
void printReversed(std::string str) {
printReversedHelper(str, 0);
}The second solution opts to remove words from the string as it finds them, then passes the shortened string to the next call.
void printReversed(std::string str) {
std::string s = "";
int i = 0;
while (str[i] != ' ') {
if (str[i] == '\n') {
std::cout << s << " ";
return;
}
s += str[i];
i++;
}
printReversed(str.substr(i+1, str.length()-i));
std::cout << s << " ";
}
Contributed by Annika Tsai.
Given a const list of strings that represent names, write a function that will iterate through the list and print out all names that contain the letter a.
given a const list of names:
const list<string> names = {"George", "Ryan", "Elise", "Tom", "Hank"}, the output of the function should contain "Ryan" and "Hank". #### Solution Remember that if you pass a container as a const reference parameter, you have to use a const_iterator as opposed to a regular iterator.
void print_names(const list &names) {
list::const_iterator it;
for (it = names.begin(); it!= names.end(); it++) {
string name = *it;
for (int i = 0; i < name.length(); i++) {
if (name[i] == 'a') cout << *it << endl;
}
}
}Contributed by Frank Fu.
Write a function called multiply that takes two intergers, x and y, as its arguments and returns the resulting integer product. You MUST use recursion to implement your multiply function, and you are not allowed to use any loops or the multiplication/division operators * and / in your code. Also, be sure to write a main function that prompts the user to enter the two numbers x and y before calling the multiply function in the main function to produce the product. You can assume that the user will not enter anything other than integers as inputs, but be sure to account for special cases such as when x or y is 0 or when either of them is negative.
Example 1: Please enter the number x: -2 Please enter the number y: -2 The product of x and y is: 4
Example 2: Please enter the number x: 0 Please enter the number y: -1 The product of x and y is: 0
Example 3: Please enter the number x: -2 Please enter the number y: 5 The product of x and y is: -10
Example 4: Please enter the number x: 9 Please enter the number y: 4 The product of x and y is: 36
#include <iostream>
using namespace std;
int multiply(int x, int y) {
// 0 multiplied with anything should return 0
if (x == 0 || y == 0)
return 0;
// Add x with itself with a y number of times
// Recursively calling multiply(x, y-1)
if (y > 0)
return (x + multiply(x, y - 1));
// If y is negative, we want to return the negative of the result
if (y < 0)
return -multiply(x, -y);
}
int main() {
int x, y, z;
cout << "Please enter the number x: ";
cin >> x;
cout << "Please enter the number y: ";
cin >> y;
z = multiply(x, y);
cout << "The product of x and y is: " << z << endl;
return 0;
}Contributed by Jason Yee.
Suppose the following structure represented a node in a binary tree: struct Node { int value; Node* left; Node* right; }; Write a function, printTree, that accepts a pointer to a Node and prints the contents of the tree in a breadth-first order, with each value on its own line, assuming that the passed Node is the root of the tree.
#include <iostream>
struct Node {
int value;
Node* left;
Node* right;
};
void printTree(Node* root) {
/*The cleanest way to write this code is to use a recursive algorithm; this is
the methodology demonstrated in this example of a solution.
If you'd like to practice a non-recursive approach, you will need to use make
good use of an arbitrary data structure to hold Node* values; you may wish
to dynamically allocate and reallocate memory for an array, or use one of the
C++ STL's various containers.*/
if (root != nullptr) { /*Shouldn't do anything if there is no Node to handle*/
/*The basis of the breadth-first traversal is to first handle the data
held by the current node, then perform the same process for each Node's
children.*/
/*First, print the current node's value:*/
std::cout << root->value << endl;
/*Now repeat the process described above for each of the children.
Each child is the root of a subtree that can be processed through
a breadth-first transversal.
This is why a recursive algorithm is suitable.
Don't worry about passing nullptr to printTree in the case where a
child does not exist; the check we did at the start of this function
fixes that.*/
printTree(root->left);
printTree(root->right);
}
}Contributed by Ryan Lo.
Given a random array of strings with only 1 duplicate, write a function called "getDup()" to return the duplicate string in O(n) time. If no duplicates, return the string "-1". The function takes the string array and the size of the array as inputs
If given an array:
string s[] = {"go", "bruins", "defeat", "the", "USC", "trojans", "we", "beat", "USC"};
then getDup(s, 9) should return "USC" as the duplicate string #include <iostream>
using namespace std;
#include <string>
#include <cassert>
#include <unordered_map>
string getDup(string s[], int n) {
unordered_map<string, bool> map;
for (int i = 0; i < n; i ++) {
if (map[s[i]] == true) return s[i];
map[s[i]] = true;
}
return "-1";
}
int main() {
/*Given a random array of strings with only 1 duplicate, write a function to return the duplicate string in O(n) time. If no duplicates, return the string "-1". The function takes the string array and the size of the array as inputs
*/
string s[] = {"go", "bruins", "defeat", "the", "USC", "trojans", "we", "beat", "USC"};
string dup = getDup(s, 9);
assert(dup == "USC");
cout << "All cases worked" << endl;
}
Contributed by John Stucky.
Suppose you have a car dealership that has a collection of cars. Each car has a make, model, unique car ID number, and price. Describe one or more data structures that can do the following:
(a) Given a car manufacturer/make (e.g., Toyota), generate a collection of unique models made by that manufacturer present at the dealership.
(b) Given a car's unique ID number, find the next most expensive car (so the dealer can upsell a customer).
Then use these data structures to implement a CarDealership class that is constructed from a collection of cars and can perform the operations listed above. The code for Car and a prototype for CarDealership have been provided.
struct Car{
int id;
string make;
string model;
double price;
explicit Car(int i = -1, string m = "", string n = "", double p = -1.0) {
id = i;
make = m;
model = n;
price = p;
}
bool operator<(const Car& rhs) const;
};
bool Car::operator<(const Car& rhs) const {
return price < rhs.price;
}
class CarDealership{
public:
explicit CarDealership(const vector<Car>& cars); // to be implemented
vector<string> car_models(string manufacturer); // to be implemented
Car upsell(int id); // to be implemented
private:
// to be implemented
};
A small CarDealership has 7 cars:
| ID | Make | Model | Price |
|---|---|---|---|
| 1 | Toyota | Camry | 20000 |
| 2 | Toyota | Prius | 28000 |
| 3 | Toyota | 4Runner | 36000 |
| 4 | Ford | Focus | 18000 |
| 5 | Ford | F150 | 27000 |
| 6 | Toyota | Camry | 19000 |
| 7 | Ford | F150 | 26150 |
A call to car_models("Toyota") should return a vector of size 3 with strings "Camry", "Prius", "4Runner" in any order.
A call to upsell(5) should return a car with id, make, model, and price of 2, Toyota, Prius, 28000, respectively.
One sensible way to efficiently compute the list of models given a manufacturer is to use a hash table, or an unordered map, from each make to its associated models, where the models are an unordered set. Explicitly, this is an unordered_map<string, unordered_set<string>>.
To quickly find a car given its ID, one can use an unordered map from IDs to Cars: unordered_map<int, Car>. Then once one has a Car object, one can find the next most expensive car by using an ordered set, sorted by price: set<Car>.
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <iostream>
using namespace std;
struct Car{
int id;
string make;
string model;
double price;
explicit Car(int i = -1, string m = "", string n = "", double p = -1.0) {
id = i;
make = m;
model = n;
price = p;
}
bool operator<(const Car& rhs) const;
};
bool Car::operator<(const Car& rhs) const {
return price < rhs.price;
}
class CarDealership{
public:
explicit CarDealership(const vector<Car>& cars);
vector<string> car_models(string manufacturer);
Car upsell(int id);
private:
unordered_map<string, unordered_set<string>> makeToModels;
unordered_map<int, Car> idToCar;
set<Car> carBST;
};
CarDealership::CarDealership(const vector<Car>& cars) {
for (int i = 0; i < cars.size(); i++) {
Car currentCar = cars[i];
unordered_map<string, unordered_set<string>>::iterator it;
it = makeToModels.find(currentCar.make);
if (it == makeToModels.end()) {
unordered_set<string> models;
models.insert(currentCar.model);
makeToModels.insert(pair<string, unordered_set<string>>(currentCar.make, models));
} else {
(it->second).insert(currentCar.model);
}
idToCar[currentCar.id] = currentCar;
carBST.insert(currentCar);
}
}
vector<string> CarDealership::car_models(string manufacturer) {
unordered_map<string, unordered_set<string>>::iterator it = makeToModels.find(manufacturer);
vector<string> matches;
if (it == makeToModels.end()) {
return matches;
} else {
unordered_set<string>& models = it->second;
for (unordered_set<string>::iterator it2 = models.begin(); it2 != models.end(); ++it2) {
matches.push_back(*it2);
}
}
return matches;
}
Car CarDealership::upsell(int id) {
unordered_map<int, Car>::iterator it = idToCar.find(id);
if (it == idToCar.end()) {
Car c;
return c;
}
set<Car>::iterator it2 = carBST.find(it->second);
++it2; // increment to the next car by price
if (it2 == carBST.end()) {
Car c;
return c;
}
return (*it2);
}
int main() {
Car c1(1, "Toyota", "Camry", 20000);
Car c2(2, "Toyota", "Prius", 28000);
Car c3(3, "Toyota", "4Runner", 36000);
Car c4(4, "Ford", "Focus", 18000);
Car c5(5, "Ford", "F150", 27000);
Car c6(6, "Toyota", "Camry", 19000);
Car c7(7, "Ford", "F150", 29000);
vector<Car> cars;
cars.push_back(c1);
cars.push_back(c2);
cars.push_back(c3);
cars.push_back(c4);
cars.push_back(c5);
cars.push_back(c6);
cars.push_back(c7);
CarDealership dealer(cars);
vector<string> tmodels = dealer.car_models("Toyota");
for (int i = 0; i < tmodels.size(); i++) {
cout << tmodels[i] << " ";
}
cout << endl;
Car up = dealer.upsell(c6.id);
cout << up.make << " " << up.model << " " << up.price << endl;
}
Contributed by Stephanie Lam.
Given the following struct for a node of a binary tree, write the getHeight function, which determines the maximum height of the tree. The maximum height is defined as the maximum number of nodes in the longest path from the root node to a leaf node. The parameter passed into the getHeight function is the node of the tree.
struct Node {
int val;
Node* left;
Node* right;
}
int getHeight(Node* n) {
// complete function
}The solution can be found using recursion. We get the height of the left subtree and the height of the right subtree, and then take the maximum value of the two, adding 1 for the root node.
int getHeight(Node* n) {
if (n == nullptr) {
return 0;
} else {
int left_height = getHeight(n->left);
int right_height = getHeight(n->right);
// return the max height between the left and right subtrees
if (left_height < right_height)
return right_height + 1;
else
return left_height + 1;
}
}Contributed by Yiyin Jin.
Given a linked list, determine if it has a cycle in it.
We go through each node one by one and record each node's reference (or memory address) in a hash table. If the current node is null, we have reached the end of the list and it must not be cyclic. If current node’s reference is in the hash table, then return true.
public boolean hasCycle(ListNode head) {
Set<ListNode> nodesSeen = new HashSet<>();
while (head != null) {
if (nodesSeen.contains(head)) {
return true;
} else {
nodesSeen.add(head);
}
head = head.next;
}
return false;
}
Contributed by Jason Wong.
Write a function to determine the index of the first non-repeated character in a string. If no non-repeated characters exist, return -1. The string we pass in will consist of only characters a-z; that is, only lower cased letters. Strive for efficiency. After you are done, analyze the time and space complexity of your function. Can you do better?
Function skeleton below:
int firstUniqueCharacter(string s) {
}
Input: abbccdd Output: 0, because a is non-repeated, and is at index 0
Input: aabbcdefg Output: 4, because c is the first non-repeated character in the string
Input: aabbccddeee Output: -1, because there are no non-repeated characters
#include <string>
using namespace std;
/*
Analysis:
The time complexity of my function is O(s), where s is the length of the string
We loop through 26 characters, then loop through our string twice. Look up in
my int array is O(1). We have O(26 + s + s), which is O(s)
My function uses O(1) space; I only use an int array, of size 26.
*/
int firstUniqueCharacter(string s) {
// We do not need a BST or Hash table. We know that there are 26 lower cased letters
int map[26];
for (int i = 0 ; i < 26; i ++) {
map[i] = 0;
}
// Each entry int the array indicates the count of eah character
for (int i = 0 ; i < s.size() ; i++) {
int index = s[i] - 'a';
map[index]++;
}
for (int i = 0 ; i < s.size() ; i++) {
int index = s[i] - 'a';
// If we only saw the character once, this is the first non-repeated character
if (map[index] == 1) {
return i;
}
}
// If reached here, we havent found a non-repeated character
return -1;
}
Contributed by Jung Hyun Park.
Given a vector set of numbers, write a program that would find the length of the longest increasing subsequence of the vector.
vector<int> v{ 1, 4, 2, 9, 12, 7, 6 };
cout << "Length is: " << coolFunc(v);
Try it out friends!
#include <iostream>
#include <vector>
using namespace std;
int bSearch(const vector<int> &v, int l, int r, int key) {
while (r-l > 1) {
int m = l + (r-l)/2;
if (v[m] >= key)
r = m;
else
l = m;
}
return r;
}
int coolFunc(const vector<int> &v) {
if (v.size() == 0)
return 0;
vector<int> temp(v.size(), 0);
int length = 1; // length of longest subsequence
temp[0] = v[0];
for (int i = 1; i < v.size(); i++) {
if (v[i] < temp[0])
temp[0] = v[i]; // change smallest value
else if (v[i] > temp[length-1])
temp[length++] = v[i]; // add term to subsequence
else
temp[bSearch(temp, -1, length-1, v[i])] = v[i];
}
return length;
}
Contributed by Justin Hong.
Write a function to determine whether two strings are anagrams. You may use the std::sort function after including .
Two strings are anagrams if they have the same number of same letters. Therefore strings that are anagrams must be identical after they are both sorted.
#include <string>
#include <vector>
using namespace std;
bool isAnagram(string first, string second) {
if (first.size() != second.size()) return false;
sort(first.begin(), first.end());
sort(second.begin(), second.end());
if (first == second) return true;
return false;
}Contributed by William Shao.
Implement a FIFO (first in first out) queue class. The only member variables you can use are two std::stacks. Implement the class using the following skeleton:
#include <stack>
class StackQueue{
private:
std::stack<int> stackOne;
std::stack<int> stackTwo;
public:
void push(int x) { //Push an int into the queue
}
void pop(){ //Remove the oldest int in the queue
}
int front() { //Return the oldest value queue (Don't remove it)
}
}
Imagine putting the stacks head to tail. We push to the top of one stack and when we want to pop, we "pour" the contents of the first stack into the second, so now the oldest values are on top and newest on bottom.
#include <stack>
class StackQueue {
private:
std::stack<int> stackOne;
std::stack<int> stackTwo;
public:
void push(int x) { // Push an int into the queue
stackOne.push(x);
}
void pop() { // Remove the oldest int in the queue
if (stackOne.empty() && stackTwo.empty()) {
return;
}
if (stackTwo.empty()) {
while (!stackOne.empty()) {
stackTwo.push(stackOne.top());
stackOne.pop();
}
}
stackTwo.pop();
}
int front() { // Return the oldest value queue (Don't remove it)
if (stackTwo.empty()) {
while (!stackOne.empty()) {
stackTwo.push(stackOne.top());
stackOne.pop();
}
}
return stackTwo.top();
}
}Contributed by Jennifer Tan.
Write a function that takes a sorted linked list of ints and remove all nodes with duplicates values.
struct node {
int value;
node *next;
};
void removeDuplicates(node* root) {
node* curr = root;
while (curr != nullptr && curr->next != nullptr) {
if (curr->value == curr->next->value) {
curr->next = curr->next->next;
} else {
curr = curr->next;
}
}
}Contributed by Chaoran Lin.
Given a string representing a word, determine if it is a palindrome using a queue and a stack.
Input: racecar Output: True
Input: avid diva Output: True
Input: butterfly Output: False
A stack as a LIFO (last-in-first-out) data structure while a queue is FIFO (first-in-first-out). Using this knowledge, we can see that if a string is a palindrome, after pushing all of its characters to a stack and a queue, the stack would be identical to the queue. Therefore we can simply iterate through the stack and queue and compare their characters.
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
bool isPalindrome(string s) {
stack<char> st;
queue<char> q;
for (int i = 0; i < s.length(); i++) {
st.push(s[i]);
q.push(s[i]);
}
bool isPalindrome = true;
for (int i = 0; i < s.length() / 2; i++) {
if (st.top() != q.front()) {
isPalindrome = false;
break;
}
st.pop();
q.pop();
}
return isPalindrome;
}Contributed by Neda Vesselinova.
Given two integer vectors, compute the intersection of the vectors using the find function. The intersection is a vector consisting of all elements that appear in both vectors. Note that the input vectors may have repeated integers, but the intersection should not.
vector<int> x;
x.push_back(1);
x.push_back(2);
x.push_back(3);
x.push_back(2);
x.push_back(7);
vector<int> y;
y.push_back(7);
y.push_back(3);
y.push_back(6);
y.push_back(2);
y.push_back(9);
vector<int> z = intersection(x, y)Vector z should consist of 2, 3, and 7 (in any order).
For every element of vec1, check whether it is also in vec2 and has not already
been added to the intersect vector. If so, add it to the vector. You only need to
iterate through every element of one of the vectors because any elements that belong
in the intersection will appear in either vector.
vector<int> intersection(vector<int> vec1, vector<int> vec2) {
vector<int> intersect_vector;
for (int i = 0; i < vec1.size(); i++) {
if ((find(vec2.begin(), vec2.end(), vec1[i]) != vec2.end()) &&
(find(intersect_vector.begin(), intersect_vector.end(),
vec1[i]) == intersect_vector.end()))
intersect_vector.push_back(vec1[i]);
}
return intersect_vector;
}Contributed by Omar Ozgur.
Create a class TwoSum that includes a data structure of your choice.
Create a function insert that inserts an integer into the data structure,
a function remove that removes a specified integer from the data structure,
and a function findSum that returns true if there is a pair of integers that
add to the given target value, and false otherwise. You are free to use any
standard libraries that were covered in class. Note: There are many correct
answers. Think about using data structures that would lead to increased efficiency.
TwoSum ts;
ts.findSum(0) => false
ts.insert(0);
ts.findSum(0) => true
ts.insert(1);
ts.insert(2);
ts.insert(3);
ts.findSum(5) => true;
ts.remove(3);
ts.findSum(3) => true;
ts.findSum(5) => false;In the solution below, an unordered_set is used to store integers, which
allows for efficient lookups for the remove and findSum methods. The
method used allows for the target sum to be found in a single traversal of
the elements. However, it is possible to make findSum run in constant
time if more time and space is used in the insert and remove methods.
#include <unordered_set>
#include <cassert>
using namespace std;
class TwoSum {
public:
void insert(int x);
void remove(int x);
bool findSum(int target);
private:
unordered_set<int> seen;
};
void TwoSum::insert(int x) {
seen.insert(x);
}
void TwoSum::remove(int x) {
seen.erase(x);
}
bool TwoSum::findSum(int target) {
if (seen.find(target) != seen.end())
return true;
for (unordered_set<int>::iterator it = seen.begin(); it != seen.end(); it++) {
// target = (target - *it) + *it
// Since we iterate with it, *it is known
// target is also known, so ll we need is (target - *it)
if (seen.find(target - *it) != seen.end()) {
return true;
}
}
return false;
}
int main() {
TwoSum ts;
assert(ts.findSum(0) == false);
ts.insert(0);
assert(ts.findSum(0) == true);
ts.insert(1);
ts.insert(2);
ts.insert(3);
assert(ts.findSum(5) == true);
ts.remove(3);
assert(ts.findSum(3) == true);
assert(ts.findSum(5) == false);
}Contributed by Matthew Wong.
Given an array of integers, write a function to return the sum of all the elements in the array.
Do not use a loop of any kind! You must use recursion! Use this as the head of your function:
int arraySum(int a[], int n)
int arraySum(int a[], int n) {
// Base case: no more elements to add
if (n == 0)
return 0;
// Recursive case: add to current with array of one less element
int sum = a[0] + arraySum(a+1, n-1);
return sum;
}Contributed by Jason Xu.
Given an unsorted 2D array of integers, write a function that returns the number of integers in the array that appear more than once. The width and height of the array will also be given as parameters.
Input: nums = { {3, 1, 2, 2}, {40, 1, 1, 1}, {5000, 40, 8, 3} } height = 3 width = 4
Output: 4
This is only one possible solution that runs in O(n). Some of the #includes might not be needed.
#include <stdio.h>
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int countDups(int ** arr, int height, int width) {
if (width < 1 || height < 1)
return 0;
// An unordered map allows constant lookup (if small amount of collisions)
unordered_map<int, int> vals;
unordered_map<int, int>::const_iterator checker;
int curr = 0;
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
curr = arr[i][j];
// Check if our unordered_map already has the value
checker = vals.find(curr);
// If not, add it as a new value
if (checker == vals.end())
vals.insert({curr, 0});
// Otherwise increment occurences of that value
else
vals[curr]++;
}
}
// Count all unique elements with more than one occurence
int count = 0;
for (checker = vals.begin(); checker != vals.end(); checker++)
if (checker->second > 0)
count++;
return count;
}Contributed by Yi Peng.
Using the already defined NoisyClass, what will the following code print out?
#include <iostream>
using namespace std;
class NoisyClass {
private:
string s;
public:
NoisyClass() {
cout << "[C] Default constructor" << endl;
}
explicit NoisyClass(string stuff) {
s = stuff;
cout << "[P] Parameterized constructor" << endl;
}
NoisyClass(const NoisyClass& other) {
s = other.s;
cout << "[~] Copy constructor" << endl;
}
~NoisyClass() {
cout << "[D] Destructor" << endl;
}
NoisyClass& operator= (const NoisyClass& other) {
s = other.s;
cout << "[=] Assignment" << endl;
return *this;
}
};
struct SoMeta {
NoisyClass n[2];
NoisyClass* ptr[2];
};
int main() {
SoMeta s;
SoMeta* ptr;
SoMeta* dynamicYo = new SoMeta();
delete dynamicYo;
}[C] Default Constructor [C] Default Constructor [C] Default Constructor [C] Default Constructor [D] Destructor [D] Destructor [D] Destructor [D] Destructor
Contributed by Bowei Wang.
Given the root of a binary tree, write a function invertTree() to invert all the child nodes.
The structure for each node is given below:
Struct Node { int val; Node* left; Node* right; }
void invertTree(Node* root) {
if (root == NULL)
return;
Node* temp = root->right;
root->right = root->left;
root->left = temp;
invertTree(root->right);
invertTree(root->left);
}Contributed by Jeffrey Jiang.
Consider the following code segment. We want to use the defined classes to implement an ordered linked list (ascending order).
class Node {
public:
virtual int size();
virtual Node* add(int val);
virtual bool contains(int val);
};
class Empty : Node {
public:
virtual int size() {
return 0;
}
virtual Node* add(int val) {
return new Node*(val, this);
}
virtual bool contains(int val) {
return false;
}
};
class Element : Node {
public:
Element(int e, Node* n) {
next = n;
elem = e;
}
// Implement size(), contains(), and add()
virtual int size();
virtual Node* add(int val);
virtual bool contains(int val);
private:
Node* next;
int elem;
};Using polymorphism, implement the size(), add(), and contains() in the Element class so that for any initialized Node* list, list->size() will return the size of the list. Assume that there are only unique values in this linked list, so if we are trying to add a value that is already in the list, just leave the list unchanged.
HINT: We have provided the definition for Empty. See the definition of Empty and figure out what Empty as a Node means and use the things returned as hints to implementing the Element functions.
You are not allowed to use NULL or nullptr in your implementation and you cannot define any new member variables or helper functions.
class Element : Node {
public:
Element(int e, Node* n) {
next = n;
elem = e;
}
virtual int size() {
return 1 + next->size();
}
virtual Node* add(int val) {
if (val == elem)
return this;
else if (val < elem) // we just found the location to insert.
return new Element(val, this);
else {
next = next->add(val);
return this;
}
}
virtual bool contains(int val) {
if (val == elem)
return true;
if (val < elem) // we are past that value.
return false;
return next->contains(val);
}
private:
Node* next;
int elem;
};The main points to consider in this problem are using polymorphism and the recursive nature of linked lists to implement each problem. While the solution is very simplistic, it is actually quite a difficult problem for those who have not seen this before.
Based on the data structures that we are given, Empty is defined to be a class that represents the "end" of the list, acting as the NULL at the end of the list. However, because of polymorphism, it can provide the end conditions of each of the "recursive" functions. Thus, every Element will eventually point to the Empty node.
Size is the easiest to implement. Because we do not have anything saved for the size of the list, we can only compute it by traversing the entire list and counting the number of nodes are in the list. This can be done by calling the size of the list defined by the next node and then adding one to it.
Next, contains is the next easiest to implement. Clearly, if the node we are looking at contains the element that we are looking for, we return true. If the value we are looking for is less than the element of the node we are looking at, that means that, because of the ordered property of the list, we have passed the value without finding it, and so we return false. Otherwise, we ask the next node to see if it has found the value, and simply return that value.
Finally, based on these two, we can take it to the next level in add. It is similar to contains, in that we have to find the location of where the value has to go. After we find it, however, the trick is that we want to create a new node that points to the node we are looking at and return that node back to the previous caller. This allows us to update the pointer above to include every node that has been created.
Additionally, it may be of interest to note that in order to avoid memory leaks, a destructor must be defined for the class to remove all the children.
Contributed by Prathyush Katukojwala.
Write a function to check if a binary tree is balanced. A binary tree is balanced if, for any node, the left and right subtrees do not differ by more than 1 in height.
struct TreeNode { // TreeNode struct
int val;
TreeNode* left;
TreeNode* right;
};
bool isBalanced(TreeNode* node) {
// An empty tree is balanced
if (node == nullptr)
return true;
// Difference in height of left and right subtrees must be within 1
// Both subtrees must be balanced
return abs(height(node->left) - height(node->right)) <= 1
&& isBalanced(node->left)
&& isBalanced(node->right);
}
int height(TreeNode* root) {
// Height of an empty tree is 0
if (root == nullptr)
return 0;
// Height of a tree is 1 more than the height of the longer
// of the left and right subtrees
return 1 + max(height(node->left), height(node->right));
}Contributed by Christian Warloe.
Write a function that takes in a pointer to a node representing the head of a linked list and return a pointer to the middle of that list.
struct node{
int val;
node* next;
};
node* middle(node* head) {
node* middle = head;
if (head == nullptr)
return head;
node* end = head;
while (end != nullptr) {
if (end->next == nullptr)
break;
end = end->next->next;
middle = middle->next;
}
return middle;
}Contributed by Hongyi Zhang.
Given just the pointer to a non-terminal Node within a singly linked linked list,
remove the given element from the linked list.
(While preserving the integrity of the data structure of course!)
1 -> 2 -> 3 -> 4
removeNode(&<second_node>)
1 -> 3 -> 4This problem is actually pretty trivial if you think about it! Instead of removing the given element, why not acquire the value of the next element, and remove that instead? This will allow us to ensure the linked list is still properly linked!
#include <iostream>
#include <vector>
using namespace std;
struct Node {
explicit Node(int v) : val(v), next(nullptr) {}
Node* next;
int val;
};
void removeNode(Node* n) {
// n is a non-terminal node of some linked list
// Let's remove the next element in the node instead
Node* to_remove = n->next;
// Acquire the next element's value
n->val = n->next->val;
// Point ourselves to the subsequent element
n->next = n->next->next;
// De-allocate the removed element
delete to_remove;
}
void printList(Node* head) {
cout << "Printing list: ";
while (head != nullptr) {
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
int main() {
vector<Node*> ptrs;
Node* head = new Node(0);
ptrs.push_back(head);
Node* prev = head;
for (int i = 1; i < 10; i++) {
Node* n = new Node(i);
ptrs.push_back(n);
prev->next = n;
prev = n;
}
printList(head);
removeNode(ptrs[3]);
printList(head);
removeNode(ptrs[0]);
printList(head);
removeNode(ptrs[8]);
printList(head);
}Contributed by Jeffrey Chan.
Implement a function split that takes in a string and returns a vector of strings
such that each string within the vector is a substring of the original string that
was separated by a space. You are allowed to use the C++ string and vector libraries.
Function declaration: vector<string> split(string s)
string s = "Jeffrey is a genius!";
vector<string> splitString = split(s);
// Vector splitString should look like:
// ["Jeffrey", "is", "a", "genius!"]
// Each string in the vector was separated by a space in original stringvector<string> split(string s) {
vector<string> answer;
string temp = "";
for (int k = 0; k < s.size(); k++) {
if (s[k] != ' ') {
temp += s[k];
} else {
answer.push_back(temp);
temp = "";
}
}
answer.push_back(temp);
return answer;
}Contributed by Jeremiah Fan.
We can represent a term in a polynomial as an array with the first element being the coefficient and the second element being the exponent. A polynomial can be represented as an array/vector of these terms. Given such an array, write a function that "takes the derivative" of this "polynomial". Function signature: vector<int*> derive(vector<int*> polynomial);
We are using vectors - this array literal syntax is just for our own understanding.
derive([[1, 2], [3, 4], [5, 6]]) => [[2, 1], [12, 3], [30, 5]]
derive([[2, 0], [4, 3], [6, 5]]) => [[12, 2], [30, 4]]vector<int*> derive(vector<int*> polynomial) {
int index = -1;
for (vector<int*>::const_iterator iterator = polynomial.begin();
iterator != polynomial.end(); iterator++) {
// Multiply coefficient by the power
(*iterator)[0] *= (*iterator)[1];
// Subtract one from the power
(*iterator)[1]--;
if ((*iterator)[0] == 0) {
index = iterator - polynomial.begin();
delete *iterator;
}
}
if (index != -1)
polynomial.erase(polynomial.begin() + index);
return polynomial;
}Contributed by Rohan Varma.
bool exists(Node *root, Node *dest)
Returns true if a node exists in a binary tree.
// Type your code here, or load an example.
#include <string>
#include <vector>
using namespace std;
struct Node {
int val;
Node *left, *right;
};
bool exists(Node *root, Node *dest) {
if (!root || !dest) {
return false;
}
if (root == dest) {
return true;
}
return exists(root->left, dest) || exists(root->right, dest);
}Contributed by Adam Romayor.
Write a function swapPairs that is passed the head of a singly linked list
and swaps adjacent nodes. Return the head of the new list.
You may not change the value of the node.
Definitions for the problem:
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* swapPairs(ListNode* head);1->2->3->4 should return 2->1->4->3
NULL returns NULL
1->2->3->4->5 returns 2->1->4->3->5
1 returns 1
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* swapPairs(ListNode* head) {
if (head == NULL) return NULL;
if (head->next == NULL) return head;
ListNode* curr = head;
ListNode* nxt = head->next;
ListNode* hd = nxt;
ListNode *prev = NULL;
while (curr!= NULL) {
if (nxt != NULL) {
if (prev != NULL)
prev->next = nxt;
curr->next = nxt->next;
nxt->next = curr;
}
prev = curr;
curr = curr->next;
if (curr != NULL)
nxt = curr->next;
}
return hd;
}Contributed by Connor Borden.
Given the head of a binary search tree and an integer, write a function that returns whether the integer is within the binary search tree. Write this function without recursion. Here is a skeleton for the problem:
struct Node {
Node* left;
Node* right;
int val;
};
bool search(Node* a, int dest) {
*Enter code here*
}struct Node {
Node* left;
Node* right;
int val;
};
bool search(Node* a, int dest) {
while (a != nullptr) {
if (a->val == dest)
return true;
else if (a->val > dest)
a = a->left;
else
a = a->right;
}
return false;
}Contributed by Ramya Satish.
Given a string, return true if the string is "balanced" in terms of parentheses, and false if it is not. Note that multiple types of parentheses / brackets may be used, and all of these have to be balanced. The brackets must open and close in the correct order.
"()" -> true
"[]()" -> true
"{" -> false
"[]]" -> false
"[()]" -> true
"[(])" -> false
#include <string>
#include <stack>
using namespace std;
class Expression {
public:
bool isValidParen(string s) {
stack<char> paren;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
paren.push(s[i]);
}
if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
if (paren.size() == 0) {
return false;
} else if (s[i] == ')' && paren.top() != '(') {
return false;
} else if (s[i] == ']' && paren.top() != '[') {
return false;
} else if (s[i] == '}' && paren.top() != '{') {
return false;
}
paren.pop();
}
}
if (paren.size() != 0) {
return false;
}
return true;
}
};Contributed by Alex Wu.
Given a pointer to the root of a binary tree, with nodes declared as follows:
struct node {
int value;
node *left;
node *right;
};Write a recursive function, depth_of_x, that returns the depth of the shallowest node that holds the value x. Your function should return 1 if x is held in the rood node, and 0 if x cannot be found. Use the following header:
int depth_of_x(node * root, int x) {}
For example, given the tree with nodal values:
3
/ \
4 5
/ \ \
2 1 4
depth_of_x(root, 4) should return 2.
#include <algorithm>
struct node {
int value;
node *left;
node *right;
};
int depth_of_x(node * root, int x) {
if (root == nullptr)
return 0;
if (root->value == x)
return 1;
int left_depth = depth_of_x(root->left, x);
int right_depth = depth_of_x(root->right, x);
// If x is found in both right and left, increment depth of shallower one
if (left_depth != 0 && right_depth != 0)
return std::min(left_depth, right_depth) + 1;
// If x is found in left but not right, increment depth of left
if (left_depth != 0)
return left_depth + 1;
// If x is found in right but not left, increment depth of right
if (right_depth != 0)
return right_depth + 1;
// x was not found in either
return 0;
}Contributed by Matt Fabius.
Write a function that traverses a linked list and removes the first instance of a Node with a given value.
#include <iostream>
using namespace std;
class Node {
public:
int m_value;
Node* m_next;
Node* m_prev;
};
void remove(int val, Node* head) {
if (head == nullptr) {
return;
} else if (head->m_value == val) {
head->m_prev->m_next = head->m_next;
head->m_next->m_prev = head->m_prev;
delete head;
return;
}
Node* p = head->m_next;
for (; p != head; p = p->m_next) { // for a circular linked list
if (p == nullptr) {
return;
} else if (p->m_value == val) {
p->m_prev->m_next = p->m_next;
p->m_next->m_prev = p->m_prev;
delete p;
return;
}
}
}Contributed by Michael Li.
Given a list of unique positive integers, find the smallest missing integer not in the list, starting from 1.
[] -> 1
[1, 4, 3] -> 2
[4, 2, 5, 1, 3] -> 6
You can sort the list and look for the first integer that's not in the list, starting at 1. This is an O(n * log n) algorithm. To get O(n), maintain a hash table that contains the integers in the list. Then, starting from 1, test if the integer is in the hash table and return the first one that isn't.
#include <vector>
#include <unordered_set>
#include <limits.h>
using namespace std;
unsigned firstMissing(vector<unsigned> boxNums) {
unordered_set<unsigned> foundNums;
for (unsigned i = 0; i < boxNums.size(); i++) {
foundNums.insert(boxNums[i]);
}
for (unsigned i = 1; i < UINT_MAX; i++) {
if (!foundNums.count(i)) {
return i;
}
}
return UINT_MAX;
}
Contributed by Aniqa Kamal.
Find the lowest common ancestor of two nodes in a binary tree.
struct Node {
int val;
Node* left, right;
};
Node* findLowestCommonAncestor(Node* root, Node* a, Node* b) {
if (!root || !a || !b)
return NULL;
if (a->val == root->val || b->val == root->val)
return root;
Node* left = findLowestCommonAncestor(root->left, a, b);
Node* right = findLowestCommon(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;
class Base1 {
public:
Base1() {
cout << "Base1's constructor called" << endl;
}
~Base1() {
cout << "Base1's destructor called" << endl;
}
};
class Base2 {
public:
Base2() {
cout << "Base2's constructor called" << endl;
}
~Base2() {
cout << "Base2's destructor called" << endl;
}
};
class Derived: public Base1, public Base2 {
public:
Derived() {
cout << "Derived's constructor called" << endl;
}
~Derived() {
cout << "Derived's destructor called" << endl;
}
};
int main() {
Derived d;
return 0;
}Base1's constructor called
Base2's constructor called
Derived's constructor called
Derived's destructor called
Base2's destructor called
Base1's destructor called
In cases of Multiple Inheritance, constructors of base classes are always called in derivation order from left to right and Destructors are called in reverse order.
Contributed by Brendon Daugherty.
Write the function lotsOfFours that, given a non-negative number k, returns 4 to the power of k, without using the * operator, or any loops!
The code actually is pretty simple, as long as you don’t forget to include the base case!
Essentially, every power k is 4 times the power before it, so we use the + operator 4 times, as we are restricted from using the multiplication operator!
int lotsOfFours(int k) {
// k < 0 return an error!
if (k < 0)
return -1;
// Dont forget your base case!!!
else if (k == 0)
return 1;
else
return lotsOfFours(k-1) + lotsOfFours(k-1) + lotsOfFours(k-1) + lotsOfFours(k-1);
// Essentially, for every 4 we add 4 of what we had before together!
}Contributed by Tyler Carson.
You are given a postfix expression stored in a C-string consisting of single-digit positive integers and arithmetic operators. Write a function int evalPostfix(char* c), which evaluates the postfix expression contained in the C-string stored at c, and returns the resulting value.
- You may declare your own structs or classes or use existing structures from the C standard library.
- You may assume that for any initial operand x, 0 < x <= 9
- You may assume that the arithmetic operations contained in c will be limited to {+, -, *, /}, and will be represented using their corresponding ASCII characters.
- You may assume that the expression passed to your function is syntactically valid.
input: {'1', '1', '+', '2', '-', '\0'}
output: 0
input: {'5', '2', '/', '3', '*', '\0'}
output: 6
#include <stack>
int evalPostfix(char* c) {
std::stack<int> operands;
char* cur = c;
while (*cur != '\0') {
if (isdigit(*cur)) {
operands.push(*cur-48);
} else {
int a = operands.top();
operands.pop();
int b = operands.top();
operands.pop();
switch (*cur) {
case '+':
operands.push(b+a);
break;
case '-':
operands.push(b-a);
break;
case '*':
operands.push(b*a);
break;
case '/':
operands.push(b/a);
break;
}
}
cur++;
}
return operands.top();
}
Contributed by Xiaoxu Wu.
The prices of a stock can be represented by an vector of integers, where the indices of the vector represent time, and the value at each index represents the price of the stock. Write a function that takes such a vector, and returns the maximum profit that could be made by buying and then selling the stock once.
You may assume the following:
- Price of the stock may vary from 0 to 1000 (inclusive)
- A profit can definitely be made
If you are unfamiliar with stock basics, here are some basic ideas:
- You may buy a stock at a certain price and sell it at a certain price. The return is the price you sell it at minus the price you buy it at. You want to maximize that value.
- Clearly, you have to buy a stock first before you can sell. You cannot sell before you buy.
- If you do understand stocks, you probably realized that this problem is oversimplified. Yes, we are only buying and selling one share of the stock. If you don't know what this means, don't worry about it.
Input:
{100, 200, 500, 200, 1000}
Output:
900
Input
{50, 100, 500, 200, 600, 300}
Output:
550
It is important to realize that we can maximize profits by iterating through the vector, taking the smallest value up to the index and the value at the index, and subtracting the former from the latter. We will update another integer variable, max, only if we find a value larger than what it is currently. We keep track of the smallest value up to the index with another integer variable, and we initiate it to be 1000, the largest possible value of a stock (as given in the problem).
#include <vector>
using namespace std;
int maxProfit(const vector<int>& stock) {
int max = 0;
int minSoFar = 1000;
for (int i = 0; i < stock.size(); i++) {
if (stock[i] < minSoFar)
minSoFar = stock[i];
else if (stock[i] - minSoFar > max)
max = stock[i] - minSoFar;
}
return max;
}Contributed by Allison Ko.
Implement the merge function which, given two sorted arrays, merges them into one sorted array. Assume they are in non-decreasing order, and that inputs are valid (i.e. you don't have to check if the input arrays are actually sorted). Return a pointer to your merged array. Your solution should have O(n) time complexity.
int* merge(int list1[], int n1, int list2[], int n2) {
// your code here
}Given list1 = {-3, 4, 30, 48, 52} and list2 = {-30, -17, 0, 2, 16}
Return a pointer to the array {-30, -17, -3, 0, 2, 4, 16, 30, 48, 52}
int* merge(int list1[], int n1, int list2[], int n2) {
int i = 0, j = 0, k = 0;
int *result = new int[n1 + n2];
while (i < n1 || j < n2) {
if (i == n1) {
result[k] = list2[j];
k++;
j++;
} else if (j == n2) {
result[k] = list1[i];
k++;
i++;
} else if (list1[i] < list2[j]) {
result[k] = list1[i];
k++;
i++;
} else {
result[k] = list2[j];
k++;
j++;
}
}
return result;
}Contributed by Hana Kim.
A class Dessert has derived class Pie, which has member variables Filling and Crust that are objects. What does the following code output?
#include <iostream>
using namespace std;
class Filling {
public:
explicit Filling(string type) {
cout << "I am " << type << " pie." << endl;
}
~Filling() {
cout << "Spice" << endl;
}
};
class Crust {
public:
Crust() {
cout << "I'm crust." << endl;
}
~Crust() {
cout << "Flaky!" << endl;
}
};
class Dessert {
public:
Dessert() {
cout << "The best meal." << endl;
}
~Dessert() {
cout << "It's over." << endl;
}
virtual void eat() {
cout << "Ouch." << endl;
}
void cook() {
cout << "Burnt." << endl;
}
};
class Pie : public Dessert {
public:
explicit Pie(string type)
:myFilling(type) {
cout << "Lovely pie!" << endl;
}
~Pie() {
cout << "All gone!" << endl;
}
virtual void eat() {
cout << "Ow." << endl;
}
void cook() {
cout << "Baked." << endl;
}
private:
Filling myFilling;
Crust myCrust;
};
void person(Dessert *d) {
d->eat();
d->cook();
}
int main() {
Pie p("pumpkin");
Dessert d;
person(&d);
person(&p);
}The best meal.
I am pumpkin pie.
I'm crust.
Lovely pie!
The best meal.
Ouch.
Burnt.
Ow.
Burnt.
It's over.
All gone!
Flaky!
Spice
It's over.Contributed by Kelvin Wong.
Write two classes: a base class called Animal that has a void function called speak() which prints out "hello" and a class called Dog that inherits from Animal and its speak() function prints out "hellohello". Dog's speak() function must not use cout.
#include <iostream>
using namespace std;
class Animal {
public:
void speak() {
cout << "hello";
}
};
class Dog : public Animal {
public:
void speak() {
Animal::speak();
Animal::speak();
}
};Contributed by Henry Yang.
Using recursion, find an approximation of the cube root of a double. The approximation should be within an error epsilon of the double when cubed. Only use control statements and basic arithmetic functions.
Function signature: double cbrt(double d, double epsilon)
NOTE: feel free to define a recursive helper function for cbrt to call!
cbrt(27, 0.01) returns 3.0009 (for my implementation). Note that it doesn't have to be 3 -- it could be anywhere between 2.9 and 3.1.
This solution approximates the cube root in a binary search fashion, starting with a range from 0 to the double.
double cbrt_helper(double d, double low, double high, double epsilon) {
double approx = (low + high) / 2;
double error = d - approx*approx*approx;
if (error < 0) {
error = -error;
if (error < epsilon)
return approx;
else
return cbrt_helper(d, low, approx, epsilon);
} else {
if (error < epsilon)
return approx;
else
return cart_helper(d, approx, high, epsilon);
}
}
double cbrt(double d, double epsilon) {
return cbrt_helper(d, 0, d, epsilon);
}Contributed by Michael Evangelista.
Given an unsorted doubly-linked list of integers, write a function insertValue that can insert a new integer in any position in the list. insertValue will take a Node pointer (passed by reference), a value to be inserted, and a position for the value to be inserted. Do not assume that position will be a valid position in the array.
Here is the node structure:
struct Node {
int value;
Node* next;
Node* prev;
};Given a doubly linked list of the following elements: 1, 2, 3, 4, 5, 6, here is some example input.
insertValue(head, 10, -1); // Should fail
insertValue(head, 20, 6); // Should fail
insertValue(head, 30, 3); // Should work, list should now be 1, 2, 3, 30, 4, 5, 6
insertValue(head, 40, 0); // Should work, list should now be 40, 1, 2, 3, 30, 4, 5, 6
insertValue(head, 50, 4); // Should work, list should now be 40, 1, 2, 3, 30, 50, 4, 5, 6
insertValue(head, 60, 8); // Should work, list should now be 40, 1, 2, 3, 30, 50, 4, 5, 60, 6
insertValue(head, 70, 20); // Should fail.void insertValue(Node* &head, int value, int position) {
if (head == nullptr)
return; // Check if list is empty
if (position < 0)
return; // Check if position is negative
if (position == 0) { // If it just wants us to insert at head of the list
Node *insert = new Node;
insert->value = value;
insert->next = head;
insert->prev = NULL;
head->prev = insert;
head = insert;
return;
}
// Iterate through list until position is reached
Node* ptr = head;
int count = 0;
while (ptr != nullptr && count != position) {
// Go until at desired position OR hit end of list
ptr = ptr->next; // Set to next position
count++;
}
if (ptr == nullptr) { // If true, then we hit the end of the list
return;
} else { // If here, then the loop broke because we are at the correct position
Node* insert = new Node;
insert->value = value;
insert->next = ptr;
insert->prev = ptr->prev;
ptr->prev->next = insert;
ptr->prev = insert;
}
}Contributed by Richard Yu.
Given a binary search tree with numbers already input form a sorted linked list. It may call other functions you write. Which traversion will you use through the binary search tree?
Given the implementation of the Tree and List nodes:
struct TreeNode {
int val;
TreeNode* leftChild;
TreeNode* rightChild;
explicit TreeNode(int val) {
this.val = val;
leftChild = nullptr;
rightChild = nullptr;
}
};
struct ListNode {
int val;
ListNode* next;
explicit ListNode(int val) {
this.val = val;
next = nullptr;
}
};void inOrder(TreeNode* currNode, ListNode* head) {
if (currNode->leftChild != nullptr) {
inOrder(currNode->leftChild);
}
if (head == nullptr) {
head = new ListNode(currNode->val);
} else {
ListNode* curr = head;
while (curr->next != nullptr) {
curr = curr->next;
}
curr->next = new ListNode(currNode->val);
}
if (currNode->rightChild != nullptr) {
inOrder(currNode->rightChild);
}
}
ListNode* treeToList(TreeNode* treeHead) {
ListNode* listHead = nullptr;
// Calls in-order traversal
inOrder(treeHead, listHead);
return listHead;
}Contributed by Xueyang Feng.
Given pointer to the head node of a linked list, the task is to reverse the linked list.
Input : Head of following linked list
1->2->3->4->NULL
Output : Linked list should be changed to,
4->3->2->1->NULL
Input : Head of following linked list
1->2->3->4->5->NULL
Output : Linked list should be changed to,
5->4->3->2->1->NULL
Input : NULL Output : NULL
Input : 1->NULL Output : 1->NULL
#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct node {
int data;
struct node* next;
};
/* Function to reverse the linked list */
static void reverse(struct node** head_ref) {
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
/* Function to push a node */
void push(struct node** head_ref, int new_data) {
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print linked list */
void printList(struct node *head) {
struct node *temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
}
/* Driver program to test above function*/
int main() {
/* Start with the empty list */
struct node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 85);
printf("Given linked list\n");
printList(head);
reverse(&head);
printf("\nReversed Linked list \n");
printList(head);
getchar();
}Contributed by Wandi Liu
Given the following skeleton of a singly-linked-list class, implement a function insert() that:
- takes in a new int
- checks if it's already in the set (is a duplicate), if so, return false.
- inserts the new int into the set, sorted in ascending order, from smallest to largest.
- return true if the int was inserted
#include <iostream>
using namespace std;
class SLL{
public:
SLL() {head = nullptr;}
bool insert(int new_num) {
Node* ptr = head;
// YOUR CODE HERE
return true;
}
private:
struct Node{
public:
explicit Node(int n) : m_num(n) { // node is initalized to NULL
m_next = nullptr;
}
int get_num() {return m_num;}
Node* m_next;
private:
int m_num;
};
Node* head;
};
int main() {
SLL c;
c.insert(3); // inserts & returns true
c.insert(5); // inserts & returns true
c.insert(8); // inserts & returns true
c.insert(4); // inserts & returns true
c.insert(5); // already in set, returns false!
}####### c should now contain: {3,4,5,8}
class SLL{
public:
SLL() {head = nullptr;}
bool insert(int new_num) {
Node* ptr = head;
if (ptr == nullptr) { // edge case: if the set was empty
Node* new_node = new Node(new_num);
head = new_node;
return true;
}
while (ptr->m_next && ptr->m_next->get_num() < new_num) {
// while the number isn't the largest
// and the next number is smaller than the new one
ptr = ptr->m_next; // go to the next number
}
if (!ptr->m_next) {
// if we're at the end of the set --
// (biggest number, but still smaller than the new one),
// insert the new number at the end
Node* new_node = new Node(new_num);
ptr->m_next = new_node;
return true;
} else if (ptr->m_next->get_num() == new_num) {
// if new_num is the same as next number in the set, don't insert it
return false;
} // else, insert the new node before the next number!
Node* new_node = new Node(new_num);
Node* tmp = ptr->m_next;
ptr->m_next = new_node;
new_node->m_next = tmp;
return true;
}
private:
struct Node{
public:
explicit Node(int n) : m_num(n) { // node is initalized to NULL
m_next = nullptr;
}
int get_num() {return m_num;}
Node* m_next;
private:
int m_num;
};
Node* head;
};
Contributed by Taoran Liu.
Given a pointer to a node of a binary tree, return true if the tree is symmetric, and false otherwise. Assume that an empty binary tree is symmetric. Try to solve this recursively.
1
/ \
2 2
/ \ / \
3 4 4 3
true
1
/ \
2 2
/ \ / \
3 4 3 4
false
1
/ \
2 2
\ \
3 3
false
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
explicit TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
bool ismirror(TreeNode *p, TreeNode *q) {
if (!p&&!q) return true;
else if (!p||!q) return false;
if (p->val == q->val) return ismirror(p->left, q->right) && ismirror(p->right, q->left);
else
return false;
}
bool isSymmetric(TreeNode* root) {
if (!root) return true;
return ismirror(root->left, root->right);
}
int main() {
TreeNode* tree;
tree[0] = TreeNode(1);
tree[1] = TreeNode(2);
tree[2] = TreeNode(2);
tree[3] = TreeNode(3);
tree[4] = TreeNode(3);
tree[5] = TreeNode(4);
tree[6] = TreeNode(4);
tree[0].left = &tree[1];
tree[0].right = &tree[2];
tree[1].left = &tree[3];
tree[1].right = &tree[5];
tree[2].left = &tree[6];
tree[2].right = &tree[4];
cout << isSymmetric(&tree[0]);
return 0;
}
Contributed by Changfei Shi.
Given a 5x5 character array, a target string, and a row and column to start from, write a recursive function to determine whether a word can be found by starting at the specified row and column(where the last letter of the word is found) and moving only upward and to the left.
The function should return true for the target string "helloworl"
and the character array input
hefgz mlndb rlofn lrwvd zzorl
The function should return false for the same target string
and the character array input
hnfgz mlndb rlofn lrwvd zzorl
bool recursiveWordSearch(char c[][5], string s, int row, int col) {
if (s.length() == 0) // An empty string is trivially in the 2d array
return true;
if (row < 0 || col < 0) // Past the bounds of the search, return false
return false;
if (c[row][col] == s[s.size() - 1]) {
s = s.substr(0, s.size() - 1);
bool val1 = recursiveWordSearch(c, s, row - 1, col);
bool val2 = recursiveWordSearch(c, s, row, col - 1);
return val1 || val2;
} else {
return false;
}
}Contributed by Regan Hsu.
Given a collection of intervals, merge all overlapping intervals.
For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18].
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Interval {
int start;
int end;
Interval() : start(0), end(0) {}
Interval(int s, int e) : start(s), end(e) {}
};
static bool my_cmp(const Interval &a, const Interval &b) {
return a.start < b.start;
}
vector<Interval> merge(vector<Interval> intervals) {
vector<Interval> myVec;
sort(intervals.begin(), intervals.end(), my_cmp);
for (int i = 0; i < intervals.size(); i++) {
int begin = i;
int j = i+1;
while ((j < intervals.size()) && (intervals[i].end >= intervals[j].start)) {
if (intervals[i].end >= intervals[j].end)
intervals[j].end = intervals[i].end;
i++;
j++;
}
if (begin == i) {
myVec.push_back(intervals[i]);
} else {
Interval ugh;
ugh.start = intervals[begin].start;
ugh.end = intervals[i].end;
myVec.push_back(ugh);
}
}
return myVec;
}Contributed by Robert Zalog
Implement the function provided by the following function header:
int findNum(int *nums, int n, int num);,
which returns the index of a given number num in a sorted (in ascending
order) array nums of length n. Your function must not use a for loop and
must utilize a recursive function call. In addition, your algorithm must run in
O(log n) time complexity. You can assume that the specified value will always
be found in the array (e.g., function caller will not ask you to look for 3 in
an array that does not contain a 3).
Hint:
You might want to use a helper function that takes a start and an end
parameter instead of just n.
Example function call:
int nums[6] = {1, 2, 4, 8, 10, 18};
findNum(nums, 0, 8); // returns 3int findNumHelper(int *nums, int start, int end, int num);
int findNum(int *nums, int n, int num)
{
return findNumHelper(nums, 0, n, num);
}
int findNumHelper(int *nums, int start, int end, int num)
{
int test = start + (end - start) / 2;
if (nums[test] == num) {
return test;
}
if (nums[test] > num) {
return findNumHelper(nums, start, test, num);
}
if (nums[test] < num) {
return findNumHelper(nums, test+1, end, num);
}
}Contributed by Lucas Tecot.
You are given a whole number and must count up to it in increments of 1 and 2. Find the number of ways you can count to that number.
For the number 3, we return 3. (1+1+1, 1+2, or 2+1)
For the number 4, we return 5. (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)
It turns out that this problem is essentially just fibonacci numbers. You can do it with recursion but using a loop is much more efficient.
int numCounts(int n) {
if (n <= 0)
return 0;
if (n <= 2)
return n;
int p2 = 1;
int p1 = 2;
int total = 0;
for (int i = 3; i <= n; i++) {
total = p1 + p2;
p2 = p1;
p1 = total;
}
return total;
}Contributed by Bibek Ghimire.
Write a function that takes as input a string of arbitrary length and returns a vector of all substrings of length 4 that appear more than once within the input string.
The function declaration should look like:
vector<string> findRepeats(string s);
Your function must run in O(N) time, where N is the length of the input string.
vector<string> repeats = findRepeats(“ABCABCADEFADEFA”); // repeats contains [“ABCA”, “ADEF”, “DEFA”]
#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
using namespace std;
vector<string> findRepeats(string s) {
unordered_set<string> substrings;
unordered_set<string> matches;
const int size = s.size();
const int length = 4;
// Start out with first substring to test against
substrings.insert(s.substr(0, length));
for (int i = 1; i <= (size - length); i++) {
string currSub = s.substr(i, length);
// Current substring exists earlier in the string
if (substrings.find(currSub) != substrings.end()) {
matches.insert(currSub);
}
substrings.insert(currSub);
}
vector<string> m;
for (unordered_set<string>::iterator it = matches.begin();it != matches.end(); it++) {
m.push_back(*it);
}
return m;
}
int main() {
// cout >> findRepeats("ABCABCADEFADEFA");
vector<string> m = findRepeats("ABCABCADEFADEFA");
for (int i = 0; i < m.size(); i++) {
cout << m[i];
}
}Contributed by Eric Tan.
For each situation, choose the most appropriate data structure from the following C++ STL containers:
- list, stack, queue, set, unordered_set, map, unordered_map
Then list the time complexity of performing the action specified in each situation. Explain why the container you chose is appropriate.
-
A bank wants to keep a catalogue of all of its customers' names. It frequently adds new customers to its catalogue and searches for existing customers' names. It also wants to maintain alphabetical ordering of the customers by last name. Which STL container should be used, and what is the time complexity of finding a certain customer in a catalog of n customers?
-
A school wants to keep track of the name and ID number for each of its students. The student population changes relatively little over time. The school wants to be able to quickly and frequently search up a student's ID number given a student's name. Which STL container should be used, and what is the time complexity of finding a student's ID number if the school has k students?
-
A company that makes gaming consoles has sold out on its most popular console, and it wants to keep a wait list for people who wish to buy the console when more are in stock. People who reserve a spot on the wait list earlier should be the first ones to obtain the console once more are released. What STL container should be used, and what is the time complex- ity of finding a certain person's position on the wait list, assuming there are m people on the wait list?
-
set, O(log(n)). A set is typically implemented as a binary search tree. A BST is capable of having an unlimited size (without impacting performance), and it uses only as much space as it needs (one per element). In addition, it maintains an ordering on the elements, as needed for the customer's last name.
-
unordered_map, O(1). An unordered_map is essentially a hash table that maps a key to a value, which is appropriate for pairing a student's name with his or her ID number. On average, a (well-designed) hash table can search up a key in constant time. Since the student population remains roughly the same, there is no need to worry about expanding the size of the hash table or any impact size expansion may have on its performance. Also, there are no requirements on any ordering.
-
queue, O(m). A queue is a FIFO data structure, which makes sense for this situation because the people who get on the wait list first should get off the wait list first when the console restocks.
Contributed by Caroline Quigg.
Write a function: bool isBST(Node* root).
This function will be used to determine if a tree is a binary search tree or not. Assume that the convetion we are using for BST is that values less than or equal are on the left and values strictly greater than are on the right.
One may any implement auxiliary functions needed to perform this task.
The idea behind the solution is that the children of a node should fall into a range depending on its ancestors. For example, the left child of any given node should be less than or equal to its parent, but it must also be less than its parent's parent and so on. So we keep track of the range a child node's value by keeping track of a max and min value, which we update as we recurse.
#include<climits>
struct Node{
int value;
Node* left;
Node* right;
};
bool isBSTHelper(Node* root, int min, int max) {
if ( root == nullptr)
return true;
if ((root->value <= min) || (root->value > max)) {
return false;
}
if (!isBSTHelper(root->left, min, root->value) ||
!isBSTHelper(root->right, root->value, max)) {
return false;
}
return true;
}
bool isBST(Node* root) {
return isBSTHelper(root, INT_MIN, INT_MAX);
}Contributed by Hye Won (Helen) Lee.
Find the minimum depth of a binary tree. The minimum depth is the lowest level of a tree, starting from the root node.
struct Node { int val; Node* left; Node* right; };
int minDepth(Node* root) {
if (root == nullptr) return 0;
if (root->left == nullptr && root->right == nullptr) return 1;
if (!root->left) return minDepth(root->right) + 1;
if (!root->right) return minDepth(root->left) + 1;
return min(minDepth(root->left), minDepth(root->right)) + 1;
}Contributed by Nikhil Kansal.
You are given the following code snippet.
#include <iostream>
class Base {
public:
Base(int, int&, int);
virtual ~Base();
virtual void print() const {
std::cout << a << ", " << b << ", " << *c << std::endl;
}
private:
int a;
int& b;
int* c;
};
/*
* Implement the constructor and destructor of Base here
*/
class Derived : public Base {
public:
Derived(int, int&, int);
virtual ~Derived();
virtual void print() const {
std::cout << "Called from Derived: " << std::endl;
Base::print();
}
};
/*
* Implement the constructor and destructor of Derived here
*/
int main() {
int x = 10;
Base b(5, x, 15);
b.print();
int y = 25;
Derived d(20, y, 30);
d.print();
return 0;
}Assume that everything written already is correct. Your job is to only
implement the constructors and destructors of the Base and Derived
classes such that running the program outputs exactly the following:
Constructing Base Class
5, 10, 15
Constructing Base Class
Constructing Derived Class
Called from Derived:
20, 25, 30
Destructing Derived Class
Destructing Base Class
Destructing Base Class
You may not change any of the written code. Only add code in the commented areas of the following code snippet.
// Notice the use of the initializer list to create the
// Base class, and also to assign the reference variable.
#include <iostream>
class Base {
public:
Base(int, int&, int);
virtual ~Base();
virtual void print() const {
std::cout << a << ", " << b << ", " << *c << std::endl;
}
private:
int a;
int& b;
int* c;
};
Base::Base(int _a, int& _b, int _c) : a(_a), b(_b) {
std::cout << "Constructing Base Class" << std::endl;
c = new int;
*c = _c;
}
Base::~Base() {
std::cout << "Destructing Base Class" << std::endl;
delete c;
}
class Derived : public Base {
public:
Derived(int, int&, int);
virtual ~Derived();
virtual void print() const {
std::cout << "Called from Derived: " << std::endl;
Base::print();
}
};
Derived::Derived(int _a, int& _b, int _c) : Base(_a, _b, _c) {
std::cout << "Constructing Derived Class" << std::endl;
}
Derived::~Derived() {
std::cout << "Destructing Derived Class" << std::endl;
}
int main() {
int x = 10;
Base b(5, x, 15);
b.print();
int y = 25;
Derived d(20, y, 30);
d.print();
return 0;
}Contributed by Shirley He
Given the root pointer to a binary search tree, implement the following function to print the tree in-order (use recursion):
void inOrder(Node* root);
Suppose level order of the tree : A / B C / D E F G / H I J K L
Inorder : H D I B J E K A L F C G
#include <iostream>
using namespace std;
struct Node {
int key;
Node* left;
Node* right;
};
void inOrder(Node* root) {
if ( root ) {
inOrder(root->left);
cout << root->key << " ";
inOrder(root->right);
}
}
int main() {
Node* root;
root->key = 10;
root->left = new Node;
root->left->key = 20;
root->left->left = nullptr;
root->left->right = nullptr;
root->right = nullptr;
inOrder(root);
return 0;
}Contributed by Michael Germano.
Given the following classes and main function, find the integer result.
class foo {
public:
explicit foo(int x) : y(x) {
if (y % 2 == 0) {
y *= 4;
y-= 1;
} else {
y *= 3;
}
}
virtual int doSomething() {
y -= 3;
return y;
}
private:
int y;
};
class bar : public foo {
public:
explicit bar(int x): foo(x * 2 + 1), x(x) {}
virtual int doSomething() {
int f = foo::doSomething();
x *= f;
return x;
}
private:
int x;
};
int main() {
foo * a = new bar(3);
foo b(4);
int result = a->doSomething() - b.doSomething();
// What is result?
delete a;
}
result == 42
Starting at main, we create foo *a that points to a dynamically allocated
bar object called a. We first enter bar's constructor for a. Here we construct
foo with value 7, since 3 * 2 + 1 = 7.
We then enter foo's constructor. Since 7 is odd, we multiply it by 3 (y is now 21 for a). Now we set x for a to 3 and our construction for a is finished.
Next we create b, constructing it with value 4. Since 4 is even we multiply by 4 and subtract 1 (y is now 15 for b).
We then we calculate a->doSomething(). Since this function is virtual,
we call the function for the bar class. This function then calls
foo::doSomething(); which returns 18 since 21 - 3 = 18.
Next we multiply x (which is 3) by this result which gives 3*18 = 54 and we return this value.
For the b.doSomething() function call, we simply subtract 3 from our y value
(15) and return this value (12). Lastly we set our result integer to the
difference between these two values: result = 54 - 12 = 42 and we are done.
© 2017 UCLA UPE Tutoring Committee.