Q1.

Print K largest(or smallest) elements in an array

Given an array arr[] of size N, the task is to printing K largest elements in an array

#include <iostream>
#include <algorithm>
using namespace std;

void printKLargest(int arr[], int n, int k) {

sort(arr, arr + n, greater<int>());
for (int i = 0; i < k; i++) {
cout << arr[i] << " ";
}
}

int main() {
int arr[] = {1, 23, 12, 9, 30, 2, 50};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
printKLargest(arr, n, k);
return 0;
}

Q2. Check Equal Arrays

Given two arrays arr1 and arr2 of equal size, the task is to find whether the given arrays are
equal. Two arrays are said to be equal if both contain the same set of elements,
arrangements (or permutations) of elements may be different though. Note: If there are
repetitions, then counts of repeated elements must also be the same for two arrays to be
equal.

#include <iostream>
#include <unordered_map>
using namespace std;

bool checkEqualArrays(int arr1[], int arr2[], int n) {

unordered_map<int, int> countMap;
for (int i = 0; i < n; i++) {
countMap[arr1[i]]++;
}
for (int i = 0; i < n; i++) {
countMap[arr2[i]]--;
}
for (auto it : countMap) {
if (it.second != 0) {
return false;
}
}
 return true;
}

int main() {
int arr1[] = {1, 2, 5, 4, 0};
int arr2[] = {2, 4, 5, 0, 1};
int n = sizeof(arr1) / sizeof(arr1[0]);
if (checkEqualArrays(arr1, arr2, n)) {
cout << "Arrays are equal";
} else {
cout << "Arrays are not equal";
}
return 0;
}

ALTERNATE SOLUTION

#include <iostream>
#include <algorithm>
using namespace std;

