Data Structures & Algorithms (Java) – Interview

Prep Guide
Building a strong foundation in DSA is critical for coding interviews. Below is a structured overview from
basic to advanced topics, with brief explanations and Java examples. Each concept is linked to how it
appears in real interviews (e.g. typical problems).

Time & Space Complexity

• Definition: Measures how runtime or memory grows with input size. Time complexity
quantifies operations as a function of input size (Big-O notation), while space complexity
measures additional memory used 1 .
• Why it matters: Always evaluate an algorithm’s Big-O. For example, searching an unsorted array
is O(n), whereas binary search on a sorted array is O(log n) 2 . Interviewers expect you to justify
complexities.

Basic Data Structures

Arrays

• Structure: Contiguous memory of fixed-size elements (same type). Each element accessed by
index (0-based) 3 . Ideal for constant-time access (O(1) reads/writes).
• Usage in interviews: Array problems are ubiquitous (e.g. subarray sums, sorting, two-pointer,
sliding window). Common operations include traversal, sorting, and search.
• Key operations:
• Access by index: int x = arr[i]; (O(1)).
• Looping: for(int i=0; i<n; i++) {...} (O(n)).
• Example (prefix sum): Precompute cumulative sums to answer range-sum queries fast.

int[] arr = {1,2,3,4};

int[] prefix = new int[[Link]];
prefix[0] = arr[0];
for(int i=1; i<[Link]; i++) {
prefix[i] = prefix[i-1] + arr[i];
}
// Sum of arr[1..3] = prefix[3] - prefix[0] = 9
[Link](prefix[3] - prefix[0]);

Use cases: Sliding-window or prefix-sum techniques optimize brute-force subarray sums 4 5 .

Strings

• Concept: In Java, String is an immutable object holding a sequence of characters. Once

created, its contents cannot change 6 . (Concatenation creates new strings.)

1
 • Usage: String problems (palindromes, anagrams, parsing) are common. E.g. checking if a string
is a palindrome can be done with two-pointer sweep on a char array or StringBuilder .
• Example: Reverse a string using StringBuilder :

String s = "hello";
String rev = new StringBuilder(s).reverse().toString();
[Link](rev); // "olleh"

• Key points: Remember Java string pool and immutability – e.g. using StringBuilder or
StringBuffer for mutable string operations in interview problems can improve performance.

Linked Lists

• Structure: A sequence of nodes where each node contains data and a reference ( next ) to the
next node. No contiguous memory is needed 7 .
• Variants: Singly-linked (each node → next), doubly-linked (each node ↔ next and previous).
• Advantages: Inserting/deleting at head or middle is O(1) if you have the node (no shifting
elements as in arrays) 7 .
• Usage: Common interview tasks include reversing a list, detecting cycles (Floyd’s cycle detection),
merging lists, finding the k-th node from end, etc.
• Example (cycle detection – fast & slow pointers):

class ListNode { int val; ListNode next; }

boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while(fast!=null && [Link]!=null) {
slow = [Link];
fast = [Link];
if(slow == fast) return true; // cycle found
}
return false;
}

Pattern: This uses the fast & slow pointer technique 8 to detect loops in O(n) time.

Stacks & Queues

• Stack: LIFO (Last-In-First-Out) linear structure 9 . Push to add, pop to remove the most recent
element. Think of a stack of plates 9 .
• Usage: Stack is used in DFS recursion, balancing symbols (parentheses), expression evaluation
(infix→postfix), and backtracking (e.g. undo operations).
• Java: Use Deque<Integer> stack = new ArrayDeque<>(); or Stack<> .
• Queue: FIFO (First-In-First-Out) linear structure 10 . Enqueue to add, dequeue to remove the
oldest element.
• Usage: Queue underpins BFS (see graph section), scheduling (CPU tasks), and sliding-window
problems.
• Java: Use Queue<Integer> queue = new LinkedList<>(); .

2
Hash Tables (HashMap)

• Concept: Stores key-value pairs with (on average) constant-time operations. A hash function
maps keys to array indices 11 .
• Usage: Extremely common in interviews for counting/frequency (e.g. two-sum problem,
grouping anagrams, caching). Example: use a HashMap<String, Integer> to count
occurrences.
• Properties: Typical operations (put, get, remove) are O(1) average-case. Handles collisions (often
via chaining or open addressing).
• Example (two-sum):

