Crack the top 40 C++ coding interview questions

C++ from Scratch Series

• Why C++ is a good first language to learn

• Beginner’s Guide to C++

• Intermediate C++ Tutorial

• Multithreading and Concurrency in C++

• Top 40 C++ Coding Interview Questions

C++ is a popular OOP programming language used across the tech industry. Companies like Microsoft, LinkedIn, Amazon, and PayPal list C++ as their main programming language with others for coding interviews.

Overall, C++ is a must-have skill for modern developers interested in these large companies.

Today, we’ll go through the top 40 C++ coding interview questions used to test C++. By the end, you’ll have the confidence and hands-on experience to approach any C++ interview confidently.

Here’s what we’ll cover today:

• Big O Notation
• Data Structures
• Recursion
• Dynamic Programming
• More practice questions
• Wrapping up and next steps
  

Solution Explanation

On line 6 in the outer loop, int i=1; runs once, i<n; gets executed ${n}/{3}+1$ times and i+=3 is executed ${n}/{3}$ times.

In the inner loop, int j=1; gets executed ${n}/{3}$ times in total. j<n; executes $({n}/{3})$ $*$ $({n}/{2}+1)$ times and j+=2 gets executed $({n}/{3})$ $*$ $({n}/{2})$ times.

For more information, see our line by line breakdown:

Added together, the runtime complexity is $15+$ $({5n}/3)$ $+(2n^2)/3$

Now convert this to Big O.

1. Drop the leading constants: $n+n^2$
2. Drop lower order terms: $n^2$

2. Nested Loop with Multiplication

Find the Big O complexity of the following code:

int main() {
  int n = 10; //n can be anything
  int sum = 0;
  float pie = 3.14;
  int var = 1;

  while (var < n){
    cout << pie << endl;
    for (int j=0; j<var; j++)
      sum+=1;
    var*=2;  
  }
  cout<<sum;
}

Solution Explanation

Runtime complexity: $4+$ $4log$₂$(n)$ $+6n$

Big O: $O(n)$

3. Common mistakes with nested loop

Find the Big O complexity of the following code:

for( int i=0; i<array.length; i++){
  for(int j=0; j<10000; j++)
  {
    // some useful work done here.
  }
}

Solution Explanation

This is a “gotcha” question that tests if you really understand Big O.

Even if they’re nested, the inner loop’s number of executions is not dependent on the input. It will always execute the same number of times.

A common mistake is to answer $O(10000n)$. Big O calculates for asymptotic behavior therefore, we remove constants like 10,000.

The correct answer is then $O(n)$.

4. Do-while loop

Find the complexity of the following code:

Solution Explanation

The for loop from lines 6-8 calculates the average of the contents of the array. It’s complexity is $O(n)$.

The do-while loop from lines 14-24 is tricky. It may seem that the complexity is $O(n^2)$ because of the nested loops.

In fact ,we have to account for two possibilities.

1. The average calculated for the given input array also occurs in the array.
2. The average is a float and doesn’t appear in the array.

If the average is a float then the nested while loop on lines 16-17 will increment the value of the variable j to the size of the input array. Also, the do-while condition will become false.

The complexity in this case will be $O(n)$

If the average does appear in the array and the array consists of all the same numbers, then the nested while loop of lines 16-17 will not run. The if clause of lines 20-23 will kick-in and increment j to the size of the array as the outer do-while loop iterates.

Hence the overall complexity of the snippet is $O(n)$.

5. Recursive Complexity

Find the Big O complexity of the following code:

int recursiveFun1(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun1(n-1);
}

int recursiveFun2(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun2(n-5);
}

int recursiveFun3(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun3(n/5);
}

void recursiveFun4(int n, int m, int o)
{
    if (n <= 0)
    {
        printf("%d, %d\n",m, o);
    }
    else
    {
        recursiveFun4(n-1, m+1, o);
        recursiveFun4(n-1, m, o+1);
    }
}

int recursiveFun5(int n)
{
    for (i = 0; i < n; i += 2) {
        // do something
    }

    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun5(n-5);
}

Solution

For this one, it’s best to break down the problem function by function.

int recursiveFun1(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun1(n-1);
}

This function is called n times before reaching base case. It therefore has a Big O complexity of $O(n)$.

int recursiveFun2(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun2(n-5);
}

This function is called n-5 times and simplifies to $O(n)$ with Big O.

int recursiveFun3(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun3(n/5);
}

The complexity here is $log(n)$ because of every time we divide by 5 before calling the function.

void recursiveFun4(int n, int m, int o)
{
    if (n <= 0)
    {
        printf("%d, %d\n",m, o);
    }
    else
    {
        recursiveFun4(n-1, m+1, o);
        recursiveFun4(n-1, m, o+1);
    }
}

Here the complexity is $O(2^n)$ because each function calls itself twice unless recurred n times.

int recursiveFun5(int n)
{
    for (i = 0; i < n; i += 2) {
        // do something
    }

    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun5(n-5);
}

Finally, the for loop executes $n/2$ times because i iterates by 2 and the recursion takes $n-5$ since the loop is called recursively.

Together, they have a complexity of $2n^2-10n$ or $O(n^2)$.

Solution and Breakdown

Time complexity: $O(n)$

We use three iterators simultaneously to traverse each of the arrays. Each pointer starts at the 0th index because that is the smallest in the list.

The program first looks to see if the 0th element is shared. Then, we’ll return that value.

Otherwise, we’ll see which iterator amongst the three points to the smallest value and will increment that iterator so that it will point to the next index. We have found the solution when all iterators match.