bool checkEqualArrays(int arr1[], int arr2[], int n) {

sort(arr1, arr1 + n);
sort(arr2, arr2 + n);
for (int i = 0; i < n; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}

int main() {
int arr1[] = {1, 2, 5, 4, 0};
int arr2[] = {2, 4, 5, 0, 1};
int n = sizeof(arr1) / sizeof(arr1[0]);
if (checkEqualArrays(arr1, arr2, n)) {
cout << "Arrays are equal";
} else {
cout << "Arrays are not equal";
}
return 0;
}
Q3..Missing In Array
Given an array arr of size n 1 − that contains distinct integers in the range of 1 to n
(inclusive), find the missing element. The array is a permutation of size n with one element
missing. Return the missing element.

#include <iostream>
using namespace std;

int findMissing(int arr[], int n) {

int total = n * (n + 1) / 2;
int sum = 0;
for (int i = 0; i < n - 1; i++) {
sum += arr[i];
}
return total - sum;
}

int main() {
int arr[] = {1, 2, 4, 5, 6};
int n = 6;
cout << "Missing number is: " << findMissing(arr, n);
return 0;
}

Q4. Count Inversions

Given an array of integers. Find the Inversion Count in the array. Two array elements arr[i]
and arr[j] form an inversion if arr[i] > arr[j] and i < j. Inversion Count: For an array, inversion
count indicates how far (or close) the array is from being sorted. If the array is already sorted
then the inversion count is 0. If an array is sorted in the reverse order then the inversion
count is the maximum.

class Solution {
public:
long long merge(long long arr[], int st, int mid, int end) {
long long cnt = 0;
vector<long long> temp;
int l = st, r = mid + 1;

while (l <= mid && r <= end) {

if (arr[l] <= arr[r]) {
temp.push_back(arr[l++]);
} else {
temp.push_back(arr[r++]);
cnt += (mid - l + 1);
}
}
 while (l <= mid) {
temp.push_back(arr[l++]);
}

while (r <= end) {

temp.push_back(arr[r++]);
}

for (int i = st; i <= end; i++) {

arr[i] = temp[i - st];
}

return cnt;
}

long long mergesort(long long arr[], int st, int end) {

long long cnt = 0;
if (st >= end) return cnt;

int mid = (st + end) / 2;

cnt += mergesort(arr, st, mid);
cnt += mergesort(arr, mid + 1, end);
cnt += merge(arr, st, mid, end);

return cnt;
}

long long int inversionCount(long long arr[], int n) {

return mergesort(arr, 0, n - 1);
}
};

int main() {
Solution sol;
long long arr[] = {2, 4, 1, 3, 5};
int n = sizeof(arr) / sizeof(arr[0]);
cout << sol.inversionCount(arr, n);
return 0;
}

Q5.Merge Two Sorted Array

#include <iostream>
#include <vector>
using namespace std;
vector<int> mergeSortedArrays(int arr1[], int n1, int arr2[], int n2) {
vector<int> merged;
int i = 0, j = 0;

while (i < n1 && j < n2) {

if (arr1[i] <= arr2[j]) {
merged.push_back(arr1[i++]);
} else {
merged.push_back(arr2[j++]);
}
}

while (i < n1) {

merged.push_back(arr1[i++]);
}

while (j < n2) {

merged.push_back(arr2[j++]);
}

return merged;
}

int main() {
int arr1[] = {1, 3, 5, 7};
int arr2[] = {2, 4, 6, 8};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int n2 = sizeof(arr2) / sizeof(arr2[0]);

vector<int> result = mergeSortedArrays(arr1, n1, arr2, n2);

for (int val : result) {

cout << val << " ";
}

return 0;
}

Q6.Equilibrium Index/Point
Given an array arr of non-negative numbers. The task is to find the first equilibrium point in
an array. The equilibrium point in an array is an index (or position) such that the sum of all
elements before that index is the same as the sum of elements after it. Note: Return
equilibrium point in 1-based indexing. Return -1 if no such point exists

#include <iostream>
using namespace std;

int equilibriumPoint(int arr[], int n) {

long long totalSum = 0, leftSum = 0;
for (int i = 0; i < n; i++) totalSum += arr[i];

for (int i = 0; i < n; i++) {

totalSum -= arr[i];
if (leftSum == totalSum) return i + 1;
leftSum += arr[i];
}
return -1;
}

int main() {
int arr[] = {1, 3, 5, 2, 2};
int n = sizeof(arr) / sizeof(arr[0]);
cout << equilibriumPoint(arr, n);
return 0;
}

Q7..Median of 2 Sorted Arrays of Different Sizes

Given two sorted arrays array1 and array2 of size m and n respectively. Find the median of
the two sorted arrays.

class Solution {
public:
double MedianOfArrays(vector<int>& array1, vector<int>& array2) {
vector<int> mergedArray;
int i = 0, j = 0;

while (i < array1.size() && j < array2.size()) {

if (array1[i] < array2[j]) {
mergedArray.push_back(array1[i++]);
} else {
mergedArray.push_back(array2[j++]);
}
}

while (i < array1.size()) {

mergedArray.push_back(array1[i++]);
}

while (j < array2.size()) {

mergedArray.push_back(array2[j++]);
}
 int totalSize = mergedArray.size();

if (totalSize % 2 == 0) {
return (mergedArray[totalSize / 2 - 1] + mergedArray[totalSize / 2]) / 2.0;
} else {
return mergedArray[totalSize / 2];
}
}
};

ALTERNATE SOLUTION

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

class Solution {
public:
double MedianOfArrays(vector<int>& arr1, vector<int>& arr2) {
if (arr1.size() > arr2.size())
return MedianOfArrays(arr2, arr1);

int m = arr1.size();
int n = arr2.size();
int low = 0, high = m;

while (low <= high) {

int partitionX = (low + high) / 2;
int partitionY = (m + n + 1) / 2 - partitionX;

int maxLeftX = (partitionX == 0) ? INT_MIN : arr1[partitionX - 1];

int minRightX = (partitionX == m) ? INT_MAX : arr1[partitionX];

int maxLeftY = (partitionY == 0) ? INT_MIN : arr2[partitionY - 1];

int minRightY = (partitionY == n) ? INT_MAX : arr2[partitionY];

if (maxLeftX <= minRightY && maxLeftY <= minRightX) {

if ((m + n) % 2 == 0) {
return (double)(max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2;
} else {
return (double)max(maxLeftX, maxLeftY);
}
} else if (maxLeftX > minRightY) {
high = partitionX - 1;
} else {
low = partitionX + 1;
 }
}

return -1; // If inputs are invalid

}
};

int main() {
Solution sol;
vector<int> arr1 = {1, 3, 8, 9, 15};
vector<int> arr2 = {7, 11, 18, 19, 21, 25};
cout << sol.MedianOfArrays(arr1, arr2);
return 0;
}

Q8.Insert Node in bst

Given a BST and a key k. If k is not present in the BST, Insert a new Node with a value equal
to k into the BST. If k is already present in the BST, don't modify the BST. Return the root of
the modified BST after inserting k.

class Solution {
public:
void find(Node* root, int data, bool &pres) {
if (root == NULL) return;
if (root->data == data) {
pres = true;
return;
}
if (root->data > data) find(root->left, data, pres);
else find(root->right, data, pres);
}

Node* solve(Node* node, int data) {

if (node == NULL) {
return new Node(data);
}
if (node->data > data) node->left = solve(node->left, data);
else node->right = solve(node->right, data);
return node;
}

Node* insert(Node* node, int data) {

bool pres = false;
find(node, data, pres);
if (pres) return node;
return solve(node, data);
 }
};

Q9.Triangle Path Sum

Given a triangle array, return the minimum path sum to reach from top to bottom. For each
step, you may move to an adjacent number of the row below. More formally, if you are on
index i on the current row, you may move to either index i or index i + 1 on the next row.

class Solution {
public:
int minPath(int i, int j, int n, vector<vector<int>>& tri, vector<vector<int>>& dp) {
if (i == n - 1)
return tri[i][j];
if (dp[i][j] != -1)
return dp[i][j];

dp[i][j] = tri[i][j] + min(minPath(i + 1, j, n, tri, dp), minPath(i + 1, j + 1, n, tri, dp));

return dp[i][j];
}

int minimizeSum(int n, vector<vector<int>>& triangle) {

vector<vector<int>> dp(n, vector<int>(n, -1));
return minPath(0, 0, n, triangle, dp);
}
};

Q10.Coin Change
Given an integer array coins[ ] of size N representing different denominations of currency
and an integer sum, find the number of ways you can make sum by using different
combinations from coins[ ]. Note: Assume that you have an infinite supply of each type of
coin. And you can use any coin as many times as you want.

class Solution {
public:
long long int count(int coins[], int N, int sum) {
vector<vector<long long>> memo(N + 1, vector<long long>(sum + 1, -1));
return helper(coins, N, sum, memo);
}

long long helper(int coins[], int N, int sum, vector<vector<long long>>& memo) {
if (sum == 0) return 1;
if (N == 0) return 0;

if (memo[N][sum] != -1) return memo[N][sum];

 if (coins[N - 1] <= sum) {
memo[N][sum] = helper(coins, N, sum - coins[N - 1], memo) + helper(coins, N - 1,
sum, memo);
} else {
memo[N][sum] = helper(coins, N - 1, sum, memo);
}

return memo[N][sum];
}
};

Q11.Binary Search
Given a sorted array arr and an integer k, find the position(0-based indexing) at which k is
present in the array using binary search.

#include <iostream>
using namespace std;

int binarySearch(int arr[], int n, int k) {

int low = 0, high = n - 1;

while (low <= high) {

int mid = low + (high - low) / 2;

if (arr[mid] == k)
return mid;
else if (arr[mid] < k)
low = mid + 1;
else
high = mid - 1;
}

return -1;
}

int main() {
int arr[] = {1, 3, 5, 7, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 7;

int pos = binarySearch(arr, n, k);

cout << pos; // Output: 3
return 0;
}
Q12.Floyd Warshall
The problem is to find the shortest distances between every pair of vertices in a given
edge-weighted directed graph. The graph is represented as an adjacency matrix of size n*n.
Matrix[i][j] denotes the weight of the edge from i to j. If Matrix[i][j]=-1, it means there is no
edge from i to j. Note : Modify the distances for every pair in-place

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
void shortest_distance(vector<vector<int>>& matrix) {
int n = matrix.size();

for (int i = 0; i < n; i++) {

matrix[i][i] = 0;
for (int j = 0; j < n; j++) {
if (matrix[i][j] == -1)
matrix[i][j] = 1e9;
}
}

for (int k = 0; k < n; k++) {

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][k] != 1e9 && matrix[k][j] != 1e9)
matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]);
}
}
}

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {
if (matrix[i][j] == 1e9)
matrix[i][j] = -1;
}
}
}
};

