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.

1. Binary tree with insert, search, delete operations
2. Move memory without temporary variable
3. Match brackets in a string
4. Sum of bits in 32-bit binary representation
5. Linked list - insert, delete, reverse
6. Longest continuous sequence
7. Longest sequence
8. Longest valid parentheses
9. Kth largest
10. Mutatable priority queue

Code

The repository contains the C++ solution codes.

Solutions

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

   Link to solution code.

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.

   Link to solution code.

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.

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

   Link to solution code.

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
   

   Link to solution code.

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.

   Link to solution code.

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
   

   Link to solution code.

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
   

   Link to solution code.

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
   

   Link to solution code.

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, ...
   

   Link to solution code.

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
    

    Link to solution code.