Preparing for coding interviews requires revising a large number of data structures, algorithms, and problem-solving patterns — often under tight timelines. This DSA Cheat Sheet is designed to give you a fast, structured, and interview-focused revision path, especially if you’re using Java. It covers the most important patterns, common questions, time–space complexities, and Java-specific notes that top companies frequently test.
You can use this DSA cheat sheet as a 7-day revision guide, a pre-interview refresher, or a concept-by-concept reference while solving LeetCode, HackerRank, or GFG problems. Every section is concise, practical, and aligned with real interview expectations, so you focus only on what actually matters.
Whether you’re brushing up on arrays, graphs, trees, dynamic programming, greedy approaches, or bit manipulation, this guide helps you quickly recall patterns, understand where to apply them, and review essential Java implementations — without getting overwhelmed.
Think of this DSA cheat sheet as your quick-access prep guide — compact, focused, and designed to boost recall during interviews or coding rounds. No fluff, just the patterns, techniques, and mini Java snippets you need.
Use this DSA cheat sheet to:
- 🧩 Quickly revise patterns before coding interviews
- 💬 Practice how to explain your approach to interviewers
- ⚡ Follow a 7-day revision plan to cover all major DSA topics efficiently
- 📌 Spot common pitfalls and improve problem-solving speed
With this DSA cheat sheet, each algorithm becomes easy to remember, helping you convert theory into coding muscle memory.
Table of Contents
Arrays & Strings – DSA Cheat Sheet
1. Two Pointers
This is the first and probably the most important algorithm of the DSA cheat sheet.
When to use: comparing or filtering elements in a sorted array/string.
Idea: If you move two pointers (i, j) at different speeds, you can avoid nested loops.
int[] nums = {1,1,2,2,3};
int j = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[j]) nums[++j] = nums[i];
}
System.out.println(j + 1); // unique count
Complexity: O(n)
Interview phrasing: “I used the two pointers to track unique elements. And I’ll be moving the second only when a new value appears.”
2. Sliding Window
Again one of the best algorithms of the DSA cheat sheet.
For more on the sliding window algorithm part of the DSA cheat sheet, please check Sliding Window Algorithm – Fixed & Variable Size Solutions.
When to use: When the input has continuous subarrays or substrings, e.g., “longest substring without repeat.”
Idea: Expand right, shrink left while maintaining a condition.
String s = "abcabcbb";
int left = 0, maxLen = 0;
Set<Character> seen = new HashSet<>();
for (int right = 0; right < s.length(); right++) {
while (seen.contains(s.charAt(right)))
seen.remove(s.charAt(left++));
seen.add(s.charAt(right));
maxLen = Math.max(maxLen, right - left + 1);
}
System.out.println(maxLen);
Complexity: O(n)
Interview phrasing: “I keep a window of unique chars. Then I expand it until invalid, then contract from the left.”
3. Prefix Sum
When to use: fast range queries or subarray sums.
Idea: Precompute running sums.
int[] arr = {1,2,3,4};
int[] prefix = new int[arr.length + 1];
for (int i = 1; i <= arr.length; i++)
prefix[i] = prefix[i - 1] + arr[i - 1];
System.out.println(prefix[3] - prefix[1]); // sum(1..2)
Complexity: O(n) preprocessing, O(1) query
Interview phrasing: “I precomputed prefix sums so each query becomes O(1).”
4. Kadane’s Algorithm
When to use: maximum subarray sum (profit, streaks).
Idea: Running sum reset when it goes negative.
int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
int max = nums[0], cur = nums[0];
for (int i = 1; i < nums.length; i++) {
cur = Math.max(nums[i], cur + nums[i]);
max = Math.max(max, cur);
}
System.out.println(max);
Complexity: O(n)
Interview phrasing: “At every step, I decide to continue or restart the subarray. All the while tracking the max.”
5. Frequency Map
Leetcode Problem: Word Frequency
When to use: When we have to count elements quickly (e.g., anagram or top-k).
Idea: HashMap with counts.
String s = "banana";
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray())
freq.put(c, freq.getOrDefault(c, 0) + 1);
System.out.println(freq.get('a'));
Complexity: O(n)
Interview phrasing: “I maintain a frequency map — classic counting pattern.”
6. Reverse String In-Place
When to use: easy warm-up or validation question.
Idea: Two-pointer swap.
char[] ch = "hello".toCharArray();
int i = 0, j = ch.length - 1;
while (i < j) {
char tmp = ch[i];
ch[i++] = ch[j];
ch[j--] = tmp;
}
System.out.println(new String(ch));
Complexity: O(n)
Interview phrasing: “Simple two-pointer reversal — no extra space used.”
7. Subarray Sum Equals K (Prefix + Map)
When to use: count subarrays summing to k.
Idea: Store prefix sums and their frequency.
int[] nums = {1,2,3};
int k = 3, sum = 0, count = 0;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
for (int n : nums) {
sum += n;
count += map.getOrDefault(sum - k, 0);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
System.out.println(count);
Complexity: O(n)
Interview phrasing: “Track prefix sums and how often each sum occurred in O(n) time and O(n) space.”
8. Rotate Array
When to use: shifting arrays cyclically.
Idea: Reverse-parts trick.
int[] nums = {1,2,3,4,5,6,7};
int k = 3;
k %= nums.length;
reverse(nums, 0, nums.length-1);
reverse(nums, 0, k-1);
reverse(nums, k, nums.length-1);
void reverse(int[] a, int l, int r) {
while (l < r) {
int t = a[l];
a[l++] = a[r];
a[r--] = t;
}
}
Complexity: O(n)
Interview phrasing: “Rotate via triple reverse — clean and in-place.”
Arrays & Strings – Interview Insight:
- Common in LeetCode easy/medium questions.
- Patterns like Two Pointers and Sliding Window appear in FAANG coding rounds frequently.
- Good for warm-up questions or quick screeners.
Stacks & Queues – DSA Cheat Sheet
9. Valid Parentheses (Stack)
This is one of the important algorithms of the DSA cheat sheet.
When to use: check balanced brackets, expressions, XML tags.
Idea: Push opens, pop on closes, validate stack empty at end.
String s = "({[]})";
Stack<Character> st = new Stack<>();
for (char c : s.toCharArray()) {
if ("({[".indexOf(c) >= 0) st.push(c);
else if (st.isEmpty() ||
"({[".indexOf(st.pop()) != ")}]".indexOf(c)) return false;
}
return st.isEmpty();
Complexity: O(n)
Interview phrasing: “I am using a stack to ensure proper nesting.”
10. Next Greater Element (Monotonic Stack)
When to use: find next larger number to the right.
Idea: Maintain stack of indices with decreasing values.
int[] nums = {2,1,2,4,3}, res = new int[nums.length];
Stack<Integer> st = new Stack<>();
for (int i = nums.length - 1; i >= 0; i--) {
while (!st.isEmpty() && st.peek() <= nums[i]) st.pop();
res[i] = st.isEmpty() ? -1 : st.peek();
st.push(nums[i]);
}
System.out.println(Arrays.toString(res));
Complexity: O(n)
Interview phrasing: “I use a monotonic stack. This is done to store potential next greater elements in linear time.”
11. Evaluate Reverse Polish Notation
When to use: expression evaluation.
Idea: Push operands, pop 2 on operator and apply.
String[] tokens = {"2","1","+","3","*"};
Stack<Integer> st = new Stack<>();
for (String t : tokens) {
if ("+-*/".contains(t)) {
int b = st.pop(), a = st.pop();
switch (t) {
case "+": st.push(a + b); break;
case "-": st.push(a - b); break;
case "*": st.push(a * b); break;
case "/": st.push(a / b); break;
}
} else st.push(Integer.parseInt(t));
}
System.out.println(st.pop());
Complexity: O(n)
Interview phrasing: “I used a stack to simulate postfix evaluation — classic O(n).”
12. Queue via Two Stacks
When to use: When we have to design a queue with only stacks.
Idea: Use two stacks (in for push, out for pop).
Stack<Integer> in = new Stack<>(), out = new Stack<>();
void push(int x) { in.push(x); }
int pop() {
if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
return out.pop();
}
Complexity: Amortized O(1)
Interview phrasing: “I use two stacks to balance push/pop direction.”
Stacks & Queues – Interview Insight:
- Stack: frequent in parsing, expression evaluation, monotonic stack problems.
- Queue: BFS and design questions; two-stack queue is a popular FAANG interview design problem.
- Medium difficulty usually; focus on implementation + complexity understanding.
Trees – DSA Cheat Sheet
13. Binary Tree Traversals
For more on the tree algorithms part of the DSA cheat sheet, please check DFS vs BFS: A Comprehensive Guide with Problems and Solutions in Java.
When to use: standard tree operations.
Idea: Recursive DFS (inorder, preorder, postorder).
void inorder(TreeNode root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.val + " ");
inorder(root.right);
}
Complexity: O(n)
Interview phrasing: “Traversal patterns define how you process subtrees.”
14. Level Order Traversal (BFS)
This is one the easiest examples of the DSA cheat sheet.
When to use: layer-by-layer processing.
Idea: Use queue for breadth-first.
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode n = q.poll();
System.out.print(n.val + " ");
if (n.left != null) q.add(n.left);
if (n.right != null) q.add(n.right);
}
}
Complexity: O(n)
Interview phrasing: “Use a queue to process nodes level by level (BFS).”
15. Maximum Depth of Binary Tree
This is one of the important examples in the DSA cheat sheet.
When to use: height calculation.
Idea: Recursively compute max(left, right) + 1.
int depth(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(depth(root.left), depth(root.right));
}
Complexity: O(n)
Interview phrasing: “Simple post-order recursion for height.”
16. Validate BST
When to use: check BST invariants.
Idea: Inorder must be sorted or range constraints.
boolean isValid(TreeNode n, long min, long max) {
if (n == null) return true;
if (n.val <= min || n.val >= max) return false;
return isValid(n.left, min, n.val) && isValid(n.right, n.val, max);
}
Complexity: O(n)
Interview phrasing: “I maintain min/max bounds per subtree to verify BST property.”
17. Lowest Common Ancestor
When to use: find shared ancestor in binary tree.
Idea: Return node if found on either side.
TreeNode lca(TreeNode r, TreeNode p, TreeNode q) {
if (r == null || r == p || r == q) return r;
TreeNode left = lca(r.left, p, q);
TreeNode right = lca(r.right, p, q);
if (left != null && right != null) return r;
return left != null ? left : right;
}
Complexity: O(n)
Interview phrasing: “I traverse both subtrees and return the node where paths split.”
Trees – Interview Insight:
- Traversals are basic but form the foundation for recursive/tree DP questions.
- LCA and validation appear in medium-level FAANG interviews.
- Focus on recursion, iterative approaches, and edge cases (null nodes, skewed trees).
Graphs – DSA Cheat Sheet
18. Graph Representation
When to use: adjacency list is most common.
Idea: Map node → neighbors list.
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] e : edges) {
graph.computeIfAbsent(e[0], x -> new ArrayList<>()).add(e[1]);
graph.computeIfAbsent(e[1], x -> new ArrayList<>()).add(e[0]); // undirected
}
Complexity: O(V + E)
Interview phrasing: “Graph stored as adjacency list for O(V+E) space and traversal.”
19. BFS Traversal
For more on the BFS traversal algorithms part of the DSA cheat sheet, please check DFS vs BFS: A Comprehensive Guide with Problems and Solutions in Java.
When to use: shortest path in unweighted graph.
Idea: Queue tracks frontier.
Queue<Integer> q = new LinkedList<>();
Set<Integer> vis = new HashSet<>();
q.add(0); vis.add(0);
while (!q.isEmpty()) {
int node = q.poll();
for (int nei : graph.getOrDefault(node, List.of())) {
if (vis.add(nei)) q.add(nei);
}
}
Complexity: O(V + E)
Interview phrasing: “BFS spreads layer by layer to find the shortest distance.”
20. DFS Traversal
For more on the DFS traversal algorithms part of the DSA cheat sheet, please check DFS vs BFS: A Comprehensive Guide with Problems and Solutions in Java.
When to use: connected components, topo sort, cycle detect.
Idea: Recursive stack visiting neighbors.
void dfs(int node, Set<Integer> vis, Map<Integer,List<Integer>> g) {
if (!vis.add(node)) return;
for (int nei : g.getOrDefault(node, List.of()))
dfs(nei, vis, g);
}
Complexity: O(V + E)
Interview phrasing: “I use DFS to explore depth-first and mark visited nodes.”
21. Topological Sort
When to use: ordering tasks with dependencies (DAG).
Idea: DFS postorder reversal or Kahn’s algorithm.
Stack<Integer> st = new Stack<>();
Set<Integer> vis = new HashSet<>();
void topo(int node, Map<Integer,List<Integer>> g) {
if (!vis.add(node)) return;
for (int nei : g.getOrDefault(node, List.of()))
topo(nei, g);
st.push(node);
}
Complexity: O(V + E)
Interview phrasing: “Topological order is reverse of postorder for DAG.”
22. Dijkstra’s Algorithm
When to use: shortest path with non-negative weights.
Idea: Priority queue relaxation.
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
Map<Integer,Integer> dist = new HashMap<>();
pq.add(new int[]{src,0});
dist.put(src,0);
while (!pq.isEmpty()) {
var [u,du] = pq.poll();
if (du > dist.get(u)) continue;
for (var e : graph.getOrDefault(u,List.of())) {
int v = e[0], w = e[1];
int nd = du + w;
if (nd < dist.getOrDefault(v, Integer.MAX_VALUE)) {
dist.put(v, nd);
pq.add(new int[]{v, nd});
}
}
}
Complexity: O((V + E) log V)
Interview phrasing: “I use a priority queue to greedily pick the closest unvisited node.”
Graphs – Interview Insight:
- BFS/DFS traversal questions common for pathfinding, connectivity, and cycle detection.
- Topological sort and Dijkstra: medium to hard; appear in scheduling and shortest-path problems.
- Understand graph representation (adjacency list/matrix) for efficient coding.
Dynamic Programming (DP) – DSA Cheat Sheet
When interviewers mention “DP,” don’t panic — it’s just recursion with memory. You find overlapping subproblems, store results, and avoid recomputing. Think: “Can I break this into smaller identical problems?”
For more on the Dynamic Programming(DP) algorithm part of the DSA cheat sheet, please check Master Dynamic Programming and Its 2 Techniques: Memoization and Tabulation.
23. Fibonacci (Memoization)
Why it matters: The simplest DP — every other DP builds on it.
int fib(int n, Map<Integer,Integer> memo) {
if (n <= 1) return n;
if (memo.containsKey(n)) return memo.get(n);
int val = fib(n-1, memo) + fib(n-2, memo);
memo.put(n, val);
return val;
}
Complexity: O(n)
Explain: “Top-down recursion that caches intermediate results.”
24. Climbing Stairs
Why: Classic variation of Fibonacci.
int climb(int n) {
int[] dp = new int[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];
}
Complexity: O(n)
Explain: “At each step, you can reach via 1 or 2 jumps → same recurrence as Fibonacci.”
25. Coin Change (Minimum Coins)
Why: One of the most repeated DP patterns.
int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp, amount+1);
dp[0] = 0;
for (int c : coins)
for (int i=c; i<=amount; i++)
dp[i] = Math.min(dp[i], dp[i-c]+1);
return dp[amount] > amount ? -1 : dp[amount];
}
Complexity: O(amount × coins)
Explain: “I build up from smaller amounts using bottom-up DP.”
26. Longest Increasing Subsequence
Why: Appears in disguise — “longest chain”, “max envelopes,” etc.
int lis(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int max = 1;
for (int i=0; i<nums.length; i++)
for (int j=0; j<i; j++)
if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j]+1);
for (int v : dp) max = Math.max(max, v);
return max;
}
Complexity: O(n²)
Explain: “For each number, I look for smaller previous ones and extend the chain.”
27. 0/1 Knapsack
Why: Base for subset, partition, and resource allocation problems.
int knapsack(int[] wt, int[] val, int W) {
int n = wt.length;
int[][] dp = new int[n+1][W+1];
for (int i=1; i<=n; i++)
for (int w=0; w<=W; w++)
dp[i][w] = wt[i-1] <= w
? Math.max(val[i-1]+dp[i-1][w-wt[i-1]], dp[i-1][w])
: dp[i-1][w];
return dp[n][W];
}
Complexity: O(nW)
Explain: “I fill a 2D DP table by choosing or skipping items.”
28. Longest Common Subsequence (LCS)
Why: Foundation for edit distance, diff tools, and DNA matching.
int lcs(String a, String b) {
int[][] dp = new int[a.length()+1][b.length()+1];
for (int i=1; i<=a.length(); i++)
for (int j=1; j<=b.length(); j++)
dp[i][j] = (a.charAt(i-1)==b.charAt(j-1))
? 1+dp[i-1][j-1]
: Math.max(dp[i-1][j], dp[i][j-1]);
return dp[a.length()][b.length()];
}
Complexity: O(mn)
Explain: “I build a DP table comparing prefixes of both strings.”
29. Edit Distance
Why: Google spell checker’s logic — how many edits to match strings.
int edit(String a, String b) {
int[][] dp = new int[a.length()+1][b.length()+1];
for (int i=0;i<=a.length();i++) dp[i][0]=i;
for (int j=0;j<=b.length();j++) dp[0][j]=j;
for (int i=1;i<=a.length();i++)
for (int j=1;j<=b.length();j++)
dp[i][j] = (a.charAt(i-1)==b.charAt(j-1))
? dp[i-1][j-1]
: 1+Math.min(dp[i-1][j-1], Math.min(dp[i][j-1], dp[i-1][j]));
return dp[a.length()][b.length()];
}
Complexity: O(mn)
Explain: “I use dynamic programming to find the fewest edits between prefixes.”
30. Maximum Subarray (Kadane’s Algorithm)
Why: The most popular DP problem.
int kadane(int[] arr) {
int maxSoFar = arr[0], curr = arr[0];
for (int i=1; i<arr.length; i++) {
curr = Math.max(arr[i], curr + arr[i]);
maxSoFar = Math.max(maxSoFar, curr);
}
return maxSoFar;
}
Complexity: O(n)
Explain: “I track running sums and reset when the sum turns negative.”
Dynamic Programming (DP) – Interview Insight:
- Fibonacci, Climbing Stairs: warm-ups.
- Coin Change, LIS, Knapsack, LCS, Edit Distance: common medium/hard problems.
- Practice bottom-up and top-down; focus on state definition and transition.
Greedy Patterns – DSA Cheat Sheet
For more on the Greedy algorithm part of the DSA cheat sheet, please check Greedy Algorithm: A Comprehensive Guide With Examples.
31. Activity Selection / Meeting Rooms
Why: Earliest finish first — simple, elegant, greedy.
int[][] meetings = {{1,3},{2,4},{3,5}};
Arrays.sort(meetings, Comparator.comparingInt(a->a[1]));
int count=0, end=-1;
for (int[] m: meetings)
if (m[0] >= end) { count++; end = m[1]; }
Complexity: O(n log n)
Explain: “Always pick the meeting that finishes earliest.”
32. Huffman Encoding (Conceptual)
Why: Classic greedy tree-based compression.
Idea: Build a min-heap of frequencies, merge lowest two repeatedly.
Explain: “It’s greedy because each merge is locally optimal — leads to global optimum.”
33. Fractional Knapsack
Why: Mixes sorting + ratios + greedy thinking.
double knap(int[] val, int[] wt, int W) {
int n = val.length;
double[][] items = new double[n][2];
for (int i=0; i<n; i++) items[i] = new double[]{val[i], wt[i]};
Arrays.sort(items, (a,b)->Double.compare(b[0]/b[1], a[0]/a[1]));
double total = 0;
for (double[] it: items) {
if (W >= it[1]) { total += it[0]; W -= it[1]; }
else { total += it[0]*(W/it[1]); break; }
}
return total;
}
Complexity: O(n log n)
Explain: “Greedy on value/weight ratio always yields the optimal fractional result.”
34. Minimum Coins for Change (Greedy)
When works: when denominations are canonical (like Indian currency).
Explain: “Always pick the largest denomination ≤ remaining amount.”
Greedy Patterns – Interview Insight:
- Activity Selection, Huffman, Fractional Knapsack: classic patterns.
- FAANG prefers clean greedy reasoning and proof of correctness.
- Usually medium difficulty; sorting and priority queue usage important.
Bit Manipulation Patterns – DSA Cheat Sheet
This is one of the important patterns in the DSA cheat sheet, but often overlooked.
35. Single Number
Why: Find the unique among pairs.
int single(int[] nums) {
int res = 0;
for (int n : nums) res ^= n;
return res;
}
Complexity: O(n)
Explain: “XOR cancels duplicates because a ⊕ a = 0.”
36. Count Bits (Number of 1s)
This pattern in the DSA cheat sheet is very important from interview point of view.
int count(int n) {
int cnt=0;
while(n>0) { cnt += n&1; n>>=1; }
return cnt;
}
Explain: “Repeatedly shift and count the lowest bit.”
37. Power of Two Check
boolean isPow2(int n) {
return n>0 && (n&(n-1))==0;
}
Explain: “Power of two has only one bit set.”
38. Subsets Using Bits
for (int mask=0; mask<(1<<n); mask++) {
List<Integer> subset = new ArrayList<>();
for (int i=0; i<n; i++)
if ((mask & (1<<i)) != 0) subset.add(nums[i]);
}
Explain: “Each subset corresponds to a binary mask.”
Bit Manipulation Patterns – Interview Insight:
- Single Number, Count Bits: common in easy/medium interviews.
- Focus on XOR properties and mask manipulation.
- Appears occasionally in FAANG “tricky” problems.
Linked List – DSA Cheat Sheet
39. Reverse a Linked List
When to use: Reversing order of nodes.
Idea: Iteratively rewire .next pointers or recursively reverse.
// Iterative
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
head = prev;
Complexity: O(n)
Interview phrasing: “I iteratively reversed the linked list by rewiring the next pointers.”
40. Detect Cycle
When to use: Check if the list loops back.
Idea: Use slow and fast pointers (Floyd’s Tortoise & Hare).
ListNode slow = head, fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast) return true;
}
return false;
Complexity: O(n) time, O(1) space
Interview phrasing: “I used two pointers moving at different speeds to detect a cycle.”
41. Merge Two Sorted Lists
When to use: Combine two ordered lists efficiently.
Idea: Compare nodes and build a new sorted list.
ListNode dummy = new ListNode(0), tail = dummy;
while(l1 != null && l2 != null){
if(l1.val < l2.val){ tail.next = l1; l1 = l1.next; }
else { tail.next = l2; l2 = l2.next; }
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
Complexity: O(n + m)
Interview phrasing: “I merged two sorted lists by choosing the smaller node step by step.”
Linked List Basics – Interview Insight:
- Single/double linked list reversal, cycle detection, merge sorted lists: core FAANG patterns.
- Medium difficulty; pointer manipulation errors are common pitfalls.
- Good for live coding rounds.
Heaps & Priority Queue – DSA Cheat Sheet
For more on heaps & priority queues part of the DSA cheat sheet, please check Heap Sort Algorithm Explained: A Beginner Friendly Guide with Leetcode Solutions In Java.
42. Find Kth Largest Element
When to use: Quickly find top elements in a list.
Idea: Use a min-heap of size k.
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int n : nums){
pq.add(n);
if(pq.size() > k) pq.poll();
}
return pq.peek();
Complexity: O(n log k)
Interview phrasing: “I maintained a min-heap of size k to track the kth largest efficiently.”
43. Top K Frequent Elements
When to use: Frequency-based selection.
Idea: Count elements → heap of top k.
Map<Integer,Integer> freq = new HashMap<>();
for(int n : nums) freq.put(n, freq.getOrDefault(n,0)+1);
PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->freq.get(a)-freq.get(b));
for(int n : freq.keySet()){
pq.add(n);
if(pq.size() > k) pq.poll();
}
return new ArrayList<>(pq);
Complexity: O(n log k)
Interview phrasing: “I combined a frequency map with a min-heap to get top k elements.”
44. Merge K Sorted Lists
When to use: Combine multiple sorted lists.
Idea: Use a priority queue to always pick the smallest current node.
PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(a->a.val));
for(ListNode l : lists) if(l != null) pq.add(l);
ListNode dummy = new ListNode(0), tail = dummy;
while(!pq.isEmpty()){
tail.next = pq.poll();
tail = tail.next;
if(tail.next != null) pq.add(tail.next);
}
return dummy.next;
Complexity: O(N log k), N = total nodes
Interview phrasing: “I used a min-heap to merge k sorted lists efficiently.”
Heaps & Priority Queue – Interview Insight:
- Top-K problems, sliding window maximum, and scheduling problems.
- PriorityQueue/heap usage is essential.
- Medium difficulty; focus on insert/remove operations and time complexity.
Hashing Patterns – DSA Cheat Sheet
45. Two Sum / Pair Sum
When to use: Find two numbers adding up to target.
Idea: HashMap for complement lookup.
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
int comp = target - nums[i];
if(map.containsKey(comp)) return new int[]{map.get(comp), i};
map.put(nums[i], i);
}
Complexity: O(n)
Interview phrasing: “I used a hash map to find complements in one pass.”
46. Subarray with Given Sum
When to use: Count subarrays summing to k.
Idea: Prefix sum + HashMap frequency.
Map<Integer,Integer> map = new HashMap<>();
map.put(0,1); int sum=0, count=0;
for(int n : nums){
sum += n;
count += map.getOrDefault(sum-k,0);
map.put(sum, map.getOrDefault(sum,0)+1);
}
Complexity: O(n)
Interview phrasing: “I tracked prefix sums and their frequency to find subarrays.”
47. Anagram Grouping
When to use: Group words that are anagrams.
Idea: Sort string or use character count as key.
Map<String,List<String>> map = new HashMap<>();
for(String s : strs){
char[] ch = s.toCharArray(); Arrays.sort(ch);
String key = new String(ch);
map.computeIfAbsent(key, k->new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
Complexity: O(n * k log k), k = word length
Interview phrasing: “I used sorted character strings as keys to group anagrams.”
Hashing Patterns – Interview Insight:
- Frequency maps, two-sum, anagrams: extremely common in FAANG interviews.
- Usually easy/medium; focus on O(1) lookups and collision handling.
Sorting Algorithms – DSA Cheat Sheet
48. Quick Sort
When to use: General-purpose fast sorting.
Idea: Partition array and recursively sort partitions.
void quickSort(int[] arr, int low, int high){
if(low<high){
int p = partition(arr,low,high);
quickSort(arr,low,p-1);
quickSort(arr,p+1,high);
}
}
Complexity: O(n log n) avg, O(n²) worst
Interview phrasing: “I used quick sort with divide-and-conquer partitioning.”
49. Merge Sort
When to use: Stable sort, divide and conquer.
Idea: Recursively split, sort, and merge.
void mergeSort(int[] arr, int l, int r){
if(l<r){
int m = l + (r-l)/2;
mergeSort(arr,l,m);
mergeSort(arr,m+1,r);
merge(arr,l,m,r);
}
}
Complexity: O(n log n)
Interview phrasing: “Merge sort recursively splits and merges arrays.”
50. Counting / Radix Sort
When to use: Non-comparison sort for integers.
Idea: Count occurrences or sort digit by digit.
int max = Arrays.stream(arr).max().getAsInt();
int[] count = new int[max+1];
for(int n : arr) count[n]++;
int idx=0;
for(int i=0;i<count.length;i++)
while(count[i]-- > 0) arr[idx++] = i;
Complexity: O(n + k), k = max element
Interview phrasing: “Counting sort counts frequencies for O(n) sorting.”
51. Heap Sort
For more on the Heap sort algorithm part of the DSA cheat sheet, please check Heap Sort Algorithm Explained: A Beginner Friendly Guide with Leetcode Solutions In Java.
When to use: Sorting via heap.
Idea: Build max-heap and extract max iteratively.
for(int i=arr.length/2-1;i>=0;i--) heapify(arr,arr.length,i);
for(int i=arr.length-1;i>=0;i--){
int temp=arr[0]; arr[0]=arr[i]; arr[i]=temp;
heapify(arr,i,0);
}
Complexity: O(n log n)
Interview phrasing: “I built a max-heap and repeatedly extracted the largest element.”
Sorting Algorithms Overview – Interview Insight:
- Quick, Merge, Heap sort: theoretical knowledge expected.
- Stability, time/space complexity, and worst-case scenarios are often asked.
- Applies to interview questions needing sorted input or optimization.
Cheat Tables – DSA Cheat Sheet
1. Big-O Table – Data Structures & Operations
| Data Structure | Access | Search | Insertion | Deletion |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) |
| Queue | O(n) | O(n) | O(1) | O(1) |
| Linked List | O(n) | O(n) | O(1) | O(1) |
| Hash Table (Avg) | O(1) | O(1) | O(1) | O(1) |
| Hash Table (Worst) | O(n) | O(n) | O(n) | O(n) |
| Binary Search Tree | O(log n) | O(log n) | O(log n) | O(log n) |
| AVL / Balanced BST | O(log n) | O(log n) | O(log n) | O(log n) |
2. Sorting Complexity Table
| Sorting Algorithm | Best Case | Average Case | Worst Case | Space |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) |
3. Graph Traversal Complexity Table
| Algorithm | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| BFS (Adj List) | O(V + E) | O(V) | Level-wise traversal |
| DFS (Adj List) | O(V + E) | O(V) | Recursive or stack-based |
| Dijkstra (Min-Heap) | O((V + E) log V) | O(V + E) | Non-negative weights |
| Bellman-Ford | O(V × E) | O(V) | Can handle negative weights |
| Topological Sort | O(V + E) | O(V) | Only for DAG |
| Floyd-Warshall | O(V³) | O(V²) | All-pairs shortest paths |
7-Day DSA Revision Plan (Java-Focused DSA Cheat Sheet)
| Day | Focus | Key Patterns | Target Practice |
|---|---|---|---|
| 1 | Arrays & Strings | Sliding Window, Two Pointers | LeetCode 1, 15, 3, 121 |
| 2 | HashMap Logic | Frequency, Anagrams | LeetCode 49, 560 |
| 3 | Stacks & Queues | Monotonic Stack, BFS | LeetCode 20, 739, 207 |
| 4 | Trees & Graphs | Traversals, DFS/BFS, LCA | LeetCode 102, 236, 200 |
| 5 | DP Basics | Climb Stairs, Coin Change | LeetCode 70, 322 |
| 6 | DP Advanced | LIS, Knapsack, LCS | LeetCode 300, 1143 |
| 7 | Greedy + Bits | Activity, XOR tricks | LeetCode 56, 136 |
Wrap-Up – DSA Cheat Sheet
If you’ve read till here — you’re already ahead of 80% of candidates. This DSA cheat sheet will help you in exams/ interviews. Use this DSA cheat sheet wisely and effectively.
But don’t just read patterns. Code them. Tweak them. Break them. Rebuild them.
Here’s the mindset:
Every algorithm is a story.
Learn the why before the how.
And when you forget, come back to this DSA cheat sheet — your friendly Java mentor will still be waiting. 💪
Frequently Asked Questions (FAQ) – DSA Cheat Sheet
Q1: What is the best way to use this DSA cheat sheet?
A: Use it for quick revision before coding interviews. Focus on patterns, practice the code snippets, and revisit tricky algorithms regularly.
Q2: Can I rely only on this DSA cheat sheet to prepare for interviews?
A: No, this is a revision tool. Pair it with problem-solving practice on platforms like LeetCode, HackerRank, or Codeforces for best results.
Q3: Is this DSA cheat sheet suitable for beginners in Java?
A: Yes. It includes Java snippets for each pattern and explains the intuition, complexity, and interview phrasing.
Q4: How often should I revise using this DSA cheat sheet?
A: Ideally, go through it once a week and use the 7-day revision plan included. Repetition helps in memorizing patterns effectively.
Q5: Are all DSA topics covered here?
A: Most common patterns and algorithms are included. Advanced topics like graphs, DP variations, and Greedy patterns are also covered, but continual problem-solving is recommended.
Q6: Can I download this DSA cheat sheet as a PDF?
A: Yes, we provide a downloadable PDF version for offline practice and reference.
Q7: Does this DSA cheat sheet help with coding interviews at top tech companies?
A: Absolutely. It’s designed to cover patterns and problem types frequently asked at FAANG and other tech interviews.
Q8: Are the code snippets tested?
A: Yes. All Java snippets are concise, runnable, and optimized for clarity and learning.
Q9: Can I use this DSA cheat sheet for competitive programming?
A: Yes, it’s a quick reference for patterns and algorithms, but in contests, you’ll need to write the code yourself.
Q10: How is this DSA cheat sheet updated?
A: It’s periodically revised based on new patterns, interview trends, and user feedback to ensure it stays relevant.
To keep yourself up to date with our latest content, please subscribe to our newsletter by dropping your email address here: Signup for Our Newsletter.
Please follow us on Medium.
Further Reading
- How to crack technical interview – Google, Amazon & more
- How to Prepare for and Crack the Coding Interview
- Machine Coding Round – What is it & how to crack it
- Digital Wallet Design – Machine Coding Round Solution
- Best Coding Platform To Become A Coding Expert
- The ultimate guide to interview preparation