Crack the top 40 C++ coding interview questions

void averager(int[] A) {
      float avg = 0.0f;
      int j, count;
      for (j = 0; j < A.length; j++) {
         avg += A[j];
      }
    avg = avg / A.length;
    count = j = 0;
   do {
      while (j < A.length && A[j] != avg) {
             j++;
      }
      if (j < A.length) {
              A[j++] = 0;
               count++;
      }
  } while (j < A.length);
}

int find_least_common_number(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
  int i = 0, j = 0, k = 0;
  while(i < arr1.size() && j < arr2.size() && k < arr3.size()) {
    // Finding the smallest common number
    if((arr1[i] == arr2[j]) && (arr2[j] == arr3[k]))
      return arr1[i];
    // Let's increment the iterator
    // for the smallest value.
    if(arr1[i] <= arr2[j] &&  arr1[i] <= arr3[k]) {
      i++;
    }
    else if(arr2[j] <= arr1[i] && arr2[j] <= arr3[k]) {
      j++;
    }
    else if(arr3[k] <= arr1[i] && arr3[k] <= arr2[j]) {
      k++;
    }
  }
  return -1;
}
int main(int argc, char* argv[]) {
  vector<int> v1 = {6, 7, 10, 25, 30, 63, 64};
  vector<int> v2 = {1, 4, 5, 6, 7, 8, 50};
  vector<int> v3 = {1, 6, 10, 14};
  int result = find_least_common_number(v1, v2, v3);
  cout << "Least Common Number: " <<result;
}

void move_zeros_to_left(int A[], int n) {
   
  if (n < 1) return;
  
  int write_index = n - 1;
  int read_index = n - 1;
  while(read_index >= 0) {
    if(A[read_index] != 0) {
      A[write_index] = A[read_index];
      write_index--;
    }
    read_index--;
  }
  while(write_index >= 0) {
    A[write_index] = 0;
    write_index--;
  }
}
int main() {
  int v[] = {1, 10, 20, 0, 59, 63, 0, 88, 0};
  int n = sizeof(v) / sizeof(v[0]);
  cout << "Original Array" <<endl;
  
  for(int x=0 ; x<n; x++) {
    cout << v[x];
    cout << ", ";
  }  
  
  move_zeros_to_left(v, n);
  
  cout << endl<< "After Moving Zeroes to Left"<< endl;
  for(int i=0 ; i<n; i++) {
    cout << v[i];
    cout << ", ";
  }  
}  

// Helper function to merge two lists.
LinkedListNode* merge_alternating(LinkedListNode* list1, LinkedListNode* list2) {
  if (list1 == nullptr) {
    return list2;
  }
  if (list2 == nullptr) {
    return list1;
  }
  LinkedListNode* head = list1;
  while (list1->next != nullptr && list2 != nullptr) {
    LinkedListNode* temp = list2;
    list2 = list2->next;
    temp->next = list1->next;
    list1->next = temp;
    list1 = temp->next;
  }
  if (list1->next == nullptr) {
    list1->next = list2;
  }
  return head;
}
LinkedListNode* reverse_even_nodes(LinkedListNode* head) {
  // Let's extract even nodes from the existing
  // list and create a new list consisting of 
  // even nodes. We will push the even nodes at
  // head since we want them to be in reverse order.
  LinkedListNode* curr = head;
  LinkedListNode* list_even = nullptr;
  while (curr != nullptr && curr->next != nullptr) {
    LinkedListNode* even = curr->next;
    curr->next = even->next;
    // Push at the head of new list.
    even->next = list_even;
    list_even = even;
    curr = curr->next;
  }
  // Now, merge the two lists
  // Original: 1,2,3,4,5
  // Modified original: 1,3,5
  // List_even: 4,2
  // Merged: 1,4,3,2,5
  return merge_alternating(head, list_even);
}
int main() {
  vector<int> v1 = {7, 14, 21, 28, 9};
  LinkedListNode* list_head = LinkedList::create_linked_list(v1);
  
  cout << "Original list: ";
  LinkedList::display(list_head);
  list_head = reverse_even_nodes(list_head);
  cout <<"After reversing even nodes: ";
  LinkedList::display(list_head);
}

