DS, OOP , Algorithms Exam Preb

Big O

Describes how an algorithm's time or space grows as input size grows

O(1)

Constant time. Runtime does not grow with input size

O(n)

Linear time. Runtime grows directly with input size

O(n²)

Quadratic time. Usually caused by nested loops over the same input

O(log n)

Logarithmic time. Usually caused by repeatedly cutting the input in half

O(n log n)

Usually appears in efficient sorting algorithms like merge sort, heap sort, and C++ sort

Drop constants in Big O

O(2n) becomes O(n), and O(10n) becomes O(n)

Drop smaller terms

O(n² + n) becomes O(n²)

Hash map lookup

Average O(1), but uses extra space

Brute force Two Sum

Checks every pair, so time complexity is O(n²)

Optimized Two Sum

Uses a hash map, so average time complexity is O(n)

i += 2 in a loop

Still O(n), because n/2 becomes O(n)

O(log n)

Usually happens when the loop repeatedly multiplies or divides the value

Nested loops

Multiply their complexities

Separate code blocks

Add their complexities, then keep the biggest term

O(nm)

Used when one loop depends on n and the nested loop depends on m

O(n log n)

Common for efficient sorting like C++ sort()

vector push_back

O(1) amortized

unordered_map loop

O(n) average time if each operation is O(1)

Amortized O(1)

Most operations are O(1), but sometimes one operation is slower. When averaged over many operations, the cost is still O(1).

vector push_back complexity

In C++, vector.push_back() is O(1) amortized because adding is usually constant time, but sometimes the vector resizes and copies elements.

Why vector push_back is not always exactly O(1)

When the vector is full, it may allocate bigger memory and move or copy old elements, which can take O(n). But this happens only sometimes.

Same Big O = same speed?

No. Two algorithms can both be O(n), but one can still be faster in real life because Big O ignores constants and smaller details.

Example of same Big O but different speed

A loop that checks n items once and a loop that checks n items with 10 operations each are both O(n), but the first is usually faster.

What Big O tells us

Big O tells us how runtime grows as input grows. It does not tell the exact running time.

Why we drop constants

O(2n), O(10n), and O(n) are all written as O(n) because Big O focuses on growth rate, not exact operations.

Big O compares growth, not exact speed

This means two algorithms can have the same Big O but still perform differently in practice.

Bitmasking

A technique where one integer stores multiple yes/no values using its binary bits.

Bitmask

The integer that holds the combined flags.

Bit flag

One bit inside the bitmask that represents one option, permission, or state.

Bitwise operators for bitmasking

Use | to add a flag, & to check a flag, and & ~ to remove a flag.

Stack clue

If the problem needs the most recent item first, use a stack.

Valid Parentheses pattern

Push opening brackets. For every closing bracket, check whether it matches the most recent opening bracket.

Why Valid Parentheses uses stack

Because brackets must close in reverse order: the last opened bracket must be closed first.

LIFO

Last In, First Out. The last item added is the first item removed.

stack.push(x)

Adds x to the top of the stack.

stack.top()

Returns the item at the top of the stack without removing it.

stack.pop()

Removes the item at the top of the stack.

stack.empty()

Returns true if the stack has no elements.

Stack runtime error

Calling top() or pop() on an empty stack can cause a runtime error.

Safe stack rule

Before using st.top() or st.pop(), check st.empty().

Opening bracket in Valid Parentheses

If the character is '(', '[', or '{', push it into the stack.

Closing bracket in Valid Parentheses

If the character is ')', ']', or '}', first check if the stack is empty, then check if the top matches.

Valid Parentheses final check

After processing all characters, return true only if the stack is empty.

Why return false when stack is empty on a closing bracket

Because there is no previous opening bracket to match with this closing bracket.

Most recent opening bracket

The bracket on top of the stack. It is the one that must match the current closing bracket.

break vs continue

break stops the entire loop, while continue skips only the current iteration and moves to the next one.

stoi() in Baseball Game

Only call stoi() after checking special operations like C, D, and +. The final else means the operation must be a number.

