# Coding Questions in C++

In this post, we will answer several programming challenge questions in C++. For easy testing of our single-file solutions, simply copy the entire source code and paste it into an online coding tool such as Coderpad at https://coderpad.io/sandbox.

## Questions

More programming challenge questions in C++ will be added as time permits. Let me know if there is any particular problem you would like to have solved here.

## Code

The repository contains the C++ solution codes.

## Solutions

1. Create a binary tree with insert, search and delete operations.

2. Move memory of an array from one location to another pointed by a new array pointer, without using temporary variables. The new and old memory regions might be overlapping. Copy the source array from the front into the destination, if they overlap at the front of the source array. Whereas, copy the source from the rear into the destination, if they overlap at the rear of the source array.

3. Given a string containing just the characters ‘(‘, ‘)’, ‘[’, ‘]’, ‘{‘, ‘}’, determine if the input string is valid. An input string is valid if :
• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.

Note that an empty string is also considered valid. String below are considered valid strings.

 ""
"()"
"()[]{}"
"{[]}"


Strings below are considered as invalid strings.

 "["
"}{"
"{()"
"(]"
"([)]"


4. Count the number of 1’s in a binary representation of a 32bit integer. A look-up table or hash map which stores integers and their corresponding bit count is used to solve this problem. Several test cases are shown below.
 Input: 1 // binary = 0000 0001
Input: 5 // binary = 0000 0101
Input: 15 // binary = 0000 1111
Input: 19 // binary = 0001 0011
Input: 22 // binary = 0001 0110


Expected output:

 Output: 1
Output: 2
Output: 4
Output: 3
Output: 3


5. Create a singly linked list with the following operations: insert at the tail, given a pointer delete the node (except the last node), and reverse.

6. Given two strings, find the longest continuous sequence of characters common to the two strings. The problem is solved using dynamic programming pradigm. A testcase is as follows.
 string str1 = "abcdefghijklmnopqrst";
string str2 = "abcd3ekl3abfgs";


Expected output:

 Max elements: 4
Max sequence: abcd


7. Given two strings, find the longest continuous or non-continous sequence with same ordering of characters common to the two strings. The problem is solved using dynamic programming pradigm. A testcase is as follows.
 string str1 = "abcdefghijklmnopqrst";
string str2 = "abcd3ekl3abfgs";


Expected output:

 Max elements: 8


8. Given a string containing just characters ‘(‘ and ‘)’, return the start and end indexes of the longest valid parentheses substring. Several test cases are shown below.
 Input: "" // answer: startIndex = 0, endIndex = 0
Input: "(()" // answer: startIndex = 1, endIndex = 2
Input: ")()())" // answer: startIndex = 1, endIndex = 4
Input: "())((())" // answer: startIndex = 4, endIndex = 7
Input: "())(()" // answer: startIndex = 0, endIndex = 1


Expected output:

 Longest valid parentheses of  is   , from  0 to  0
Longest valid parentheses of (() is () , from  1 to  2
Longest valid parentheses of )()()) is ()() , from  1 to  4
Longest valid parentheses of ())((()) is (()) , from  4 to  7
Longest valid parentheses of ())(() is () , from  0 to  1


9. Return the kth largest element, from an infinite stream of integers, at any point in time. The problem is solved using a priority queue. The priority queue is implemented by a minimum heap of size k. Read the top value of the heap to get the kth largest value at any point in time. Example input:
 vector<int> stream = {10, 20, 11, 70, 50, 40, 100, 5, ...};
int k = 3;


Expected STDOUT output:

 \$ -, -, 10, 11, 20, 40, 50, 50, ...


10. Build a priority queue whose elements’ priority can be updated dynamically. This problem is solved using the following two data structures:
• unordered_map<> functions as a set to hold all unique elements in the queue
• multimap<> functions to hold all inserted elements sorted by priority

Operation of the data structres is as follows:

• New element, which is not present in unordered_map<>, is pushed into the multimap<> and unordered_map<>.
• New element, which is present in unordered_map<>, is pushed into the multimap<> if it has a higher priority. Priority of the element in unordered_map<> is incremented to the higher value.
• To pop() the highest priority element from the queue: Firstly, elements are sequentially removed from the top of the multimap<> until an element which is also present in unordered_map<> is reached. This helps remove duplicate entries present in multimap<>. Once reached, remove the element from both multimap<> and unordered_map<>.

Example testcase:

 MutatablePriorityQueue mpq;
mpq.push('a',3); // value: 'a', priority: 3
cout << mpq.top() << "\n";
mpq.push('b',4); // value: 'b', priority: 4
mpq.push('c',3); // value: 'c', priority: 3
cout << mpq.top() << "\n";
mpq.push('a',5); // value: 'a', priority: 5
cout << mpq.top() << "\n";
mpq.pop();
cout << mpq.top() << "\n";
mpq.pop();
cout << mpq.top() << "\n";


Expected STDOUT output:

 a
b
a
b
c