Data Structures - Complete Interview Guide

Table of Contents
1. Basic Concepts
2. Arrays

3. Linked Lists
4. Stacks

5. Queues
6. Trees
7. Hash Tables/HashMap

8. Graphs

9. Heaps

10. Advanced Data Structures

11. Algorithms & Complexity

Basic Concepts

1. What is a Data Structure?

Answer: A data structure is a way of organizing and storing data in memory so that it can be accessed
and modified efficiently. It defines the relationship between data elements and the operations that can be
performed on them.

2. Types of Data Structures?

Answer:

1. Linear Data Structures: Array, Linked List, Stack, Queue

2. Non-Linear Data Structures: Tree, Graph

3. Static Data Structures: Array (fixed size)
4. Dynamic Data Structures: Linked List, Stack, Queue (variable size)

3. What is Time Complexity?

Answer: Time complexity measures the amount of time an algorithm takes to complete as a function of
input size. Common notations:

O(1) - Constant time

O(log n) - Logarithmic time
O(n) - Linear time

O(n log n) - Linearithmic time

O(n²) - Quadratic time

4. What is Space Complexity?

Answer: Space complexity measures the amount of memory an algorithm uses as a function of input
size, including both auxiliary space and input space.

5. What is Big O Notation?

Answer: Big O notation describes the upper bound of algorithm's time or space complexity in the worst-
case scenario.

Arrays

6. What is an Array?
Answer: An array is a collection of elements of the same data type stored in contiguous memory
locations, accessed using indices.

7. Advantages and Disadvantages of Arrays?

Answer: Advantages:

Fast access O(1) using index

Memory efficient
Simple to implement

Disadvantages:

Fixed size (static arrays)

Insertion/deletion is expensive O(n)

Memory waste if not fully utilized

8. What is Dynamic Array?

Answer: A dynamic array can resize itself during runtime. Examples: ArrayList (Java), vector (C++), list
(Python).

9. How to find duplicate elements in an array?

Answer:

java
 // Using HashSet
findDuplicates((int
public static void findDuplicates int[[] arr
arr)) {
Set<
Set<Integer
Integer>
> seen = new HashSet
HashSet<
<>();
Set<
Set<Integer
Integer>
> duplicates = new HashSet
HashSet<
<>();

arr)) {
for (int num : arr
seen..add
if (!seen add((num
num))) {
duplicates..add
duplicates add((num
num));
}
}

System.
[Link].
[Link](
println("Duplicates: " + duplicates)
duplicates);
}

10. How to rotate an array?

Answer:

java

// Left rotation by k positions

public static void leftRotate(
leftRotate(int[
int[] arr,
arr, int k)
k) {
int n = arr.
[Link];
length;
n;;
k=k%n

reverse((arr
reverse arr,, 0, k - 1);
reverse((arr
reverse arr,, kk,, n - 1);
reverse((arr
reverse arr,, 0, n - 1);
}

reverse((int
private static void reverse int[[] arr
arr,, int start
start,, int end
end)) {
end)) {
while (start < end
arr[[start
int temp = arr start]];
arr[[start
arr start]] = arr
arr[[end
end]];
arr[[end
arr end]] = temp
temp;;
start++
start++;;
end--
end--;;
}
}

Linked Lists

11. What is a Linked List?

Answer: A linked list is a linear data structure where elements (nodes) are stored in sequence, and each
node contains data and a reference/pointer to the next node.

12. Types of Linked Lists?

Answer:

1. Singly Linked List: Each node points to next node

2. Doubly Linked List: Each node has pointers to both next and previous nodes

3. Circular Linked List: Last node points back to first node

13. Advantages and Disadvantages of Linked Lists?

Answer: Advantages:

Dynamic size

Efficient insertion/deletion O(1)

Memory allocation during runtime

Disadvantages:

No random access O(n)

Extra memory for pointers

Not cache-friendly

14. How to detect a cycle in linked list?

Answer:

java

// Floyd's Cycle Detection (Tortoise and Hare)

hasCycle((ListNode head
public boolean hasCycle head)) {
head;;
ListNode slow = head
head;;
ListNode fast = head

fast..next != null
while (fast != null && fast null)) {
slow..next
slow = slow next;;
fast..next
fast = fast next..next
next;;

fast)) {
if (slow == fast
true;; // Cycle detected
return true
}
}
false;;
return false
}
15. How to reverse a linked list?

Answer:

java

// Iterative approach
reverseList((ListNode head
public ListNode reverseList head)) {
null;;
ListNode prev = null
head;;
ListNode current = head

null)) {
while (current != null
ListNode next = current.
[Link]
next;;
current..next = prev
current prev;;
current;;
prev = current
next;;
current = next
}

prev;; // New head

return prev
}

16. How to find middle element of linked list?

Answer:

java

findMiddle((ListNode head
public ListNode findMiddle head)) {
head;;
ListNode slow = head
head;;
ListNode fast = head

fast..next != null
while (fast != null && fast null)) {
slow..next
slow = slow next;;
fast..next
fast = fast next..next
next;;
}

slow;; // Middle element

return slow
}

