✦ Reference Hub

DSA Syntax Cheatsheet

Every data structure you need for interviews — C++, Java, and Python side by side. Declaration, operations, and key gotchas.

How to use this page

Click the language tabs on each section to switch between C++, Java, and Python. Each section ends with a "Points to Remember" box of critical gotchas.

1. Arrays / Lists

C++
// Declaration
int arr[5] = {1, 2, 3, 4, 5};           // fixed-size
vector<int> v = {1, 2, 3};               // dynamic
vector<int> v(5, 0);                    // size 5, all zeros

// Access & Modify
v[0];                                   // O(1) access
v.push_back(10);                        // O(1) amortized append
v.pop_back();                            // O(1) remove last
v.insert(v.begin() + 2, 99);           // O(N) insert at index
v.erase(v.begin() + 2);                // O(N) remove at index

// Size & Iteration
v.size();                                // number of elements
v.empty();                               // true if empty
for (int x : v) { /* range-for */ }
for (int i = 0; i < v.size(); i++) { v[i]; }

// Slice (no built-in, use constructor)
vector<int> sub(v.begin() + 1, v.begin() + 4); // [1,4)

// Sort & Reverse
sort(v.begin(), v.end());               // ascending
sort(v.begin(), v.end(), greater<int>()); // descending
reverse(v.begin(), v.end());

// Min / Max
*min_element(v.begin(), v.end());
*max_element(v.begin(), v.end());

// 2D array
vector<vector<int>> grid(3, vector<int>(4, 0)); // 3×4, zeros
grid[1][2] = 5;
Java
// Declaration
int[] arr = {1, 2, 3, 4, 5};            // fixed-size
int[] arr = new int[5];                  // initialized to 0
ArrayList<Integer> list = new ArrayList<>();

// Access & Modify
arr[0];                                  // O(1) access
list.add(10);                            // O(1) amortized append
list.add(2, 99);                        // O(N) insert at index
list.remove(2);                         // O(N) remove at index
list.set(0, 42);                        // O(1) update
list.get(0);                            // O(1) get

// Size & Iteration
arr.length;                              // fixed array size
list.size();                             // ArrayList size
list.isEmpty();
for (int x : list) { /* enhanced for */ }

// Sublist
list.subList(1, 4);                     // view [1,4) — not a copy!

// Sort
Arrays.sort(arr);                       // primitive array
Collections.sort(list);                 // ArrayList
Collections.sort(list, Collections.reverseOrder());
arr = IntStream.range(0, arr.length).boxed()
      .sorted((a,b) -> b-a).mapToInt(Integer::intValue).toArray();

// Min / Max
Collections.min(list);
Collections.max(list);

// 2D array
int[][] grid = new int[3][4];           // 3×4, zeros
grid[1][2] = 5;
Python
# Declaration
arr = [1, 2, 3, 4, 5]
arr = [0] * 5                           # size 5, all zeros

# Access & Modify
arr[0]                                   # O(1)
arr[-1]                                  # last element
arr.append(10)                           # O(1) amortized
arr.pop()                                # O(1) remove last
arr.insert(2, 99)                       # O(N) insert at index
arr.pop(2)                              # O(N) remove at index

# Size & Iteration
len(arr)
for x in arr: pass
for i, x in enumerate(arr): pass

# Slice
arr[1:4]                                # new list [1,4)
arr[:3]                                 # first 3
arr[-2:]                                # last 2
arr[::-1]                               # reversed copy

# Sort
arr.sort()                               # in-place, O(N log N)
arr.sort(reverse=True)
sorted_arr = sorted(arr)               # returns new list
arr.sort(key=lambda x: -x)            # custom key

# Min / Max
min(arr)
max(arr)

# 2D array
grid = [[0] * 4 for _ in range(3)]     # 3×4, zeros ← correct way
grid[1][2] = 5
⚠ Points to Remember — Arrays
  • Python: [[0]*4]*3 creates 3 references to the SAME inner list. Always use list comprehension: [[0]*4 for _ in range(3)]
  • Java: list.subList(1,4) returns a view — modifying it modifies the original.
  • C++: v.size() returns size_t (unsigned). v.size() - 1 when size=0 wraps to a huge number — check !v.empty() first.
  • All: Inserting/deleting at the middle is O(N) — use LinkedList or Deque if you need frequent insertions.