int main() {
vector<vector<int>> graph = {
{0, 3, -1, 7},
{8, 0, 2, -1},
{5, -1, 0, 1},
 {2, -1, -1, 0}
};

Solution sol;
sol.shortest_distance(graph);

for (const auto& row : graph) {

for (int dist : row) {
if (dist == -1)
cout << "INF ";
else
cout << dist << " ";
}
cout << "\n";
}

return 0;
}

Q13.Smallest subarray with sum greater than x

Given a number x and an array of integers arr, find the smallest subarray with sum greater
than the given value. If such a subarray does not exist, return 0 in that case.

class Solution {
public:
int smallestSubWithSum(int x, vector<int>& arr) {
int sum = 0, i = 0;
int n = arr.size();
int mini = INT_MAX;

for (int j = 0; j < n; j++) {

sum += arr[j];

while (sum > x) {

mini = min(mini, j - i + 1);
sum -= arr[i++];
}
}

return (mini == INT_MAX) ? 0 : mini;

}
};
Q14.Ticket Encoding Sequence
You are working at a ticketing company that generates unique ticket codes for various
events. You have given a number N and your task is to print the Nth ticket code. The ticket
codes are generated based on a specific encoding sequence. The encoding sequence
follows the recursive formula as described below:

The ticket code for the first ticket (ticket #1) is "A."
Now, to generate rth ticket you have to take an r-1 th ticket and create a new encoding by
writing down the frequency followed by a digit.
for example Ticket#(r-1) = "1121A" (Two 1, One 2, One 1, One A) so Ticket#(r) = "2112111A"

#include <iostream>
#include <string>

using namespace std;

string generateTicketCode(int N) {
string ticketCode = "A";

for (int i = 2; i <= N; i++) {

string newTicketCode = "";
char currentChar = ticketCode[0];
int charCount = 0;

for (int j = 0; j < ticketCode.length(); j++) {

if (ticketCode[j] == currentChar) {
charCount++;
} else {
newTicketCode += to_string(charCount) + currentChar;
currentChar = ticketCode[j];
charCount = 1;
}
}

newTicketCode += to_string(charCount) + currentChar;

ticketCode = newTicketCode;
}

return ticketCode;
}

int main() {
int N = 4;
string ticketCode = generateTicketCode(N);
cout << ticketCode << endl;
return 0;
}
Q15.Program to check valid mobile number

Mobile Number validation criteria:

The first digit should contain numbers between 6 to 9.
The remaining 9 digits can contain any number between 0 to 9.
The mobile number can have 11 digits also by including 0 at the starting.
The mobile number can be of 12 digits also by including 91 at the starting
The number which satisfies the above criteria is a valid mobile Number.

#include <iostream>
#include <string>
using namespace std;

bool isValidMobileNumber(const string& num) {

int len = num.length();
string mobile = num;

if (len == 12 && num.substr(0, 2) == "91") {

mobile = num.substr(2);
} else if (len == 11 && num[0] == '0') {
mobile = num.substr(1);
}

if (mobile.length() != 10) return false;

if (mobile[0] < '6' || mobile[0] > '9') return false;

for (int i = 1; i < 10; i++) {

if (mobile[i] < '0' || mobile[i] > '9') return false;
}

return true;
}

int main() {
string number;
cin >> number;

if (isValidMobileNumber(number)) {
cout << "Valid mobile number\n";
} else {
cout << "Invalid mobile number\n";
}

return 0;
}
Q16.Bus Routes

You are given an array routes representing bus routes where routes[i] is a bus route that the
ith bus repeats forever.

For example, if routes[0] = [1, 5, 7], this means that the 0th bus travels in the sequence 1 ->
5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... forever.

You will start at the bus stop source (You are not on any bus initially), and you want to go to
the bus stop target. You can travel between bus stops by buses only.

Return the least number of buses you must take to travel from source to target. Return -1 if it
is not possible.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;

int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {

unordered_map<int, vector<int>> to_routes;
for (int i = 0; i < routes.size(); ++i)
for (int j : routes[i])
to_routes[j].push_back(i);

queue<pair<int, int>> bfs;

bfs.push({S, 0});
unordered_set<int> seen = {S};

while (!bfs.empty()) {
int stop = bfs.front().first, bus = bfs.front().second;
bfs.pop();

if (stop == T)
return bus;

for (int i : to_routes[stop]) {

for (int j : routes[i]) {
if (seen.find(j) == seen.end()) {
seen.insert(j);
bfs.push({j, bus + 1});
}
}
routes[i].clear(); // Avoid re-processing this route
}
 }
return -1;
}

int main() {
vector<vector<int>> routes = {
{1, 2, 7},
{3, 6, 7}
};
int source = 1, target = 6;

int result = numBusesToDestination(routes, source, target);

cout << result << endl; // Output: 2

return 0;
}

Q17.Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all
unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int>> ans;
vector<int> ds;
findCombination(0, target, candidates, ans, ds);
return ans;
}