17. How to merge two sorted linked lists?

Answer:

java

mergeTwoLists((ListNode l1
public ListNode mergeTwoLists l1,, ListNode l2
l2)) {
ListNode((0);
ListNode dummy = new ListNode
dummy;;
ListNode current = dummy

null)) {
while (l1 != null && l2 != null
l1..val <= l2
if (l1 l2..val
val)) {
current..next = l1
current l1;;
l1 = l1
l1..next
next;;
} else {
current..next = l2
current l2;;
l2 = l2.
[Link];
next;
}
current..next
current = current next;;
}

// Add remaining elements

current..next = (l1 != null
current null)) ? l1 : l2
l2;;
dummy..next
return dummy next;;
}

18. How to remove nth node from end?

Answer:

java

removeNthFromEnd((ListNode head
public ListNode removeNthFromEnd head,, int n
n)) {
ListNode dummy = new ListNode
ListNode((0);
dummy.
[Link] = head;
head;
dummy;;
ListNode first = dummy
dummy;;
ListNode second = dummy

// Move first pointer n+1 steps ahead

n;; ii++
for (int i = 0; i <= n ++)) {
first..next
first = first next;;
}

// Move both pointers until first reaches end

null)) {
while (first != null
first..next
first = first next;;
second..next
second = second next;;
}

// Remove the nth node

second..next = second
second second..next
next..next
next;;
dummy..next
return dummy next;;
}
Stacks

19. What is a Stack?

Answer: A stack is a linear data structure that follows Last In First Out (LIFO) principle. Elements are
added and removed from the same end called "top".

20. Basic Stack Operations?

Answer:

push(): Add element to top - O(1)

pop(): Remove top element - O(1)

peek()/top(): View top element without removing - O(1)

isEmpty(): Check if stack is empty - O(1)

size(): Get number of elements - O(1)

21. Implementation of Stack using Array?

Answer:

java

