Introduction Cheat Sheet

1. What is DSA?

Data Structures + Algorithms

Data Structure: A way to organize and store data so operations can be performed efficiently.
Algorithm: A finite sequence of steps used to solve a problem.

Examples:

Array → data structure
Hash Map → data structure
Binary Search → algorithm
Merge Sort → algorithm

The goal is not just to make a program work, but to make it work efficiently.

2. Why DSA matters in interviews

Interview problems usually test whether you can:

Understand the problem.
Identify the right data structure.
Choose an appropriate algorithm.
Analyze time and space complexity.
Implement it correctly.
Explain trade-offs.

A working solution is only part of the answer.

3. Data Structure vs Algorithm

Concept	Question it answers
Data Structure	How should I store/manage the data?
Algorithm	How should I process/solve the problem?

Example:

Find whether a number exists in a collection.

Using an array:

nums = [10, 20, 30, 40]

10 in nums

This may require scanning elements → O(n).

Using a hash set:

nums = {10, 20, 30, 40}

10 in nums

Average lookup → O(1).

Same problem, different data structure, different performance.

4. Correctness vs Efficiency

There are two separate questions:

Correctness

Does the algorithm always produce the correct answer?

Efficiency

How much time and memory does it use?

For example, two algorithms may both correctly sort an array:

Bubble Sort → O(n²)
Merge Sort → O(n log n)

Both are correct, but their performance differs significantly for large inputs.

5. Complexity

We usually measure:

Time Complexity

How the number of operations grows as input size n grows.

Space Complexity

How much additional memory grows as n grows.

Common complexities:

Complexity	Name
O(1)	Constant
O(log n)	Logarithmic
O(n)	Linear
O(n log n)	Linearithmic
O(n²)	Quadratic
O(2ⁿ)	Exponential
O(n!)	Factorial

Typical goal:

Reduce time and/or extra space while maintaining correctness.

6. Big-O intuition

Big-O describes the growth rate, not the exact running time.

For example:

for x in nums:
    print(x)

If nums has n elements:

Time = O(n)

If:

for x in nums:
    for y in nums:
        print(x, y)

Then:

Time = O(n²)

7. Ignore constants

If an algorithm performs:

3n + 10

operations, we describe it as:

O(n)

Because Big-O focuses on asymptotic growth.

Similarly:

O(2n) → O(n)
O(5n + 100) → O(n)
O(n² + n) → O(n²)

8. Dominant term

Keep the fastest-growing term.

Example:

O(n² + n + 50)

becomes:

O(n²)

because n² dominates as n becomes large.

9. Space complexity

Example:

result = []

for x in nums:
    result.append(x)

If n elements are stored in result:

Extra space = O(n)

An algorithm using only a few variables:

total = 0
for x in nums:
    total += x

uses:

Extra space = O(1)

Note: input storage and auxiliary/extra space are often discussed separately. In interviews, be explicit about what you are counting.

10. Trade-offs

Sometimes we spend memory to save time.

Example:

Without a set

Search repeatedly through an array:

Time: potentially O(n) per lookup.

With a set

Build a set first:

seen = set(nums)

Then average lookup is O(1).

You used:

Extra space: O(n)

to improve lookup performance.

This is a classic time-space trade-off.

11. The DSA problem-solving pattern

For most interview problems:

1. Understand the input/output
2. Identify constraints
3. Think of brute force
4. Analyze complexity
5. Look for a better data structure/pattern
6. Implement
7. Test edge cases
8. Explain complexity

Do not immediately jump into code.

12. Questions to ask yourself

When you see a new problem:

Input

What is the input type?
How large can n be?
Are duplicates possible?
Is the data sorted?
Can values be negative?
Is the input mutable?

Operations

Do I need fast lookup?
Do I need fast insertion/deletion?
Do I need ordering?
Do I need to maintain frequency?
Do I need to access elements by index?

Constraints

The constraints often tell you the expected complexity.

Rough interview intuition:

n ≈ 10        → many approaches work
n ≈ 100       → O(n²) often acceptable
n ≈ 1,000     → O(n²) may still work depending on limits
n ≈ 100,000   → usually aim for O(n log n) or O(n)
n ≈ 1,000,000 → usually aim for O(n) or O(log n)

These are heuristics, not strict rules. Actual time limits and operation costs matter.

13. Core idea to remember

Choose the data structure based on the operations you need.

Examples:

Fast index access       → Array
Fast average lookup     → Hash Map / Hash Set
LIFO                    → Stack
FIFO                    → Queue
Hierarchical data       → Tree
Network relationships   → Graph
Repeated min/max        → Heap

Interview takeaway

When explaining a solution, aim to say:

“I need operation X to be fast, so I’ll use data structure Y. This gives me Z time complexity and requires W additional space.”

That is the core DSA mindset.

Quick Revision

DSA = Data Structures + Algorithms

Data Structure → organizes data
Algorithm      → solves/processes a problem

Time Complexity  → how runtime grows
Space Complexity → how extra memory grows

Common:
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

Big-O:
- Ignore constants
- Keep dominant term
- Focus on growth as n increases

Key principle:
Choose the data structure based on the operations you need.