DSA EssentialsCheatsheets, Key Points & Interview Questions

Module 1 – Algorithm and Complexity Fundamentals

Algorithm and Complexity Fundamentals

• An algorithm is a finite, step-by-step procedure for solving a problem.
• A correct algorithm should:
• Accept valid input.
• Produce the required output.
• Terminate after finite steps.
• Be logically correct.
• Use reasonable resources.
• Input size, usually represented by n, determines how an algorithm’s running time grows.
• Time complexity measures how the number of operations grows with input size.
• Space complexity measures additional memory required by an algorithm.
• Auxiliary space means extra memory used apart from the input storage.
• Big-O notation, O(g(n)), gives an asymptotic upper bound.
• Big-Omega notation, Ω(g(n)), gives an asymptotic lower bound.
• Big-Theta notation, Θ(g(n)), gives a tight asymptotic bound.
• Constant factors are ignored in asymptotic analysis.
• For example: 3n2+5n+10=Θ(n2)3n^2+5n+10 = (n^2)3n2+5n+10=Θ(n2)
• Common complexity order from faster to slower: O(1)<O(log⁡n)<O(n2)<O(n3)<O(2n)<O(n!)O(1) < O( n) < O(n) < O(n n) < O(n^2) < O(n^3) < O(2^n) < O(n!)O(1)<O(logn)<O(n2)<O(n3)<O(2n)<O(n!)
• A single loop from 0 to n-1 normally has O(n) complexity.
• Two nested loops each running n times normally have O(n2)O(n^2)O(n2) complexity.
• If the input is repeatedly divided by two, the complexity is usually O(log⁡n)O( n)O(logn).
• Binary search has O(log⁡n)O( n)O(logn) time complexity.
• Merge sort has O(nlog⁡n)O(n n)O(nlogn) time complexity.
• The worst-case time complexity of ordinary quicksort is O(n2)O(n^2)O(n2).
• A recursive algorithm must have a base case.
• Without a valid base case, recursion may continue indefinitely or cause stack overflow.
• Best-case complexity describes the most favorable input arrangement.
• Worst-case complexity describes the least favorable input arrangement.
• Average-case complexity describes expected performance over input distributions.
• A stable sorting algorithm preserves the relative order of equal elements.
• An in-place algorithm uses O(1) or limited extra memory apart from the input.
• A recursive algorithm solves a problem using calls to itself.
• An iterative algorithm uses loops to repeat operations.
• Divide and conquer has three stages:
• Divide.
• Conquer.
• Combine.
• Merge sort and binary search use divide and conquer.
• Dynamic programming is useful when a problem has overlapping subproblems and optimal substructure. The booklet emphasizes asymptotic notation, recurrence analysis, Master Theorem, divide and conquer, dynamic programming, greedy algorithms, and graph algorithms as core algorithm topics.

Arrays

• An array stores elements of the same type in contiguous memory.
• Array indexing generally starts from 0 in C++.
• Accessing an array element by index takes O(1) time.
• Searching an unsorted array takes O(n) time in the worst case.
• Inserting at the beginning of an array takes O(n) because elements must shift.
• Inserting at the end takes O(1) if space is available.
• Deleting from the beginning takes O(n).
• A static array has fixed size.
• A dynamic array can grow or shrink during execution.
• C++ vector is a dynamic array.
• A two-dimensional array is commonly stored in row-major order in C++.
• A prefix sum stores cumulative sums to answer range-sum queries efficiently.
• A sliding window maintains a changing range of elements.
• The two-pointer technique uses two indexes to solve array or string problems efficiently.
• Kadane’s algorithm finds the maximum subarray sum in O(n).
• The Dutch National Flag algorithm sorts 0, 1, and 2 in O(n).
• A majority element appears more than n/2 times.
• Moore’s Voting Algorithm finds a majority element in O(n) time and O(1) extra space.
• Hashing can solve Two Sum in O(n) average time.
• Sorting an array before solving a problem may enable binary search or two-pointer techniques.

Array Code: Maximum Subarray Sum