typedef LinkedListNode* node_ptr;
// this method splits linked list in two halves by iterating over whole list
// It returns head pointers of first and 2nd halves of linked lists in first_second
// Head of 1st half is just the head node of linked list
void split_in_half(node_ptr head, pair<node_ptr, node_ptr>& first_second) {
  if (head == nullptr) {
    return;
  }
  // Only one element in the list.
  if (head->next == nullptr) {
    first_second.first = head;
    first_second.second = nullptr;
  } else {
    // Let's use the classic technique of moving two pointers:
    // 'fast' and 'slow'. 'fast' will move two steps in each
    // iteration where 'slow' will be pointing to middle element
    // at the end of loop.
    node_ptr slow, fast;
    slow = head;
    fast = head->next;
    while (fast != nullptr) {
      fast = fast->next;
      if (fast != nullptr) {
        fast = fast->next;
        slow = slow->next;
      }
    }
    first_second.first = head;
    first_second.second = slow->next;
    // Terminate first linked list.
    slow->next = nullptr;
  }
}
node_ptr merge_sorted_lists(node_ptr first, node_ptr second) {
  if (first == nullptr) {
    return second;
  }
  else if (second == nullptr) {
    return first;
  }
  node_ptr new_head;
  if (first->data <= second->data) {
    new_head = first;
    first = first->next;
  }
  else {
    new_head = second;
    second = second->next;
  }
  node_ptr new_current = new_head;
  while (first != nullptr && second != nullptr) {
    node_ptr temp = nullptr;
    if (first->data <= second->data) {
      temp = first;
      first = first->next;
    } else {
      temp = second;
      second = second->next;
    }
    new_current->next = temp;
    new_current = temp;
  }
  if (first != nullptr) {
    new_current->next = first;
  } else if (second != nullptr) {
    new_current->next = second;
  }
  return new_head;
}
node_ptr merge_sort(node_ptr head) {
  // No need to sort a single element.
  if (head == nullptr || head->next == nullptr) {
    return head;
  }
  // Let's split the list in half, sort the sublists
  // and then merge the sorted lists.
  pair<node_ptr,node_ptr> first_second;
  split_in_half(head, first_second);
  first_second.first = merge_sort(first_second.first);
  first_second.second = merge_sort(first_second.second);
  return merge_sorted_lists(first_second.first, first_second.second);
}
int main() {
  vector<int> v1 = {29, 23, 82, 11, 4, 3, 21};
  node_ptr list_head_1 = LinkedList::create_linked_list(v1);
  cout << "Unsorted list: ";
  LinkedList::display(list_head_1);
  list_head_1 = merge_sort(list_head_1);
  cout<<"Sorted list: ";
  LinkedList::display(list_head_1);
}

#include <bits/stdc++.h> 
using namespace std; 
  
// Function to print a substring 
// str[low..high] 
void printSubStr( 
    string str, int low, int high) 
{ 
    for (int i = low; i <= high; ++i) 
        cout << str[i]; 
} 
  
// This function prints the 
// longest palindrome substring 
// It also returns the length of 
// the longest palindrome 
int longestPalSubstr(string str) 
{ 
    // get length of input string 
    int n = str.size(); 
  
    // table[i][j] will be false if substring 
    // str[i..j] is not palindrome. 
    // Else table[i][j] will be true 
    bool table[n][n]; 
  
    memset(table, 0, sizeof(table)); 
  
    // All substrings of length 1 
    // are palindromes 
    int maxLength = 1; 
  
    for (int i = 0; i < n; ++i) 
        table[i][i] = true; 
  
    // check for sub-string of length 2. 
    int start = 0; 
    for (int i = 0; i < n - 1; ++i) { 
        if (str[i] == str[i + 1]) { 
            table[i][i + 1] = true; 
            start = i; 
            maxLength = 2; 
        } 
    } 
  
    // Check for lengths greater than 2. 
    // k is length of substring 
    for (int k = 3; k <= n; ++k) { 
        // Fix the starting index 
        for (int i = 0; i < n - k + 1; ++i) { 
            // Get the ending index of substring from 
            // starting index i and length k 
            int j = i + k - 1; 
  
            // checking for sub-string from ith index to 
            // jth index iff str[i+1] to str[j-1] is a 
            // palindrome 
            if (table[i + 1][j - 1] && str[i] == str[j]) { 
                table[i][j] = true; 
  
                if (k > maxLength) { 
                    start = i; 
                    maxLength = k; 
                } 
            } 
        } 
    } 
  
    cout << "Longest palindrome substring is: "; 
    printSubStr(str, start, start + maxLength - 1); 
  
    // return length of LPS 
    return maxLength; 
} 
  