public int[] twoSum(int[] arr, int target) {

Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<[Link];i++){
int need = target - arr[i];
if([Link](need)) {
return new int[]{[Link](need), i};
}
[Link](arr[i], i);
}
return new int[]{-1,-1};
}

Pattern: Hash tables often optimize naive O(n²) search to O(n).

Trees (Binary Trees & BSTs)

• Binary Tree: Hierarchical structure where each node has at most two children (left/right) 12 .
Common operations: insert, search, traverse (preorder/inorder/postorder), depth-first.
• Binary Search Tree (BST): A special binary tree where left subtree < node < right subtree.
Enables O(log n) average search/insert if balanced.
• Usage: Many problems use tree traversals or BST properties (e.g. validating BST, LCA, range
queries).
• Heaps: A complete binary tree supporting heap property 13 (min-heap: parent ≤ children; max-
heap: parent ≥ children).
• Efficient min/max retrieval: O(1) to peek, O(log n) to insert/pop.
• Java: PriorityQueue<Integer> pq = new PriorityQueue<>(); (min-heap by default).
• Usage: Interview tasks include “find k-th largest element” (using a min-heap of size k) or heap
sort.

Graphs

• Definition: A graph is a non-linear data structure with a set of vertices (nodes) and edges
connecting pairs of vertices 14 . Can be directed or undirected, weighted or unweighted.
• Representation: Commonly adjacency list ( List<List<Integer>> ) or adjacency matrix.
• Usage: Graph problems are frequent (networking, social graphs). Typical tasks include traversal
(BFS/DFS), shortest paths, connectivity, cycles, and spanning trees.
• Key algorithms:
• BFS (Breadth-First Search) – level-order traversal using a queue; finds shortest path in
unweighted graph 15 .

3
 • DFS (Depth-First Search) – explores as far as possible along each branch before backtracking;
uses recursion/stack 16 .
• Code example (BFS, Java):

void bfs(int start, List<List<Integer>> adj) {

boolean[] vis = new boolean[[Link]()];
Queue<Integer> q = new LinkedList<>();
[Link](start); vis[start]=true;
while(![Link]()){
int u = [Link]();
[Link](u + " ");
for(int v: [Link](u)){
if(!vis[v]) { vis[v]=true; [Link](v); }
}
}
}

• Cycle detection: In directed graphs, use DFS or BFS with recursion stack/visited flags.
• Trees vs Graphs: Remember that a tree is a special acyclic connected graph.

Tries (Prefix Trees)

• Structure: A tree where each node represents a character of a string. Strings are stored by paths
from root to leaf 17 . Commonly, each node has up to 26 (or more) child pointers (for letters/
digits).
• Usage: Efficient for prefix-based search (autocomplete, dictionary). For example, find all words
sharing a prefix in O(len(prefix)). Also used in IP routing (bitwise trie), etc.
• Example: Insert and search in a trie (conceptual):

class TrieNode {
TrieNode[] next = new TrieNode[26];
boolean isWord;
}
// Insert “cat”:
TrieNode root = new TrieNode();
String word = "cat";
TrieNode cur = root;
for(char c: [Link]()) {
int idx = c - 'a';
if([Link][idx]==null) [Link][idx] = new TrieNode();
cur = [Link][idx];
}
[Link] = true;

Segment Trees (Advanced)

• Definition: A tree built over an array that enables fast range queries and updates 18 . Each node
covers an interval (segment) of the array.
• Use case: When you need to repeatedly query/update sums/min/max over subarrays in O(log n)
time.

4
 • Usage: Interview problems include Range Sum Query, Range Minimum Query with updates.
• Concept: Build in O(n), query/update each in O(log n) by traversing relevant tree branches 18 .

Union-Find (Disjoint Set) (Advanced)

• Definition: Data structure managing disjoint sets with two operations: find(x) (which set an
element belongs to) and union(a,b) (merge sets). It stores a forest of trees with path
compression and union by rank for efficiency.
• Cited: “A disjoint-set (union-find) stores a partition of a set into disjoint subsets; it provides
operations for merging sets and finding a representative of a set 19 .”
• Usage: Key in Kruskal’s MST algorithm and connectivity queries (e.g. determine if adding an
edge creates a cycle).
• Example (conceptual): Use an array parent[] where initially parent[i]=i . For edge (u,v),
check if find(u)==find(v) to detect cycle; otherwise union(u,v) 19 .