2. Strings

C++
string s = "hello";
s.size();   s.length();                  // both work
s[0];                                    // char access O(1)
s.substr(1, 3);                         // start=1, len=3 → "ell"
s.find("ll");                           // index or string::npos
s.rfind("l");                           // last occurrence
s.replace(1, 2, "XY");                 // replace 2 chars at pos 1
s + " world";                           // concatenation (new string)
s.compare("hello") == 0;               // lexicographic compare
reverse(s.begin(), s.end());            // in-place reverse
sort(s.begin(), s.end());               // sort characters

// Type conversions
stoi("123");    stol("123");           // string → int/long
to_string(42);                         // int → string

// Efficient string building
string result;
result.reserve(1000);                  // pre-allocate
for (char c : s) result += c;          // efficient

// Check character type
isdigit('5');  isalpha('a');  isalnum('a');
tolower('A');  toupper('a');
Java
String s = "hello";
s.length();
s.charAt(0);                            // char access O(1)
s.substring(1, 4);                     // [1,4) → "ell"
s.indexOf("ll");                       // -1 if not found
s.lastIndexOf("l");
s.contains("ell");
s.replace("l", "X");                   // replaces ALL occurrences
s.replaceAll("\\d", "#");             // regex replace
s + " world";                         // new String (immutable!)
s.equals("hello");                    // value equality
s.compareTo("world");                  // lexicographic
s.trim();   s.strip();                   // remove whitespace
s.toUpperCase();  s.toLowerCase();
s.toCharArray();                         // String → char[]
s.split(" ");                          // String → String[]
String.join(",", arr);                  // join array
s.startsWith("he");  s.endsWith("lo");

// Type conversions
Integer.parseInt("123");
Long.parseLong("123");
String.valueOf(42);    Integer.toString(42);

// Efficient string building — use StringBuilder!
StringBuilder sb = new StringBuilder();
sb.append("hello");
sb.insert(0, "X");
sb.deleteCharAt(0);
sb.reverse();
sb.toString();
Python
s = "hello"
len(s)
s[0]                                     # char access O(1)
s[1:4]                                  # slice "ell"
s.find("ll")                            # -1 if not found
s.rfind("l")
"ll" in s                                # contains
s.replace("l", "X")                    # all occurrences
s + " world"                            # new string (immutable)
s == "hello"                            # value equality
s.strip()    s.lstrip()    s.rstrip()
s.upper()    s.lower()
s.split(" ")                           # list of strings
",".join(["a", "b"])                   # "a,b"
s.startswith("he")   s.endswith("lo")
s[::-1]                                 # reverse string
list(s)                                 # string → list of chars
"".join(list(s))                        # list of chars → string

# Type conversions
int("123")
str(42)
ord('a')    # char → ASCII (97)
chr(97)     # ASCII → char 'a'

# Efficient building
parts = []
for c in s: parts.append(c)
result = "".join(parts)               # O(N), not O(N²)
⚠ Points to Remember — Strings
  • Java: Strings are immutable. s += c in a loop = O(N²). Always use StringBuilder.
  • Python: Same issue — s += c in a loop is O(N²). Use a list and join at the end.
  • Java: Use .equals() not == to compare string values. == checks reference equality.
  • C++: s.substr(pos, len) — second arg is LENGTH, not end index. Java's substring(start, end) uses end index.
  • Python: Strings are immutable — s[0] = 'X' throws TypeError. Convert to list first.

3. HashMap / Dictionary

C++
unordered_map<int, int> m;             // O(1) avg — hash map
map<int, int> m;                       // O(log N) — sorted by key

m[5] = 10;                              // insert / update
m.count(5);                             // 1 if exists, 0 if not
m.find(5) != m.end();                  // check existence
m.at(5);                               // get — throws if not found
m[5];                                   // get — INSERTS 0 if not found!
m.erase(5);                            // remove key
m.size();
m.empty();