// Driver Code 
int main() 
{ 
    string str = "Galaxy"; 
    cout << "\nLength is: "
         << longestPalSubstr(str); 
    return 0; 
} 

void str_rev(char *str, int len) {
  if (str == nullptr || len < 2) {
    return;
  }
  char *start = str;
  char *end = str + len - 1;
  while (start < end) {
    if (start != nullptr && end != nullptr) {
      char temp = * start;
      *start = *end;
      *end = temp;
    }
    start++;
    end--;
  }
}
void reverse_words(char *sentence) {
  // Here sentence is a null-terminated string ending with char '\0'.
  if (sentence == nullptr) {
    return;
  }
  // To reverse all words in the string, we will first reverse
  // the string. Now all the words are in the desired location, but
  // in reverse order: "Hello World" -> "dlroW olleH".
  int len = strlen(sentence);
  str_rev(sentence, len);
  // Now, let's iterate the sentence and reverse each word in place.
  // "dlroW olleH" -> "World Hello"
  char *start = sentence;
  char *end;
  while (true) {
    // find the  start index of a word while skipping spaces.
    while (start && *start == ' ') {
      ++start;
    }
    if (start == nullptr || *start == '\0') {
      break;
    }
    // find the end index of the word.
    end = start + 1;
    while (end && *end != '\0' && *end != ' ') {
      ++end;
    }
    // let's reverse the word in-place.
    if (end != nullptr) {
      str_rev(start, (end - start));
    }
    start = end;
  }
}
int main() {
  string str = "Red Car";
  char *a = const_cast<char*>(str.c_str());
  cout << a << endl;
  reverse_words(a);
  cout << a << endl;
}

#include "queue.h"
#include "stack.h"
myQueue reverseK(myQueue queue, int k) {
//1.Push first k elements in queue in a stack.
//2.Pop Stack elements and enqueue them at the end of queue
//3.Dequeue queue elements till "k" and append them at the end of queue  
    if (!queue.isEmpty()) {
        myStack stack(k);
        int count = 0;
        while (count < k) {
            stack.push(queue.dequeue());
            count++;
        }
        while (!stack.isEmpty()) {
            queue.enqueue(stack.pop());
        }
        int size = queue.getSize();
        for (int i = 0; i < size - k; i++) {
            queue.enqueue(queue.dequeue());
        }
    }
    return queue;
}
int main(){
    myQueue mQ(5);
    
    mQ.enqueue(1);
    mQ.enqueue(2);
    mQ.enqueue(3);
    mQ.enqueue(4);
    mQ.enqueue(5);
    mQ=reverseK(mQ,5);
    mQ.showqueue(); //show queue prepended in the hidden code
    return 0;
}

using namespace std;
#include <iostream>
#include <queue>
#include <vector>
class TreeNode {
 public:
  int val = 0;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) {
    val = x;
    left = right = nullptr;
  }
};
class ZigzagTraversal {
 public:
  static vector<vector<int>> traverse(TreeNode *root) {
    vector<vector<int>> result;
    if (root == nullptr) {
      return result;
    }
    queue<TreeNode *> queue;
    queue.push(root);
    bool leftToRight = true;
    while (!queue.empty()) {
      int levelSize = queue.size();
      vector<int> currentLevel(levelSize);
      for (int i = 0; i < levelSize; i++) {
        TreeNode *currentNode = queue.front();
        queue.pop();
        // add the node to the current level based on the traverse direction
        if (leftToRight) {
          currentLevel[i] = currentNode->val;
        } else {
          currentLevel[levelSize - 1 - i] = currentNode->val;
        }
        // insert the children of current node in the queue
        if (currentNode->left != nullptr) {
          queue.push(currentNode->left);
        }
        if (currentNode->right != nullptr) {
          queue.push(currentNode->right);
        }
      }
      result.push_back(currentLevel);
      // reverse the traversal direction
      leftToRight = !leftToRight;
    }
    return result;
  }
};
int main(int argc, char *argv[]) {
  TreeNode *root = new TreeNode(12);
  root->left = new TreeNode(7);
  root->right = new TreeNode(1);
  root->left->left = new TreeNode(9);
  root->right->left = new TreeNode(10);
  root->right->right = new TreeNode(5);
  root->right->left->left = new TreeNode(20);
  root->right->left->right = new TreeNode(17);
  vector<vector<int>> result = ZigzagTraversal::traverse(root);
  cout << "Zigzag traversal: ";
  for (auto vec : result) {
    for (auto num : vec) {
      cout << num << " ";
    }
  }
}