Algorithm Paradigms & Techniques

Recursion

• Definition: A technique where a function calls itself to solve smaller instances of the same
problem 20 . Each call works on a smaller input until a base case is reached.
• Key points: Always have a base case to stop recursion 20 . Each recursive call adds a stack frame
(memory). Recursive solutions can often be converted to iterative ones (using a stack).
• Usage: Many interview problems (tree traversals, graph DFS, divide-and-conquer like merge
sort) use recursion.
• Example: Factorial

int fact(int n) {
if (n <= 1) return 1; // base case
return n * fact(n - 1); // recursive case
}

Sorting & Searching

• Binary Search: Search a sorted array in O(log n) by repeatedly halving the search space 2 .
Requires random access and sorted data.

int binarySearch(int[] arr, int target) {

int left = 0, right = [Link] - 1;
while (left <= right) {
int mid = left + (right - left)/2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}

Cited: “Binary Search is a searching algorithm on a sorted array, dividing the interval in half each
step 2 .”

5
 • Merge Sort: D&C algorithm that splits array, sorts halves recursively, and merges 21 .
Guaranteed O(n log n) time.
• Quick Sort: D&C algorithm picking a pivot, partitioning around it, then recursively sorting
partitions 22 . Average O(n log n), worst O(n²) if pivot poorly chosen.
• Others: Insertion/Selection (O(n²)), HeapSort (O(n log n)), and Java’s built-in [Link]()
(Timsort for objects, QuickSort/HeapSort for primitives).
• Usage: Be ready to code or explain common sorts. For interview prep, know their time/space
tradeoffs (e.g. merge sort uses O(n) extra space, quicksort can be in-place).

Two-Pointer Technique

• Idea: Use two indices moving through an array (often sorted) to find pairs or subarrays. Start
left=0 and right=n-1 (or both at ends) and move towards each other based on a condition
23 .
• Use cases: Two-sum in sorted array, removing duplicates from sorted array, partitioning, or
finding subarray with a given sum.
• Example (two-sum on sorted array):

boolean twoSumSorted(int[] arr, int target) {

int left = 0, right = [Link]-1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) return true;
if (sum < target) left++;
else right--;
}
return false;
}

Cited: “Two-pointer begins with two corners of the array... move pointers inward based on sum
23 .”

Sliding Window

• Idea: Maintain a window [L..R] over the array/string, adjusting boundaries to satisfy constraints.
Use previous window computation to slide efficiently 5 .
• Use cases: Subarray/substring problems like “longest substring without repeats”, “max sum
subarray of size k”, or any problem involving continuous ranges.
• Pattern: Expand right to grow window, shrink left to discard old elements, and track
desired property (sum, count, etc).
• Example: Longest subarray with sum ≤ K (pseudocode):

int left=0, sum=0, maxLen=0;

for(int right=0; right<n; right++){
sum += arr[right];
while(sum > K && left<=right){
sum -= arr[left++];
}
maxLen = [Link](maxLen, right-left+1);
}

6
 Cited: “Sliding Window uses results of the previous window for next computations 5 .”

Prefix Sum

• Idea: Precompute sums of prefixes of an array so that range sums can be answered in O(1). E.g.
prefix[i] = arr[0]+...+arr[i] .
• Usage: Useful in array subrange sum/count queries. Combine with hash maps for subarray sum
equals K problems (store prefix[i] counts).
• Cited: Defined as prefixSum[i] = arr[0] + ... + arr[i] 4 .

Bit Manipulation

• Concept: Using bitwise operators ( &, |, ^, <<, >>, ~ ) to solve problems efficiently 24 .
• Tips:
• x & (x-1) removes the lowest set bit (useful to count bits).
• x ^ y computes difference masks (odd counts detection).
• Check even/odd with x & 1 .
• Use cases: Power-of-two checks, bit masks for subsets, encoding sets. In interviews, bit tricks
often optimize brute force (e.g. use bitmask to iterate subsets of up to 20 items).
• Cited: “Bit manipulation uses bitwise operators on binary representations to optimize solutions
24 .”