void findCombination(int ind, int target, vector<int>& arr, vector<vector<int>>& ans,

vector<int>& ds) {
if (target == 0) {
ans.push_back(ds);
return;
}
for (int i = ind; i < arr.size(); i++) {
 if (i > ind && arr[i] == arr[i - 1]) continue;
if (arr[i] > target) break;
ds.push_back(arr[i]);
findCombination(i + 1, target - arr[i], arr, ans, ds);
ds.pop_back();
}
}
};

int main() {
vector<int> candidates = {10, 1, 2, 7, 6, 1, 5};
int target = 8;

Solution sol;
vector<vector<int>> result = sol.combinationSum2(candidates, target);

for (auto &combination : result) {

for (int num : combination) {
cout << num << " ";
}
cout << "\n";
}

return 0;
}

Q18.Largest Rectangle in Histogram

Given an array of integers heights representing the histogram's bar height where the width of
each bar is 1, return the area of the largest rectangle in the histogram.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> st;
int area = 0, n = heights.size();

for (int i = 0; i < n; i++) {

while (!st.empty() && heights[i] < heights[st.top()]) {
int bar = st.top(); st.pop();
int pse = st.empty() ? -1 : st.top();
 int nse = i;
area = max(area, heights[bar] * (nse - pse - 1));
}
st.push(i);
}