class Stack {
int[[] stack
private int stack;;
top;;
private int top
capacity;;
private int capacity

Stack((int size
public Stack size)) {
int[[size
stack = new int size]];
size;;
capacity = size
top = -1;
}

push((int item
public void push item)) {
if (top == capacity - 1) {
RuntimeException(("Stack Overflow")
throw new RuntimeException Overflow");
}
stack[[++
stack ++top
top]] = item
item;;
}

pop(() {
public int pop
if (top == -1) {
RuntimeException(("Stack Underflow")
throw new RuntimeException Underflow");
}
stack[[top
return stack top--
--]];
}

public int peek(

peek() {
if (top == -1) {
RuntimeException(("Stack is empty")
throw new RuntimeException empty");
}
stack[[top
return stack top]];
}

isEmpty(() {
public boolean isEmpty
return top == -1;
}
}

22. Implementation of Stack using Linked List?

Answer:

java
 class StackNode {
data;;
int data
next;;
StackNode next

StackNode((int data
StackNode data)) {
this..data = data
this data;;
}
}

class Stack {
top;;
private StackNode top

push((int data
public void push data)) {
StackNode((data
StackNode newNode = new StackNode data));
newNode..next = top
newNode top;;
newNode;;
top = newNode
}

public int pop(

pop() {
if (top == null)
null) {
RuntimeException(("Stack Underflow")
throw new RuntimeException Underflow");
}
top..data
int data = top data;;
top..next
top = top next;;
data;;
return data
}

peek(() {
public int peek
null)) {
if (top == null
RuntimeException(("Stack is empty")
throw new RuntimeException empty");
}
top..data
return top data;;
}
}

23. Applications of Stack?

Answer:

Expression evaluation and conversion

Function call management

Undo operations
Browser back button

Syntax parsing
Backtracking algorithms

24. How to check balanced parentheses using stack?

Answer:

java

isBalanced((String ss)) {
public boolean isBalanced
Stack<
Stack<Character
Character>
> stack = new Stack
Stack<
<>();

for (char c : ss..toCharArray

toCharArray(()) {
'[')) {
if (c == '(' || c == '{' || c == '['
stack..push
stack push((c);
']')) {
} else if (c == ')' || c == '}' || c == ']'
stack..isEmpty
if (stack isEmpty(()) return false
false;;

stack..pop
char top = stack pop(();
'(')) ||
if ((c == ')' && top != '('
(c == '}' && top != '{'
'{')) ||
(c == ']' && top != '['
'['))) {
false;;
return false
}
}
}

stack..isEmpty
return stack isEmpty(();
}

Queues

25. What is a Queue?

Answer: A queue is a linear data structure that follows First In First Out (FIFO) principle. Elements are
added at rear and removed from front.

26. Basic Queue Operations?

Answer:

enqueue(): Add element to rear - O(1)

dequeue(): Remove element from front - O(1)

front(): View front element - O(1)

rear(): View rear element - O(1)

isEmpty(): Check if queue is empty - O(1)

27. Types of Queues?

Answer:

1. Simple Queue: Basic FIFO queue

2. Circular Queue: Last position connects to first

3. Priority Queue: Elements have priorities

4. Deque (Double-ended Queue): Insertion/deletion at both ends

28. Implementation of Queue using Array?

Answer:

java

class Queue {
int[[] queue
private int queue;;
private int front,
front, rear,
rear, size,
size, capacity;
capacity;

Queue((int capacity
public Queue capacity)) {
this..capacity = capacity
this capacity;;
int[[capacity
queue = new int capacity]];
front = 0;
rear = -1;
size = 0;
}

enqueue((int item
public void enqueue item)) {
capacity)) {
if (size == capacity
RuntimeException(("Queue is full")
throw new RuntimeException full");
}
capacity;;
rear = (rear + 1) % capacity
queue[[rear
queue rear]] = item
item;;
size++
size++;;
}

dequeue(() {
public int dequeue
if (size == 0) {
RuntimeException(("Queue is empty")
throw new RuntimeException empty");
}
int item = queue[
queue[front]
front];
capacity;;
front = (front + 1) % capacity
size--
size--;;
item;;
return item
}
}

29. What is Circular Queue?

Answer: A circular queue is a linear data structure where the last position is connected back to the first
position, forming a circle. It efficiently utilizes memory.

30. What is Priority Queue?

Answer: A priority queue is an abstract data type where each element has a priority. Elements are served
based on priority rather than insertion order. Usually implemented using heaps.

Trees

31. What is a Tree?

Answer: A tree is a hierarchical data structure consisting of nodes connected by edges. It has a root node
and subtrees of children with no cycles.

32. Tree Terminology?

Answer:

Root: Top node with no parent

Leaf: Node with no children

Height: Longest path from root to leaf

Depth: Distance from root to a node

Degree: Number of children of a node

33. What is Binary Tree?

Answer: A binary tree is a tree where each node has at most two children: left child and right child.

34. Types of Binary Trees?

Answer:

1. Full Binary Tree: Every node has 0 or 2 children

2. Complete Binary Tree: All levels filled except possibly last, filled left to right
3. Perfect Binary Tree: All internal nodes have 2 children, all leaves at same level
4. Balanced Binary Tree: Height difference between left and right subtrees ≤ 1

35. What is Binary Search Tree (BST)?

Answer: A BST is a binary tree where:

Left subtree contains nodes with values less than parent

 Right subtree contains nodes with values greater than parent
Both subtrees are also BSTs

36. BST Operations Time Complexity?

Answer:

Search: O(log n) average, O(n) worst case

Insertion: O(log n) average, O(n) worst case

Deletion: O(log n) average, O(n) worst case

37. Tree Traversal Methods?

Answer:

1. Inorder (Left-Root-Right): For BST, gives sorted order

2. Preorder (Root-Left-Right): Used for copying tree

3. Postorder (Left-Right-Root): Used for deleting tree

4. Level Order (BFS): Level by level traversal

java

// Inorder Traversal
inorder((TreeNode root
public void inorder root)) {
null)) {
if (root != null
inorder((root
inorder root..left
left));
System..out
System out..print
print((root
root..val + " ")
");
inorder((root
inorder root..right
right));
}
}

// Level Order Traversal

levelOrder((TreeNode root
public void levelOrder root)) {
Queue<
Queue<TreeNode
TreeNode>
> queue = new LinkedList
LinkedList<
<>();
queue..offer
queue offer((root
root));

queue..isEmpty
while (!queue isEmpty(()) {
queue..poll
TreeNode node = queue poll(();
System..out
System out..print
print((node
node..val + " ")
");

node..left != null
if (node null)) queue
queue..offer
offer((node
node..left
left));
node..right != null
if (node null)) queue
queue..offer
offer((node
node..right
right));
}
}

38. How to find height of binary tree?

Answer:

java

height((TreeNode root
public int height root)) {
null)) return -1; // or 0 depending on definition
if (root == null

return 1 + Math.
[Link](
max(height(
height(root.
[Link])
left), height(
height(root.
[Link])
right));
}

39. How to check if tree is balanced?

Answer:

java

isBalanced((TreeNode root
public boolean isBalanced root)) {
return checkHeight(
checkHeight(root)
root) != -1;
}

checkHeight((TreeNode root
private int checkHeight root)) {
null)) return 0;
if (root == null

checkHeight((root
int leftHeight = checkHeight root..left
left));
if (leftHeight == -1) return -1;

checkHeight((root
int rightHeight = checkHeight root..right
right));
if (rightHeight == -1) return -1;

Math..abs
if (Math abs((leftHeight - rightHeight
rightHeight)) > 1) {
return -1; // Not balanced
}

Math..max
return Math max((leftHeight
leftHeight,, rightHeight
rightHeight)) + 1;
}

40. What is AVL Tree?

Answer: AVL tree is a self-balancing BST where the height difference between left and right subtrees is at
most 1 for all nodes.

41. What is Red-Black Tree?

Answer: A Red-Black tree is a self-balancing BST where each node has a color (red or black) and follows
specific rules to maintain balance.
Hash Tables/HashMap

42. What is a Hash Table?

Answer: A hash table is a data structure that maps keys to values using a hash function. It provides
average O(1) time complexity for search, insertion, and deletion.

43. What is a Hash Function?

Answer: A hash function converts keys into array indices. A good hash function:

Distributes keys uniformly

Is deterministic

Is fast to compute

44. What is Collision in Hashing?

Answer: Collision occurs when two different keys produce the same hash value.

45. Collision Resolution Techniques?

Answer:

1. Chaining (Open Hashing): Use linked lists at each array index

2. Open Addressing (Closed Hashing):
Linear Probing
Quadratic Probing

Double Hashing

46. What is Load Factor?

Answer: Load factor = Number of elements / Size of hash table. When load factor exceeds threshold
(usually 0.75), hash table is resized.

47. HashMap vs HashTable in Java?

Answer:

HashMap HashTable

Not synchronized Synchronized

Allows null keys/values No null keys/values

Fast performance Slower due to synchronization

Not thread-safe Thread-safe

48. How does HashMap work internally?

Answer:

1. Uses array of buckets

2. Hash function determines bucket index

3. Collisions handled by chaining (linked list/tree)

4. Converts to balanced tree when chain length > 8 (Java 8+)

49. What is ConcurrentHashMap?

Answer: ConcurrentHashMap provides thread-safe operations with better performance than HashTable
by using segment-based locking.

50. HashMap implementation example?

Answer:

java
 class MyHashMap {
private static class Node {
key,, value
int key value;;
next;;
Node next

Node((int key
Node key,, int value
value)) {
this..key = key
this key;;
this..value = value
this value;;
}
}

private Node[
Node[] buckets;
buckets;
16;;
private int capacity = 16

MyHashMap(() {
public MyHashMap
Node[[capacity
buckets = new Node capacity]];
}

private int hash(

hash(int key)
key) {
return key % capacity;
capacity;
}

put((int key
public void put key,, int value
value)) {
hash((key
int index = hash key));
buckets[[index
Node head = buckets index]];

// Update existing key

head;;
Node current = head
null)) {
while (current != null
current..key == key
if (current key)) {
current..value = value
current value;;
return;;
return
}
current..next
current = current next;;
}

// Add new key

Node((key
Node newNode = new Node key,, value
value));
newNode..next = head
newNode head;;
buckets[[index
buckets index]] = newNode
newNode;;
}

get((int key
public int get key)) {
hash((key
int index = hash key));
buckets[[index
Node current = buckets index]];

null)) {
while (current != null
current..key == key
if (current key)) {
current..value
return current value;;
}
current..next
current = current next;;
}

return -1; // Key not found

}
}

Graphs

51. What is a Graph?

Answer: A graph is a non-linear data structure consisting of vertices (nodes) connected by edges. It
represents relationships between objects.

52. Types of Graphs?

Answer:

1. Directed vs Undirected

2. Weighted vs Unweighted
3. Connected vs Disconnected

4. Cyclic vs Acyclic

5. Simple vs Multigraph

53. Graph Representation Methods?

Answer:

1. Adjacency Matrix: 2D array representing edges

2. Adjacency List: Array of lists representing connections
3. Edge List: List of all edges

54. Graph Traversal Algorithms?

Answer:

DFS (Depth-First Search):

java
 dfs((int vertex
public void dfs vertex,, boolean
boolean[[] visited
visited,, List
List<
<List
List<
<Integer
Integer>
>> adj
adj)) {
visited[[vertex
visited vertex]] = true
true;;
System..out
System out..print
print((vertex + " ")
");

adj..get
for (int neighbor : adj get((vertex
vertex))) {
visited[[neighbor
if (!visited neighbor]]) {
dfs((neighbor
dfs neighbor,, visited
visited,, adj
adj));
}
}
}

BFS (Breadth-First Search):

java

bfs((int start
public void bfs start,, List
List<
<List
List<
<Integer
Integer>
>> adj
adj)) {
boolean[[] visited = new boolean
boolean boolean[[adj
adj..size
size(()];
Queue<
Queue<Integer
Integer>
> queue = new LinkedList
LinkedList<
<>();

visited[[start
visited start]] = true
true;;
queue..offer
queue offer((start
start));

queue..isEmpty
while (!queue isEmpty(()) {
queue..poll
int vertex = queue poll(();
System..out
System out..print
print((vertex + " ")
");

adj..get
for (int neighbor : adj get((vertex
vertex))) {
visited[[neighbor
if (!visited neighbor]]) {
visited[[neighbor
visited neighbor]] = true
true;;
queue..offer
queue offer((neighbor
neighbor));
}
}
}
}

55. What is Shortest Path Algorithm?

Answer:

1. Dijkstra's Algorithm: Single source shortest path (non-negative weights)

2. Bellman-Ford: Single source (handles negative weights)

3. Floyd-Warshall: All pairs shortest paths

56. What is Minimum Spanning Tree?

Answer: A spanning tree with minimum total edge weight. Algorithms:

1. Kruskal's Algorithm: Sort edges, use Union-Find

2. Prim's Algorithm: Start from vertex, grow tree greedily

Heaps

57. What is a Heap?

Answer: A heap is a complete binary tree that satisfies the heap property:

Max Heap: Parent ≥ children

Min Heap: Parent ≤ children

58. Heap Operations?

Answer:

Insert: Add element maintaining heap property - O(log n)

Extract Max/Min: Remove root element - O(log n)

Peek: View root element - O(1)

Heapify: Convert array to heap - O(n)

59. How to implement Priority Queue using Heap?

Answer:

java
 class MinHeap {
int[[] heap
private int heap;;
size;;
private int size
capacity;;
private int capacity

MinHeap((int capacity
public MinHeap capacity)) {
this..capacity = capacity
this capacity;;
int[[capacity
heap = new int capacity]];
size = 0;
}

private int parent(

parent(int i)
i) { return (i - 1) / 2; }
leftChild((int ii)) { return 2 * i + 1; }
private int leftChild
rightChild((int ii)) { return 2 * i + 2; }
private int rightChild

insert((int value
public void insert value)) {
capacity)) {
if (size == capacity
RuntimeException(("Heap is full")
throw new RuntimeException full");
}

// Insert at end
heap[[size
heap size]] = value
value;;
size++
size++;;

// Heapify up
heapifyUp((size - 1);
heapifyUp
}

heapifyUp((int index
private void heapifyUp index)) {
heap[[parent
while (index > 0 && heap parent((index
index))] > heap
heap[[index
index]]) {
swap((index
swap index,, parent
parent((index
index)));
parent((index
index = parent index));
}
}

extractMin(() {
public int extractMin
if (size == 0) {
RuntimeException(("Heap is empty")
throw new RuntimeException empty");
}

heap[[0];
int min = heap
heap[
heap[0] = heap[
heap[size - 1];
size--
size--;;
heapifyDown((0);
heapifyDown

min;;
return min
}

heapifyDown((int index
private void heapifyDown index)) {
index;;
int smallest = index
leftChild((index
int left = leftChild index));
rightChild((index
int right = rightChild index));

heap[[left
if (left < size && heap left]] < heap
heap[[smallest
smallest]]) {
left;;
smallest = left
}
if (right < size && heap[
heap[right]
right] < heap[
heap[smallest]
smallest]) {
right;;
smallest = right
}

index)) {
if (smallest != index
swap((index
swap index,, smallest
smallest));
heapifyDown((smallest
heapifyDown smallest));
}
}

swap((int ii,, int jj)) {

private void swap
heap[[i];
int temp = heap
heap[[i] = heap
heap heap[[j];
heap[[j] = temp
heap temp;;
}
}

60. Applications of Heap?

Answer:

Priority Queue implementation

Heap Sort algorithm

Finding kth largest/smallest element

Graph algorithms (Dijkstra's, Prim's)

Advanced Data Structures

61. What is Trie?

Answer: Trie (Prefix Tree) is a tree-like data structure used to store and search strings efficiently. Each
node represents a character.

java
 class TrieNode {
TrieNode[[] children = new TrieNode
TrieNode TrieNode[[26
26]];
false;;
boolean isEndOfWord = false
}

class Trie {
root;;
private TrieNode root

Trie(() {
public Trie
TrieNode(();
root = new TrieNode
}

insert((String word
public void insert word)) {
root;;
TrieNode current = root
word..toCharArray
for (char c : word toCharArray(()) {
'a';;
int index = c - 'a'
current..children
if (current children[[index
index]] == null
null)) {
current..children
current children[[index
index]] = new TrieNode
TrieNode(();
}
current = current.
[Link][
children[index]
index];
}
current..isEndOfWord = true
current true;;
}

search((String word
public boolean search word)) {
root;;
TrieNode current = root
for (char c : word.
[Link](
toCharArray()) {
'a';;
int index = c - 'a'
current..children
if (current children[[index
index]] == null
null)) {
false;;
return false
}
current..children
current = current children[[index
index]];
}
current..isEndOfWord
return current isEndOfWord;;
}
}

62. What is Union-Find (Disjoint Set)?

Answer: Union-Find is a data structure that keeps track of elements partitioned into disjoint sets.
Supports union and find operations efficiently.

63. What is Segment Tree?

Answer: Segment tree is a binary tree used for storing intervals or segments. Allows querying sums,
minimums, maximums over array ranges in O(log n).

64. What is Fenwick Tree (Binary Indexed Tree)?

Answer: A data structure that provides efficient methods for prefix sum calculations and updates in O(log
n) time.

Algorithms & Complexity

65. What is Recursion?

Answer: Recursion is a programming technique where a function calls itself. Must have:

Base case (stopping condition)

Recursive case (function calls itself)

66. What is Dynamic Programming?

Answer: DP is an optimization technique that solves complex problems by breaking them down into
simpler subproblems and storing results to avoid redundant calculations.

67. What is Memoization?

Answer: Memoization is storing results of expensive function calls and returning cached result when
same inputs occur again.

68. Sorting Algorithms Comparison?

Answer:

Algorithm Best Case Average Case Worst Case Space Stable

Bubble Sort O(n) O(n²) O(n²) O(1) Yes

Selection Sort O(n²) O(n²) O(n²) O(1) No

Insertion Sort O(n) O(n²) O(n²) O(1) Yes

Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes

Quick Sort O(n log n) O(n log n) O(n²) O(log n) No

Heap Sort O(n log n) O(n log n) O(n log n) O(1) No

69. What is Binary Search?

Answer:

java
 binarySearch((int
public int binarySearch int[[] arr
arr,, int target
target)) {
arr..length - 1;
int left = 0, right = arr

right)) {
while (left <= right
left)) / 2;
int mid = left + (right - left

arr[[mid
if (arr mid]] == target
target)) {
mid;;
return mid
arr[[mid
} else if (arr mid]] < target
target)) {
left = mid + 1;
} else {
right = mid - 1;
}
}

return -1; // Not found

}

70. What is Two Pointer Technique?

Answer: Two pointer technique uses two pointers to solve problems efficiently. Common patterns:

Opposite ends moving inward

Slow and fast pointers

Sliding window

71. What is Sliding Window Technique?

Answer: Sliding window maintains a subset of elements (window) and slides it through the array to solve
problems efficiently.

72. LinkedHashMap vs HashMap?

Answer:

HashMap: No ordering guaranteed

LinkedHashMap: Maintains insertion order using doubly-linked list

73. TreeMap vs HashMap?

Answer:

HashMap: O(1) operations, no ordering

TreeMap: O(log n) operations, sorted by keys (Red-Black tree)

74. What is HashSet?

Answer: HashSet is a Set implementation using HashMap internally. Stores unique elements with O(1)
average time complexity.

75. How to find intersection of two arrays?

Answer:

java

int[[] intersection
public int intersection((int
int[[] nums1
nums1,, int
int[[] nums2
nums2)) {
Set<
Set<Integer
Integer>
> set1 = new HashSet
HashSet<
<>();
nums1)) {
for (int num : nums1
set1..add
set1 add((num
num));
}

Set<
Set<Integer
Integer>
> result = new HashSet
HashSet<
<>();
nums2)) {
for (int num : nums2
set1..contains
if (set1 contains((num
num))) {
result..add
result add((num
num));
}
}

result..stream
return result stream(().mapToInt
mapToInt((Integer
Integer::::intValue
intValue)).toArray
toArray(();
}

76. What is LRU Cache?

Answer: LRU (Least Recently Used) Cache removes the least recently used item when cache is full.

java
 class LRUCache {
Map<
private Map<Integer
Integer,, Node
Node>
> cache
cache;;
capacity;;
private int capacity
head,, tail
private Node head tail;;

class Node {
key,, value
int key value;;
prev,, next
Node prev next;;

Node((int key
Node key,, int value
value)) {
this..key = key
this key;;
this.
[Link] = value;
value;
}
}

LRUCache((int capacity
public LRUCache capacity)) {
this..capacity = capacity
this capacity;;
HashMap<
cache = new HashMap<>();
head = new Node(
Node(0, 0);
tail = new Node(
Node(0, 0);
head..next = tail
head tail;;
tail..prev = head
tail head;;
}

get((int key
public int get key)) {
cache..get
Node node = cache get((key
key));
if (node == null)
null) return -1;

moveToHead((node
moveToHead node));
node..value
return node value;;
}

put((int key
public void put key,, int value
value)) {
cache..get
Node node = cache get((key
key));

null)) {
if (node == null
Node((key
Node newNode = new Node key,, value
value));
cache..put
cache put((key
key,, newNode
newNode));
addToHead((newNode
addToHead newNode));

cache..size
if (cache size(() > capacity
capacity)) {
Node tail = removeTail(
removeTail();
cache..remove
cache remove((tail
tail..key
key));
}
} else {
node..value = value
node value;;
moveToHead((node
moveToHead node));
}
}

addToHead((Node node
private void addToHead node)) {
node..prev = head
node head;;
node..next = head
node head..next
next;;
head..next
head next..prev = node
node;;
head..next = node
head node;;
}

removeNode((Node node
private void removeNode node)) {
node..prev
node prev..next = node
node..next
next;;
node..next
node next..prev = node
node..prev
prev;;
}

moveToHead((Node node
private void moveToHead node)) {
removeNode((node
removeNode node));
addToHead(
addToHead(node)
node);
}

removeTail(() {
private Node removeTail
tail..prev
Node lastNode = tail prev;;
removeNode((lastNode
removeNode lastNode));
lastNode;;
return lastNode
}
}

77. What is Morris Traversal?

Answer: Morris traversal is an inorder tree traversal algorithm that uses O(1) space by temporarily
modifying the tree structure.

78. What is Topological Sort?

Answer: Topological sorting of a Directed Acyclic Graph (DAG) is a linear ordering of vertices such that
for every directed edge (u,v), vertex u comes before v.

79. What is Strongly Connected Components?

Answer: In a directed graph, strongly connected components are maximal sets of vertices such that
there's a path from every vertex to every other vertex in the component.

80. What is Kadane's Algorithm?

Answer: Algorithm to find maximum sum contiguous subarray in O(n) time.

java
 maxSubArray((int
public int maxSubArray int[[] nums
nums)) {
nums[[0];
int maxSoFar = nums
nums[[0];
int maxEndingHere = nums

nums..length
for (int i = 1; i < nums length;; ii++
++)) {
Math..max
maxEndingHere = Math max((nums
nums[[i], maxEndingHere + nums
nums[[i]);
Math..max
maxSoFar = Math max((maxSoFar
maxSoFar,, maxEndingHere
maxEndingHere));
}

maxSoFar;;
return maxSoFar
}

Additional Important Questions

81. How to implement Stack using Queue?

Answer:

java

class MyStack {
Queue<
private Queue<Integer
Integer>
> q1 = new LinkedList
LinkedList<
<>();
Queue<
private Queue<Integer
Integer>
> q2 = new LinkedList
LinkedList<
<>();

push((int xx)) {
public void push
q2..offer
q2 offer((x);
q1..isEmpty
while (!q1 isEmpty(()) {
q2..offer
q2 offer((q1
q1..poll
poll(());
}
Queue<
Queue<Integer
Integer>
> temp = q1
q1;;
q1 = q2;
q2;
temp;;
q2 = temp
}

pop(() {
public int pop
q1..poll
return q1 poll(();
}

top(() {
public int top
q1..peek
return q1 peek(();
}

empty(() {
public boolean empty
q1..isEmpty
return q1 isEmpty(();
}
}

82. How to implement Queue using Stack?

Answer:

java

class MyQueue {
Stack<
private Stack<Integer
Integer>
> input = new Stack
Stack<
<>();
private Stack<
Stack<Integer>
Integer> output = new Stack<
Stack<>();

push((int xx)) {
public void push
input..push
input push((x);
}

pop(() {
public int pop
peek(();
peek
return output.
[Link](
pop();
}

peek(() {
public int peek
output..empty
if (output empty(()) {
input..empty
while (!input empty(()) {
output..push
output push((input
input..pop
pop(());
}
}
output..peek
return output peek(();
}

empty(() {
public boolean empty
input..empty
return input empty(() && output
output..empty
empty(();
}
}

83. How to find kth largest element?

Answer:

java
 // Using Min Heap
findKthLargest((int
public int findKthLargest int[[] nums
nums,, int kk)) {
PriorityQueue<
PriorityQueue<Integer
Integer>
> minHeap = new PriorityQueue
PriorityQueue<
<>();

nums)) {
for (int num : nums
minHeap..offer
minHeap offer((num
num));
minHeap..size
if (minHeap size(() > kk)) {
minHeap..poll
minHeap poll(();
}
}

return minHeap.
[Link](
peek();
}

84. What is Dutch National Flag Problem?

Answer: Sorting array containing only 0s, 1s, and 2s in O(n) time using three pointers.

java

sortColors((int
public void sortColors int[[] nums
nums)) {
int low = 0, mid = 0, high = nums.
[Link] - 1;

high)) {
while (mid <= high
nums[[mid
if (nums mid]] == 0) {
swap((nums
swap nums,, low
low++
++,, mid
mid++
++));
nums[[mid
} else if (nums mid]] == 1) {
mid++
mid++;;
} else {
swap(
swap(nums,
nums, mid,
mid, high--
high--));
}
}
}

85. How to detect and remove cycle in linked list?

Answer:

java

detectAndRemoveCycle((ListNode head
public ListNode detectAndRemoveCycle head)) {
head..next == null
if (head == null || head null)) return head
head;;

head,, fast = head

ListNode slow = head head;;

// Detect cycle
fast..next != null
while (fast != null && fast null)) {
slow = slow.
[Link];
next;
fast..next
fast = fast next..next
next;;
fast)) break
if (slow == fast break;;
}

fast..next == null
if (fast == null || fast null)) return head
head;; // No cycle

// Find start of cycle

head;;
slow = head
fast)) {
while (slow != fast
slow..next
slow = slow next;;
fast..next
fast = fast next;;
}

// Remove cycle
while (fast.
[Link] != slow)
slow) {
fast..next
fast = fast next;;
}
fast..next = null
fast null;;

head;;
return head
}

86. How to find if two strings are anagrams?

Answer:

java

isAnagram((String ss,, String tt)) {

public boolean isAnagram
length(() != tt..length
if ([Link] length(()) return false
false;;

int[[] count = new int

int int[[26
26]];

for (int i = 0; i < ss..length

length((); ii++
++)) {
count[[[Link]
count charAt((i) - 'a'
'a']]++
++;;
count[[[Link]
count charAt((i) - 'a'
'a']]--
--;;
}

count)) {
for (int c : count
false;;
if (c != 0) return false
}

true;;
return true
}
87. What is the best way to find duplicates in array?

Answer:

java

// Method 1: Using HashSet - O(n) time, O(n) space

List<
public List<Integer
Integer>
> findDuplicates
findDuplicates((int
int[[] nums
nums)) {
Set<
Set<Integer
Integer>
> seen = new HashSet
HashSet<
<>();
List<
List<Integer
Integer>
> duplicates = new ArrayList
ArrayList<
<>();

nums)) {
for (int num : nums
seen..add
if (!seen add((num
num))) {
duplicates..add
duplicates add((num
num));
}
}
duplicates;;
return duplicates
}

// Method 2: For array with elements 1 to n - O(n) time, O(1) space

List<
public List<Integer
Integer>
> findDuplicates2
findDuplicates2((int
int[[] nums
nums)) {
List<
List<Integer
Integer>
> result = new ArrayList
ArrayList<
<>();

nums..length
for (int i = 0; i < nums length;; ii++
++)) {
Math..abs
int index = Math abs((nums
nums[[i]) - 1;
nums[[index
if (nums index]] < 0) {
result..add
result add((Math
Math..abs
abs((nums
nums[[i]));
} else {
nums[[index
nums index]] = -nums
nums[[index
index]];
}
}

result;;
return result
}

88. How to implement LFU (Least Frequently Used) Cache?

Answer:

java
class LFUCache {
Map<
private Map<Integer
Integer,, Integer
Integer>
> values
values;;
Map<
private Map<Integer
Integer,, Integer
Integer>
> frequencies
frequencies;;
Map<
private Map<Integer
Integer,, LinkedHashSet
LinkedHashSet<
<Integer
Integer>
>> frequencyGroups
frequencyGroups;;
capacity;;
private int capacity
minFrequency;;
private int minFrequency

LFUCache((int capacity
public LFUCache capacity)) {
this..capacity = capacity
this capacity;;
HashMap<
values = new HashMap<>();
HashMap<
frequencies = new HashMap<>();
frequencyGroups = new HashMap<
HashMap<>();
minFrequency = 1;
}

get((int key
public int get key)) {
values..containsKey
if (!values containsKey((key
key))) return -1;

updateFrequency(
updateFrequency(key)
key);
return values.
[Link](
get(key)
key);
}

put((int key
public void put key,, int value
value)) {
return;;
if (capacity <= 0) return

values..containsKey
if (values containsKey((key
key))) {
values.
[Link](
put(key,
key, value)
value);
updateFrequency((key
updateFrequency key));
return;;
return
}

values..size
if (values size(() >= capacity
capacity)) {
evictLFU(();
evictLFU
}

values..put
values put((key
key,, value
value));
frequencies..put
frequencies put((key
key,, 1);
frequencyGroups..computeIfAbsent
frequencyGroups computeIfAbsent((1, k -> new LinkedHashSet
LinkedHashSet<
<>()).add
add((key
key));
minFrequency = 1;
}

private void updateFrequency(

updateFrequency(int key)
key) {
frequencies..get
int freq = frequencies get((key
key));
frequencies..put
frequencies put((key
key,, freq + 1);

frequencyGroups..get
frequencyGroups get((freq
freq)).remove
remove((key
key));
frequencyGroups..get
if (freq == minFrequency && frequencyGroups get((freq
freq)).isEmpty
isEmpty(()) {
minFrequency++
minFrequency++;;
}

frequencyGroups..computeIfAbsent
frequencyGroups computeIfAbsent((freq + 1, k -> new LinkedHashSet
LinkedHashSet<
<>()).add
add((key
key));
}

evictLFU(() {
private void evictLFU
frequencyGroups..get
int keyToEvict = frequencyGroups get((minFrequency
minFrequency)).iterator
iterator(().next
next(();
frequencyGroups..get
frequencyGroups get((minFrequency
minFrequency)).remove
remove((keyToEvict
keyToEvict));
values.
[Link](
remove(keyToEvict)
keyToEvict);
frequencies..remove
frequencies remove((keyToEvict
keyToEvict));