Divide & Conquer

• Idea: Break problem into independent subproblems, solve each recursively, and combine
results.
• Examples: Merge sort and quicksort are classic D&C sorts 22 21 . Binary search also D&C (split
search space in half).
• Pattern: Often recursion-based. Emphasize splitting input (e.g. split array into two halves).
• When to use: When problem naturally divides (binary search, sorts, closest pair, Karatsuba
multiplication, etc.).

Greedy Algorithms

• Definition: At each step, pick the locally optimal choice hoping to reach a global optimum 25 .
No backtracking; once a choice is made it’s never undone.
• Use cases: Interval scheduling (pick earliest finishing task), Dijkstra’s algorithm (choose next
closest node) 15 , Prim’s MST, Huffman coding (choose two smallest weights each time), etc.
• Caution: Greedy does not always yield correct solution (unless problem has the “greedy choice
property”).
• Cited: “Greedy algorithms make the locally optimal choice at each stage 25 .”

Backtracking

• Definition: Systematically search through candidate solutions, abandoning (“backtracking”) a

path as soon as it fails to satisfy constraints 26 . Essentially recursion + undo steps.
• Use cases: Permutations/combinations generation, N-Queens, Sudoku, subset sum, Hamiltonian
paths.
• Pattern: Choice → recurse → undo (backtrack). Use pruning to cut branches (e.g. if partial
solution violates constraints).
• Cited: “Backtracking incrementally builds solutions and undoes choices on dead ends 26 .”

7
Dynamic Programming (DP)

• Concept: For problems with optimal substructure and overlapping subproblems, store results
of subproblems to avoid recomputation 27 .
• Top-down (Memoization): Write recursive solution but cache results in a table (often Map or
array).
• Bottom-up (Tabulation): Iteratively fill a DP table from base cases up to final solution.
• State reduction: Optimize space by only storing needed previous rows or columns. For example,
Fibonacci DP only needs last two values.
• Example (Fibonacci with memo):

Map<Integer,Integer> memo = new HashMap<>();

int fib(int n) {
if(n<=1) return n;
if([Link](n)) return [Link](n);
int res = fib(n-1) + fib(n-2);
[Link](n, res);
return res;
}

• Common patterns:
• Knapsack, LIS, LCS, Coin Change: Classic DP patterns.
• DP Optimization: Tabulation vs. memoization, and reducing state space (e.g. sliding window
over DP rows).
• Cited: “DP breaks a complex problem into subproblems, storing their results to avoid
recomputing 27 .”

Graph Algorithms (Advanced)

• BFS (Breadth-First Search): Level-order traversal using a queue. Finds shortest path in
unweighted graphs 15 . Useful to find minimum moves/steps, shortest path (unweighted), and
in bipartite checking.
• DFS (Depth-First Search): Explore as deep as possible before backtracking (can use recursion).
Useful for connectivity, topological sort, and detecting cycles 16 .
• Dijkstra’s Algorithm: Finds shortest paths from a source to all nodes in a weighted graph with
non-negative weights. Uses a priority queue (min-heap) to pick the closest unvisited node each
time 28 . Time ~O(E log V).
• Kruskal’s Algorithm: Builds a Minimum Spanning Tree (MST) by sorting edges by weight and
adding them if they don’t form a cycle. Utilizes Union-Find to detect cycles. Cited: “Kruskal finds
the Minimum Spanning Tree by adding lowest-weight edges while skipping those that create
cycles 29 .”
• Prim’s Algorithm: Builds MST by starting from one vertex and repeatedly adding the cheapest
edge from the growing tree to a new vertex 30 . Another greedy MST approach (equivalent
outcome to Kruskal on connected graphs). Cited: “Prim’s algorithm is a greedy method to find an
MST in a weighted undirected graph 30 .”
• Topological Sort: Produces a linear ordering of vertices in a Directed Acyclic Graph (DAG) so that
for every edge u→v, u comes before v 31 . Commonly done via DFS (post-order) or Kahn’s
algorithm (BFS with in-degree). Used to schedule tasks with dependencies.
• A* (A-star) Search: A heuristic pathfinding algorithm (best-first search). It uses a priority queue
ordered by f = g + h, where g = cost so far, h = estimated remaining cost (heuristic) 32 . Finds