while (!st.empty()) {
int bar = st.top(); st.pop();
int pse = st.empty() ? -1 : st.top();
int nse = n;
area = max(area, heights[bar] * (nse - pse - 1));
}

return area;
}
};

int main() {
Solution sol;
vector<int> histogram = {2, 1, 5, 6, 2, 3};
cout << sol.largestRectangleArea(histogram) << endl; // Output should be 10
return 0;
}

Q19.Mailing list
Given a list of email ids, determine the validity of each of them without using regex or built-in
email parsers.Refer the sample input and output to understand the main rules of validation to
be used in this problem.
INPUT- The first line of input contains a positive integer N representing the number of email
ids. The next N lines of input contain strings representing email ids.

#include <iostream>
#include <string>
using namespace std;

bool isValidEmail(const string& email) {

int atPos = -1;
int dotPos = -1;
int n = email.size();

// Rule 1: Cannot have spaces and must not start or end with '@' or '.'
if (email.empty() || email.front() == '@' || email.back() == '@' ||
email.front() == '.' || email.back() == '.') return false;

// Rule 2: Must contain exactly one '@'

int atCount = 0;
 for (int i = 0; i < n; ++i) {
char ch = email[i];

if (ch == ' ') return false; // no spaces allowed

if (ch == '@') {
atCount++;
atPos = i;
}
}

if (atCount != 1) return false;

// Rule 3: There must be a '.' after '@'

dotPos = -1;
for (int i = atPos + 1; i < n; ++i) {
if (email[i] == '.') {
dotPos = i;
break;
}
}

if (dotPos == -1 || dotPos == atPos + 1 || dotPos == n - 1) return false;

// Rule 4: No empty local part or domain part

string local = email.substr(0, atPos);
string domain = email.substr(atPos + 1);

if (local.empty() || domain.empty()) return false;

return true;
}

int main() {
int N;
cin >> N;
cin.ignore(); // to clear the newline after N

for (int i = 0; i < N; ++i) {

string email;
getline(cin, email);

if (isValidEmail(email))
cout << "Valid" << endl;
else
cout << "Invalid" << endl;
}
 return 0;
}