If any of the three iterators reaches the end of the array before its finds a common number, we’ll return -1.

7. Move All Zeros to the Beginning of the Array

Problem Statement

“Given an integer array, move all elements that are 0 to the left while maintaining the order of other elements in the array. The array must be modified in-place.”

Hints:

• Use reader/writer indexes
• You cannot use a simple chronological sort as elements other than zeros must maintain their position.

Solution and Breakdown

Time complexity: $O(n)$

We keep two markers: read_index and write_index. Both start pointed to the end of the array.

While moving read_index towards the start of the array:

If read_index points to 0, we that skip element.

If read_index points to a non-zero value, we write the value at read_index to the write_index and then decrement write_index.

Once read_index reaches the end of the array, we assign zeros based on the location of write_index. Any values on or before write_index must be zeros.

8. Reverse Even Nodes in a Linked List

Problem Statement

“Given a singly linked list, reverse the nodes at even indices (starting at 1).”

Hint:

• Create a list for even numbers

Solution and breakdown

Time Complexity: $O(n)$

We will create two lists comprising of nodes at even and odd indices.

We avoid copying data of elements or reallocating memory to improve efficiency.

We push extracted nodes to the head of list_even to reverse their order while merging.

Once the two lists are in the correct order, we merge their nodes alternately to create our solution.

9. Sort a Linked List Using Merge Sort

Problem Statement

“Given the head pointer of a linked sort, sort the linked list in ascending order using merge sort, and return the new head pointer of sorted linked list.”

Hint:

• Divide and Conquer

Solution and Breakdown

Time Complexity: $O(nlogn)$

Mergesort is a commonly asked for in interviews. First, you divide the list into smaller lists, then sort each smaller list, and finally combine the sorted lists.

In the dividing step, we split our input linked list in half until there is a linked list of size 1 or 0. Linked lists of size 1 and 0 are always sorted.

In the combining step, we merge sorted lists until we have a completely sorted list.

10. Count of Palindromic Substrings

Problem Statement

“Find the total number of palindromic substrings within a given string.”

Hint:

• This problem is a variation on the “Longest Subsequence” question type.

Solution and Breakdown

Time Complexity: $O(n^2)$

This solution uses a boolean table with a column for each letter. If the X and Y column are the same letter, the table returns that space as true. Otherwise, it returns false.

Here it is step-by-step:

1. Maintain a boolean table[n][n] filled from the bottom up.
2. If the substring is a palindrome, the value of table[i][j] is true. Otherwise the value is false.
3. To calculate table[i][j], we check the value of table[i+1][j-1]. If the value is true and str[i] is same as str[j], then the substring is a palindrome and we make table[i][j] true.
4. Otherwise, the value of table[i][j] is made false.
5. We then fill the table that was previously for the substring of length = 1 and length =2.

11. Reverse Words in a Sentence

Problem Statement

“Reverse the order of words in a given string.”

Hints:

• The problem asks for reversing word order, not letters within the word.
• Each word will be separated by spaces

Solution and Breakdown

Time Complexity: $O(n)$

The program works in two stages:

1. Reverse the entire string
2. Reverse each word in-place

Stage 2 works by setting a pointer for the beginning of the word, start, at the on element 0 or the first element after a space. We also set another pointer for the end of the word, end, on the element right before the next space.

Both pointers then iterate toward each other, swapping values on each element.

Once the pointers are on the same element, the word has be correctly reversed and our pointers move to the next word.

Our program is complete once all words have been reversed back to their proper order.

12. Reverse First k Elements of Queue

Problem Statement

“Implement the function myQueue reverseK(myQueue queue, int k) which takes a queue and a number k as input and reverses the first k elements of the queue.”

Solution and Breakdown

Time Complexity: $O(n)$

First we dequeue the first k elements from the front of the queue and push them in the stack we created on line 9 with stack.push(queue.dequeue()).

Once all the k values have been pushed to the stack, we start popping them and sequentially enqueuing them on line 14. We’ll queue them to the back using queue.enqueue(stack.pop()). At the end of this step, we will be left with an empty stack and the k reversed elements will be appended to the back of the queue.

Finally on line 19 we’ll move the resersed elements to the front of the queue usings queue.enqueue(queue.dequeue()). Each element is first dequeued from the back.

13. Zigzag Traversal

Problem Statement:

"Given a binary tree, populate an array to represent its zigzag level order traversal.

You should populate the values of all nodes of the first level from left to right, then right to left for the next level, alternating in the same way for all levels."

Hints:

• This question is an iteration of the “Binary Tree Level Order Traversal” question type

Solution and Breakdown

Time Complexity: $O(n)$

1. We start by pushing the root node to the queue.
2. We then iterate through the queue until the queue is empty.
3. In each iteration, we first count the elements in the queue (let’s call it levelSize). We will have this many nodes in the current level.
4. Next, remove levelSize nodes from the queue and push their value in an array to represent the current level.
5. After removing each node from the queue, insert both of its children into the queue.
6. If the queue is not empty, flip the direction of the traversal and repeat from step 3 for the next level.

14. Determine if an Undirected Graph is a Tree

Problem Statement:

“Create function bool isTree(Graph g) that takes a graph as input and returns if the passed graph is a tree.”

A graph is a tree if:

• There are no cycles.
• All nodes of the graph are reachable from all other nodes of the graph, directly or through traversal.

Hints:

• This can be solved using either Depth First Search or Breadth First Search

Solution and Breakdown