#include "Graph.h"
using namespace std;
bool checkCycle(Graph g,int vertex, bool* visited, int parent)
{
    // Mark the current vertex as visited
    visited[vertex] = true;
    // Recursive calls for all the vertices adjacent to this vertex
    Node* temp =(g.getArray())[vertex].getHead();
    while (temp != NULL) {
        // If an adjacent is not visited, then make recursive call on the adjacent
        if (!visited[temp->data]) {
            if(checkCycle(g,temp->data,visited,vertex))
                return true;
        }
        else if (temp->data != parent)
            return true;
        //^ If an adjacent is visited and not parent of current
        // vertex, then there is a cycle.
        temp = temp->nextElement;
    }
    return false;
}
bool isTree(Graph g)
{
    bool *visited = new bool[g.getVertices()];
    for (int i = 0; i < g.getVertices(); i++)
        visited[i] = false;
    if (checkCycle(g,0, visited, -1))
        return false;
    for (int i = 0; i < g.getVertices(); i++) {
        if (!visited[i])
            return false;
    }
    delete[] visited;
    visited = NULL;
    return true;
}
int main() {
    Graph g(5);
    g.addEdge(1,0);
    g.addEdge(0,2);
    g.addEdge(0,3);
    g.addEdge(3,4);
    Graph g2(5);
    g2.addEdge(1, 0);
    g2.addEdge(0, 2);
    g2.addEdge(2, 1);
    g2.addEdge(0, 3);
    g2.addEdge(3, 4);
    cout << isTree(g) << endl;
    cout << isTree(g2) << endl;
}

#include "Trie.h"
bool isFormationPossible(vector<string> list,string word){
  //Create Trie and insert vector elements in it
  Trie * trie = new Trie();
  
  for(int x = 0; x < list.size(); x++){
    trie->insertNode(list[x]);
  }
  
  TrieNode * currentNode = trie->getRoot(); 
  for (int i=0; i<word.size(); i++){
     char index  = trie->getIndex(word[i]);
    // if the prefix of word does not exist, word would not either
    if (currentNode->children[index] == NULL){
      return false;
    }
    // if the substring of the word exists as a word in trie, check whether rest of the word also exists, if it does return true
    else if (currentNode->children[index]->isEndWord == true && trie->searchNode(word.substr(i+1))){
      return true;
    }
    currentNode = currentNode->children[index];
  }
  return false;
}
int main() {
  vector<string> keys = {"he", "hello", "loworld"};
  if(isFormationPossible(keys, "helloworld"))
    cout << "true\n";
  else
    cout << "false\n";
  
  return 0;
}

#include <bits/stdc++.h> 
using namespace std; 
// Method to shuffle 2*n sized array's elements
void shuffleArrayRecursive(int left, int right, int arr[]) { 
	// Base case: return if 2 elements, no shuffle needed
	if (right - left == 1) 
		return; 
	// get middle index of whole array
	int middle = (left + right) / 2; 
  
	// get second half of first array 
	int mmiddle = (left + middle) / 2; 
	// get first half of second array 
	int temp = middle + 1; 
	// swapping elements for subarray
	for (int i = mmiddle + 1; i <= middle; i++) 
		swap(arr[i], arr[temp++]); 
	// Pass divided first and second half to the 
  // recursive routine
	shuffleArrayRecursive(left, middle, arr); 
	shuffleArrayRecursive(middle + 1, right, arr); 
} 
void shuffler(int a[], int n){
	shuffleArrayRecursive(0, n-1, a);
}
int main() { 
	int a[] = { 1, 3, 5, 7, 2, 4, 6, 8 }; 
	int n = sizeof(a) / sizeof(a[0]); 
	shuffler(a, n); 
  
	for (int i = 0; i < n; i++) 
		cout << a[i] << " "; 
  
	return 0; 
} 

