C++ Programming

Problem 1 (Given a string, find the length of the longest substring in it with no more than K distinct characters.)

Code (C++)

 

using namespace std;

 

#include <iostream>

#include <string>

#include <unordered_map>

 

class LongestSubstringKDistinct {

public:

  static int findLength(const string &str, int k) {

    int windowStart = 0, maxLength = 0;

    unordered_map<char, int> charFrequencyMap;

    // in the following loop we'll try to extend the range [windowStart, windowEnd]

    for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {

      char rightChar = str[windowEnd];

      charFrequencyMap[rightChar]++;

      // shrink the sliding window, until we are left with 'k' distinct characters in the frequency

      // map

      while ((int)charFrequencyMap.size() > k) {

        char leftChar = str[windowStart];

        charFrequencyMap[leftChar]--;

        if (charFrequencyMap[leftChar] == 0) {

          charFrequencyMap.erase(leftChar);

        }

        windowStart++; // shrink the window

      }

      maxLength = max(maxLength, windowEnd - windowStart + 1); // remember the maximum length so far

    }

 

    return maxLength;

  }

};

 

int main(int argc, char *argv[]) {

  cout << "Length of the longest substring: " << LongestSubstringKDistinct::findLength("araaci", 2)

       << endl;

  cout << "Length of the longest substring: " << LongestSubstringKDistinct::findLength("araaci", 1)

       << endl;

  cout << "Length of the longest substring: " << LongestSubstringKDistinct::findLength("cbbebi", 3)

       << endl;

}

Problem 2

Given an array of characters where each character represents a fruit tree, you are given two baskets and your goal is to put maximum number of fruits in each basket. The only restriction is that each basket can have only one type of fruit.

Here is what our algorithm will look like

 

using namespace std;

 

#include <iostream>

#include <unordered_map>

#include <vector>

 

class MaxFruitCountOf2Types {

 public:

  static int findLength(const vector<char>& arr) {

    int windowStart = 0, maxLength = 0;

    unordered_map<char, int> fruitFrequencyMap;

    // try to extend the range [windowStart, windowEnd]

    for (int windowEnd = 0; windowEnd < arr.size(); windowEnd++) {

      fruitFrequencyMap[arr[windowEnd]]++;

      // shrink the sliding window, until we are left with '2' fruits in the frequency map

      while ((int)fruitFrequencyMap.size() > 2) {

        fruitFrequencyMap[arr[windowStart]]--;

        if (fruitFrequencyMap[arr[windowStart]] == 0) {

          fruitFrequencyMap.erase(arr[windowStart]);

        }

        windowStart++;  // shrink the window

      }

      maxLength = max(maxLength, windowEnd - windowStart + 1);

    }

 

    return maxLength;

  }

};

 

int main(int argc, char* argv[]) {

  cout << "Maximum number of fruits: "

       << MaxFruitCountOf2Types::findLength(vector<char>{'A', 'B', 'C', 'A', 'C'}) << endl;

  cout << "Maximum number of fruits: "

       << MaxFruitCountOf2Types::findLength(vector<char>{'A', 'B', 'C', 'B', 'B', 'C'}) << endl;

}

 

Problem 3 :

Cyclic Sort (easy)

Problem Statement 

We are given an array containing ‘n’ objects. Each object, when created, was assigned a unique number from 1 to ‘n’ based on their creation sequence. This means that the object with sequence number ‘3’ was created just before the object with sequence number ‘4’. (Concept)

C++ Code 

using namespace std;

 

#include <iostream>

#include <vector>

 

class CyclicSort {

 public:

  static void sort(vector<int> &nums) {

    int i = 0;

    while (i < nums.size()) {

      int j = nums[i] - 1;

      if (nums[i] != nums[j]) {

        swap(nums, i, j);

      } else {

        i++;

      }

    }

  }

 

 private:

  static void swap(vector<int> &arr, int i, int j) {

    int temp = arr[i];

    arr[i] = arr[j];

    arr[j] = temp;

  }

};

 

int main(int argc, char *argv[]) {

  vector<int> arr = {3, 1, 5, 4, 2};

  CyclicSort::sort(arr);

  for (auto num : arr) {

    cout << num << " ";

  }

  cout << endl;

 

  arr = vector<int>{2, 6, 4, 3, 1, 5};

  CyclicSort::sort(arr);

  for (auto num : arr) {

    cout << num << " ";

  }

  cout << endl;

 

  arr = vector<int>{1, 5, 6, 4, 3, 2};

  CyclicSort::sort(arr);

  for (auto num : arr) {

    cout << num << " ";

  }

  cout << endl;

}

 Some Basic Interview Questions on C++ (Part I)

Q1.What is the main difference between the keyword struct and class?

Ans : The keyword struct is used for resembling public members by default, while the keyword class is used for resembling private members by default

Q2. Can we have a String primitive data type in C++?

Ans: No, we cannot have a String primitive data type in C++. Instead we can have a class from the Standard Template Library(STL)

Q3. Define Block Scope Variable?

Ans: A Block scope variable is the one that is specified as a block using the C++ that can be declared anywhere within the block.

Q4. Can we use access specifiers to achieve data hiding in C++?

Ans: Yes, we can use access specifiers to achieve data hiding in C++. These include Private and Protected

Q5.What is wrong with this code?

T *p=new T[10];

delete p;

Ans: The above code is syntactically correct and will compile fine.

The only problem is that it will just delete first element of the array.

Though the entire array is deleted, only the destructor of the first element will be called and the memory for the for the first element is released.

Q6. What do you mean by ‘void’ return type?

Ans: All functions should return a value as per the general syntax.

However, in case, if we don’t want a function to return any value, we use “void” to indicate that. This means that we use “void” to indicate that the function has no return value or it return “void”