Vector as record/history

A vector can work like a history list when we need to add the newest value and remove the most recent value using push_back() and pop_back().

Algorithm

A step-by-step strategy used to solve a problem.

Data structure vs algorithm

A data structure stores/organizes data, while an algorithm is the strategy used to solve the problem.

Brute force

Try all possible answers directly. It is usually simple but often expensive.

Brute force usefulness

Brute force is useful because it proves you understand the problem before optimizing.

Backtracking

An algorithm technique that builds an answer step by step, tries choices, explores them, then undoes the choice to try another.

Backtracking rhythm

Choose, explore, undo.

Backtracking clue

Use backtracking when the problem says generate all, all permutations, all combinations, all valid arrangements, or all paths.

State

The current situation of the algorithm, such as the current node, current cell, current partial answer, or used values.

Undo in backtracking

Removing the last choice so the algorithm can try another choice.

Pruning

Skipping a path early because it already violates a rule or cannot lead to a useful answer.

Permutation

An arrangement where order matters. For example, [1,2] and [2,1] are different permutations.

Combination

A selection where order does not matter. For example, [1,2] and [2,1] are the same combination.

Subsets pattern

For each item, choose take or skip. Total subsets for n items is 2^n.

Permutations pattern

Choose one unused item each time. For n items, total permutations is n!.

DFS

Depth First Search. It explores deeply first, usually using recursion or a stack.

DFS clue

Use DFS for exploring connected nodes, trees, graphs, grids, paths, and backtracking-style problems.

BFS

Breadth First Search. It explores level by level, usually using a queue.

BFS clue

Use BFS for shortest path, minimum steps, level order traversal, nearest target, and spread step by step problems.

Why BFS finds shortest path

In an unweighted graph, BFS explores all nodes 1 step away before 2 steps away, so the first time it reaches a node is the shortest path.

Connected component

A separate group of connected nodes.

Island in grid problem

A connected group of land cells, usually 1s, connected up/down/left/right.

Visited in DFS/BFS

Marks nodes or cells already processed so we do not count them again or loop forever.

Frequency counting

Count how many times each item appears.

Frequency counting clue

Use frequency counting for anagrams, most frequent, character counts, duplicates with counts, or how many times something appears.

Lookup

Check quickly if something exists, usually using a hash set or hash map.

Lookup clue

Use lookup when asking: have I seen this before? Does this value exist?

Hash set use

Use a hash set when you only need to know whether a value exists.

Hash map use

Use a hash map when you need key to value, such as number to index or character to count.

Two pointers

Use two positions to scan data, often from both ends or at different speeds.

Two pointers left-right clue

Use left-right pointers for palindrome, sorted pair problems, reverse, or comparing both ends.

Slow and fast pointers

Use two pointers where slow moves 1 step and fast moves 2 steps, often for linked list middle or cycle detection.

Sliding window

A two-pointer pattern for continuous subarrays or substrings where the window expands and shrinks.

Sliding window clue

Use sliding window for longest substring, shortest substring, subarray, continuous block, at most K, or without repeating.

Sliding window movement

Right expands the window, left shrinks or fixes the window.

Prefix sum

A running total from the start of the array to the current index.

Prefix sum clue

Use prefix sum for range sum, sum between indexes, subarray sum, or many sum queries.

Prefix sum formula

sum from i to j = prefix[j] - prefix[i - 1].

Greedy

Choose the best local option at each step without going back.

Greedy clue

Use greedy when a local best choice safely leads toward the global best answer, like keeping the lowest stock price so far.

Dynamic Programming

An algorithm technique for repeated subproblems where we store previous answers to avoid recalculating.

DP clue

Use DP for number of ways, maximum/minimum over choices, can/cannot reach, repeated subproblems, or best answer up to index i.

Sorting clue

Use sorting when order makes the problem easier, such as grouping anagrams, handling duplicates, intervals, or using two pointers.

Binary search

Search by cutting the search space in half each time.

Binary search clue

Use binary search when the array is sorted or the answer space is monotonic.