#include <iostream>
using namespace std; 
// returns minimum of two numbers
int min2(int a, int b){
  return a < b ? a : b;
}
/* 
   Utility method, called recursively to collect
   coins from `l` to `r` using the height array
   assuming that h height has already been collected
*/
int minimumStepsUtil(int l, int r, int h, int height[]) { 
	// base condition: all coins already collected 
	if (l >= r) 
		return 0; 
	// find minimum height index
	int m = l; 
	for (int i = l; i < r; i++) 
		if (height[i] < height[m]) 
			m = i; 
	/* 
    Calculate min steps by: 
		a) collecting all vertical line coins 
       (total r - l) 
		b) collecting all lower horizontal line coins
       recursively on left and right segments 
  */
	return min2(r - l, 
			minimumStepsUtil(l, m, height[m], height) + 
			minimumStepsUtil(m + 1, r, height[m], height) + 
			height[m] - h); 
} 
/*
    calls the recursive utility function
    and returns the minimum number of steps
    using height array
*/
int minimumSteps(int height[], int N) { 
	return minimumStepsUtil(0, N, 0, height); 
} 
// Testing minimumSteps() method
int main() { 
	int height[] = { 2, 1, 2, 5, 1 }; 
	int N = sizeof(height) / sizeof(int); 
	cout << minimumSteps(height, N) << endl; 
	return 0; 
}

#include <iostream>
#include <string>
using namespace std; 
int totalVowels(string text, int len, int index) 
{ 
  //Write your code here
  int count=0;
  if (len==0){return 0;}
  char single=toupper(text[index]);
  if(single=='A' || single=='E' || single=='I' || single=='O' || single=='U')  
  {  
    count++;
  }
    return count + totalVowels(text,len-1,index+1);
} 
//Function to test your code
int main(){
  cout<<"The string is: Hello World"<<endl;
  cout<<"The total number of vowels in this string are: "<<totalVowels("Hello World",10,0)<<endl;
  cout<<"The string is: STR"<<endl;
  cout<<"The total number of vowels in this string are: "<<totalVowels("STR",3,0)<<endl;
  cout<<"The string is: AEIOUaeiouSs"<<endl;
  cout<<"The total number of vowels in this string are: "<<totalVowels("AEIOUaeiouSs",12,0)<<endl;
}

using namespace std;
#include <iostream>
#include <vector>
class Staircase {
public:
  int CountWays(int n) {
    vector<int> dp(n + 1, 0);
    return CountWaysRecursive(dp, n);
  }
  int CountWaysRecursive(vector<int> &dp, int n) {
    if (n == 0) {
      return 1; // base case, we don't need to take any step, so there is only one way
    }
    if (n == 1) {
      return 1; // we can take one step to reach the end, and that is the only way
    }
    if (n == 2) {
      return 2; // we can take one step twice or jump two steps to reach at the top
    }
    if (dp[n] == 0) {
      // if we take 1 step, we are left with 'n-1' steps;
      int take1Step = CountWaysRecursive(dp, n - 1);
      // similarly, if we took 2 steps, we are left with 'n-2' steps;
      int take2Step = CountWaysRecursive(dp, n - 2);
      // if we took 3 steps, we are left with 'n-3' steps;
      int take3Step = CountWaysRecursive(dp, n - 3);
      dp[n] = take1Step + take2Step + take3Step;
    }
    return dp[n];
  }
};
int main(int argc, char *argv[]) {
  Staircase *sc = new Staircase();
  cout << sc->CountWays(3) << endl;
  cout << sc->CountWays(4) << endl;
  cout << sc->CountWays(5) << endl;
  delete sc;
}

using namespace std;
#include <iostream>
int find_max_sum_sub_array(int A[], int n) {
  if (n < 1) {
    return 0;
  }
  
  int curr_max = A[0];
  int global_max = A[0];
  for (int i = 1; i < n; ++i) {
    if (curr_max < 0) {
      curr_max = A[i];
    } else {
      curr_max += A[i];
    }
    if (global_max < curr_max) {
      global_max = curr_max;
    }
  }
  return global_max;
}
int main() {
    
    int v[] = {-4, 2, -5, 1, 2, 3, 6, -5, 1};
    cout << "Sum of largest subarray: " << find_max_sum_sub_array(v, sizeof(v) / sizeof(v[0])) << endl;
    return 0;
  }