-
Notifications
You must be signed in to change notification settings - Fork 6
CS 32 (Fall '17)
Contributed by Alex Hunsader.
Consider the following code:
#include <stdio.h>
#include <iostream>
#include <list>
using namespace std;
int main() {
list <int> l;
for (int i = 0; i < 5; i++)
l.push_front(i);
l.push_front(4);
for (int i = 0; i < 6; i++)
l.push_back(i);
list<int>::iterator it = l.begin();
for (; it != l.end(); it++) {
if (*it == 4)
it = l.erase(it);
}
for (it = l.begin(); it != l.end(); it++)
cout << *it << " ";
return 0;
}What will the code print?
a) There is undefined behavior. The code should use "it" wherever there is "*it".
b) There is undefined behavior. The code tries to increment an iterator that no longer exists.
c) 4 3 2 1 0 0 1 2 3 5
d) 4 4 3 2 1 0 0 1 2 3 4 5
e) 3 2 1 0 0 1 2 3 5
c)
The code properly uses iterators and the erase() function so there is no undefined behavior. The code attempts to delete all values in a list where the value is a 4. It is close but does not behave correctly when two 4s are put in a row. This is because the erase() function returns the next value in the list. The for loop then increments again, skipping the current value.
Contributed by Alden Perrine.
Two class definitions are given below. Assume no other constructors are defined, and that any methods for setting/getting or working with the data is not shown.
// class definition for problem
#include <string>
class inner_problem {
public:
explicit inner_problem(std::string val) {
s = val;
}
private:
std::string s;
};
class im_a_problem {
public:
im_a_problem(int size, std::string val);
im_a_problem& operator=(const im_a_problem& iap);
private:
int a_size;
int * arr;
inner_problem ip;
}; // <--- don't forget this! Write out implementations for the constructor and assignment operators of the im_a_problem class.
im_a_problem :: im_a_problem(int size, std::string val)
: ip(val) {
int* arr = new int[size];
a_size = size;
}
im_a_problem& im_a_problem:: operator=(const im_a_problem& iap) {
if (&iap == this) // check if same varaible
return *this;
delete [] arr; // delete already allocated array
this->a_size = iap.a_size;
arr = new int[a_size];
for (int i = 0; i < a_size; ++i)
arr[i] = iap.arr[i];
ip = iap.ip;
return *this;
}
Contributed by Aidan Wolk.
Convert this initial implementation of a max-heap to a min-heap, and use templates instead a fixed int type:
#include <vector>
#define parent(index) (index - 1) / 2
class MaxHeap {
std::vector<int> values;
public:
void add(int value) {
// Insert new value into heap
values.push_back(value);
int index = values.size() - 1;
// Sift the newly inserted value up
while (index != 0 &&
values[index] > values[parent(index)]) {
// Swap value with parent
std::swap(values[index], values[parent(index)]);
index = parent(index);
}
}
// ...
};The solution should be able to be used as:
MinHeap<double> heap;
heap.add(5.0);First we replace usages of int referencing the vector member variable with a variable type, using a template:
#include <vector>
#define parent(index) (index - 1) / 2
template <typename T>
class MaxHeap {
std::vector<T> values;
public:
void add(T value) {
// Insert new value into heap
values.push_back(value);
int index = values.size() - 1;
// Sift the newly inserted value up
while (index != 0 &&
values[index] > values[parent(index)]) {
// Swap value with parent
std::swap(values[index], values[parent(index)]);
index = parent(index);
}
}
// ...
};Then we convert the max-heap to a min-heap by "sifting up" newly inserted values if they are less than their parent values, instead of greater than:
#include <vector>
#define parent(index) (index - 1) / 2
template <typename T>
class MaxHeap {
std::vector<T> values;
public:
void add(T value) {
// Insert new value into heap
values.push_back(value);
int index = values.size() - 1;
// Sift the newly inserted value up
while (index != 0 &&
values[index] < values[parent(index)]) {
// Swap value with parent
std::swap(values[index], values[parent(index)]);
index = parent(index);
}
}
// ...
};Contributed by Caleb Chau.
Given the root node of a binary tree, delete all the nodes of the tree using a level order traversal. Hint: use a queue
#include <queue>
struct Node {
Node(const int key, const int value) {
k = key;
v = value;
left = right = nullptr;
}
int k;
int v;
Node* left;
Node* right;
};
void clear(Node* root) {
Node* curr = root;
// The tree is already empty
if (curr == nullptr) {
return;
}
// Queue for a level-order traversal
std::queue<Node*> q;
q.push(curr);
while (!q.empty()) {
Node* node = q.front();
q.pop();
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
delete node;
}
root = nullptr;
}Contributed by Brandon Oestereicher.
// The given C++ function takes a linked list of integers as a parameter
// and rearranges the elements of the list. When it is called with a list
// containing the integers 1, 2, 3, 4, 5, 6, 7 in that order, what will
// the contents of the list be after the function has executed?
struct node {
int num;
struct node *next;
};
void mix(struct node *list) {
struct node* p;
struct node* q;
int temp;
if ((!list) || !list->next) {
return;
}
p = list;
q = list->next;
while (q) {
temp = p->num;
p->num = q->num;
q->num = temp;
p = q->next;
q = p?p->next:0;
}
}A: 1, 2, 3, 4, 5, 6, 7
B: 1, 3, 4, 5, 2, 7, 6
C: 2, 1, 4, 3, 6, 5, 7
D: 2, 3, 4, 5, 6, 7, 1
Correct answer: C
Contributed by Binyi Wu.
Consider the binary tree structure:
struct TreeNode {
int item; // The data in this node.
TreeNode *left; // Pointer to the left subtree.
TreeNode *right; // Pointer to the right subtree.
};
We define subtree here as the node and its adjacent child leaves (the child leaves that connect directly to this node). So a typical subtree will be {node, node -> left, node -> right}.
Implement the function max_subtree(TreeNode* root) that takes the root of the tree as input, and returns the largest sum of the sub-tree.
Input:
2
/ \
4 3
/ \ / \
1 9 5 2
Expected output: 14
#include <iostream>
using namespace std;
// Tree structure
struct TreeNode {
int item; // The data in this node.
TreeNode *left; // Pointer to the left subtree.
TreeNode *right; // Pointer to the right subtree.
};
int max_subtree(const TreeNode* root) {
// recursion ends
if (root == nullptr)
return 0;
int sum = root -> item;
if (root -> left != nullptr) {
sum += root -> left -> item;
}
if (root -> right != nullptr) {
sum += root -> right -> item;
}
int a = max_subtree(root->left);
int b = max_subtree(root->right);
int c = a > b ? a : b;
return sum > c ? sum : c;
}
/**
The subtree in this main function is:
2
/ \
4 3
/ \ / \
1 9 5 2
Thus the sum is 1 + 9 + 4 = 14 in this case
*/
int main(int argc, const char * argv[]) {
// Example tree
TreeNode* root = new TreeNode;
TreeNode* l = new TreeNode;
TreeNode* r = new TreeNode;
TreeNode* ll = new TreeNode;
TreeNode* rr = new TreeNode;
TreeNode* lr = new TreeNode;
TreeNode* rl = new TreeNode;
root -> item = 2;
root -> left = l;
root -> right = r;
l -> item = 4;
l -> left = ll;
l -> right = lr;
r -> item = 3;
r -> left = rl;
r -> right = rr;
ll -> item = 1;
lr -> item = 9;
rl -> item = 5;
rr -> item = 2;
ll->left = nullptr;
lr->left = nullptr;
rl->left = nullptr;
rr->left = nullptr;
ll->right = nullptr;
lr->right = nullptr;
rl->right = nullptr;
rr->right = nullptr;
// function to be implemented
cout << max_subtree(root);
}Contributed by Jinjing Zhou.
Write a template function that takes in the start and the end of an array (can be of any type) and return the minimum element of the array.
double array[] = {1.5,2.5,3.0,2.3,2.1};
min(array, array+5); //result: 3.0
using namespace std;
template T min(T* begin, T* end) {
T min_val = *begin++;
if(min_val > *begin)
min_value = *begin;
begin++;
}Contributed by Jinjing Zhou.
Write a function that takes in the root node of a BST, and return the height of the tree.
int height(Node *ptr) {
if(ptr == nullptr)
return 0;
int left_height = height(ptr->left);
int right_height = height(ptr->right);
if(left_height >= right_height)
return 1+left_height;
else return 1+right_height;
}Contributed by Jonathan Quach.
Your problem description. Remember to wrap in-line code in ticks!
Suppose someone asked you to review four implementations of the function mergeTwoLists() that combines two sorted, singly-linked lists. Given that all four implementations all work, which one of the following implementations will take the longest time to complete?
/**
* Definition for singly-linked list.
* struct Node {
* int val;
* Node *next;
* Node(int x) : val(x), next(nullptr) {}
* };
*/
// (1)
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode dummy(INT_MIN);
ListNode *tail = &dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy.next;
}
// (2)
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
if (!l1)
return l2;
if (!l2)
return l1;
if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
return nullptr;
}
// (3)
ListNode *mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l2)
return l1;
if (!l2)
return l2;
vector<int> myVec;
ListNode* itr = l1;
while (itr) {
myVec.push_back(itr->val);
itr = itr->next;
}
itr = l2;
while (itr) {
myVec.push_back(itr->val);
itr = itr->next;
}
sort(myVec.begin(), myVec.end());
ListNode* temp = new ListNode(myVec[0]);
ListNode* nhead = temp;
for (int i = 1; i < myVec.size(); i++) {
ListNode* p = nhead;
while (p->next)
p = p->next;
ListNode* temp = new ListNode(myVec[i]);
p->next = temp;
}
return nhead;
}
// (4)
ListNode *mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *Head = new ListNode(0);
ListNode *pre = Head;
while (l1 && l2) {
if (l1->val < l2->val) {
pre->next = l1;
pre = l1;
l1 = l1->next;
} else {
pre->next = l2;
pre = l2;
l2 = l2->next;
}
}
if (l1)
pre->next = l1;
if (l2)
pre->next = l2;
ListNode *Result = Head->next;
delete Head;
return Result;
}Implementation (3) would take the longest because the sort function takes O((M+N)log(M+N)) operations to process all the nodes from both lists; all other implementations only take O(M+N) operations.
Contributed by Joseph Mo.
Given two lists sorted in increasing order, use recursion to merge the lists into a single list sorted in increasing order. Each list consists of a series of nodes, with each node containing an int data value and a pointer to the next node.
struct Node{
int value;
Node* next;
}Write the function Node* merge(Node* listA, Node* listB) that merges the two lists and returns a pointer to the head of the merged list. Assume that both listA and listB are sorted in increasing order.
/* Merges the lists headed by headA and headB into 1 list
Assume headA and headB are sorted in increasing order
Return the head node of the resulting list
*/
Node* merge(Node* listA, Node* listB) {
if (listA == nullptr) {
return listB;
} else if (listB == nullptr) {
return listA;
} else if (listA->value < listB->value) {
listA->next = merge(listA->next, listB);
return listA;
} else {
listB->next = merge(listA, listB->next);
return listB;
}
}Contributed by Justin Li.
Consider the following two functions:
int loop1(int n) {
int sum = 0;
for (int i = n; i >= 0; i--) {
for (int j = i; j > 0; j /= 2) {
sum++;
}
}
return sum;
}
int loop2(int n) {
int sum = 0;
for (int i = n; i >= 0; i /= 2) {
for (int j = i; j > 0; j--) {
sum++;
}
}
return sum;
}What is the time complexity for loop1? What is the time complexity for loop2? Are they the same? Explain.
The time complexity for loop1 is O(nlog(n)), and the time complexity for loop2 is O(n), so they are different. The time complexity for both loops is determined by how many times sum++ is called in both functions. In loop1, sum++ is called log(n) + log(n-1) + log(n-2) + ... + log(2) + log(1) = O(nlog(n)) times. In loop2, sum++ is called n + n/2 + n/4 + n/8 + ... + 2 + 1 = O(2n) = O(n) times.
Contributed by William Chou.
Given the code:
#include <iostream>
using namespace std;
class A {
public:
A() {
cout << "A" << " ";
}
~A() {
cout << "~A" << " ";
}
};
class B : public A{
public:
B() {
cout << "B" << " ";
}
~B() {
cout << "~B" << " ";
}
};
class C : public B {
public:
C() {
cout << "C" << " ";
}
~C() {
cout << "~C" << " ";
}
};
// main function
int main() {
C c;
}which of the following represents the correct output?
A) C B A ~C ~B ~A
B) C B A ~A ~B ~C
C) A B C ~A ~B ~C
D) B A C ~B ~A ~C
E) A B C ~C ~B ~A
E) A B C ~C ~B ~A
Contributed by Vansh Gandhi.
You must write a function that checks whether a given Binary Tree is a valid Binary Search Tree. Try to do this as efficiently as possible (it is possible in O(n)). It might be helpful to make use of a helper function.
Your function defintion should be bool isBST(Node *root);
A Node is defined as
typedef struct Node {
int val;
Node *left;
Node *right;
} Node;As with most tree problems, the best way to go about the solution is by using recursion. First define a helper function, that takes in two addtional arguments, a min and max (which represents the min and max values that the current value of the node can be). Then, recursively check if the left and right subtrees are valid BSTs as well.
#include <iostream>
#include <climits>
using namespace std;
typedef struct Node {
int val;
Node *left;
Node *right;
} Node;
bool bstHelper(Node *root, int min, int max) {
if (root == nullptr) {
return true;
}
bool isWithinConstraints = root->val > min && root->val < max;
bool isLeftTreeBST = bstHelper(root->left, min, root->val);
bool isRightTreeBST = bstHelper(root->right, root->val, max);
return isWithinConstraints && isLeftTreeBST && isRightTreeBST;
}
bool isBST(Node *root) {
return bstHelper(root, INT_MIN, INT_MAX);
}
int main() {
// Example of usage
Node left;
left.val = 2;
left.right = nullptr;
left.left = nullptr;
Node right;
right.val = 7;
right.right = nullptr;
right.left = nullptr;
Node root;
root.val = 5;
root.left = &left;
root.right = &right;
if (isBST(&root)) {
cout << "Valid BST" << endl;
} else {
cout << "Invalid BST" << endl;
}
return 0;
}Contributed by Vaibhav Aggarwal.
In the following scenarios, which operation has a better runtime efficiency? Or are they the same? Assume an open hastable with no collisions.
a. Accessing an element in an array vs accessing a value in a hashtable given it's key
b. Inserting an element into a random position in an array vs inserting a new key and value into a hastable
c. Searching for an element in a SORTED array vs searching for a value in a hashtable without knowing its corresponding key
a. Their runtime efficiencies are the same, they are both O(1) operations.
b. Inserting a new key and value into a hashtable is faster. It is O(1), while inserting an element into a random position in an array can be O(N) in the worst case since you could have to shift every element to the right if inserting into the front of the array.
c. Searching for an element in a sorted array is faster. It is O(log(n)) with a binary search, while searching for a value in a hashtable is O(n) in the worst case.
Contributed by Hannah Kwon.
Given the following program, what is the correct output?
#include <iostream>
#include <string>
#include <ctype.h>
using namespace std;
class Animal {
public:
explicit Animal(string name) {
m_name = name;
}
void say_name() {
cout << "My name is " << m_name << "." << endl;
}
private:
string m_name;
};
class Dog : public Animal {
public:
Dog(string name, string favorite_toy) : Animal(name) {
m_favorite_toy = favorite_toy;
}
void bark() {
cout << "Woof!" << endl;
}
void say_favorite_toy() {
cout << "My favorite toy is a " << m_favorite_toy << "." << endl;
}
private:
string m_favorite_toy;
};
class Beagle : public Dog {
public:
explicit Beagle(string name) : Dog(name, "bone") {}
};
class Maltese : public Dog {
public:
Maltese(string name, string favorite_toy) : Dog(name, favorite_toy) {}
};
int main(int argc, const char * argv[]) {
Animal animal("Fred");
Beagle beagle("Toby");
animal.say_name();
beagle.say_name();
Dog dog("Sam", "frisbee");
beagle.bark();
beagle.say_favorite_toy();
dog.say_favorite_toy();
Maltese maltese("Lola", "slipper");
maltese.say_favorite_toy();
maltese.say_name();
dog.say_favorite_toy();
}(a)
My name is Fred.
My name is Toby.
Woof!
My favorite toy is a frisbee.
My favorite toy is a frisbee.
My favorite toy is a frisbee.
My name is Lola.
My favorite toy is a frisbee.
(b)
My name is Fred.
My name is Toby.
Woof!
My favorite toy is a bone.
My favorite toy is a frisbee.
My favorite toy is a slipper.
My name is Lola.
My favorite toy is a frisbee.
(c)
My name is Fred.
My name is Toby.
Woof!
My favorite toy is a bone.
My favorite toy is a bone.
My favorite toy is a slipper.
My name is Lola.
My favorite toy is a slipper.
(d)
My name is Fred.
My name is Toby.
Woof!
My favorite toy is a bone.
My favorite toy is a frisbee.
My favorite toy is a slipper.
My name is Lola.
My favorite toy is a slipper.
(e) Does not compile.
(b)
Contributed by Haozhuo Huang.
What will the program behave after we remove the const after int get_a() const?
The program will not compile because add_one needs a const A object and the compiler has no right to check whether get_a modifies the object or not so it will give a compilation error.
#include <iostream>
using namespace std;
class A {
public:
A(): m_a(10) {}
int get_a() const {return m_a;}
private:
int m_a;
};
int add_one(const A& obj) {
return obj.get_a() + 1;
}
int main() {
A some_A();
add_one(some_A);
}Contributed by Hengda Shi.
Suppose we are given with two programs below, determine the output of the program.
First Program:
#include <iostream>
using namespace std;
class Felidae {
public:
void output() {
cout << "Fel" << endl;
}
};
class Cat: public Felidae {
public:
void output() {
cout << "Meow" << endl;
}
};
int main() {
// downcasting
Felidae *f = new Cat();
f->output();
Cat *c = new Cat();
c->output();
delete f;
delete c;
}Second Program:
#include <iostream>
using namespace std;
class Felidae {
public:
virtual void output() {
cout << "Fel" << endl;
}
};
class Cat: public Felidae {
public:
void output() {
cout << "Meow" << endl;
}
};
int main() {
// downcasting
Felidae *f = new Cat();
f->output();
Cat *c = new Cat();
c->output();
delete f;
delete c;
}As we can see in the code snippet, when a parent class pointer can point to different objects of itself and even inherited classes in heap, it is called polymorphism. It means that a parent class pointer can point to different type of content.
When you are downcasting a abstract class pointer, virtual keyword will become handy because it will help you find the correct function associated with the class which you downcasted to rather than calling the function in the abstract class.
The output of the first program:
Fel
MeowThe output of the second program:
Meow
MeowContributed by Honghua Zhang.
What is the Big O Complexity with respect to a and/or b, for the following function?
A) O(ab)
B) O(b)
C) O(log(a))
D) O(log(b))
E) O(1)
int qpow(int a, int b) {
int ans = 1;
while (b) {
if (b % 2 == 1)
ans = (ans * a) % 1003;
a = (a * a) % 1003;
b /= 2;
}
return ans;
}D)
Jason Less.
Given a binary tree, the goal is to return a variation of a level-order traversal of the tree's nodes using a zig-zag pattern (i.e. from left to right for one row, and then from right to left for the next, and so on).
Input:
[3, 9, 20, null, null, 15, 7]
Output:
[ [3], [20, 9], [15, 7] ]
#include <vector>
#include <queue>
using namespace std;
/* Idea: Do level-order tree traversal, and use a queue to push the nodes as you go down. */
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if (root == nullptr) return vector<vector<int>> ();
vector<vector<int>> rs; // Return vector of vectors
queue<TreeNode*> a; // Queue to store current node of the current level
a.push(root); // Push root to start
bool goRight = true; // Initially, process nodes from left to right
while (!a.empty()) { // While there are still nodes to process
int size = a.size();
vector<int> row(size); // Create a vector that can hold all nodes for a given row
for (int i = 0; i < size; i++) { // Process each node
TreeNode* node = a.front();
a.pop();
int index;
if (goRight) index = i; // If going left to right, index = i
else // If going right to left, index = size - 1 -i
index = size - 1 - i;
row[index] = node->val; // Current row element value
if (node->left) a.push(node->left); // Push the node's children (if it has any)
if (node->right) a.push(node->right);
}
goRight = !goRight; // Reverse direction to process on next level
rs.push_back(row); // Push current level to vector of vectors result
}
return rs;
}
Contributed by Anirudh Veeraragavan.
Write a function countPos that accepts an integer array and size and returns the number of elements of the list that are positive. The function must be implemented using recursion. The keywords do, while, and for are not allowed in the function.
int arr[] = {1, -4, 0, 4, 8, 0};
countPos(arr, 6) = 3;
int countPos(int arr[], int size) {
if (size == 0)
return 0;
if (arr[0] > 0)
return 1 + countPos(arr + 1, size - 1);
return countPos(arr + 1, size - 1);
}Contributed by Arpit Jasapara.
Read the code provided below. Determine what the code is supposed to do and pick the correct answer.
#include <cmath>
class Node {
public:
Node* left;
Node* right;
int value;
};
int depth(Node* root) {
if (root == nullptr)
return 0;
if (depth(root->left) >= depth(root->right))
return 1 + depth(root->left);
return 1 + depth(root->right);
}
bool doSomething(Node* root) {
if (root == nullptr)
return true;
int diff = abs(depth(root->left) - depth(root->right));
return diff <= 1 && doSomething(root->left) && doSomething(root->right);
}A) This code determines the total height of a tree, and performs calculations between subtrees to determine which is larger.
B) This code determines if the tree is a binary tree, and if it is height-balanced where depth of two subtrees differs by at most 1.
C) This code creates a linked list that forks into two lists at each node, and sums the differences.
D) This code takes a binary tree and finds the largest possible depth from the root, and whether or not it is rooted at the root.
E) This code does something else entirely, and the above answers do not represent the code accurately.
The answer is B! The code helps determine if a binary tree is height-balanced.
Atibhav Mittal
Given the following function, what is the output of the following function call?
mystery(83105);
a) Stack Overflow (Program Execution never ends) b) 013=85 c) 83=105 d) 50138=
The answer is b)
void mystery(int x) {
if (x == 0) {
cout << "=";
} else {
int y = x % 10;
if (y < 5) {
cout << y;
mystery(x / 10);
} else {
mystery(x / 10);
cout << y;
}
}
}Contributed by Pochao Yang.
Given a binary tree, find its maximum depth.
The max depth is the # of nodes along the longest path from the root node down to the farthest leaf node.
#include <iostream>
#include <algorithm>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
explicit TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int helper(TreeNode* root, int& result) {
if (!root) {
return 0;
}
return max(helper(root->left, result), helper(root->right, result)) + 1;
}
class Solution {
public:
int maxDepth(TreeNode* root) {
int result = 0;
helper(root, result);
return result;
}
};
Contributed by Qingyi Zhao.
What are the advantages and disadvantages of inline functions in C++? And when should we use them?
Pros:
- It speeds up your program by avoiding function calling overhead.
- It save overhead of variables push/pop on the stack, when function calling happens.
- It save overhead of return call from a function.
- It increases locality of reference by utilizing instruction cache.
- By marking it as inline, you can put a function definition in a header file (i.e. it can be included in multiple compilation unit, without the linker complaining)
Cons:
- It increases the executable size due to code expansion.
- C++ inlining is resolved at compile time. Which means if you change the code of the inlined function, you would need to recompile all the code using it to make sure it will be updated
- When used in a header, it makes your header file larger with information which users don’t care.
- As mentioned above it increases the executable size, which may cause thrashing in memory. More number of page fault bringing down your program performance.
- Sometimes not useful for example in embedded system where large executable size is not preferred at all due to memory constraints.
When to use. Function can be made as inline as per programmer need. Some useful recommendation are mentioned below:
- Use inline function when performance is needed.
- Use inline function over macros.
- Prefer to use inline keyword outside the class with the function definition to hide implementation details.
Contributed by Shawye Ho.
Implement the following function USING RECURSION:
int sumArray(int intArray[], int n) {
}This function takes an array of ints, and sums the first n elements of the array. Assume that n will always be less than or equal to the total number of elements in the array.
For example, if int arr[] = { -9, 7, 8, 33, 42, 17, -6 }; then sumArray(arr, 0) should return 0, sumArray(arr, 4) should return 39, and sumArray(arr, 7) should return 92.
One possible solution is given. This particular solution starts calculating the total starting from the last ((n-1)th) element of the array to be summed.
int sumArray(int intArray[], int n) {
if (n == 0)
return 0;
int total = intArray[n - 1];
return (total + sumArray(intArray, n - 1));
}Contributed by Nguyen Nguyen.
Your problem description. Remember to wrap in-line code in ticks!
Problem Description: Given the binary tree in the code below, what is the output of the code snippet?
a) 1 3 2 5 6
b) 1 2 5 6 3
c) 2 3 1 6 5
d) 5 6 2 3 1
The correct answer is a. If one is to draw out the binary tree, they will see that traversing the binary tree with a queue will perform a level-order traversal.
//
// main.cpp
// CheckPrime
//
// Created by nguyen nguyen on 11/26/17.
// Copyright © 2017 nguyen nguyen. All rights reserved.
//
#include <iostream>
#include <math.h>
#include <queue>
using namespace std;
struct Node {
Node* left;
Node* right;
int value;
};
int main() {
Node* root = new Node;
root -> value = 1;
Node* left = new Node;
left -> value = 3;
Node* right = new Node;
right -> value = 2;
left -> left = new Node;
left -> left -> value = 5;
right -> right = new Node;
right -> right -> value = 6;
root -> left = left;
root -> right = right;
queue<Node*> container;
container.push(root);
while (!container.empty()) {
Node* curr = container.front();
container.pop();
cout << curr -> value << " ";
if (curr -> left)
container.push(curr -> left);
if (curr -> right)
container.push(curr -> right);
}
}Muchen Liu.
Given the node struct as follow:
struct Node {
int val;
Node* left;
Node* right;
};We have two root nodes of two trees, test if two trees are the same
If you solution would benefit from a textual description, put that here. If you only want to provide the code, then remove these sentences!
struct Node {
int val;
Node* left;
Node* right;
};
bool isSameTree(Node* p, Node* q) {
if (!p)
return !q;
if (!q)
return !p;
return (p->val == q->val) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}Contributed by Nate Sookwongse.
A sorted singly-linked list is similar to a singly-linked list, except that each Node is sorted in ascending order at all times. Create a function called insert, which takes in a Node pointer for the head of the list and an int for the value of the Node to be inserted. This function should create a new Node with the value passed into this function and places this new Node in the correct spot in the list so that the sorted order is maintained. The function should also return a Node pointer, which is the head of the sorted singly-linked list after inserting the new Node. Make sure to handle the case that a empty list (NULL pointer) is passed in.
struct Node {
int val;
Node* next;
};
Node* insert(Node *head, int val) {
// write your solution here
}struct Node {
int val;
Node* next;
};
Node* insert(Node *head, int val) {
Node *ptr = head;
Node* new_node = new Node;
new_node->val = val;
// new Node should be inserted in the beginning and returned as new head
if (head == NULL || head->val >= val) {
new_node->next = head;
return new_node;
}
while (ptr->next != NULL && ptr->next->val < val) {
ptr = ptr->next;
}
// new Node should be inserted between ptr and ptr->next
new_node->next = ptr->next;
ptr->next = new_node;
return head;
}Contributed by Kevin Tan.
Given a binary tree root and an integer sum, write a function hasGivenPathWithSum(Tree *root, int sum) that uses recursion in a meaningful way to determine if there is a path in the tree from root to leaf such that the values of all nodes in the path sum up to sum.
Note: Helper functions are allowed.
// Definition for binary tree:
struct Tree {
int value;
Tree *left;
Tree *right;
};If
root =
3
/ \
2 9
/ \ \
-1 -4 5
and sum = 4, hasGivenPathWithSum(root, sum) should return true.
If we take the leftmost path from 3 -> 2 -> -1, we get 3 + 2 -1 = 4 == sum.
If
root =
5
/ \
3 2
\
1
and sum = 8, hasGivenPathWithSum(root, sum) should return false.
There is no root to leaf path such that the total sum of values in that path equal to exactly 8.
The trick to this problem is that we need to write a helper function that has extra parameters. Without it (with perhaps the exception of global variables), we have no way of keeping track of the sum of previous node values as we traverse the tree. We also need a parameter that keeps track of whether or not the parent is a leaf.
Our main function will merely call this helper function to do all of the work.
Edge cases:
-
rootis nullptr. In this case, we return true if and only ifsumis 0. -
rootis a leaf. In this case, we return true if and only ifroot->value == sum
// Definition for binary tree:
struct Tree {
int value;
Tree *left;
Tree *right;
};
bool subTreeHasPath(Tree *currentNode, int &sum, int currentSum, bool parentIsLeaf);
bool hasPathWithGivenSum(Tree *root, int sum) {
// root is nullptr; return true if sum == 0 and false otherwise.
if (!root) {
return sum == 0;
}
// Tree has only one node; return true if sum == node's value and false otherwise.
if (!root->left && !root->right) {
return sum == root->value;
}
// Use helper function.
return subTreeHasPath(root, sum, 0, false);
}
// currentNode: The current Tree node to process.
// sum: The original target sum.
// currentSum: The sum of values in the current path down the tree.
// parentIsLeaf: True if the Node that called subTreeHasPath is a leaf, false otherwise.
bool subTreeHasPath(Tree *currentNode, int &sum, int currentSum, bool parentIsLeaf) {
// currentNode is nullptr, meaning that we have either reached the end of a path from root to
// leaf or one of the parent nodes' children is nullptr. We check if our currentSum == sum,
// and if it is we return true if the parent node is a leaf and false otherwise.
if (!currentNode) {
if (currentSum == sum) {
return parentIsLeaf;
} else {
return false;
}
}
// Add the current node's value to our total running sum, and determine whether or not the
// current node is a leaf.
int newSum = currentSum + currentNode->value;
bool isLeaf = !currentNode->left && !currentNode->right;
// Using recursion check if the left or right subtrees have a valid path.
bool leftHasPath = subTreeHasPath(currentNode->left, sum, newSum, isLeaf);
bool rightHasPath = subTreeHasPath(currentNode->right, sum, newSum, isLeaf);
// If the left subtree or right subtree has a valid path, return true.
return leftHasPath || rightHasPath;
}Contributed by Kyle Wong.
Given a Node pointer head and an integer parameter diff, determine if the difference between the values of the adjacent nodes equal to diff. Note this difference is not the absolute value; rather it is the difference (next node's value - current node's value). Check the Example for more details.
Input: 1->3->5->7->9, 2 Output: true Explanation: The adjacent nodes all have a difference of 1.
Input: 1->2->1->2->3, 1 Output: false Explanation: Most of the adjacent nodes have the difference of 1, but the portion of the linked list 2->1 makes a difference of -1, which does not equal to 1.
#include <stdio.h>
#include <iostream>
using namespace std;
struct Node {
int val;
Node* next;
};
bool checkNodeDifference(Node* head, int diff) {
if (head == nullptr)
return true;
Node* curr = head;
Node* next = head->next;
while (curr->next != nullptr) {
if (next->val - curr->val != diff)
return false;
curr = next;
next = next->next;
}
return true;
}Contributed by Kevin Qian.
Predict the output of the following code.
#include <iostream>
using namespace std;
typedef int T1;
typedef double T2;
template <typename T1, typename T2>
T1 func(T1 x, T2 y) {
return x - y;
}
template <typename T>
T func(T x, T y) {
return x + y;
}
T1 func(T1 x, T2 y) {
return x * y;
}
int main(int argc, char *argv[]) {
cout << func(1, 2) << endl;
cout << func(1.0, 2) << endl;
cout << func(2, 3.0) << endl;
}3
-1
6
Contributed by William Lee.
Given a sorted increasing array of ints that has been rotated, find the minimum element index in O(log N) time.
Rotating an array is defined as moving all elements after and including an index, from the end to the beginning of the array. Note that rotating starting at index 0 produces the array itself!
Examples of some rotations:
[0,2,3,5] -> [3,5,0,2] (rotated at index 2)
[1,2,3] -> [1,2,3] (rotated at index 0)
Note that left always is 0 and right always is length of array - 1 for simplicity.
findMin([3,5,0,2], 0, 3) = 2
findMin([1,2,3], 0, 2) = 0
Use binary search. Suppose we found the middle index, mid. If arr[mid] is larger than element right after or arr[mid] is less than element right before, we can find the minimum element. Else, handle the case where mid is on the right side (smaller elements) or left side (larger elements). If mid on right side, the min is on its left. If mid on left side, the min is on its right.
#include <iostream>
using namespace std;
/**
find index of minimum element in rotated sorted array
Given: sorted array contains an increasing sequence that is rotated (or not at all)
*/
int findMin(int arr[], int left, int right) {
if (right < left) {
// haven't found the index where arr[index + 1] < arr[index]
return 0;
}
if (right == left) {
// look at 1 element
return left;
}
// middle of range
int mid = (left + right) / 2;
if (mid < right && arr[mid + 1] < arr[mid]) {
// found the minimum!
return mid + 1;
}
if (mid > left && arr[mid] < arr[mid - 1]) {
// found the minimum!
return mid;
}
// is mid on the lower or upper end?
if (arr[right] > arr[mid]) {
// mid is on lower end, so look on the left
return findMin(arr, left, mid - 1);
}
// the other case
return findMin(arr, mid + 1, right);
}Contributed by Kyle Romero.
You are the founder and CEO of a hot new mobile gaming company called Hot Daddy Games. You want to gather more data about the types of people using your games. You are to design a class called AgeStream that is able to take in ages and maintains a count of the number of people who have played your game of a certain age. Your class should contain three functions that meet the specifications below:
- A constructor that initializes any data structures that your class uses
-
void giveAge(int age)- a function that takes in an age representing someone of that age has played your game -
int getAgeCount(int age)- a function that returns the current count of people of age that have played your game
AgeStream ageThing;
ageThing.giveAge(35);
ageThing.giveAge(18);
ageThing.giveAge(35);
int thirtyFiveCount = getAgeCount(35);
int eighteenCount = getAgeCount(18);
// thirtyFiveCount = 2 and eighteenCount = 1
class AgeStream {
public:
AgeStream() {
for (int i = 0; i < 150; i++)
ages[i] = 0;
}
void giveAge(int age) {
ages[age]++;
}
int getAgeCount(int age) {
return ages[age];
}
private:
int ages[150];
};Contributed by Analisse Reyes.
Complete the reverse function that reverses the elements in s. s is a stack and q is an empty queue.
void reverse(stack *s, queue *q) {
if (s.empty()) {
return;
}
while (!s.empty()) {
q.push(s.top());
s.pop();
}
while (!q.empty()) {
s.push(q.front());
q.pop();
}
}Contributed by Andrew Xue.
Implement a function erase(node* List, node* tail, int x) to erase all nodes with value x from List. List is a doubly linked list, and List is the head. List has both head and tail. If no such node exists, do nothing.
struct node {
int val;
node* next;
node* prev;
}
void erase(node* List, node* tail, node X)
{
if(List == NULL)
return;
node* temp = List;
while(temp != tail)
{
if (temp->val == x)
{
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
}
}
}
Contributed by Andrew Ding.
Input: List1 = 1->3->7, List2 = 0->4->5->6
Output: 0->1->3->4->5->6->7
#include <iostream>
struct ListNode {
int val;
ListNode *next;
explicit ListNode(int x){
val = x;
next = NULL;
}
};
ListNode *mergeLists(ListNode *l1, ListNode *l2) {
ListNode *dummy = new ListNode(-1);
ListNode *tail = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy->next;
}Contributed by Lawrence Lee.
Modify the following class so that passing a vector of WeirdNumber objects to the STL sort function will order all numbers in descending order, with the exception that odd numbers must go before even numbers.
#include <iostream>
class WeirdNumber{
public:
explicit WeirdNumber(int number) : m_int(number) { }
void printVal() {
std::cout << m_int;
}
private:
int m_int;
};With the WeirdNumber class is defined/included, the following program should output "53142"
#include <algorithm>
#include <vector>
int main() {
// an array of normal integers, "numbers"
const int LEN = 5;
int numbers[LEN] = {1, 2, 3, 4, 5};
// initializes a vector of corresponding WeirdNumber objects using ints from numbers
// ie. weirdnumbers = { 1, 2, 3, 4, 5}
std::vector<WeirdNumber> weirdnumbers(numbers, numbers + LEN);
// sort the weird numbers using the STL sort function with default comparison
std::sort(weirdnumbers.begin(), weirdnumbers.end());
// prints elements of weirdnumbers in order
for (std::vector<WeirdNumber>::iterator i = weirdnumbers.begin(); i != weirdnumbers.end(); i++)
i->printVal();
}In order for the above program to compile, we have to define a custom comparison operator so that the STL sort function can make comparisons with the "<" operator. Overloading the comparison operator will not answer the question because we are only allowed to modify the WeirdNumber class. The custom comparison operator must also be defined as const, since the STL sort function takes const references.
#include <iostream>
class WeirdNumber{
public:
explicit WeirdNumber(int number) : m_int(number) { }
void printVal() {
std::cout << m_int;
}
bool operator<(const WeirdNumber &other) const {
if ((m_int % 2) != (other.m_int % 2)) // if the two numbers are not both odd/even
return m_int % 2;
else // if the two numbers are both odd/even
return m_int > other.m_int;
}
private:
int m_int;
};Contributed by Spenser Wong.
Consider the fibonacci sequence. The nth term of the fibonacci sequence is defined by the formula f(n) = f(n-1) + f(n-2). Using recursion, write a function that takes in an integer n, and returns the nth term of the fibonacci sequence. You may assume that f(0) = 0 and f(1) = 1. You may also assume that n is nonnegative, and you will not be asked to compute a term with a value greater than the maximum positive integer value. Is a recursive approach the most effective way to solve this problem? Why or why not?
fibonacci(0) = 0;
fibonaccci(1) = 1;
fibonacci (2) = 1;
fibonacci (3) = 2;
fibonacci (4) = 3;
fibonacci (5) = 5;
fibonacci (6) = 8;
fibonacci (7) = 13;
...
int fibonacci(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}No, a recursive approach is not the most effecctive way to solve this problem. This is because as n grow larger, the amount of recursive calls required by fibonacci grows at an incredibly fast rate, as the function is essentially adding 1 to itself over and over again. For example, the 25th term of the fibonacci sequence is 75025. A much more effective solution is to solve the problem iteratively, storing results and using them to calculate the next results in the sequence.
Sriharshini Duggirala.
The following functions print out the data in each node of a binary tree, all three are depth first traversals. a.) Specify which function is Inorder, Preorder, and Postorder. b.) Write the output of the data for the following binary tree.
1
/ \
2 3
/ \
4 5
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
};
void func1(struct Node* node) {
if (node == NULL)
return;
func1(node->left);
func1(node->right);
cout << node->data;
}
void func2(struct Node* node) {
if (node == NULL)
return;
func2(node->left);
cout << node->data;
func2(node->right);
}
void func3(struct Node* node) {
if (node == NULL)
return;
cout << node->data;
func3(node->left);
func3(node->right);
} Answer:
a.)
Inorder: (func2)
Preorder: (func3)
Postorder: (func1)
b.)
45231 //func1
42513 //func2
12453 //func3
Contributed by Steven Lara.
When accessing data from objects, things can go wrong if the variable exists in a derived class but not in the base class. Which of the following is the correct way of accessing a derived object's data after assignment to the base class?
class A
{
public:
int hallo;
};
class B : public A {
public:
int wassup;
};
int main() {
//the following 7 lines of code are incorrect
A foo;
B bar;
bar.hallo = 5;
bar.wassup = 7;
foo = bar;
cout << foo.wassup;
}
A)
A foo;
B bar;
foo.hallo = 5;
foo.wassup = 7;
bar = foo;
cout << bar.wassup;
B)
A *foo;
B *bar;
bar = new B;
bar->hallo = 5;
bar->wassup = 7;
foo = bar;
cout << ((B *)foo)->wassup;
C)
A foo;
B bar;
bar.hallo = 5;
bar.wassup = 7;
foo.hallo = bar.hallo;
foo.wassup = foo.wassup;
cout << foo.wassup;
B is the correct answer. Dynamic variables will allow for reference to derived variables. (B *) is a static cast. Static casts allow for this type of reference when the type of object is known to be a derived class.
Contributed by Tina Luo.
Given the below c++ code of printing the inorder traversal of a binary tree, decide the Big O of the function inorder(node *root). Assume the binary tree has n nodes and e edges.
struct node {
int data;
struct node* left;
struct node* right;
};
int inorder(node *root) {
if (root == NULL) {
return 0; }
inorder(root->left);
cout << root->data << "\n";
inorder(root->right); }Options:
a) O(n+e)
b) O(n)
c) O(2^n)
d) O(nlogn)
b)
The function uses recursion, so it is confusing how to calculate Big O. Stepping back and looking at the big picture, each node is visited only once. So the Big O is simply O(n).
Contributed by Daniel Li.
What's the run-time of this recursive function?
int function(int n){
if (n<=1){
return 1;
}
return function(n-1)+function(n-1);
}
A) O(n^3)
B) O(log(n))
C) O(n^2)
D) O(2^n)
D, because each layer of the recursive tree has 2x the calls of the previous layer. The patterning goes 2^0+2^1+2^2.. this sums to 2^(n+1)-1. It may be helpful to draw out the tree to see this pattern.
© 2017 UCLA UPE Tutoring Committee.