// Iterate
for (auto& [key, val] : m) {
    // structured bindings (C++17)
}
for (auto& p : m) {
    p.first; p.second;
}

// Default value (getOrDefault equivalent)
m.count(key) ? m[key] : 0;            // safe get

// Frequency count pattern
for (int x : nums) m[x]++;            // m[x] initializes to 0
Java
HashMap<Integer, Integer> m = new HashMap<>();
TreeMap<Integer, Integer> m = new TreeMap<>(); // sorted

m.put(5, 10);                          // insert / update
m.get(5);                              // returns null if not found
m.getOrDefault(5, 0);                 // safe get with default
m.containsKey(5);
m.containsValue(10);
m.remove(5);
m.size();    m.isEmpty();

// Iterate
for (Map.Entry<Integer, Integer> e : m.entrySet()) {
    e.getKey(); e.getValue();
}
for (int key : m.keySet()) { m.get(key); }
for (int val : m.values()) { }

// Frequency count pattern
m.put(x, m.getOrDefault(x, 0) + 1);

// Compute if absent
m.putIfAbsent(key, new ArrayList<>());
m.computeIfAbsent(key, k -> new ArrayList<>()).add(val);
Python
m = {}
m = dict()
from collections import defaultdict, Counter

m[5] = 10                               # insert / update
m[5]                                    # KeyError if not found
m.get(5)                                # None if not found
m.get(5, 0)                            # default 0 if not found
5 in m                                   # containsKey
del m[5]    m.pop(5)                    # remove
len(m)

# Iterate
for key in m: pass
for key, val in m.items(): pass
for val in m.values(): pass

# Frequency count — Counter is best
from collections import Counter
freq = Counter(nums)
freq.most_common(3)                    # top 3 most frequent

# defaultdict — no KeyError
d = defaultdict(int)                   # default 0
d = defaultdict(list)                  # default []
d[key].append(val)                      # safe
⚠ Points to Remember — HashMap
  • C++: m[key] INSERT a default value if key doesn't exist. Use m.count(key) or m.find(key) != m.end() to check first.
  • Java: HashMap allows one null key. TreeMap does not allow null keys (throws NullPointerException).
  • Java: Always use getOrDefault(key, 0) for frequency counting — get(key) returns null which causes NullPointerException when auto-unboxed.
  • Python: Python dicts maintain insertion order (Python 3.7+). If you need sorted order, use sorted(m.items()).
  • Python: Counter from collections is the cleanest way to count frequencies. It also supports arithmetic operations between counters.

4. HashSet

C++
unordered_set<int> s;                // O(1) avg
set<int> s;                            // O(log N) — sorted

s.insert(10);
s.count(10);                           // 1 or 0
s.find(10) != s.end();                // contains
s.erase(10);
s.size();    s.empty();

// Iterate
for (int x : s) { }

// Set operations (manual)
set<int> result;
set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(),
                 inserter(result, result.begin()));
set_union(s1.begin(), s1.end(), s2.begin(), s2.end(),
          inserter(result, result.begin()));
Java
HashSet<Integer> s = new HashSet<>();
TreeSet<Integer> s = new TreeSet<>();  // sorted
LinkedHashSet<Integer> s = new LinkedHashSet<>(); // insertion order

s.add(10);
s.contains(10);
s.remove(10);
s.size();    s.isEmpty();
for (int x : s) { }

// Set operations
Set<Integer> intersection = new HashSet<>(s1);
intersection.retainAll(s2);              // intersection

Set<Integer> union = new HashSet<>(s1);
union.addAll(s2);                        // union

Set<Integer> diff = new HashSet<>(s1);
diff.removeAll(s2);                      // difference
Python
s = set()
s = {1, 2, 3}

s.add(10)
10 in s                                 # O(1) contains
s.remove(10)                           # KeyError if not found
s.discard(10)                          # safe remove
len(s)
for x in s: pass

# Set operations — very clean in Python
s1 & s2                                 # intersection
s1 | s2                                 # union
s1 - s2                                 # difference
s1 ^ s2                                 # symmetric difference
s1.intersection(s2)
s1.union(s2)
s1.issubset(s2)
s1.issuperset(s2)

5. Stack