8
 shortest path in weighted graphs faster than Dijkstra if a good heuristic is available. Used in
game maps and routing.

Patterns & Techniques for Brute-Force Optimization

• Fast & Slow Pointers: (See linked list section.) Also used in array problems for cycle detection or
finding midpoints. E.g. find middle element: advance one pointer by 2 steps (fast) and one by 1
step (slow) each loop.
• Meet-in-the-Middle: Split problem in two (often for subset problems) to reduce exponential
time. Not often required at entry level, but good to mention.
• Greedy-Pruning: Even in backtracking/recursion, use greedy insight to cut branches early.
• State Caching (Memo): Use hash maps or arrays to store intermediate results (DP).
• Bitmasking: Represent subsets as bitmasks to iterate efficiently (for N up to ~20).
• Two-Pointers & Sliding Window: As above, for linear-time subarray problems.
• Prefix/Suffix Caches: Store cumulative information (sums, products, mins, etc.) in auxiliary
arrays to answer queries or speed-up brute loops.

Each of these patterns helps transform brute-force O(n²) or O(2ⁿ) approaches into more efficient
solutions when applicable.

This guide covers the essentials and advanced topics (segment trees, tries, union-find, graph
algorithms, DP optimizations) for interview readiness. Use Java idioms ( ArrayList , HashMap ,
PriorityQueue , Deque , etc.) and practice coding these structures and algorithms. Understanding
when and how each concept is used (e.g. “sliding window for subarrays”, “DFS for graph traversal”, “DP
for optimization problems”) will prepare you for typical questions at companies like Google or Amazon.

Sources: Authoritative definitions and explanations from standard DSA references and tutorials 3 5

4 23 8 15 16 28 29 30 19 18 17 1 20 22 21 2 6 26 25 27 31 .

1 Time complexities of different data structures | GeeksforGeeks

[Link]

2 Binary Search Algorithm – Iterative and Recursive Implementation | GeeksforGeeks

[Link]

3 Understanding the Array Data Structure: Characteristics & Operations

[Link]

4 Prefix Sum Array – Implementation and Applications | GeeksforGeeks

[Link]

5 Sliding Window Technique | GeeksforGeeks

[Link]

6 Why Java Strings are Immutable? | GeeksforGeeks

[Link]

7 Linked List Data Structure | GeeksforGeeks

[Link]

8 How does Floyd’s slow and fast pointers approach work? | GeeksforGeeks
[Link]

9
 9 Stack Data Structure | GeeksforGeeks
[Link]

10 Queue Data Structure | GeeksforGeeks

[Link]

11 Hash Data Structure

[Link]

12 Binary Tree Data Structure | GeeksforGeeks

[Link]

13 Binary Heap | GeeksforGeeks

[Link]

14 Introduction to Graph Data Structure | GeeksforGeeks

[Link]

15 Breadth First Search or BFS for a Graph | GeeksforGeeks

[Link]

16 Depth First Search or DFS for a Graph | GeeksforGeeks

[Link]

17 Trie Data Structure | GeeksforGeeks

[Link]

18 Segment Tree | GeeksforGeeks

[Link]

19 Disjoint-set data structure - Wikipedia

[Link]

20 Introduction to Recursion | GeeksforGeeks

[Link]

21 3-way Merge Sort | GeeksforGeeks

[Link]

22 Quick Sort | GeeksforGeeks

[Link]

23 Two Pointers Technique | GeeksforGeeks

[Link]

24 Bits manipulation (Important tactics) | GeeksforGeeks

[Link]

25 Greedy algorithm - Wikipedia

[Link]

26 Introduction to Backtracking | GeeksforGeeks

[Link]

27 Overlapping Subproblems Property in Dynamic Programming | DP-1 | GeeksforGeeks

[Link]

28 Dijkstra’s Algorithm to find Shortest Paths from a Source to all | GeeksforGeeks

[Link]

29 DSA Kruskal's Algorithm

[Link]

10
30 Prim's algorithm - Wikipedia
[Link]

31 Topological Sorting | GeeksforGeeks

[Link]

32 A* Search Algorithm | GeeksforGeeks

[Link]

11