Problem Solving + CP + Algorithm
Striver Must Try Interview Sheet
Leet Code Excel Sheet by Me
1. Suppose you have an array with 11 digits. Five numbers each appear exactly twice, and one number appears only once. How can you find the single number without using any extra array or map, and with a time complexity of O(n)?
function singleNumber(nums) {
let result = 0;
for (let i = 0; i < nums.length; i++) {
result ^= nums[i]; //bitwise XOR operation
}
return result;
}
389. Find the Difference: You are given two strings s and t. String t is generated by random shuffling string s and then add one more letter at a random position. Return the letter that was added to t.
Brute force Approach
class Solution {
public:
char findTheDifference(string s, string t) {
if (s.size() < 1)
return t[0];
unordered_map<char,int> mapping;
for (int i = 0; i < t.size(); i++) {
mapping[t[i]]++;
}
for (int i = 0; i < s.size(); i++) {
mapping[s[i]]--;
}
for (auto it : mapping) {
if (it.second != 0) {
return it.first;
}
}
return 'a';
}
};Optimal Approach
class Solution {
public:
char findTheDifference(string s, string t) {
s += t;
int ans = 0;
for(auto it : s ){
ans ^= it;
}
return ans;
}
};2. Reverse the array without any additional array! (Two Pointer Approach)
int array[] = {1, 2, 3, 4, 5, 6, 7};
int start = 0;
int end = 6;
while (start < end){ // (Two Pointer Approach )
int temp = array[start];
array[start] = array[end];
array[end] = temp;
start++;
end--;
}
for(auto it : array){
cout << it << sp;
}3. Given a number. Find the sum of the digits of the number ?
int number = 123456;
int count = 0;
while (number > 0)
{
int digit = number % 10;
count += digit;
number = number / 10;
}
cout << count << endl;4. Merge these two sorted arrays using one loop?
#include <bits/stdc++.h>
using namespace std;
int main() {
int arr1[] = {0, 1, 2, 3, 4};
int arr2[] = {3, 4, 6, 7, 9};
int arr1Size = sizeof(arr1) / sizeof(arr1[0]);
int arr2Size = sizeof(arr2) / sizeof(arr2[0]);
int arr1Pointer = 0;
int arr2Pointer = 0;
vector<int>mergedArray;
// Mergin Two Array with Comparison
while(arr1Pointer < arr1Size && arr2Pointer < arr2Size){
if(arr1[arr1Pointer] > arr2[arr2Pointer]){
mergedArray.push_back(arr2[arr2Pointer]);
arr2Pointer++;
}
else{
mergedArray.push_back(arr1[arr1Pointer]);
arr1Pointer++;
}
}
// Add Leftover array 1 values
for(int i = arr1Pointer ; i < arr1Size; i++){
mergedArray.push_back(arr1[i]);
}
// Add Leftover array 2 values
for(int i = arr2Pointer; i < arr2Size; i++){
mergedArray.push_back(arr2[i]);
}
// Printing New Merged Array
for(auto index : mergedArray){
cout << index << " ";
}
}5. Find out which is the last /previous palindrome number of a given number. (Example: 20 is given, so 11 is the palindrome number) [Reverse a Number]
bool checkPalindrome(int n)
{
int reverse = 0;
int temp = n;
while (temp != 0)
{
reverse = (reverse * 10) + (temp % 10);
temp = temp / 10;
}
return (reverse == n);
}
void solve()
{
int n;
cin >> n;
for (int i = n; i > 0; i--)
{
int temp = i;
if (checkPalindrome(temp))
{
cout << "Last Palindrome : ";
cout << temp << endl;
break;
}
}
}6. An array of letters from a-z is given. Find out the first non-repeated letter. (like array [A, B,V,C,A,C,V,P] is given, here B is the first non-repeated letter).
int firstUniqueChar(string s) {
vector<int> count(26, 0);
for (auto it : s) {
count[it - 'a']++;
}
for (int i = 0; i < s.size(); i++) {
if (count[s[i] - 'a'] == 1)
return i;
}
return -1;
}
int main() {
string s = "abvcacvp";
char ans = firstUniqueChar(s) + 'a';
cout << ans;
}Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Example 1:
Input: nums = [1,2,3,1]
Output: trueExample 2:
Input: nums = [1,2,3,4]
Output: false class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_map<int,int> mp;
for(auto i : nums) mp[i]++;
bool flag = false;
for(auto i : mp){
if(i.second >= 2) return true;
}
return flag;
}
};8. How To Check If a Value Is A Power Of 2 Or Not ?
bool isPowerOfTwo(int number){
if(number == 0) return false;
while(number%2 == 0){
number /= 2;
}
if(number == 1) return false;
else return true;
}
int main() {
int value = 7 ;
int powerOf2 = isPowerOfTwo(value); // Best Solution : powerOf2 = n & (n - 1);
if (powerOf2 == 0)
cout << "YES" << endl;
else
cout << "NO" << endl;
}9.1. Find All Substrings of a String
class Solution {
public:
string substrings(string s) {
int size = s.size();
vector<string> substrings;
for (int i = 0; i < size; i++) {
string temp = "";
for (int j = i; j < size; j++) {
temp += s[j];
substrings.push_back(temp);
}
}
for(auto it : substrings){
cout << it << endl;
}
}
};9.2. Find Substring in a String
void solve()
{
//* Sometimes you win, sometimes you learn..." - Good Wisher
string s = "I am a student of Shahjalal University of Science and Technology";
string sub = "student";
int s_length = s.length();
int sub_length = sub.length();
bool found = false;
int index = -1;
for (int i = 0; i <= s_length - sub_length; i++)
{
bool match = true;
for (int j = 0; j < sub_length; j++)
{
if (s[i + j] != sub[j])
{
match = false;
break;
}
}
if (match)
{
found = true;
index = i;
break;
}
}
cout << index << endl; // index of first occurrence of sub in s
if (found)
cout << "Found" << endl;
else
cout << "Not Found" << endl;
}Time Complexity: O(N * M)
Best Complexity: KMP Algorithm = O(N + M)
10. How do you swap two numbers without using a third variable
int a = 2, b = 3 ;
b = b + a; // now b is sum of both the numbers b = 5
a = b - a; // b - a = (b + a) - a = b (a is swapped) a = 5 - 2 = 3
b = b - a; // (b + a) - b = a (b is swapped) b = 5 - 3 = 2
// a = 3 , b = 211. GCD of Two Numbers
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}12. A string of 9 characters will be given. There will be 3 blocks of 3 characters in the String. each character will have a numerical value. you need to find the sum of the numerical values of each block and then finally concave the answer of each block and form a string. rw-x-r-rw Here r = 4 , x = 2, w = 1, - = 0 What is the answer?
void solve()
{
//* Sometimes you win, sometimes you learn..." - Good Wisher
//string str = "910209091";
string str = "410204041";
string ans = "";
int temp = 0;
for (int i = 1; i <= str.size(); i++)
{
if (i % 3 != 0)
{
temp += str[i - 1] - '0';
}
else
{
temp += str[i - 1] - '0';
cout << temp << endl;
string blockSum = "";
// Corner Case : Sum > 9
while (temp > 0)
{
int lastDigit = temp % 10;
blockSum += lastDigit + '0';
temp = temp / 10;
}
reverse(blockSum.begin(), blockSum.end());
ans += blockSum;
temp = 0;
}
}
cout << ans << endl;
}13. Write code to Calculate frequency of characters in a string
void solve()
{ //* Sometimes you win, sometimes you learn..." - Good Wisher
string s;
map<char, int> mp;
cin >> s;
for (int i = 0; i < s.size(); i++){
mp[s[i]]++;
}
for (auto it : mp){
cout << it.first << " = " << it.second << endl;
}
}14. Write code Check if the given string is Palindrome or not
void solve()
{ //* Sometimes you win, sometimes you learn..." - Good Wisher
string s;
cin >> s;
bool palindrome = true;
int first = 0;
int last = s.length() - 1;
while (first <= last) {
if (s[first] != s[last]){
palindrome = false;
break;
}
first++;
last--;
}
cout << palindrome << endl;
}15. Find the Missing Number Between 1-N: 268. Missing Number
void solve(){
//* Sometimes you win, sometimes you learn..." - Good Wisher
int arr[] = { 1, 3, 7, 5, 6, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int total = n * (n + 1) / 2; // Sum of n natural numbers
for(int i = 0; i < n; i++)
{
total -= arr[i];
}
cout << total << endl;
}16. Write code to Check if two strings are Anagram or not : 242. Valid Anagram
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
bool isAnagram(string s, string t)
{
int countCharacter[26] = {0};
for (auto index : s){
countCharacter[index - 'a']++;
}
for (auto index : t){
countCharacter[index - 'a']--;
}
for (auto index : countCharacter){
if (index != 0){
return false;
}
}
return true;
}17. 2nd Smallest Number in an Array
void solve(){
//* Sometimes you win, sometimes you learn..." - Good Wisher
int arr[] = {111, 13, 25, 9, 34, 1};
int n = sizeof(arr) / sizeof(arr[0]);
int first = INT_MAX, second = INT_MAX;
for (int i = 0; i < n; i++){
first = min(first, arr[i]);
}
for(int i = 0; i < n; i++){
if(arr[i] != first){
second = min(second, arr[i]);
}
}
cout << "First : " << first << " Second : " << second << endl;
}18. Write code of Perfect number (Divisors of a Number)
bool checkPerfectNumber(int num) {
vector<int> divisors;
for (int i = 1; i * i <= num; i++) {
if (num % i == 0) {
if (i == num / i) {
divisors.push_back(i);
} else {
divisors.push_back(i);
divisors.push_back(num / i);
}
}
}
int sum = 0;
for (auto it : divisors) {
if(it == num) continue; // corner cae
cout << it << endl;
sum += it;
}
cout << "Sum = " <<sum <<endl;
if(sum == num)
return true;
return false;
}19. Write a code for Binary Search
int binarySearch(int arr[], int n, int target) {
int low = 0, high = n - 1;
while (low <= high){
int mid = (high + low) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return -1;void solve()
{
//* Sometimes you win, sometimes you learn..." - Good Wisher
int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int n = sizeof(arr) / sizeof(arr[0]); // Calculate the size of the array here
int target = 3;
int result = binarySearch(arr, n, target);
if (result == -1)
cout << "Element is not present in array" << endl;
else
cout << "Element is present at index " << result << endl;
}20. Find non-repeating characters in a string
void solve()
{
//* Sometimes you win, sometimes you learn..." - Good Wisher
string s = "google";
int n = s.size();
map<char, int> count;
for (int i = 0; i < n; i++)
{
count[s[i]]++;
}
for (auto it : count)
{
if (it.second == 1)
{
cout << it.first << endl;
}
}
}void solve(){
//* Sometimes you win, sometimes you learn..." - Good Wisher
int number;
cin >> number;
string s = "";
while (number > 0){
int rem = number % 26;
if (rem == 0){
s += 'Z';
number = (number / 26) - 1;
}
else{
s += (rem - 1) + 'A';
number = number / 26;
}
}
reverse(s.begin(), s.end());
cout << s << endl;
}class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> pq;
// Max heap Default : Highest Value at Top
for (int i = 0; i < nums.size(); i++) {
pq.push(nums[i]); // inserting values in priority queue(Max Heap)
// Min Heap : use '-' Sign = -nums[i]
}
int temp = 0;
while (!pq.empty()) {
temp++;
if (temp == k) {
return pq.top(); //get the top value
}
cout << pq.top() << endl;
pq.pop(); // if not remove the top value
}
return -1;
}
};Combining these two parts:
The time complexity for inserting all elements into the priority queue (building the max-heap) is
O(nlogn)The time complexity for extracting the k-th largest element is
O(klogn).
Overall Time Complexity
Therefore, the overall time complexity of the code is: O(nlogn+klogn)
In the worst case, k is proportional to n making the complexity: k=== n
O(nlogn+nlogn) = O(nlogn)
23. Find a number is a prime or not
Complexity:
Root(N)
prime = true;
notPrime = false;
if( n == 1) return notPrime;
for(int i = 2 ; i*i <= n ; i++){
if(n%i != o) return notPrime;
}
return prime;Complexity :
N*Log(Log(N)
int countPrimes(int n) {
bool prime[n+1];
for(int i = 0; i <= n; i++) prime[i] = true;
for (int p = 2; p * p <= n; p++) {
if (prime[p] == true) {
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
int cnt = 0;
for(int i = 2; i < n; i++)
{
if(prime[i] == true) cnt++;
}
return cnt;
}24. Circular rotation of an array by K positions
void solve()
{
//* Sometimes you win, sometimes you learn..." - Good Wisher
int arr[] = {1, 2, 3, 4, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
int ans[n] = {0};
int k;
cin >> k;
k = k % n; // corner case : k > n
for (int i = k; i < n; i++)
{
cout << arr[i] << sp;
}
for (int i = 0; i < k; i++)
{
cout << arr[i] << sp;
}
cout << endl;
}25.Dynamic Programming: Climbing Stairs
class Solution {
public:
int climbStairs(int n) {
if (n == 0 || n == 1) {
return 1;
}
vector<int> dp(n + 1);
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};int maxDepth(TreeNode* root) {
if (!root)
return 0;
int maxLeft = maxDepth(root->left);
int maxRight = maxDepth(root->right);
return max(maxLeft, maxRight) + 1;
}
27. Diameter of Binary Tree: The diameter of a binary tree is the length of the longest path between any two nodes in a tree.
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
int longestPath = 0;
diameter(root, longestPath);
return longestPath;
};
int diameter(TreeNode* curr, int& longestPath) {
if (curr == NULL)
return 0;
// Recursively calculate the diameter of left and right subtrees
int left = diameter(curr->left, longestPath);
int right = diameter(curr->right, longestPath);
// Update the maximum diameter encountered so far
longestPath = max(longestPath, left + right);
// Return the depth of the current node
return max(left, right) + 1;
}
};28. Linked List Cycle: Determine if the linked list has a cycle in it.
Use two pointers, walker and runner.
walker moves step by step. runner moves two steps at time.
if the Linked List has a cycle walker and runner will meet at some point.
class Solution {
public:
bool hasCycle(ListNode* head) {
if (head == NULL)
return false;
ListNode* walker = head;
ListNode* runner = head;
while (runner->next != NULL && runner->next->next != NULL) {
walker = walker->next;
runner = runner->next->next;
if (walker == runner)
return true;
}
return false;
}
};29. Middle of the Linked List: If there are two middle nodes, return the second middle node.
Each time,
walkergo 1 step whilerunnergo 2 steps. Whenrunnerarrives at the end,walkerwill arrive right in the middle.
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* walker = head;
ListNode* runner = head;
// Check if runner reached endpoint
while (runner && runner->next) {
walker = walker->next;
runner = runner->next->next;
}
return walker;
}
};class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (list1 == NULL)
return list2;
if (list2 == NULL)
return list1;
ListNode* mergeList = list1;
if (list1->val > list2->val) {
mergeList = list2;
list2 = list2->next;
} else {
mergeList = list1;
list1 = list1->next;
}
ListNode* currHead = mergeList;
while (list1 && list2) {
if (list1->val > list2->val) {
currHead->next = list2;
list2 = list2->next;
} else {
currHead->next = list1;
list1 = list1->next;
}
currHead = currHead->next;
}
if (!list1) {
currHead->next = list2;
} else {
currHead->next = list1;
}
return mergeList;
}
};class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *nextNode, *prevNode = NULL;
while (head) {
nextNode = head->next;
head->next = prevNode;
prevNode = head;
head = nextNode;
}
return prevNode;
}
};32. Maximum Subarray
Given an integer array nums, find the subarray with the largest sum, and return its sum.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.class Solution {
public:
int maxSubArray(vector<int>& nums) {
int currentMax = 0;
int finalMax = INT_MIN;
int start = 0, end = 0, tempStart = 0;
for (int i = 0; i < nums.size(); i++) {
if (currentMax <= 0) {
currentMax = nums[i];
tempStart = i;
} else {
currentMax += nums[i];
}
if (currentMax > finalMax) {
finalMax = currentMax;
start = tempStart;
end = i;
}
}
// Print the Sub-array
for (int i = start; i <= end; i++) {
cout << nums[i] << " ";
}
return finalMax;
}
};class Solution {
public:
int romanToInt(string s) {
unordered_map<char, int> romanMap = {{'I', 1}, {'V', 5}, {'X', 10},
{'L', 50}, {'C', 100}, {'D', 500},
{'M', 1000}};
int result = 0;
for (int i = 0; i < s.size(); i++) {
if (romanMap[s[i]] < romanMap[s[i + 1]]) {
result -= romanMap[s[i]];
} else {
result += romanMap[s[i]];
}
}
return result;
}
};class Solution {
public:
string intToRoman(int num) {
string roman = "";
int storeInt[13] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
string storeRoman[13] = {"M", "CM", "D", "CD", "C", "XC", "L",
"XL", "X", "IX", "V", "IV", "I"};
for (int i = 0; i < 13; i++) {
while (num >= storeInt[i]) {
roman += storeRoman[i];
num -= storeInt[i];
}
}
return roman;
}
};Last updated