C++
stack<int> stk;
stk.push(10);                          // O(1)
stk.pop();                              // O(1) — removes, no return
stk.top();                              // O(1) peek — doesn't remove
stk.empty();
stk.size();
Java
Deque<Integer> stk = new ArrayDeque<>(); // preferred over Stack<>
stk.push(10);   stk.addFirst(10);      // O(1)
stk.pop();      stk.removeFirst();      // O(1) remove + return
stk.peek();     stk.peekFirst();        // O(1) peek
stk.isEmpty();
stk.size();
Python
stk = []                                 # list as stack
stk.append(10)                          # O(1) push
stk.pop()                               # O(1) pop + return
stk[-1]                                 # O(1) peek
not stk                                 # is empty
len(stk)
⚠ Points to Remember — Stack
  • Java: Avoid java.util.Stack — it extends Vector and is synchronized (slow). Use ArrayDeque as a stack instead.
  • C++: stk.pop() does NOT return the value — call stk.top() first, then stk.pop().
  • All: Always check empty()/isEmpty() before top()/peek() — calling on empty stack throws exception or undefined behavior.

6. Queue

C++
queue<int> q;
q.push(10);                             // enqueue back
q.pop();                                // dequeue front — no return
q.front();                              // peek front
q.back();                               // peek back
q.empty();    q.size();
Java
Queue<Integer> q = new LinkedList<>();
Queue<Integer> q = new ArrayDeque<>(); // faster, no null

q.offer(10);    q.add(10);             // enqueue (offer returns false vs add throws)
q.poll();       q.remove();            // dequeue front (poll returns null vs remove throws)
q.peek();       q.element();           // peek (peek returns null vs element throws)
q.isEmpty();    q.size();
Python
from collections import deque
q = deque()

q.append(10)                            # enqueue right O(1)
q.popleft()                             # dequeue left O(1)
q[0]                                    # peek front O(1)
q[-1]                                   # peek back O(1)
not q                                   # is empty
len(q)

# WARNING: list as queue is O(N) for popleft
# Always use collections.deque for BFS

7. Deque (Double-Ended Queue)

C++
deque<int> dq;
dq.push_front(1);   dq.push_back(2);
dq.pop_front();      dq.pop_back();
dq.front();          dq.back();
dq[0];                                  // random access O(1)
dq.size();           dq.empty();
Java
Deque<Integer> dq = new ArrayDeque<>();
dq.addFirst(1);       dq.addLast(2);
dq.offerFirst(1);     dq.offerLast(2);
dq.removeFirst();     dq.removeLast();
dq.pollFirst();       dq.pollLast();    // null if empty
dq.peekFirst();       dq.peekLast();
dq.isEmpty();         dq.size();
Python
from collections import deque
dq = deque()
dq.appendleft(1)   dq.append(2)       # add front / back
dq.popleft()        dq.pop()            # remove front / back
dq[0]               dq[-1]             # peek front / back
dq.rotate(1)                           # rotate right by 1
len(dq)

8. Priority Queue / Heap

C++
// Max-heap (default)
priority_queue<int> maxH;

// Min-heap
priority_queue<int, vector<int>, greater<int>> minH;

maxH.push(10);                          // O(log N)
maxH.top();                             // O(1) peek max
maxH.pop();                             // O(log N) remove max
maxH.empty();    maxH.size();

// Custom comparator — min-heap by second element of pair
auto cmp = [](pair<int,int> a, pair<int,int> b) {
    return a.second > b.second;
};
priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);
Java
// Min-heap (default)
PriorityQueue<Integer> minH = new PriorityQueue<>();

// Max-heap
PriorityQueue<Integer> maxH = new PriorityQueue<>(Collections.reverseOrder());

minH.offer(10);    minH.add(10);        // O(log N)
minH.peek();                            // O(1) peek min
minH.poll();                            // O(log N) remove min, null if empty
minH.isEmpty();    minH.size();

// Custom comparator (sort by frequency, then value)
PriorityQueue<int[]> pq = new PriorityQueue<>(
    (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]
);
Python
import heapq