1#include <bits/stdc++.h>
2using namespace std;
3 
4int maxSubarraySum(const vector<int>& a) {
5    int current = a[0];
6    int best = a[0];
7 
8    for (int i = 1; i < a.size(); i++) {
9        current = max(a[i], current + a[i]);
10        best = max(best, current);
11    }
12 
13    return best;
14}
15 
16int main() {
17    vector<int> a = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
18    cout << maxSubarraySum(a);
19}
20Dry Run

Array

1-2, 1, -3, 4, -1, 2, 1, -5, 4
2Element
3	current
4	best
5	-2
6	-2
7	-2
8	1
9	1
10	1
11	-3
12	-2
13	1
14	4
15	4
16	4
17	-1
18	3
19	4
20	2
21	5
22	5
23	1
24	6
25	6
26	-5
27	1
28	6
29	4
30	5
31	6

Output

16
2The maximum subarray is:

14, -1, 2, 1
2Complexity:
3* Time: O(n)O(n)O(n).
4* Extra space: O(1)O(1)O(1).
5 
6Array Code: Move Zeroes to the End

1#include <bits/stdc++.h>
2using namespace std;
3 
4void moveZeroes(vector<int>& a) {
5    int position = 0;
6 
7    for (int x : a) {
8        if (x != 0) {
9            a[position++] = x;
10        }
11    }
12 
13    while (position < a.size()) {
14        a[position++] = 0;
15    }
16}
17 
18int main() {
19    vector<int> a = {0, 1, 0, 3, 12};
20 
21    moveZeroes(a);
22 
23    for (int x : a)
24        cout << x << " ";
25}
26Dry Run

Initial array

10 1 0 3 12
2Non-zero values are copied forward:

11 3 12 _ _
2Remaining positions are filled with zero:

11 3 12 0 0
2Complexity:
3* Time: O(n)O(n)O(n).
4* Extra space: O(1)O(1)O(1).

Strings

• A string is a sequence of characters.
• A C-style string ends with the null character '\0'.
• C++ string manages memory automatically.
• String indexing is generally O(1).
• A substring is a contiguous part of a string.
• A subsequence maintains order but does not require contiguity.
• A palindrome reads the same forward and backward.
• Two strings are anagrams if they contain the same characters with the same frequencies.
• A frequency array is useful when characters belong to a small known range.
• A hash map is useful for arbitrary or Unicode characters.
• A sliding window solves many longest-substring problems.
• The longest substring without repeated characters can be solved using a set or frequency map.
• A prefix begins at the first character.
• A suffix ends at the last character.
• A lexicographical comparison compares strings dictionary-wise.
• String concatenation may be expensive when repeated many times.
• s.find(t) returns the starting index of substring t, or string::npos if absent.
• A pangram contains every letter of the alphabet at least once.
• A string can be compressed using character-frequency counts.
• The two-pointer technique can check a palindrome in O(n).

String Code: Palindrome Check

1#include <bits/stdc++.h>
2using namespace std;
3 
4bool isPalindrome(const string& s) {
5    int left = 0;
6    int right = s.size() - 1;
7 
8    while (left < right) {
9        if (s[left] != s[right])
10            return false;
11 
12        left++;
13        right--;
14    }
15 
16    return true;
17}
18 
19int main() {
20    cout << boolalpha << isPalindrome("level");
21}
22Dry Run

String

1l e v e l
2left
3	right
4	Comparison
5	0
6	4
7	l == l
8	1
9	3
10	e == e
11	2
12	2
13	Stop

Output

1true
2Complexity:
3* Time: O(n)O(n)O(n).
4* Extra space: O(1)O(1)O(1).
5 
6String Code: First Non-Repeating Character

1#include <bits/stdc++.h>
2using namespace std;
3 
4char firstNonRepeating(const string& s) {
5    unordered_map<char, int> frequency;
6 
7    for (char c : s)
8        frequency[c]++;
9 
10    for (char c : s) {
11        if (frequency[c] == 1)
12            return c;
13    }
14 
15    return '#';
16}
17 
18int main() {
19    cout << firstNonRepeating("swiss");
20}
21Dry Run

String

1s w i s s
2Frequencies:

1s = 3
2w = 1
3i = 1

Scan again

• s: repeated.
• w: frequency is 1.

Output

1w
2Complexity:
3* Average time: O(n)O(n)O(n).
4* Extra space: O(k)O(k)O(k), where kkk is the number of distinct characters.