# Min-heap (Python heapq is always min-heap)
heap = []
heapq.heappush(heap, 10)               # O(log N)
heapq.heappop(heap)                     # O(log N) returns min
heap[0]                                 # O(1) peek min
heapq.heapify(arr)                      # in-place O(N)

# Max-heap — negate values
heapq.heappush(heap, -val)
-heapq.heappop(heap)                    # negate back

# Custom: push tuples (priority, value)
heapq.heappush(heap, (freq, val))       # sort by freq first

# K largest / K smallest
heapq.nlargest(3, arr)
heapq.nsmallest(3, arr)
⚠ Points to Remember — Priority Queue
  • C++: Default is max-heap. For min-heap use greater<int>.
  • Java: Default is min-heap. For max-heap use Collections.reverseOrder().
  • Python: Always min-heap. For max-heap negate values: push -val, pop and negate back.
  • All: PriorityQueue does NOT support O(log N) decrease-key. Use lazy deletion instead (mark stale entries).

9. Graph — BFS & DFS Templates

C++
// Build adjacency list
int n = 5;
vector<vector<int>> adj(n);
adj[0].push_back(1);                    // edge 0→1

// BFS
vector<bool> visited(n, false);
queue<int> q;
q.push(0); visited[0] = true;
while (!q.empty()) {
    int node = q.front(); q.pop();
    for (int nb : adj[node]) {
        if (!visited[nb]) {
            visited[nb] = true;
            q.push(nb);
        }
    }
}

// DFS (iterative)
stack<int> stk;
stk.push(0); visited[0] = true;
while (!stk.empty()) {
    int node = stk.top(); stk.pop();
    for (int nb : adj[node]) {
        if (!visited[nb]) {
            visited[nb] = true;
            stk.push(nb);
        }
    }
}
Java
// Build adjacency list
int n = 5;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
adj.get(0).add(1);

// BFS
boolean[] visited = new boolean[n];
Queue<Integer> q = new ArrayDeque<>();
q.offer(0); visited[0] = true;
while (!q.isEmpty()) {
    int node = q.poll();
    for (int nb : adj.get(node)) {
        if (!visited[nb]) {
            visited[nb] = true;
            q.offer(nb);
        }
    }
}
Python
from collections import defaultdict, deque

# Build adjacency list
graph = defaultdict(list)
graph[0].append(1)

# BFS
visited = set()
q = deque([0])
visited.add(0)
while q:
    node = q.popleft()
    for nb in graph[node]:
        if nb not in visited:
            visited.add(nb)
            q.append(nb)

# DFS (recursive)
def dfs(node, visited, graph):
    visited.add(node)
    for nb in graph[node]:
        if nb not in visited:
            dfs(nb, visited, graph)

10. Binary Search Templates

C++
// Standard exact match
int binarySearch(vector<int>& arr, int target) {
    int lo = 0, hi = arr.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // avoid overflow
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

// Lower bound — first index >= target
int lo = 0, hi = arr.size();
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid;
}
// lo is the answer

// Built-in
lower_bound(v.begin(), v.end(), target); // iterator to first >= target
upper_bound(v.begin(), v.end(), target); // iterator to first > target
Java
// Standard
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}

// Built-in (returns index or -(insertion point)-1)
Arrays.binarySearch(arr, target);
Python
# Standard
lo, hi = 0, len(arr) - 1
while lo <= hi:
    mid = (lo + hi) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1

# Built-in bisect module
import bisect
bisect.bisect_left(arr, target)    # first index >= target
bisect.bisect_right(arr, target)   # first index > target
bisect.insort(arr, val)            # insert maintaining sort
⚠ Points to Remember — Binary Search
  • Always use mid = lo + (hi - lo) / 2 not (lo + hi) / 2 — the latter overflows when both are large ints.
  • Know when to use lo <= hi vs lo < hi — exact match uses <=, lower/upper bound uses <.
  • C++: lower_bound/upper_bound return iterators. Subtract .begin() to get index.
  • Java: Arrays.binarySearch returns negative value if not found — not just -1.

Master your coding interview. It's completely free.

Join thousands of engineers preparing with patterns, system design, and CS fundamentals.

Start Learning → Browse Problems
Buy me a coffee