1. Which of the following is a non-linear data structure?
Difficulty: EasyType: MCQTopic: Data Structures
- Array
- Linked List
- Queue
- Tree
A tree is a non-linear data structure because elements are arranged in a hierarchical manner, where each node can have multiple children. Data is not stored sequentially or in a linear order.
Linear data structures like arrays, linked lists, and queues store elements in a sequential manner where each element has a predecessor and successor, except for the first and last elements. Non-linear structures like trees and graphs allow for more complex relationships between elements.
Correct Answer: Tree
Example Code
// Linear data structure - Array
int arr[] = {1, 2, 3, 4, 5};
// Non-linear data structure - Binary Tree
class Node {
int data;
Node left, right;
Node(int item) {
data = item;
left = right = null;
}
}2. Which data structure is used for implementing recursion?
Difficulty: EasyType: MCQTopic: Stack Operations
- Array
- Stack
- Queue
- Linked List
A stack is used to implement recursion because function calls follow the Last In First Out principle. When a function calls itself recursively, each call is pushed onto the call stack.
When a recursive function returns, the most recent call is popped from the stack first. This is why stack overflow errors occur when recursion depth is too large, as the call stack runs out of memory. The stack maintains the execution context, local variables, and return addresses for each recursive call.
Correct Answer: Stack
Example Code
// Recursive function - uses stack internally
int factorial(int n) {
if (n <= 1) return 1; // Base case
return n * factorial(n - 1); // Recursive call pushed to stack
}
// Call stack visualization:
// factorial(5)
// factorial(4)
// factorial(3)
// factorial(2)
// factorial(1) -> returns 1
// returns 2
// returns 6
// returns 24
// returns 1203. Which of the following data structures are indexed structures?
Difficulty: EasyType: MCQTopic: Array Index
- Queue
- Trees
- Linear Arrays
- None of the above
Linear arrays are indexed structures because elements can be accessed directly using their index position. Array indexing provides constant time O of 1 access to any element.
Queues do not support direct indexing as elements can only be accessed from the front. Trees use hierarchical relationships rather than indices. The ability to access elements by index makes arrays very efficient for random access operations.
Correct Answer: Linear Arrays
Example Code
// Array with direct index access - O(1)
int arr[] = {10, 20, 30, 40, 50};
int element = arr[2]; // Direct access to index 2, returns 30
// Queue - no direct index access
Queue<Integer> queue = new LinkedList<>();
queue.add(10);
queue.add(20);
// Can only access front element with peek() or poll()4. What is the worst-case time complexity of inserting n elements into an empty linked list that must be kept in sorted order?
Difficulty: MediumType: MCQTopic: Time Complexity
- O(n)
- O(log n)
- O(n log n)
- O(n^2)
Inserting n elements into a sorted linked list has worst-case time complexity of O of n squared. For each of the n insertions, you potentially need to traverse the entire list to find the correct position, which takes O of n time in the worst case.
When inserting the first element, you traverse 0 nodes. For the second element, you might traverse 1 node. For the nth element, you might traverse n minus 1 nodes. The total operations are 0 plus 1 plus 2 plus dot dot dot plus n minus 1, which equals n times n minus 1 divided by 2, giving O of n squared complexity.
Correct Answer: O(n^2)
Example Code
// Inserting in sorted linked list
void sortedInsert(Node head, int data) {
Node newNode = new Node(data);
// Traverse to find position - O(n) per insertion
Node current = head;
while (current.next != null && current.next.data < data) {
current = current.next;
}
// Insert at correct position
newNode.next = current.next;
current.next = newNode;
}
// For n insertions: O(n) * n = O(n^2)5. Stack data structure cannot be used for which of the following?
Difficulty: MediumType: MCQTopic: Stack Usage
- Expression Evaluation in Postfix Form
- String Reversal
- Recursion Implementation
- Resource Allocation and Scheduling
Resource allocation and scheduling typically require a queue data structure that follows First In First Out principle, not a stack. Tasks or resources need to be processed in the order they arrive for fair scheduling.
Stacks are excellent for expression evaluation because operators and operands can be processed using Last In First Out order. String reversal works by pushing characters onto a stack and popping them in reverse order. Recursion naturally uses the call stack to maintain function contexts.
Correct Answer: Resource Allocation and Scheduling
Example Code
// Stack - LIFO (Last In First Out)
Stack<String> stack = new Stack<>();
stack.push("First");
stack.push("Second");
stack.pop(); // Returns "Second" (last in, first out)
// Queue - FIFO for resource scheduling
Queue<String> queue = new LinkedList<>();
queue.add("First");
queue.add("Second");
queue.poll(); // Returns "First" (first in, first out)
// Resource scheduling needs FIFO, not LIFO6. A directed graph is _______ if there is a path from each vertex to every other vertex in the graph.
Difficulty: MediumType: MCQTopic: Graph Connectivity
- Weakly connected
- Strongly connected
- Tightly connected
- Linearly connected
A directed graph is strongly connected if there exists a directed path from every vertex to every other vertex in the graph. This means you can reach any vertex from any other vertex following the direction of edges.
A weakly connected graph becomes connected when you ignore edge directions. Strongly connected graphs are important in applications like analyzing web page rankings, finding cycles in dependency graphs, and studying network connectivity.
Correct Answer: Strongly connected
Example Code
// Strongly Connected Graph Example
// Graph: 1 -> 2 -> 3 -> 1
// ↓ ↑
// 4 ------→
// Can reach any vertex from any other vertex
// 1 to 2: 1->2
// 1 to 3: 1->2->3
// 1 to 4: 1->4
// 2 to 1: 2->3->1
// 3 to 2: 3->1->2
// etc.
// Weakly Connected (not strongly)
// 1 -> 2 <- 3
// Can't reach 3 from 1 following edges
7. The binary search method needs no more than ________ comparisons for an array of size n.
Difficulty: EasyType: MCQTopic: Binary Search
- (log2n) + 1
- log n
- (log n) + 1
- log2 n
Binary search requires at most log base 2 of n plus 1 comparisons. The algorithm divides the search space in half with each comparison, leading to logarithmic time complexity.
For example, with an array of 16 elements, binary search needs at most log base 2 of 16 plus 1 equals 5 comparisons. The plus 1 accounts for the final comparison that determines the exact match or confirms the element is not present. This is significantly better than linear search which requires n comparisons in the worst case.
Correct Answer: (log2n) + 1
Example Code
// Binary Search - O(log n) comparisons
int binarySearch(int arr[], int target, int left, int right) {
if (right >= left) {
int mid = left + (right - left) / 2;
// Element found at mid
if (arr[mid] == target)
return mid;
// Search left half
if (arr[mid] > target)
return binarySearch(arr, target, left, mid - 1);
// Search right half
return binarySearch(arr, target, mid + 1, right);
}
return -1; // Element not found
}
// For n=16: max comparisons = log2(16) + 1 = 4 + 1 = 58. In what traversal do we process all of a vertex's descendants before we move to an adjacent vertex?
Difficulty: MediumType: MCQTopic: Traversal Types
- BFS
- DFS
- Level Order
- Width First
Depth First Search processes all descendants of a vertex before moving to adjacent vertices. DFS explores as deep as possible along each branch before backtracking.
Breadth First Search, also called level order or width first traversal, processes all vertices at the current level before moving to the next level. DFS uses a stack for implementation while BFS uses a queue. DFS is useful for detecting cycles, topological sorting, and maze solving.
Correct Answer: DFS
Example Code
// DFS - Process all descendants first
void DFS(Node node, boolean[] visited) {
if (node == null) return;
visited[node.data] = true;
System.out.print(node.data + " ");
// Process all descendants before adjacent
for (Node neighbor : node.neighbors) {
if (!visited[neighbor.data]) {
DFS(neighbor, visited);
}
}
}
// BFS - Process level by level
void BFS(Node start) {
Queue<Node> queue = new LinkedList<>();
queue.add(start);
while (!queue.isEmpty()) {
Node node = queue.poll();
System.out.print(node.data + " ");
queue.addAll(node.neighbors);
}
}9. What is a Data Structure? Explain the difference between linear and non-linear data structures with examples.
Difficulty: EasyType: SubjectiveTopic: Data Structure Types
A data structure is a specialized format for organizing, storing, and manipulating data in a computer's memory. It defines the relationship between data elements and the operations that can be performed on them. Data structures enable efficient access and modification of data, which is crucial for writing optimized programs.
Linear data structures arrange elements in a sequential manner where each element has a predecessor and successor, except for the first and last elements. Elements are stored in a contiguous or linked manner, and you can traverse all elements in a single run. Examples include arrays where elements are stored in consecutive memory locations, linked lists where nodes are connected via pointers, stacks that follow Last In First Out principle, and queues that follow First In First Out principle.
Non-linear data structures organize elements in a hierarchical or interconnected manner where one element can be connected to multiple elements. Elements are not arranged sequentially, and you cannot traverse all elements in a single run. Examples include trees which are hierarchical structures with parent-child relationships like binary trees and binary search trees, graphs which consist of vertices connected by edges representing complex relationships, heaps which are complete binary trees used for priority queues, and tries which are tree-like structures for efficient string retrieval.
The choice between linear and non-linear structures depends on the application. Linear structures are simpler and efficient for sequential access, while non-linear structures are better for representing hierarchical or network relationships and enable more complex operations.
Example Code
// Linear Data Structure - Array
int[] linearArray = {1, 2, 3, 4, 5};
// Sequential access: arr[0], arr[1], arr[2]...
// Linear Data Structure - Linked List
class Node {
int data;
Node next;
}
// Sequential: node1 -> node2 -> node3 -> node4
// Non-Linear Data Structure - Binary Tree
class TreeNode {
int data;
TreeNode left, right;
}
// 1
// / \
// 2 3
// / \
// 4 5
// Hierarchical structure, not sequential10. Explain the differences between arrays and linked lists. When would you choose one over the other?
Difficulty: MediumType: SubjectiveTopic: Array vs Linked List
Arrays and linked lists are both linear data structures, but they differ fundamentally in how they store and access elements.
Arrays store elements in contiguous memory locations, allowing direct access to any element using its index in O of 1 time. The size is fixed at creation, making insertion and deletion expensive operations requiring shifting of elements, with time complexity of O of n. Arrays use less memory per element as they only store data, and they provide better cache locality due to contiguous storage.
Linked lists store elements as nodes scattered in memory, with each node containing data and a pointer to the next node. Access to elements requires traversal from the head, taking O of n time. The size is dynamic and can grow or shrink as needed. Insertion and deletion are efficient at O of 1 if you have a reference to the position, requiring only pointer updates. However, linked lists use more memory per element due to storing pointers, and they have poor cache locality.
Choose arrays when you need fast random access by index, when the size is known beforehand and does not change frequently, when memory efficiency is critical as arrays have less overhead, and when you need to perform many read operations compared to insertions and deletions. Arrays are ideal for implementing other data structures like heaps and hash tables, and for scenarios requiring sorted data with binary search.
Choose linked lists when the size is unknown or changes frequently, when you need frequent insertions and deletions especially at the beginning or middle, when you do not need random access to elements, and when implementing data structures like stacks, queues, and graphs. Linked lists are better when memory is fragmented and contiguous allocation is difficult.
Example Code
// Array - Fixed size, contiguous memory
int[] array = new int[5];
array[2] = 10; // O(1) access by index
// Insertion requires shifting - O(n)
for (int i = size; i > pos; i--) {
array[i] = array[i-1];
}
array[pos] = newValue;
// Linked List - Dynamic size, scattered memory
class Node {
int data;
Node next;
}
// Access requires traversal - O(n)
Node current = head;
while (current != null) {
if (current.data == target) break;
current = current.next;
}
// Insertion at position - O(1) with reference
Node newNode = new Node(value);
newNode.next = current.next;
current.next = newNode;11. What is a stack data structure? Explain its operations and provide real-world applications.
Difficulty: MediumType: SubjectiveTopic: Stack Implementation
A stack is a linear data structure that follows the Last In First Out principle, meaning the last element added is the first one to be removed. Think of it like a stack of plates where you can only add or remove plates from the top.
The fundamental operations of a stack are push which adds an element to the top with O of 1 time complexity, pop which removes and returns the top element with O of 1 complexity, peek or top which returns the top element without removing it in O of 1 time, isEmpty which checks if the stack is empty, and size which returns the number of elements. All these operations work only at one end called the top of the stack.
Stacks can be implemented using arrays with a fixed size where we maintain a top pointer, or using linked lists which provide dynamic size by adding and removing nodes at the head. The array implementation is simple and provides fast access, but has size limitations. The linked list implementation offers dynamic sizing but uses extra memory for pointers.
Real-world applications of stacks are numerous. In function call management, the call stack maintains execution contexts for nested and recursive function calls. For expression evaluation, stacks convert infix expressions to postfix or prefix notation and evaluate postfix expressions efficiently. In undo and redo operations, applications like text editors use stacks to track states. For syntax parsing, compilers use stacks to check balanced parentheses, brackets, and braces in code. In backtracking algorithms, stacks store decision points in problems like maze solving and the N-Queens puzzle. Web browsers use stacks to implement the back button functionality by storing visited pages.
Example Code
// Stack implementation using array
class Stack {
private int[] arr;
private int top;
private int capacity;
Stack(int size) {
arr = new int[size];
capacity = size;
top = -1;
}
void push(int value) {
if (top == capacity - 1) {
System.out.println("Stack Overflow");
return;
}
arr[++top] = value;
}
int pop() {
if (isEmpty()) {
System.out.println("Stack Underflow");
return -1;
}
return arr[top--];
}
int peek() {
if (isEmpty()) return -1;
return arr[top];
}
boolean isEmpty() {
return top == -1;
}
}
// Application: Balanced Parentheses
boolean isBalanced(String str) {
Stack<Character> stack = new Stack<>();
for (char c : str.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else if (c == ')' || c == '}' || c == ']') {
if (stack.isEmpty()) return false;
char top = stack.pop();
if (!isMatchingPair(top, c)) return false;
}
}
return stack.isEmpty();
}12. Explain the queue data structure, its operations, and compare it with a stack. Provide use cases for each.
Difficulty: MediumType: SubjectiveTopic: Queue Operations
A queue is a linear data structure that follows the First In First Out principle, meaning the first element added is the first one to be removed. It operates like a real-world queue or line where people are served in the order they arrive.
The fundamental operations of a queue are enqueue which adds an element to the rear end with O of 1 time complexity, dequeue which removes and returns the element from the front in O of 1 time, front or peek which returns the front element without removing it, rear which returns the last element, isEmpty which checks if the queue is empty, and size which returns the number of elements. Operations happen at two different ends unlike stacks where all operations occur at one end.
Queues can be implemented using arrays which provide fast access but have fixed size, using linked lists which offer dynamic size and efficient enqueue and dequeue operations, or using circular arrays which efficiently utilize space by wrapping around when reaching the end.
The key difference between stack and queue is the order of element removal. Stacks use Last In First Out where the most recently added element is removed first, like a stack of books. Queues use First In First Out where the oldest element is removed first, like a waiting line. Stacks have one access point called top, while queues have two points called front and rear.
Use cases for stacks include function call management in recursion, undo and redo operations, expression evaluation and syntax parsing, backtracking in algorithms, and browser back button functionality. Use cases for queues include CPU and disk scheduling in operating systems, handling asynchronous data transfer like IO buffers and pipes, breadth-first search traversal in graphs and trees, printer job scheduling where documents are printed in order received, and call center systems where calls are answered in order they arrive.
Example Code
// Queue implementation using linked list
class Queue {
class Node {
int data;
Node next;
Node(int data) { this.data = data; }
}
private Node front, rear;
void enqueue(int value) {
Node newNode = new Node(value);
if (rear == null) {
front = rear = newNode;
return;
}
rear.next = newNode;
rear = newNode;
}
int dequeue() {
if (front == null) {
System.out.println("Queue is empty");
return -1;
}
int value = front.data;
front = front.next;
if (front == null) rear = null;
return value;
}
int peek() {
if (front == null) return -1;
return front.data;
}
boolean isEmpty() {
return front == null;
}
}
// Stack vs Queue comparison
Stack: push(1), push(2), push(3), pop() -> 3 (LIFO)
Queue: enqueue(1), enqueue(2), enqueue(3), dequeue() -> 1 (FIFO)13. What is algorithm analysis? Explain time complexity and space complexity with examples.
Difficulty: MediumType: SubjectiveTopic: Algorithm Analysis
Algorithm analysis is the process of determining the computational complexity of algorithms, measuring how their time and space requirements grow as the input size increases. This helps us compare different algorithms and choose the most efficient one for a given problem.
Time complexity measures the amount of time an algorithm takes to complete as a function of input size. It represents the number of basic operations executed. We express time complexity using Big O notation which describes the worst-case, upper bound on growth rate. Common time complexities from best to worst are O of 1 for constant time where execution time does not depend on input size, O of log n for logarithmic time like binary search, O of n for linear time like linear search, O of n log n for algorithms like merge sort and quick sort, O of n squared for nested loops like bubble sort, and O of 2 to the power n for exponential time like recursive Fibonacci.
Space complexity measures the amount of memory an algorithm uses as a function of input size. It includes space for input data, temporary variables, and recursive call stack. For example, O of 1 space means using a fixed amount of memory regardless of input size, O of n space means memory grows linearly with input, and O of n squared space means memory grows quadratically.
For example, linear search has time complexity O of n because in worst case it checks every element, and space complexity O of 1 because it uses only a few variables. Binary search has time complexity O of log n because it halves the search space each time, and space complexity O of 1 for iterative implementation or O of log n for recursive due to call stack. Merge sort has time complexity O of n log n for all cases because it divides array in half recursively and merges in linear time, and space complexity O of n for the temporary arrays used during merging.
Example Code
// Example 1: O(1) time, O(1) space
int getFirstElement(int[] arr) {
return arr[0]; // Constant time, constant space
}
// Example 2: O(n) time, O(1) space
int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) { // Loop n times
if (arr[i] == target) return i;
}
return -1;
}
// Example 3: O(log n) time, O(1) space
int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 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;
}
// Example 4: O(n^2) time, O(1) space
void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// Example 5: O(n log n) time, O(n) space
void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right); // Uses O(n) extra space
}
}14. Explain different types of linked lists. How would you detect a cycle in a linked list?
Difficulty: HardType: SubjectiveTopic: Linked List Operations
A linked list is a linear data structure where elements called nodes are connected via pointers or references. Each node contains data and a reference to the next node, forming a chain-like structure.
There are several types of linked lists. A singly linked list has nodes with data and a pointer to the next node only, allowing traversal in one direction from head to tail. A doubly linked list has nodes with data and two pointers, one to the next node and one to the previous node, allowing bidirectional traversal. A circular linked list has the last node pointing back to the first node instead of null, forming a circle. This can be singly or doubly circular.
Advantages of linked lists include dynamic size that can grow or shrink at runtime, efficient insertion and deletion at O of 1 when you have a reference to the position, and no memory wastage as nodes are allocated only when needed. Disadvantages include no random access requiring O of n time to reach an element, extra memory for storing pointers in each node, and poor cache locality as nodes are scattered in memory.
To detect a cycle in a linked list, the most efficient method is Floyd's Cycle Detection Algorithm, also called the tortoise and hare algorithm. Use two pointers, slow and fast, both starting at the head. Move slow pointer one step at a time and fast pointer two steps at a time. If there is a cycle, the fast pointer will eventually meet the slow pointer inside the cycle because the fast pointer gains one step on slow pointer in each iteration. If there is no cycle, the fast pointer will reach null.
This algorithm has time complexity O of n where n is the number of nodes, and space complexity O of 1 as it uses only two pointers. Alternative methods include using a hash set to store visited nodes with O of n space, or modifying the linked list structure to mark visited nodes, but Floyd's algorithm is preferred for its constant space usage.
Example Code
// Singly Linked List Node
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
// Doubly Linked List Node
class DNode {
int data;
DNode next, prev;
DNode(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
// Floyd's Cycle Detection Algorithm
boolean hasCycle(Node head) {
if (head == null) return false;
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // Move 1 step
fast = fast.next.next; // Move 2 steps
if (slow == fast) { // Cycle detected
return true;
}
}
return false; // No cycle
}
// Time: O(n), Space: O(1)
// If cycle exists, fast catches slow in at most n steps
// If no cycle, fast reaches null in n/2 steps15. Compare different sorting algorithms. When would you choose Quick Sort over Merge Sort?
Difficulty: HardType: SubjectiveTopic: Sorting Algorithms
Sorting algorithms arrange elements in a specific order, typically ascending or descending. Understanding their characteristics helps choose the right algorithm for different scenarios.
Bubble sort repeatedly swaps adjacent elements if they are in wrong order, with time complexity O of n squared for average and worst cases and O of n for best case when array is already sorted. Space complexity is O of 1. It is simple but inefficient for large datasets and rarely used in practice.
Selection sort finds the minimum element and places it at the beginning, repeating for remaining elements. Time complexity is O of n squared for all cases and space complexity is O of 1. It performs fewer swaps than bubble sort but still inefficient for large data.
Insertion sort builds sorted array one element at a time by inserting each element into its correct position. Time complexity is O of n squared for average and worst cases, O of n for nearly sorted data, and space complexity is O of 1. It is efficient for small datasets and nearly sorted data, used in hybrid algorithms like TimSort.
Merge sort divides array into halves recursively, sorts them, and merges sorted halves. Time complexity is O of n log n for all cases, guaranteed, and space complexity is O of n for temporary arrays. It is stable, predictable, and good for large datasets, but requires extra space.
Quick sort selects a pivot, partitions array around it, and recursively sorts partitions. Time complexity is O of n log n average case, O of n squared worst case with bad pivot selection, and space complexity is O of log n for recursion stack. It is fastest in practice for most data and sorts in-place with less memory than merge sort, but not stable and worst case can be bad.
Heap sort builds a max heap and repeatedly extracts maximum to build sorted array. Time complexity is O of n log n for all cases and space complexity is O of 1. It guarantees O of n log n and uses no extra space, but slower than quick sort in practice and not stable.
Choose Quick Sort over Merge Sort when average-case performance matters more than worst-case, when memory is limited as quick sort uses O of log n space versus merge sort's O of n, when you need in-place sorting, when stability is not required, and for general-purpose sorting of random data. Choose Merge Sort when you need guaranteed O of n log n time complexity, when you need a stable sort preserving relative order of equal elements, when working with linked lists as merge sort works well without random access, and when extra space is available and acceptable.
Example Code
// Quick Sort - O(n log n) average, O(n^2) worst
void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
// Merge Sort - O(n log n) always
void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
// Copy data and merge sorted arrays
// Requires O(n) extra space
}
// Choose Quick Sort: Random data, limited memory
// Choose Merge Sort: Need stability, guaranteed O(n log n)16. Which of the following are properties of a binary tree?
Difficulty: EasyType: MCQTopic: Binary Tree Properties
- The first subset is called left subtree
- The second subtree is called right subtree
- The root cannot contain NULL
- Both A and B
In a binary tree, each node has at most two children. The first child is called the left subtree and the second child is called the right subtree. These are fundamental properties of binary trees.
The root can be null in an empty tree, so option C is incorrect. Binary trees are hierarchical structures where each node can have zero, one, or two children. The left and right terminology is a standard convention used universally in computer science.
Correct Answer: Both A and B
Example Code
// Binary Tree Node Structure
class TreeNode {
int data;
TreeNode left; // First subset - left subtree
TreeNode right; // Second subset - right subtree
TreeNode(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
// Example Binary Tree:
// 1
// / \
// 2 3
// / \
// 4 5
// Node 1: left=2, right=3
// Node 2: left=4, right=5
// Node 3: left=null, right=null17. Which of the following data structures is preferred in the implementation of a database system?
Difficulty: MediumType: MCQTopic: Database Indexing
- B-Tree
- Binary Search Tree
- AVL Tree
- B+ Tree
B plus trees are the most preferred data structure for database indexing because they are optimized for systems that read and write large blocks of data. All data records are stored in leaf nodes, making range queries very efficient.
B plus trees have several advantages over B-trees and other structures. They provide better sequential access because all leaf nodes are linked together. They support efficient range queries as you can traverse leaf nodes sequentially. The internal nodes only store keys for navigation, allowing more keys per node and reducing tree height. This minimizes disk I/O operations which is crucial for database performance.
Correct Answer: B+ Tree
Example Code
// B+ Tree characteristics:
// 1. All data in leaf nodes
// 2. Internal nodes only have keys
// 3. Leaf nodes linked for sequential access
// 4. Better for range queries
// Example B+ Tree structure:
// [10, 20]
// / | \
// [5] [15] [25,30]
// | | | |
// D1 D2 D3 D4
// D1, D2, D3, D4 are data records
// Leaf nodes linked: D1 -> D2 -> D3 -> D4
// Range query [10-25] is efficient:
// Start at D2, traverse linked list to D3
// Why not BST/AVL?
// - Not optimized for disk access
// - No sequential leaf traversal
// - Higher tree height for same data
18. Which of the following data structures is best for searching words in dictionaries?
Difficulty: MediumType: MCQTopic: Dictionary Search
- Binary Search Tree
- Graph
- N-ary tree
- Trie
A Trie, also called a prefix tree, is the best data structure for dictionary word searches because it provides efficient prefix-based searching and storage. Each node represents a character, and paths from root to nodes represent words.
Tries excel at prefix matching with time complexity O of m where m is the word length, independent of dictionary size. They enable autocomplete features efficiently, support prefix-based searches like finding all words starting with given letters, and can store additional information like word frequency. While tries use more memory than hash tables, they are unbeatable for applications requiring prefix operations.
Correct Answer: Trie
Example Code
// Trie Node Structure
class TrieNode {
TrieNode[] children = new TrieNode[26]; // For a-z
boolean isEndOfWord;
}
// Trie for words: "cat", "car", "dog"
// root
// / \
// c d
// | |
// a o
// / \ |
// t r g*
// * *
// * marks end of word
// Search "cat" - O(3) time
// Prefix search "ca" - finds "cat" and "car"
boolean search(TrieNode root, String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.children[c - 'a'] == null)
return false;
node = node.children[c - 'a'];
}
return node.isEndOfWord;
}19. How can memory be saved when storing colour information in a Red-Black tree?
Difficulty: HardType: MCQTopic: Red-Black Tree
- Using the least significant bit of one of the node's pointers to store colour information
- Another array with the colours of each node
- Keeping colour data in the node structure
- Employing both negative and positive numbering
In Red-Black trees, each node needs to store color information which is either red or black, requiring just one bit. Memory can be saved by using the least significant bit of a pointer because pointers are typically aligned to word boundaries.
Pointer alignment means the last few bits are always zero for aligned addresses. For example, with 4-byte alignment, the last 2 bits are always zero. We can use the least significant bit to store the color where 0 represents black and 1 represents red. When dereferencing the pointer, we mask out the color bit to get the actual address. This technique saves memory compared to adding a separate boolean field which typically uses a full byte or more.
Correct Answer: Using the least significant bit of one of the node's pointers to store colour information
Example Code
// Traditional approach - uses extra memory
class RBNode {
int data;
RBNode left, right, parent;
boolean isRed; // Uses 1 byte typically
}
// Memory-efficient approach
class RBNode {
int data;
long leftPtr; // Pointer with color in LSB
long rightPtr; // Pointer with color in LSB
RBNode parent;
}
// Pointer operations:
// Store: ptr = (address | colorBit)
// Get address: address = (ptr & ~1)
// Get color: color = (ptr & 1)
// Example:
// Address: 0x1000 (binary: ...0000)
// Red node: 0x1001 (binary: ...0001)
// Extract address: 0x1001 & ~1 = 0x1000
// Extract color: 0x1001 & 1 = 1 (red)20. What type of tree is a heap?
Difficulty: EasyType: MCQTopic: Heap Structure
- Binary Search Tree
- Complete Binary Tree
- Full Binary Tree
- AVL Tree
A heap is a complete binary tree where all levels are fully filled except possibly the last level, which is filled from left to right. This structure allows efficient array representation and maintains heap properties.
Complete binary trees ensure that the height is always log n, making heap operations like insert and delete efficient. The array representation is space-efficient with no wasted slots, and parent-child relationships can be calculated using simple formulas: parent at index i divided by 2, left child at 2 times i, and right child at 2 times i plus 1. This is why heaps are preferred for implementing priority queues.
Correct Answer: Complete Binary Tree
Example Code
// Heap as Complete Binary Tree
// 90 (index 0)
// / \
// 80 70 (indices 1, 2)
// / \ /
// 60 50 40 (indices 3, 4, 5)
// Array representation: [90, 80, 70, 60, 50, 40]
// Index calculations:
// Parent of node i: (i-1)/2
// Left child of node i: 2*i + 1
// Right child of node i: 2*i + 2
class MaxHeap {
int[] heap;
int size;
int parent(int i) { return (i - 1) / 2; }
int leftChild(int i) { return 2 * i + 1; }
int rightChild(int i) { return 2 * i + 2; }
}
// Why complete binary tree?
// - Efficient array representation
// - Height always log(n)
// - No wasted space21. What are the two main components of a graph?
Difficulty: EasyType: MCQTopic: Graph Terminology
- Nodes and Pointers
- Vertices and Edges
- Keys and Values
- Parents and Children
A graph consists of two main components: vertices also called nodes which represent entities or points, and edges which represent connections or relationships between vertices. This is the fundamental definition of a graph in data structures.
Vertices can represent any entity like cities, people, web pages, or computers. Edges represent relationships like roads between cities, friendships between people, or network connections. Edges can be directed showing one-way relationships or undirected showing two-way relationships. Some graphs also have weighted edges where each edge has an associated value representing distance, cost, or capacity.
Correct Answer: Vertices and Edges
Example Code
// Graph representation
class Graph {
int vertices; // Number of vertices
List<List<Integer>> adj; // Adjacency list
}
// Example Graph:
// Vertices: {A, B, C, D}
// Edges: {(A,B), (A,C), (B,D), (C,D)}
//
// A --- B
// | |
// C --- D
//
// Adjacency list representation:
// A: [B, C]
// B: [A, D]
// C: [A, D]
// D: [B, C]
// Directed graph example:
// A --> B
// ↓ ↓
// C --> D
// A: [B, C]
// B: [D]
// C: [D]
// D: []22. In an AVL tree, what is the maximum height difference allowed between left and right subtrees of any node?
Difficulty: HardType: MCQTopic: AVL Tree Balance
In an AVL tree, the balance factor of any node, which is the difference between the heights of left and right subtrees, must be at most 1. This strict balance criterion ensures that the tree remains approximately balanced and all operations maintain O of log n time complexity.
When an insertion or deletion causes the balance factor to exceed 1 or become less than negative 1, the tree performs rotations to restore balance. The four types of rotations are left rotation, right rotation, left-right rotation, and right-left rotation. This automatic rebalancing is what makes AVL trees self-balancing binary search trees and guarantees logarithmic height.
Correct Answer: 1
Example Code
// AVL Tree Node
class AVLNode {
int data;
AVLNode left, right;
int height;
// Balance factor = height(left) - height(right)
// Must be in range [-1, 0, 1]
}
// Example balanced AVL tree:
// 10 (BF=0)
// / \
// 5 15 (BF=-1, 0)
// / \
// 3 7 (BF=0, 0)
// After inserting 2, becomes unbalanced:
// 10 (BF=2) - UNBALANCED!
// / \
// 5 15
// / \
// 3 7
// /
// 2
// Right rotation restores balance:
// 5 (BF=0)
// / \
// 3 10
// / / \
// 2 7 15
int getBalance(AVLNode node) {
if (node == null) return 0;
return height(node.left) - height(node.right);
}23. Explain the different tree traversal techniques: In-order, Pre-order, and Post-order. Provide use cases for each.
Difficulty: MediumType: SubjectiveTopic: Tree Traversals
Tree traversal is the process of visiting all nodes in a tree data structure in a specific order. There are three main depth-first traversal techniques that differ in the order they visit the root node relative to its children.
In-order traversal visits nodes in the order: left subtree, root, right subtree. For binary search trees, in-order traversal visits nodes in sorted ascending order, making it useful for retrieving sorted data. The algorithm recursively traverses the left subtree, processes the current node, then recursively traverses the right subtree. Time complexity is O of n and space complexity is O of h where h is tree height due to recursion stack.
Pre-order traversal visits nodes in the order: root, left subtree, right subtree. This is useful for creating a copy of the tree, getting prefix expression of an expression tree, and serializing the tree structure. The root is processed before its children, so you see the hierarchical structure from top to bottom. It is commonly used in file system traversal where you want to process directories before their contents.
Post-order traversal visits nodes in the order: left subtree, right subtree, root. This is useful for deleting a tree as you delete children before parents, evaluating postfix expressions in expression trees, and calculating directory sizes as you need child sizes before parent size. The root is processed last after all descendants have been processed.
Level-order traversal, also called breadth-first traversal, visits nodes level by level from left to right using a queue. It is useful for finding the shortest path in unweighted trees, level-wise printing, and checking if a tree is complete. Time complexity is O of n and space complexity is O of w where w is maximum width of the tree.
The choice of traversal depends on the problem requirements. Use in-order for BST operations requiring sorted order, pre-order for tree serialization and copying, post-order for deletion and cleanup operations, and level-order for breadth-first processing.
Example Code
class TreeNode {
int data;
TreeNode left, right;
}
// In-order: Left, Root, Right
void inOrder(TreeNode root) {
if (root == null) return;
inOrder(root.left); // Visit left
System.out.print(root.data); // Process root
inOrder(root.right); // Visit right
}
// Pre-order: Root, Left, Right
void preOrder(TreeNode root) {
if (root == null) return;
System.out.print(root.data); // Process root
preOrder(root.left); // Visit left
preOrder(root.right); // Visit right
}
// Post-order: Left, Right, Root
void postOrder(TreeNode root) {
if (root == null) return;
postOrder(root.left); // Visit left
postOrder(root.right); // Visit right
System.out.print(root.data); // Process root
}
// Example tree:
// 1
// / \
// 2 3
// / \
// 4 5
// In-order: 4 2 5 1 3
// Pre-order: 1 2 4 5 3
// Post-order: 4 5 2 3 124. What is a Binary Search Tree? Explain its properties and the time complexity of its operations.
Difficulty: MediumType: SubjectiveTopic: Binary Search Tree
A Binary Search Tree is a binary tree with a specific ordering property: for every node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater than the node's value. This property makes BSTs efficient for search, insertion, and deletion operations.
The key properties of a BST are that each node has at most two children called left and right, the left subtree of a node contains only values less than the node's value, the right subtree contains only values greater than the node's value, and both left and right subtrees must also be valid BSTs. This recursive property ensures the tree maintains its ordering throughout.
Search operation starts at root and compares the target value with current node. If equal, we found the value. If target is less, search left subtree. If target is greater, search right subtree. Average time complexity is O of log n for balanced trees, worst case is O of n for skewed trees.
Insertion follows the same path as search to find the correct position, then inserts the new node as a leaf. This maintains the BST property. Time complexity is O of log n average case, O of n worst case.
Deletion has three cases. If the node has no children, simply remove it. If the node has one child, replace it with its child. If the node has two children, find the in-order successor which is the minimum value in right subtree or in-order predecessor which is maximum in left subtree, copy its value to the node being deleted, then delete the successor or predecessor. Time complexity is O of log n average, O of n worst case.
The performance of BST operations depends heavily on tree balance. In the best case with a balanced tree, height is log n and operations are efficient. In the worst case with a skewed tree where nodes form a chain, height is n and operations degrade to linear time. This is why self-balancing trees like AVL and Red-Black trees are used to guarantee logarithmic performance.
Example Code
class BSTNode {
int data;
BSTNode left, right;
}
// Search - O(log n) average, O(n) worst
BSTNode search(BSTNode root, int key) {
if (root == null || root.data == key)
return root;
if (key < root.data)
return search(root.left, key);
return search(root.right, key);
}
// Insert - O(log n) average, O(n) worst
BSTNode insert(BSTNode root, int key) {
if (root == null)
return new BSTNode(key);
if (key < root.data)
root.left = insert(root.left, key);
else if (key > root.data)
root.right = insert(root.right, key);
return root;
}
// Example BST:
// 50
// / \
// 30 70
// / \ / \
// 20 40 60 80
// Property: 20<30<40<50<60<70<80
// Balanced: height = log(n)
// Skewed (worst):
// 50
// \
// 60
// \
// 70 height = n25. Explain how a min-heap works. How do you insert an element and extract the minimum element?
Difficulty: HardType: SubjectiveTopic: Heap Operations
A min-heap is a complete binary tree where the value of each node is less than or equal to the values of its children. The minimum element is always at the root, making min-heaps perfect for implementing priority queues.
The heap property states that for any node i, the value at i is less than or equal to values at its children. This property must be maintained after every insertion and deletion. Heaps are typically implemented using arrays for space efficiency, with parent-child relationships calculated using index formulas.
To insert an element, first add the new element at the end of the array to maintain the complete binary tree property. This may violate the heap property, so perform heapify-up also called bubble-up or percolate-up. Compare the new element with its parent. If the new element is smaller, swap them. Continue this process moving up the tree until the heap property is restored or you reach the root. Time complexity is O of log n as you traverse at most the height of the tree.
To extract the minimum element, the minimum is always the root at index 0. Remove and return this element. Replace the root with the last element in the array to maintain completeness. This likely violates the heap property, so perform heapify-down also called bubble-down or percolate-down. Compare the new root with its children. Swap with the smaller child if the root is larger. Continue this process moving down the tree until the heap property is restored or you reach a leaf. Time complexity is O of log n.
Heapify-up starts at the inserted position and moves toward the root. At each step, if current node is smaller than parent, swap and continue. Stop when current node is greater than or equal to parent or reach root.
Heapify-down starts at the root and moves toward leaves. At each step, find the smallest among current node and its children. If current is not smallest, swap with the smallest child and continue. Stop when current is smallest or reach a leaf.
Min-heaps are commonly used in Dijkstra's shortest path algorithm, heap sort, finding the k smallest elements efficiently, and implementing priority queues where tasks with lower priority values are processed first.
Example Code
class MinHeap {
int[] heap;
int size;
int capacity;
// Helper methods
int parent(int i) { return (i - 1) / 2; }
int left(int i) { return 2 * i + 1; }
int right(int i) { return 2 * i + 2; }
// Insert - O(log n)
void insert(int value) {
if (size == capacity) return;
// Add at end
heap[size] = value;
int i = size++;
// Heapify-up
while (i > 0 && heap[parent(i)] > heap[i]) {
swap(heap, i, parent(i));
i = parent(i);
}
}
// Extract Min - O(log n)
int extractMin() {
if (size == 0) return -1;
int min = heap[0];
heap[0] = heap[--size]; // Replace with last
// Heapify-down
int i = 0;
while (left(i) < size) {
int smallest = i;
int l = left(i);
int r = right(i);
if (l < size && heap[l] < heap[smallest])
smallest = l;
if (r < size && heap[r] < heap[smallest])
smallest = r;
if (smallest == i) break;
swap(heap, i, smallest);
i = smallest;
}
return min;
}
}
// Example:
// Insert 3, 2, 15, 5, 4, 45
// 2
// / \
// 3 4
// / \ /
// 5 15 4526. Explain different ways to represent graphs in memory. Compare adjacency matrix and adjacency list.
Difficulty: MediumType: SubjectiveTopic: Graph Representations
Graphs can be represented in memory using two main methods: adjacency matrix and adjacency list. Each has different space and time trade-offs.
An adjacency matrix is a 2D array of size V by V where V is the number of vertices. The cell at row i and column j contains 1 or true if there is an edge from vertex i to vertex j, and 0 or false otherwise. For weighted graphs, the cell contains the edge weight instead of 1. Space complexity is O of V squared which is inefficient for sparse graphs with few edges. Time complexity to check if an edge exists is O of 1 which is very fast, but adding or removing a vertex takes O of V squared time. It is suitable for dense graphs where the number of edges is close to V squared, when you need to quickly check if an edge exists between any two vertices, and when the graph is small.
An adjacency list uses an array of lists where each index represents a vertex and contains a list of adjacent vertices. For vertex i, the list at index i contains all vertices that are directly connected to i. Space complexity is O of V plus E where E is the number of edges, which is much more efficient for sparse graphs. Time complexity to check if an edge exists is O of degree of v where degree is the number of adjacent vertices, which can be up to V in worst case. Adding a vertex is O of 1 and adding an edge is O of 1. It is suitable for sparse graphs with few edges, when you need to iterate over neighbors of vertices frequently, and when memory is limited.
For undirected graphs, each edge appears twice in the adjacency list, once in each vertex's list. For directed graphs, an edge from u to v appears only in u's list. Weighted graphs can be represented by storing pairs of vertex and weight in the adjacency list.
In practice, adjacency lists are more commonly used because most real-world graphs are sparse. Social networks, web graphs, and road networks typically have far fewer edges than the maximum possible V squared edges. However, adjacency matrices are simpler to implement and can be more efficient for dense graphs or when edge existence checks are very frequent.
Example Code
// Adjacency Matrix - O(V^2) space
class GraphMatrix {
int V;
int[][] adj;
GraphMatrix(int V) {
this.V = V;
adj = new int[V][V];
}
void addEdge(int u, int v) {
adj[u][v] = 1; // O(1)
}
boolean hasEdge(int u, int v) {
return adj[u][v] == 1; // O(1)
}
}
// Adjacency List - O(V+E) space
class GraphList {
int V;
List<List<Integer>> adj;
GraphList(int V) {
this.V = V;
adj = new ArrayList<>();
for (int i = 0; i < V; i++)
adj.add(new ArrayList<>());
}
void addEdge(int u, int v) {
adj.get(u).add(v); // O(1)
}
boolean hasEdge(int u, int v) {
return adj.get(u).contains(v); // O(degree)
}
}
// Example Graph: 0-1, 0-2, 1-2, 2-3
// Matrix:
// 0 1 2 3
// 0[0 1 1 0]
// 1[0 0 1 0]
// 2[0 0 0 1]
// 3[0 0 0 0]
// List:
// 0: [1, 2]
// 1: [2]
// 2: [3]
// 3: []27. Compare Breadth-First Search and Depth-First Search. When would you use each algorithm?
Difficulty: HardType: SubjectiveTopic: BFS vs DFS
Breadth-First Search and Depth-First Search are fundamental graph traversal algorithms with different exploration strategies and use cases.
BFS explores the graph level by level, visiting all neighbors of a vertex before moving to the next level. It uses a queue data structure to maintain the order of vertices to visit. Starting from a source vertex, BFS visits all vertices at distance 1, then all at distance 2, and so on. Time complexity is O of V plus E and space complexity is O of V for the queue and visited array. BFS guarantees finding the shortest path in unweighted graphs.
DFS explores the graph by going as deep as possible along each branch before backtracking. It uses a stack explicitly or implicitly through recursion. Starting from a source vertex, DFS explores one neighbor completely before exploring other neighbors. Time complexity is O of V plus E and space complexity is O of V for the recursion stack or explicit stack in worst case. DFS is more memory efficient for deep graphs.
Use BFS when you need to find the shortest path in an unweighted graph, when you want to find all vertices within a given distance, for level-order traversal of trees, in social networking applications to find people within a certain degree of connection, and when you want to find connected components. BFS is also useful in web crawlers for breadth-first exploration and in GPS navigation for finding nearby locations.
Use DFS when you need to detect cycles in a graph, for topological sorting in directed acyclic graphs, to find strongly connected components, when checking if a path exists between two vertices, in maze and puzzle solving where you want to explore all possibilities, and when memory is limited as DFS typically uses less memory than BFS. DFS is also used in game tree evaluation, finding articulation points and bridges in graphs, and solving constraint satisfaction problems.
A key difference is that BFS finds the shortest path and explores nearest vertices first making it suitable for level-wise processing, while DFS explores deeper before going wide making it suitable for exhaustive search and backtracking scenarios. BFS uses more memory storing entire levels while DFS memory grows with depth. Choose based on whether you need shortest paths or deep exploration.
Example Code
// BFS - Queue, Level-order
void BFS(int start) {
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.add(start);
while (!queue.isEmpty()) {
int u = queue.poll();
System.out.print(u + " ");
// Visit all unvisited neighbors
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
queue.add(v);
}
}
}
}
// DFS - Stack/Recursion, Depth-first
void DFS(int u, boolean[] visited) {
visited[u] = true;
System.out.print(u + " ");
// Visit all unvisited neighbors
for (int v : adj[u]) {
if (!visited[v]) {
DFS(v, visited);
}
}
}
// Example graph:
// 0
// / \
// 1 2
// / \
// 3 4
// BFS from 0: 0 1 2 3 4 (level-by-level)
// DFS from 0: 0 1 3 2 4 (depth-first)
// BFS: Shortest path guarantee
// DFS: Memory efficient for deep graphs28. How do you find the height of a binary tree? Explain the algorithm and its complexity.
Difficulty: HardType: SubjectiveTopic: Tree Problems
The height of a binary tree is the number of edges in the longest path from the root to a leaf node. An empty tree has height negative 1, a tree with only root has height 0, and so on. Finding the height is a fundamental tree operation.
The recursive algorithm is based on the observation that the height of a tree equals one plus the maximum height of its subtrees. For any node, we recursively calculate the height of the left subtree and the height of the right subtree, then return one plus the maximum of these two heights. The base case is when we reach a null node, which has height negative 1.
The algorithm works as follows. If the node is null, return negative 1. Recursively find the height of the left subtree. Recursively find the height of the right subtree. Return one plus the maximum of the left and right heights. This one accounts for the edge from the current node to its child.
Time complexity is O of n where n is the number of nodes, because we visit each node exactly once. Space complexity is O of h where h is the height of the tree, due to the recursion call stack. In the worst case of a skewed tree, this becomes O of n. For a balanced tree, space complexity is O of log n.
The iterative approach uses level-order traversal with a queue. We process the tree level by level, incrementing a counter for each level. Initialize height to 0 and use a queue containing the root. While the queue is not empty, get the number of nodes at current level, process all nodes at this level by dequeuing and enqueuing their children, and increment height after processing each level. This approach has O of n time and O of w space where w is the maximum width of the tree.
Variations of this problem include finding the diameter of a tree which is the longest path between any two nodes, checking if a tree is balanced where heights of subtrees differ by at most 1, and finding the minimum depth which is the shortest path from root to a leaf.
Example Code
class TreeNode {
int data;
TreeNode left, right;
}
// Recursive approach - O(n) time, O(h) space
int height(TreeNode root) {
// Base case: empty tree
if (root == null)
return -1;
// Recursive case
int leftHeight = height(root.left);
int rightHeight = height(root.right);
// Height = 1 + max of subtree heights
return 1 + Math.max(leftHeight, rightHeight);
}
// Iterative approach - Level-order
int heightIterative(TreeNode root) {
if (root == null) return -1;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int height = -1;
while (!queue.isEmpty()) {
int levelSize = queue.size();
// Process entire level
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
height++;
}
return height;
}
// Example:
// 1 height = 2
// / \
// 2 3 height = 1
// /
// 4 height = 0
// height(1) = 1 + max(height(2), height(3))
// = 1 + max(1, 0) = 229. Explain cycle detection in a graph. How do you detect cycles in directed and undirected graphs?
Difficulty: HardType: SubjectiveTopic: Graph Algorithms
Cycle detection is the problem of determining whether a graph contains a cycle, which is a path where you can start at a vertex and return to it without repeating edges. The approach differs for directed and undirected graphs.
For undirected graphs, we use DFS with parent tracking. A cycle exists if during DFS traversal, we encounter a visited vertex that is not the parent of the current vertex. The algorithm maintains a visited array and passes the parent vertex in recursive calls. Start DFS from any unvisited vertex. For each neighbor of the current vertex, if the neighbor is not visited, recursively visit it. If the neighbor is visited and is not the parent of current vertex, a cycle exists. Time complexity is O of V plus E and space complexity is O of V.
The key insight for undirected graphs is that if we reach an already visited vertex that is not our immediate parent, we must have reached it through a different path, forming a cycle. We need the parent check because in an undirected graph, the edge connecting a node to its parent would otherwise be detected as a cycle.
For directed graphs, we use DFS with recursion stack tracking. A cycle exists if we encounter a vertex that is currently in the recursion stack, meaning we found a back edge. The algorithm maintains two arrays: visited to track all visited vertices, and recursion stack to track vertices in the current DFS path. Start DFS from any unvisited vertex. Mark current vertex as visited and add to recursion stack. For each neighbor, if it is not visited, recursively visit it. If it is in the recursion stack, a cycle exists. After processing all neighbors, remove current vertex from recursion stack. Time complexity is O of V plus E and space complexity is O of V.
The difference is crucial because in directed graphs, visiting an already visited vertex only indicates a cycle if that vertex is in our current path. A vertex visited in a different DFS path does not form a cycle with our current path.
Applications of cycle detection include deadlock detection in operating systems where processes are vertices and resource requests are edges, checking for circular dependencies in build systems or package managers, detecting infinite loops in finite state machines, and verifying if topological sorting is possible which requires a directed acyclic graph.
Example Code
// Undirected Graph - DFS with parent tracking
boolean hasCycleUndirected(int v, boolean[] visited, int parent) {
visited[v] = true;
for (int neighbor : adj[v]) {
// If neighbor not visited, recurse
if (!visited[neighbor]) {
if (hasCycleUndirected(neighbor, visited, v))
return true;
}
// If visited and not parent, cycle exists
else if (neighbor != parent) {
return true;
}
}
return false;
}
// Directed Graph - DFS with recursion stack
boolean hasCycleDirected(int v, boolean[] visited, boolean[] recStack) {
visited[v] = true;
recStack[v] = true; // Add to current path
for (int neighbor : adj[v]) {
// If not visited, recurse
if (!visited[neighbor]) {
if (hasCycleDirected(neighbor, visited, recStack))
return true;
}
// If in recursion stack, back edge found
else if (recStack[neighbor]) {
return true;
}
}
recStack[v] = false; // Remove from current path
return false;
}
// Example Undirected:
// 0 - 1 - 2
// | |
// 3 ----- 4
// Cycle: 1-2-4-3-0-1
// Example Directed:
// 0 -> 1 -> 2
// ^ |
// | v
// 4 <------ 3
// Cycle: 0->1->2->3->4->030. What is the prerequisite for applying binary search on an array?
Difficulty: MediumType: MCQTopic: Binary Search
- Array must be sorted
- Array must have unique elements
- Array size must be a power of 2
- Array must be stored in contiguous memory
Binary search requires the array to be sorted because the algorithm relies on comparing the middle element with the target to decide which half to search next. If the array is not sorted, this comparison does not provide meaningful information about where the target might be.
The algorithm works by repeatedly dividing the search space in half. If the middle element is greater than the target, we search the left half. If it is less, we search the right half. This only works when elements are in sorted order. The array does not need unique elements, a specific size, or any particular memory layout.
Correct Answer: Array must be sorted
Example Code
// Binary Search - Requires sorted array
int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
if (arr[mid] < target)
left = mid + 1; // Search right half
else
right = mid - 1; // Search left half
}
return -1; // Not found
}
// Example: [1, 3, 5, 7, 9, 11, 13]
// Search 7:
// Step 1: mid=3, arr[3]=7, found!
// Time: O(log n)31. Which of the following sorting algorithms is stable?
Difficulty: MediumType: MCQTopic: Sorting Stability
- Quick Sort
- Heap Sort
- Merge Sort
- Selection Sort
A stable sorting algorithm maintains the relative order of equal elements. Merge Sort is stable because when merging two sorted arrays, if elements are equal, we always pick from the left array first, preserving the original order.
Quick Sort and Heap Sort are not stable because they can change the relative order of equal elements during partitioning or heap operations. Selection Sort is also not stable because it swaps elements without considering equal elements. Stability is important when sorting objects by multiple keys or when the original order of equal elements matters.
Correct Answer: Merge Sort
Example Code
// Stability example:
// Input: [(3,a), (1,b), (3,c), (2,d)]
// Sort by first element
// Stable sort (Merge Sort):
// Output: [(1,b), (2,d), (3,a), (3,c)]
// Note: (3,a) comes before (3,c) - order preserved
// Unstable sort (Quick Sort):
// Output: [(1,b), (2,d), (3,c), (3,a)]
// Note: (3,c) comes before (3,a) - order changed
// Why Merge Sort is stable:
void merge(int[] arr, int left, int mid, int right) {
// When arr[i] == arr[j]
// Always pick from left subarray first
if (arr[i] <= arr[j]) { // <= ensures stability
temp[k++] = arr[i++];
}
}32. What is the most critical component of a recursive function?
Difficulty: EasyType: MCQTopic: Recursion Base Case
- Loop structure
- Base case
- Variable declaration
- Return type
The base case is the most critical component because it defines when the recursion should stop. Without a proper base case, the recursive function will call itself infinitely, leading to stack overflow.
The base case is the condition where the function returns a value directly without making another recursive call. It represents the simplest version of the problem that can be solved without recursion. Every recursive call should move closer to the base case, ensuring the recursion eventually terminates.
Correct Answer: Base case
Example Code
// Factorial with base case
int factorial(int n) {
// BASE CASE - Critical!
if (n <= 1)
return 1;
// RECURSIVE CASE
return n * factorial(n - 1);
}
// Without base case - INFINITE RECURSION!
int badFactorial(int n) {
return n * badFactorial(n - 1); // Never stops!
}
// factorial(5) execution:
// 5 * factorial(4)
// 5 * 4 * factorial(3)
// 5 * 4 * 3 * factorial(2)
// 5 * 4 * 3 * 2 * factorial(1)
// 5 * 4 * 3 * 2 * 1 = 12033. Which sorting algorithm has the best average-case time complexity?
Difficulty: HardType: MCQTopic: Sorting Comparison
- Bubble Sort - O(n^2)
- Insertion Sort - O(n^2)
- Merge Sort - O(n log n)
- All have same complexity
Merge Sort has the best average-case time complexity of O of n log n among the options given. Bubble Sort and Insertion Sort both have O of n squared average and worst-case complexity, making them inefficient for large datasets.
Merge Sort consistently achieves O of n log n by dividing the array into halves recursively and merging them back in sorted order. This divide-and-conquer approach guarantees logarithmic depth with linear work at each level. Quick Sort also has O of n log n average case but can degrade to O of n squared in worst case. Merge Sort's guaranteed performance makes it reliable for all inputs.
Correct Answer: Merge Sort - O(n log n)
Example Code
// Time Complexity Comparison:
// Bubble Sort - O(n^2)
// Nested loops, compares adjacent elements
for (i = 0; i < n; i++)
for (j = 0; j < n-1; j++)
// Compare and swap
// Insertion Sort - O(n^2)
// For each element, find correct position
for (i = 1; i < n; i++)
// Shift elements - O(n)
// Merge Sort - O(n log n)
// Divide: log n levels
// Conquer: O(n) work per level
mergeSort(arr, 0, n-1)
divide into halves // log n times
merge sorted halves // O(n) per level
// For n=1000:
// Bubble/Insertion: ~1,000,000 operations
// Merge Sort: ~10,000 operations34. What is the key characteristic of backtracking algorithms?
Difficulty: MediumType: MCQTopic: Backtracking
- They always find optimal solution
- They explore all possibilities by abandoning partial solutions that cannot lead to valid solutions
- They use dynamic programming
- They have O(n) time complexity
Backtracking explores all possible solutions by building candidates incrementally and abandoning candidates as soon as it determines they cannot lead to a valid solution. This pruning of the search tree is called backtracking.
The algorithm tries to build a solution step by step. At each step, if the current partial solution cannot possibly lead to a complete valid solution, it backtracks by removing the last choice and tries a different option. This is more efficient than brute force as it avoids exploring obviously invalid paths. Backtracking does not guarantee optimal solutions and typically has exponential time complexity.
Correct Answer: They explore all possibilities by abandoning partial solutions that cannot lead to valid solutions
Example Code
// Backtracking Template
void backtrack(solution, choices) {
// Base case: found solution
if (isSolution(solution)) {
addToResults(solution);
return;
}
// Try each choice
for (choice in choices) {
// Make choice
solution.add(choice);
// Explore with this choice
if (isValid(solution)) {
backtrack(solution, newChoices);
}
// Backtrack: undo choice
solution.remove(choice);
}
}
// Example: N-Queens
// Try placing queen in each column
// If safe, recurse to next row
// If not safe or no solution found, backtrack35. What is the time complexity of linear search in the worst case?
Difficulty: EasyType: MCQTopic: Linear Search
Linear search has worst-case time complexity of O of n because in the worst case, you need to check every element in the array. This happens when the target element is at the last position or not present in the array.
Linear search examines each element sequentially from the beginning until it finds the target or reaches the end. Best case is O of 1 when the element is at the first position. Average case is O of n divided by 2 which simplifies to O of n. Linear search works on both sorted and unsorted arrays, unlike binary search which requires sorted data.
Correct Answer: O(n)
Example Code
// Linear Search - O(n) worst case
int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target)
return i; // Found at index i
}
return -1; // Not found after checking all n elements
}
// Example: [5, 2, 8, 1, 9]
// Search 9: Check 5, 2, 8, 1, 9 - found at index 4
// Search 7: Check all 5 elements - not found
// Best case: O(1) - element at index 0
// Average case: O(n/2) = O(n)
// Worst case: O(n) - element at last or not present36. What causes Quick Sort to have O(n^2) worst-case time complexity?
Difficulty: HardType: MCQTopic: Quick Sort Pivot
- Large array size
- Unsorted input
- Poor pivot selection leading to unbalanced partitions
- Duplicate elements
Quick Sort degrades to O of n squared when the pivot selection consistently creates unbalanced partitions. The worst case occurs when the pivot is always the smallest or largest element, resulting in partitions of size 0 and n minus 1.
This happens with already sorted or reverse sorted arrays when using the first or last element as pivot. Each partition step only removes one element, creating n levels of recursion with O of n work at each level, giving O of n squared total time. Using random pivot selection or median-of-three method helps avoid this worst case and maintains O of n log n average performance.
Correct Answer: Poor pivot selection leading to unbalanced partitions
Example Code
// Quick Sort worst case:
// Array: [1, 2, 3, 4, 5] (sorted)
// Pivot: last element (5)
// Partition 1: [1,2,3,4] | [5]
// Pivot: 4
// Partition 2: [1,2,3] | [4] | [5]
// Pivot: 3
// Partition 3: [1,2] | [3] | [4] | [5]
// ...
// n partitions with O(n) work each = O(n^2)
// Balanced partitions (best case):
// [1,2,3,4,5,6,7,8]
// Pivot: 4
// [1,2,3] | [4] | [5,6,7,8]
// log n levels with O(n) work = O(n log n)
// Prevention:
int choosePivot(arr, low, high) {
// Random pivot
int random = low + rand() % (high - low + 1);
return random;
// Median-of-three
int mid = (low + high) / 2;
return medianOf(arr[low], arr[mid], arr[high]);
}37. Compare linear search and binary search. In what scenarios is each algorithm preferred?
Difficulty: MediumType: SubjectiveTopic: Searching Algorithms
Linear search and binary search are fundamental searching algorithms with different requirements, performance characteristics, and use cases.
Linear search examines each element sequentially from start to end until the target is found or the array ends. It works by checking if the current element equals the target, returning the index if found, or continuing to the next element. Time complexity is O of 1 best case when element is first, O of n average and worst case. Space complexity is O of 1 as no extra space is needed. Linear search works on both sorted and unsorted arrays, and it works on any data structure with sequential access including linked lists.
Binary search divides the search space in half repeatedly by comparing the target with the middle element. It requires a sorted array. If the middle element equals target, return it. If target is smaller, search left half. If larger, search right half. Time complexity is O of log n for all cases. Space complexity is O of 1 for iterative implementation or O of log n for recursive due to call stack. Binary search only works on sorted arrays and requires random access, making it unsuitable for linked lists.
Use linear search when the array is unsorted and sorting overhead exceeds search benefit, when the array is very small where O of n is acceptable, when searching linked lists or data structures without random access, when you need to find all occurrences of an element, and when implementing simple search without complexity. Linear search is also useful when the target is likely to be near the beginning.
Use binary search when the array is already sorted or will be searched multiple times justifying the sorting cost, when dealing with large datasets where O of log n significantly outperforms O of n, when you need to find first or last occurrence in sorted array, when implementing range queries or finding closest elements, and when memory allows random access. Binary search is essential in scenarios requiring logarithmic performance like database indexing.
For example, with an array of 1 million elements, linear search might examine up to 1 million elements in worst case, while binary search examines at most 20 elements, demonstrating the massive performance difference for large datasets.
Example Code
// Linear Search - O(n)
int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target)
return i;
}
return -1;
}
// Binary Search - O(log n)
int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 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;
}
// Performance comparison:
// Array size: 1,000,000
// Linear: up to 1,000,000 comparisons
// Binary: up to 20 comparisons
// When to use:
// Linear: [3, 1, 4, 1, 5] unsorted, small
// Binary: [1, 1, 3, 4, 5] sorted, large38. Explain Merge Sort algorithm. How does it work and what are its advantages and disadvantages?
Difficulty: HardType: SubjectiveTopic: Sorting Algorithms
Merge Sort is a divide-and-conquer sorting algorithm that recursively divides the array into halves, sorts them, and merges the sorted halves back together. It guarantees O of n log n time complexity for all cases.
The algorithm works in three main steps. First, divide the array into two halves by finding the middle index. Continue dividing recursively until each subarray has one element, which is inherently sorted. Second, conquer by recursively sorting the two halves. The base case is when a subarray has one or zero elements. Third, merge the two sorted halves back together by comparing elements from both halves and placing them in correct order.
The merge operation works by maintaining two pointers, one for each sorted half. Compare elements at both pointers and place the smaller element in the result array. Move the pointer of the array from which element was taken. Continue until all elements from both halves are merged. Time complexity is O of n for merging as we process each element once.
Time complexity analysis shows that dividing the array creates log n levels because we halve the array each time. At each level, we perform O of n work to merge all subarrays at that level. Total time is O of n log n for all cases, whether best, average, or worst. Space complexity is O of n because we need temporary arrays to store the merged results. This is the main disadvantage as it requires extra space proportional to array size.
Advantages of Merge Sort include guaranteed O of n log n time complexity regardless of input, making it predictable and reliable. It is a stable sort preserving the relative order of equal elements, which is important for multi-key sorting. It works well with linked lists where no extra space is needed for merging. It is suitable for external sorting when data does not fit in memory. The algorithm is parallelizable as independent subarrays can be sorted concurrently.
Disadvantages include O of n space complexity requiring extra memory for temporary arrays, which can be prohibitive for large datasets. It is slower than Quick Sort in practice for arrays due to the overhead of copying elements. It cannot take advantage of nearly sorted data unlike Insertion Sort. It is not an in-place algorithm, requiring additional space allocation.
Merge Sort is preferred when you need guaranteed O of n log n performance, when stability is required, when dealing with linked lists, or when the dataset is too large to fit in memory requiring external sorting.
Example Code
// Merge Sort - O(n log n) always
void mergeSort(int[] arr, int left, int right) {
if (left < right) {
// Divide
int mid = left + (right - left) / 2;
// Conquer
mergeSort(arr, left, mid); // Sort left half
mergeSort(arr, mid + 1, right); // Sort right half
// Combine
merge(arr, left, mid, right);
}
}
void merge(int[] arr, int left, int mid, int right) {
// Create temp arrays
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
// Copy data
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// Merge back
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j])
arr[k++] = L[i++];
else
arr[k++] = R[j++];
}
// Copy remaining
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
// Example: [38, 27, 43, 3]
// Split: [38, 27] [43, 3]
// Split: [38] [27] [43] [3]
// Merge: [27, 38] [3, 43]
// Merge: [3, 27, 38, 43]39. Explain Quick Sort algorithm. How does partitioning work and how can you optimize pivot selection?
Difficulty: HardType: SubjectiveTopic: Quick Sort
Quick Sort is a highly efficient divide-and-conquer sorting algorithm that works by selecting a pivot element and partitioning the array around it. It is widely used due to its excellent average-case performance and in-place sorting capability.
The algorithm works as follows. First, choose a pivot element from the array using various strategies. Second, partition the array so that all elements smaller than the pivot come before it and all elements greater come after it. This puts the pivot in its final sorted position. Third, recursively apply Quick Sort to the subarrays before and after the pivot. The base case is when a subarray has one or zero elements.
The partitioning operation is the key to Quick Sort. Using the Lomuto partition scheme, we maintain an index i that tracks the boundary between smaller and larger elements. We iterate through the array with index j. If the current element is smaller than the pivot, we increment i and swap elements at i and j. This moves smaller elements to the left. Finally, we swap the pivot to its correct position at index i plus 1. Time complexity of partitioning is O of n as we examine each element once.
The Hoare partition scheme is an alternative that uses two pointers moving from both ends. Start with pointers at both ends. Move the left pointer right until finding an element greater than or equal to pivot. Move the right pointer left until finding an element less than or equal to pivot. Swap the elements at these pointers. Continue until pointers cross. This scheme makes fewer swaps on average than Lomuto.
Time complexity analysis shows that in the best and average cases, the pivot divides the array into roughly equal halves, creating log n levels of recursion with O of n work at each level, giving O of n log n total. In the worst case with poor pivot selection, each partition has size n minus 1 and 0, creating n levels with O of n work each, giving O of n squared. Space complexity is O of log n for the recursion stack in average case, O of n in worst case.
Pivot selection strategies significantly impact performance. Choosing the first or last element is simple but leads to worst case on sorted or reverse sorted arrays. Random pivot selection provides good average performance and avoids worst case on specific inputs. Median-of-three selects the median of first, middle, and last elements, providing good balance while being deterministic. Some implementations use median-of-five or even deterministic median-finding algorithms for guaranteed good pivots.
Advantages of Quick Sort include O of n log n average case with low constant factors making it faster than Merge Sort in practice. It sorts in-place requiring only O of log n extra space for recursion. It has good cache performance due to localized memory access. It is easy to implement and widely used in standard libraries.
Disadvantages include O of n squared worst case which can occur with poor pivot selection, though randomization makes this extremely unlikely. It is not stable as equal elements may be reordered. Recursive implementation can cause stack overflow for large arrays if not optimized with tail recursion or switching to Heap Sort for deep recursion.
Example Code
// Quick Sort - O(n log n) average
void quickSort(int[] arr, int low, int high) {
if (low < high) {
// Partition and get pivot index
int pi = partition(arr, low, high);
// Sort elements before and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Lomuto Partition Scheme
int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // Choose last as pivot
int i = low - 1; // Index of smaller element
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
// Improved pivot selection
int choosePivot(int[] arr, int low, int high) {
// Median-of-three
int mid = low + (high - low) / 2;
int a = arr[low], b = arr[mid], c = arr[high];
if ((a <= b && b <= c) || (c <= b && b <= a))
return mid;
if ((b <= a && a <= c) || (c <= a && a <= b))
return low;
return high;
}
// Example: [7, 2, 1, 6, 8, 5, 3, 4]
// Pivot: 4
// Partition: [2,1,3] [4] [6,8,5,7]
// Recurse on both sides40. What is recursion? Explain with examples and discuss when recursion is preferred over iteration.
Difficulty: MediumType: SubjectiveTopic: Recursion Concepts
Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller, similar subproblems. Each recursive call works on a simpler version of the original problem until reaching a base case that can be solved directly.
The essential components of recursion are the base case which is the simplest scenario that can be solved without recursion and stops the recursive calls, and the recursive case which breaks the problem into smaller instances and makes recursive calls. Each recursive call should move closer to the base case, and the function combines results from recursive calls to solve the original problem.
A simple example is calculating factorial. Factorial of n is defined as n times factorial of n minus 1, with base case factorial of 0 or 1 equals 1. This naturally maps to a recursive function. Another example is the Fibonacci sequence where each number is the sum of the two preceding ones. The base cases are F of 0 equals 0 and F of 1 equals 1. The recursive case is F of n equals F of n minus 1 plus F of n minus 2.
How recursion works internally involves the call stack. When a function calls itself, the current execution state including parameters and local variables is saved on the call stack. The recursive call executes as a new function invocation. When a recursive call completes, its result is returned and the previous state is restored from the stack. The stack unwinds as recursive calls return, eventually returning to the original caller.
Advantages of recursion include code simplicity and elegance for naturally recursive problems like tree traversal and divide-and-conquer algorithms. It provides a clear mathematical correspondence for problems defined recursively. It eliminates complex loop logic and state management. Some algorithms like tree and graph traversal are more naturally expressed recursively.
Disadvantages include performance overhead as function calls have overhead and recursion can be slower than iteration. Each recursive call consumes stack space which can lead to stack overflow for deep recursion. There is redundant computation in naive recursive solutions like Fibonacci calculating same values repeatedly. Debugging can be harder as the call stack becomes complex.
Use recursion when the problem has a recursive structure like trees, graphs, or divide-and-conquer algorithms. Use it when the recursive solution is significantly clearer than iterative as in tree traversal or backtracking. Use it when the recursion depth is manageable and will not cause stack overflow. Use it when the problem naturally divides into smaller similar subproblems. Examples include tree and graph traversal, divide-and-conquer algorithms like Merge Sort and Binary Search, backtracking problems like N-Queens and Sudoku, dynamic programming when combined with memoization, and problems involving recursive data structures.
Use iteration when performance is critical and recursion overhead matters, when recursion depth could cause stack overflow, when the iterative solution is equally clear or clearer, and when space complexity needs to be minimized. Many recursive algorithms can be converted to iterative using explicit stacks or queues.
Example Code
// Factorial - Natural recursion
int factorial(int n) {
// Base case
if (n <= 1)
return 1;
// Recursive case
return n * factorial(n - 1);
}
// Fibonacci - Multiple recursive calls
int fibonacci(int n) {
// Base cases
if (n <= 1)
return n;
// Recursive case
return fibonacci(n - 1) + fibonacci(n - 2);
}
// Binary Search - Divide and conquer
int binarySearch(int[] arr, int target, int left, int right) {
// Base case
if (left > right)
return -1;
// Recursive case
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
if (arr[mid] > target)
return binarySearch(arr, target, left, mid - 1);
return binarySearch(arr, target, mid + 1, right);
}
// Call stack for factorial(5):
// factorial(5) -> 5 * factorial(4)
// factorial(4) -> 4 * factorial(3)
// factorial(3) -> 3 * factorial(2)
// factorial(2) -> 2 * factorial(1)
// factorial(1) -> 1 (base case)
// Returns: 1 * 2 * 3 * 4 * 5 = 12041. Explain the backtracking technique with the N-Queens problem as an example. How does it differ from brute force?
Difficulty: HardType: SubjectiveTopic: Backtracking
Backtracking is an algorithmic technique for solving problems by trying to build a solution incrementally and abandoning candidates as soon as it determines they cannot lead to a valid solution. This pruning of the search space makes it more efficient than brute force.
The backtracking approach follows a general pattern. Start with an empty solution. At each step, try to extend the partial solution by adding one more element. Check if the current partial solution is valid using constraint checking. If valid, recursively continue building the solution. If the partial solution violates constraints or cannot lead to a complete solution, backtrack by removing the last added element and try a different choice. If a complete valid solution is found, record it. Continue until all possibilities are explored.
The N-Queens problem asks to place N queens on an N by N chessboard such that no two queens attack each other. Queens attack horizontally, vertically, and diagonally. The backtracking solution works row by row. For each row, try placing the queen in each column. Check if placing the queen in current position is safe by verifying no queen in previous rows attacks this position. If safe, mark this position and recursively solve for the next row. If recursive call returns false meaning no solution found, unmark this position and try next column. If all columns tried without success, backtrack to previous row. If all N queens are placed successfully, a solution is found.
The safe check verifies three conditions. First, check the column to ensure no queen in the same column in previous rows. Second, check the left diagonal by verifying positions where row minus column is constant. Third, check the right diagonal by verifying positions where row plus column is constant. We only check previous rows because we place queens row by row.
Comparing backtracking to brute force shows significant efficiency gains. Brute force would try all possible placements of N queens on N squared positions and then check if valid. This gives C of N squared choose N possibilities, which is astronomical even for small N. For N equals 8, this is over 4 billion combinations. Backtracking prunes invalid partial solutions early. If placing a queen makes position invalid, we do not explore any completions of that partial solution. For 8-Queens, backtracking explores around 15,000 nodes compared to billions in brute force.
The time complexity of backtracking is O of N factorial in worst case for N-Queens, as we have N choices for first row, N minus 1 for second row after pruning, and so on. However, practical performance is much better due to pruning. Space complexity is O of N for the recursion stack and the board representation.
Backtracking is applicable to many problems including Sudoku solver where we try numbers 1 to 9 in empty cells and backtrack if invalid, generating all permutations or combinations by building them element by element, solving constraint satisfaction problems, maze solving where we try paths and backtrack if we hit dead ends, and the knapsack problem with constraints. The key advantage is pruning the search space by abandoning partial solutions that violate constraints, making it far more efficient than exhaustive brute force.
42. How do you analyze the time and space complexity of recursive algorithms? Explain with examples.
Difficulty: MediumType: SubjectiveTopic: Complexity Analysis
Analyzing the complexity of recursive algorithms requires understanding the recursion tree, recurrence relations, and the work done at each level. The approach differs from iterative algorithms because we must account for the recursive calls and the call stack.
To analyze time complexity, first identify the base case and its complexity, usually O of 1. Second, determine the number of recursive calls made at each level. Third, calculate the work done in each call excluding recursive calls. Fourth, determine the depth of recursion which is how many levels deep the recursion goes. Fifth, combine these factors using recurrence relations or the recursion tree method.
The recursion tree method visualizes each function call as a node. The root is the initial call, and children are recursive calls. Each level represents one step of recursion depth. Count the total work done across all nodes. For example, in binary tree traversal, each node is visited once, giving O of n time complexity.
Recurrence relations express the running time as a function of the input size. For example, T of n equals 2 times T of n divided by 2 plus O of n for Merge Sort, where 2 times T of n divided by 2 represents two recursive calls on half-sized arrays, and O of n is the merge operation. Solving this using the Master Theorem or recursion tree gives O of n log n.
Common patterns include linear recursion with one recursive call like factorial where T of n equals T of n minus 1 plus O of 1, giving O of n total. Binary recursion with two calls like Fibonacci has T of n equals T of n minus 1 plus T of n minus 2 plus O of 1, giving O of 2 to the power n. Divide and conquer with balanced splits like Binary Search has T of n equals T of n divided by 2 plus O of 1, giving O of log n. Multiple branching with equal work like Merge Sort has T of n equals 2 times T of n divided by 2 plus O of n, giving O of n log n.
Space complexity analysis must consider both the call stack and auxiliary space. The call stack depth equals the maximum recursion depth. Each recursive call adds a frame to the stack. For example, factorial has recursion depth n giving O of n space. Binary Search has recursion depth log n giving O of log n space. Auxiliary space is extra space used within function calls excluding the stack. For instance, Merge Sort uses O of n auxiliary space for temporary arrays.
Examples show these principles. For factorial, we have one recursive call with O of 1 work per call, recursion depth n, giving time O of n and space O of n for the call stack. For Fibonacci naive recursion, we have two recursive calls, O of 1 work per call, recursion depth n, but the tree has 2 to the power n total nodes, giving time O of 2 to the power n and space O of n for maximum stack depth. For Binary Search, we have one recursive call, O of 1 work per call, recursion depth log n, giving time O of log n and space O of log n. For Merge Sort, we have two recursive calls, O of n work for merging, recursion depth log n, giving time O of n log n and space O of n for auxiliary arrays plus O of log n for stack.
Optimizing recursive algorithms can convert to iterative using explicit stack or queue to avoid call stack overhead. Use memoization to cache results of repeated recursive calls as in dynamic programming. Apply tail call optimization where the recursive call is the last operation, allowing some compilers to optimize space to O of 1. Use divide and conquer efficiently to minimize the work at each level.
Example Code
// Example 1: Factorial - O(n) time, O(n) space
int factorial(int n) {
if (n <= 1) return 1; // O(1)
return n * factorial(n-1); // 1 recursive call
}
// T(n) = T(n-1) + O(1) = O(n)
// Space: O(n) stack frames
// Example 2: Fibonacci - O(2^n) time, O(n) space
int fib(int n) {
if (n <= 1) return n; // O(1)
return fib(n-1) + fib(n-2); // 2 recursive calls
}
// T(n) = T(n-1) + T(n-2) + O(1) = O(2^n)
// Space: O(n) max stack depth
// Example 3: Binary Search - O(log n) time, O(log n) space
int binarySearch(int[] arr, int target, int l, int r) {
if (l > r) return -1; // O(1)
int mid = l + (r-l)/2;
if (arr[mid] == target) return mid;
if (arr[mid] > target)
return binarySearch(arr, target, l, mid-1); // 1 call
return binarySearch(arr, target, mid+1, r);
}
// T(n) = T(n/2) + O(1) = O(log n)
// Space: O(log n) stack frames
// Example 4: Merge Sort - O(n log n) time, O(n) space
void mergeSort(int[] arr, int l, int r) {
if (l < r) {
int mid = (l+r)/2;
mergeSort(arr, l, mid); // T(n/2)
mergeSort(arr, mid+1, r); // T(n/2)
merge(arr, l, mid, r); // O(n)
}
}
// T(n) = 2T(n/2) + O(n) = O(n log n)
// Space: O(n) auxiliary + O(log n) stack43. Explain Insertion Sort and Bubble Sort. When is Insertion Sort preferred despite having O(n^2) complexity?
Difficulty: MediumType: SubjectiveTopic: Sorting Applications
Insertion Sort and Bubble Sort are simple comparison-based sorting algorithms with quadratic time complexity, but they have different characteristics and use cases.
Bubble Sort works by repeatedly comparing adjacent elements and swapping them if they are in wrong order. It makes multiple passes through the array. In each pass, the largest unsorted element bubbles up to its correct position at the end. The algorithm continues until a complete pass is made without any swaps, indicating the array is sorted. Time complexity is O of n squared for average and worst cases, O of n for best case when array is already sorted. Space complexity is O of 1 as it sorts in-place. Bubble Sort is rarely used in practice due to poor performance, but it is simple to implement and understand.
Insertion Sort works like sorting playing cards in your hands. It builds the sorted array one element at a time by taking each element and inserting it into its correct position among the previously sorted elements. Start from the second element. Compare it with elements in the sorted portion, moving them right to make space. Insert the current element in its correct position. Repeat for all elements. Time complexity is O of n squared for average and worst cases when array is reverse sorted, O of n for best case when array is already sorted. Space complexity is O of 1 as it sorts in-place.
Insertion Sort is preferred over other O of n squared algorithms and sometimes even over O of n log n algorithms in specific scenarios. First, for small arrays typically fewer than 10 to 50 elements, Insertion Sort outperforms complex algorithms like Quick Sort and Merge Sort due to low constant factors and no recursion overhead. Many optimized sorting implementations like TimSort use Insertion Sort for small subarrays.
Second, for nearly sorted data, Insertion Sort performs close to O of n because each element is already close to its correct position, requiring few comparisons and shifts. This makes it excellent for sorting data that is already mostly ordered or for maintaining sorted order as new elements arrive.
Third, Insertion Sort is stable, preserving the relative order of equal elements. This is crucial when sorting by multiple keys or when the original order matters for equal elements. Fourth, it is simple to implement with minimal code, making it suitable for embedded systems or when code simplicity is important.
Fifth, it is adaptive, meaning it takes advantage of existing order in the data. The more sorted the data, the faster it runs. Sixth, it is an online algorithm that can sort data as it is received, useful for streaming scenarios. Finally, it has minimal memory overhead using only O of 1 extra space.
Bubble Sort is rarely preferred as it has worse performance than Insertion Sort in practice, lacks the adaptive property to the same degree, and has no significant advantages. Insertion Sort should be preferred for small datasets, nearly sorted data, when stability is required, in embedded systems with memory constraints, as a subroutine in hybrid sorting algorithms, and when data arrives in a stream.
For example, Python's TimSort uses Insertion Sort for small subarrays during its merge process. When sorting an array of 10 elements, Insertion Sort is faster than Quick Sort due to lower constant factors. When adding a single element to a sorted array of 1000 elements, Insertion Sort finds the position in O of n time.
Example Code
// Insertion Sort - O(n^2) worst, O(n) best
void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
// Move elements greater than key
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// Bubble Sort - O(n^2) worst, O(n) best
void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
swapped = true;
}
}
if (!swapped) break; // Array is sorted
}
}
// Example - Insertion Sort on nearly sorted:
// [1, 2, 3, 5, 4] - Only 4 needs insertion
// Compare 4 with 5, shift 5, insert 4
// Result: [1, 2, 3, 4, 5] - O(n) time
// When to use Insertion Sort:
// - Array size < 50
// - Data nearly sorted
// - Need stable sort
// - Streaming data44. What is the key principle behind dynamic programming?
Difficulty: MediumType: MCQTopic: Dynamic Programming
- Divide and conquer without overlapping subproblems
- Solving problems by storing solutions to overlapping subproblems
- Always finding the optimal solution greedily
- Using recursion without memoization
Dynamic programming solves problems by breaking them into overlapping subproblems and storing the solutions to avoid redundant computation. This is called memoization in top-down approach or tabulation in bottom-up approach.
The key insight is that many problems have overlapping subproblems, meaning the same subproblem is solved multiple times. By storing results, we avoid recalculating them. For example, in Fibonacci, F of 5 requires F of 4 and F of 3, but F of 4 also requires F of 3, so we compute F of 3 twice without memoization. Dynamic programming stores F of 3 once and reuses it.
Correct Answer: Solving problems by storing solutions to overlapping subproblems
Example Code
// Without DP - Exponential time
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2); // Recalculates same values
}
// Time: O(2^n)
// With DP - Memoization
int fibMemo(int n, int[] memo) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n]; // Return stored result
memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);
return memo[n];
}
// Time: O(n)
// With DP - Tabulation
int fibTab(int n) {
int[] dp = new int[n+1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++)
dp[i] = dp[i-1] + dp[i-2];
return dp[n];
}
// Time: O(n), Space: O(n)45. What is the difference between memoization and tabulation in dynamic programming?
Difficulty: MediumType: MCQTopic: DP Approach
- Memoization is top-down, tabulation is bottom-up
- Memoization uses iteration, tabulation uses recursion
- They are the same technique
- Memoization is faster than tabulation
Memoization is a top-down approach that uses recursion with caching. It starts with the original problem and recursively breaks it down, storing results in a cache. Tabulation is a bottom-up approach that uses iteration, starting from the smallest subproblems and building up to the solution.
Memoization computes only the required subproblems on-demand, while tabulation computes all subproblems. Memoization has recursion overhead but may skip unnecessary computations. Tabulation avoids recursion overhead and has better space optimization potential. Both have the same time complexity but different implementation styles.
Correct Answer: Memoization is top-down, tabulation is bottom-up
Example Code
// Memoization - Top-down with recursion
int dpMemo(int n, Map<Integer, Integer> memo) {
if (n <= 1) return n;
if (memo.containsKey(n)) return memo.get(n);
int result = dpMemo(n-1, memo) + dpMemo(n-2, memo);
memo.put(n, result);
return result;
}
// Solves from F(n) down to F(0)
// Tabulation - Bottom-up with iteration
int dpTab(int n) {
if (n <= 1) return n;
int[] dp = new int[n+1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++)
dp[i] = dp[i-1] + dp[i-2];
return dp[n];
}
// Solves from F(0) up to F(n)
// Memoization: Recursive, cache as needed
// Tabulation: Iterative, fill entire table46. What is the key characteristic of a greedy algorithm?
Difficulty: MediumType: MCQTopic: Greedy Algorithm
- It always finds the optimal solution
- It makes locally optimal choices at each step
- It uses dynamic programming
- It requires backtracking
Greedy algorithms make the locally optimal choice at each step, hoping to find a global optimum. At each decision point, the algorithm chooses what appears best at that moment without considering future consequences.
Greedy algorithms do not always guarantee optimal solutions for all problems. They work when the problem exhibits greedy choice property, meaning a global optimum can be reached by making locally optimal choices, and optimal substructure, where an optimal solution contains optimal solutions to subproblems. Examples include Huffman coding, Dijkstra's algorithm, and activity selection.
Correct Answer: It makes locally optimal choices at each step
Example Code
// Activity Selection - Greedy approach
int activitySelection(int[] start, int[] finish) {
// Sort by finish time
sort(start, finish);
int count = 1; // First activity
int lastFinish = finish[0];
// Greedy: Pick activity with earliest finish time
for (int i = 1; i < start.length; i++) {
if (start[i] >= lastFinish) {
count++;
lastFinish = finish[i];
}
}
return count;
}
// Greedy choice: Always pick earliest finishing activity
// Time: O(n log n)
// Coin Change - Greedy may fail
// Coins: [1, 3, 4], Amount: 6
// Greedy: 4 + 1 + 1 = 3 coins
// Optimal: 3 + 3 = 2 coins
// Greedy doesn't work for all coin systems!47. For which problem does a greedy approach NOT guarantee an optimal solution?
Difficulty: HardType: MCQTopic: DP vs Greedy
- Activity Selection Problem
- Huffman Coding
- 0/1 Knapsack Problem
- Dijkstra's Shortest Path
The 0 or 1 Knapsack problem requires dynamic programming because greedy approaches like selecting items by highest value or highest value-to-weight ratio do not guarantee optimal solutions. You cannot take fractional items, so local optimal choices may lead to suboptimal global solutions.
Activity selection, Huffman coding, and Dijkstra's algorithm all exhibit the greedy choice property where local optimal choices lead to global optimum. In contrast, knapsack requires considering all combinations of items, making it a classic DP problem. The fractional knapsack where you can take parts of items can be solved greedily, but 0 or 1 knapsack cannot.
Correct Answer: 0/1 Knapsack Problem
Example Code
// 0/1 Knapsack - Greedy FAILS
// Items: [(value=60, weight=10), (100, 20), (120, 30)]
// Capacity: 50
// Greedy by value/weight ratio:
// Ratios: [6, 5, 4]
// Pick: (60,10) + (100,20) = value 160, weight 30
// Remaining capacity: 20, can't fit (120,30)
// Total: 160
// Optimal DP solution:
// Pick: (100,20) + (120,30) = value 220, weight 50
// Total: 220 > 160
// DP approach needed:
int knapsack(int[] val, int[] wt, int W) {
int[][] dp = new int[n+1][W+1];
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= W; w++) {
if (wt[i-1] <= w)
dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]],
dp[i-1][w]);
else
dp[i][w] = dp[i-1][w];
}
}
return dp[n][W];
}48. What is the space complexity of the optimized Fibonacci DP solution?
Difficulty: HardType: MCQTopic: DP Optimization
The Fibonacci sequence can be optimized to use O of 1 space instead of O of n by observing that we only need the last two values to compute the next value. We can use two variables instead of an entire array.
The standard tabulation approach uses an array of size n plus 1, giving O of n space. However, since F of i only depends on F of i minus 1 and F of i minus 2, we can maintain just these two values in variables, updating them as we iterate. This space optimization technique is common in DP problems where the current state depends only on a fixed number of previous states.
Correct Answer: O(1)
Example Code
// Standard DP - O(n) space
int fibStandard(int n) {
int[] dp = new int[n+1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++)
dp[i] = dp[i-1] + dp[i-2];
return dp[n];
}
// Space: O(n)
// Optimized DP - O(1) space
int fibOptimized(int n) {
if (n <= 1) return n;
int prev2 = 0; // F(i-2)
int prev1 = 1; // F(i-1)
int curr = 0;
for (int i = 2; i <= n; i++) {
curr = prev1 + prev2;
prev2 = prev1; // Shift values
prev1 = curr;
}
return curr;
}
// Space: O(1) - only 3 variables!
// General pattern for space optimization:
// If dp[i] depends only on dp[i-1], dp[i-2], ...
// Use variables instead of array49. Which of the following problems uses Catalan numbers?
Difficulty: HardType: MCQTopic: Catalan Numbers
- Counting binary search trees with n nodes
- Finding shortest path in a graph
- Sorting an array
- Detecting cycles in a linked list
Catalan numbers represent the number of structurally unique binary search trees with n nodes. The nth Catalan number is C of n equals 1 divided by n plus 1 times 2n choose n, which equals 2n factorial divided by n plus 1 factorial times n factorial.
Catalan numbers appear in many combinatorial problems including counting the number of valid parentheses expressions with n pairs, the number of ways to triangulate a polygon with n plus 2 sides, the number of paths in a grid that do not cross the diagonal, and the number of ways to multiply n plus 1 matrices. The formula can be computed using dynamic programming with C of n equals sum from i equals 0 to n minus 1 of C of i times C of n minus 1 minus i.
Correct Answer: Counting binary search trees with n nodes
Example Code
// Number of unique BSTs with n nodes
int numTrees(int n) {
int[] dp = new int[n+1];
dp[0] = 1; // Empty tree
dp[1] = 1; // One node
// Catalan number formula
for (int nodes = 2; nodes <= n; nodes++) {
for (int root = 1; root <= nodes; root++) {
// Left subtree: root-1 nodes
// Right subtree: nodes-root nodes
dp[nodes] += dp[root-1] * dp[nodes-root];
}
}
return dp[n];
}
// Examples:
// n=1: 1 BST
// n=2: 2 BSTs
// n=3: 5 BSTs
// 1 1 2 3 3
// \ \ / \ / /
// 3 2 1 3 2 1
// / \ \ \
// 2 3 1 2
// Time: O(n^2), Space: O(n)50. What is the time complexity of finding the Longest Common Subsequence (LCS) of two strings using dynamic programming?
Difficulty: MediumType: MCQTopic: LCS Problem
- O(n)
- O(n log n)
- O(m * n)
- O(2^n)
The Longest Common Subsequence problem has time complexity O of m times n where m and n are the lengths of the two strings. The DP table has dimensions m plus 1 by n plus 1, and we fill each cell in constant time.
The algorithm builds a 2D DP table where dp of i of j represents the length of LCS of the first i characters of string 1 and first j characters of string 2. If characters match, dp of i of j equals dp of i minus 1 of j minus 1 plus 1. Otherwise, dp of i of j equals max of dp of i minus 1 of j and dp of i of j minus 1. Space complexity is also O of m times n, though it can be optimized to O of min of m comma n.
Correct Answer: O(m * n)
Example Code
// LCS using DP - O(m*n) time and space
int longestCommonSubsequence(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[][] dp = new int[m+1][n+1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i-1) == s2.charAt(j-1))
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m][n];
}
// Example: s1="ABCDGH", s2="AEDFHR"
// LCS: "ADH" (length 3)
//
// DP table:
// "" A E D F H R
// "" 0 0 0 0 0 0 0
// A 0 1 1 1 1 1 1
// B 0 1 1 1 1 1 1
// C 0 1 1 1 1 1 1
// D 0 1 1 2 2 2 2
// G 0 1 1 2 2 2 2
// H 0 1 1 2 2 3 351. What is Dynamic Programming? Explain its key principles and when to use it.
Difficulty: MediumType: SubjectiveTopic: Dynamic Programming
Dynamic programming is an algorithmic technique for solving optimization problems by breaking them down into simpler overlapping subproblems and storing their solutions to avoid redundant computation. It is applicable when a problem exhibits two key properties: optimal substructure and overlapping subproblems.
Optimal substructure means that the optimal solution to a problem can be constructed from optimal solutions to its subproblems. For example, the shortest path from A to C through B is the shortest path from A to B plus the shortest path from B to C. If a problem lacks this property, DP cannot be applied.
Overlapping subproblems means that the same subproblem is solved multiple times during the recursive solution. This is where DP provides its efficiency gain. For example, computing Fibonacci of 5 requires computing Fibonacci of 3 twice through different recursive paths. By storing the result of Fibonacci of 3 the first time, we can reuse it instead of recalculating.
There are two main approaches to dynamic programming. The top-down approach, called memoization, starts with the original problem and uses recursion to break it down into subproblems. It stores results in a cache such as an array or hash map to avoid recomputing. The code is often more intuitive as it follows the natural recursive structure. However, it has recursion overhead and may compute only necessary subproblems.
The bottom-up approach, called tabulation, starts with the smallest subproblems and iteratively builds up to the solution. It fills a DP table in a specific order ensuring dependencies are satisfied. The code uses iteration instead of recursion, avoiding stack overflow. It may compute all subproblems even if some are unnecessary, but often allows better space optimization.
To identify when to use dynamic programming, look for these signals. The problem asks for optimization such as maximum, minimum, longest, or shortest. The problem can be broken into similar smaller subproblems. Solving subproblems independently and combining results gives the solution. A naive recursive solution has exponential time complexity due to repeated calculations. The problem involves counting ways or possibilities. Examples include finding minimum or maximum values, counting paths or arrangements, and problems with choices at each step.
The typical steps to solve a DP problem are: first, define the DP state clearly, identifying what each DP entry represents. Second, establish the recurrence relation showing how to compute a state from previous states. Third, identify base cases where the answer is known without computation. Fourth, determine the evaluation order ensuring dependencies are computed before they are needed. Fifth, implement using either memoization or tabulation. Sixth, optimize space if the solution uses too much memory.
Common DP patterns include linear DP where state depends on previous states in a sequence like Fibonacci or climbing stairs, interval DP where state represents a range of elements like matrix chain multiplication, subset DP where we consider including or excluding elements like knapsack, grid DP where we move through a 2D grid like unique paths, and string DP involving operations on strings like edit distance or LCS.
Example Code
// Problem: Climbing Stairs
// You can climb 1 or 2 steps at a time
// How many ways to reach step n?
// 1. Define state: dp[i] = ways to reach step i
// 2. Recurrence: dp[i] = dp[i-1] + dp[i-2]
// (come from step i-1 or i-2)
// 3. Base cases: dp[0]=1, dp[1]=1
// Memoization (Top-down)
int climbStairsMemo(int n, int[] memo) {
if (n <= 1) return 1;
if (memo[n] != 0) return memo[n];
memo[n] = climbStairsMemo(n-1, memo) +
climbStairsMemo(n-2, memo);
return memo[n];
}
// Tabulation (Bottom-up)
int climbStairsTab(int n) {
if (n <= 1) return 1;
int[] dp = new int[n+1];
dp[0] = 1; dp[1] = 1;
for (int i = 2; i <= n; i++)
dp[i] = dp[i-1] + dp[i-2];
return dp[n];
}
// Space optimized - O(1)
int climbStairsOpt(int n) {
if (n <= 1) return 1;
int prev2 = 1, prev1 = 1, curr = 0;
for (int i = 2; i <= n; i++) {
curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return curr;
}52. Explain the 0/1 Knapsack problem and its dynamic programming solution. What is the difference between 0/1 and fractional knapsack?
Difficulty: HardType: SubjectiveTopic: Knapsack Problem
The 0 or 1 Knapsack problem is a classic optimization problem where you have n items, each with a weight and value, and a knapsack with capacity W. The goal is to select items to maximize total value without exceeding the capacity. Each item can be either taken completely or not taken at all, hence the name 0 or 1.
The problem exhibits optimal substructure because the optimal solution for n items and capacity W either includes the nth item or excludes it. If we include the nth item, we need the optimal solution for n minus 1 items with capacity W minus weight of nth item. If we exclude it, we need the optimal solution for n minus 1 items with capacity W. We take the maximum of these two choices.
The DP solution uses a 2D table where dp of i of w represents the maximum value achievable using the first i items with capacity w. The recurrence relation is: if weight of item i is less than or equal to w, then dp of i of w equals max of value of i plus dp of i minus 1 of w minus weight of i, which is including the item, and dp of i minus 1 of w, which is excluding the item. Otherwise, dp of i of w equals dp of i minus 1 of w as we cannot include the item.
Base cases are dp of 0 of w equals 0 for all w, meaning with zero items we get zero value, and dp of i of 0 equals 0 for all i, meaning with zero capacity we get zero value. The evaluation order is row by row, processing items one by one, and within each row, processing capacities from 0 to W. The final answer is dp of n of W.
Time complexity is O of n times W where n is the number of items and W is knapsack capacity. We fill a table of size n plus 1 by W plus 1 with constant work per cell. Space complexity is O of n times W for the 2D table, though it can be optimized to O of W using a 1D array by processing items one at a time.
The space-optimized solution uses only one row by observing that we only need the previous row to compute the current row. We can use a single array and update it in-place by iterating from right to left to avoid overwriting values we still need.
The fractional knapsack problem differs in that you can take fractions of items, not just whole items. This changes the problem fundamentally. Fractional knapsack can be solved optimally using a greedy approach. Sort items by value-to-weight ratio in descending order. Take items in this order, taking as much as possible of each item until the knapsack is full. If an item does not fit completely, take the fraction that fits. Time complexity is O of n log n for sorting.
The key difference is that 0 or 1 knapsack requires dynamic programming with O of n times W time because you cannot make locally optimal choices. You must consider combinations of items. Fractional knapsack can use greedy with O of n log n time because taking items with highest value-to-weight ratio is always optimal when fractions are allowed.
Applications of 0 or 1 knapsack include resource allocation with constraints, portfolio optimization, cargo loading where items cannot be split, and project selection with budget constraints. The problem is NP-complete in general, but the DP solution is pseudo-polynomial with time depending on W.
Example Code
// 0/1 Knapsack - DP Solution
int knapsack01(int[] values, int[] weights, int W, int n) {
int[][] dp = new int[n+1][W+1];
// Build table bottom-up
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= W; w++) {
// Can we include item i-1?
if (weights[i-1] <= w) {
// Max of include vs exclude
dp[i][w] = Math.max(
values[i-1] + dp[i-1][w - weights[i-1]], // Include
dp[i-1][w] // Exclude
);
} else {
// Cannot include, carry forward
dp[i][w] = dp[i-1][w];
}
}
}
return dp[n][W];
}
// Time: O(n*W), Space: O(n*W)
// Space Optimized - 1D array
int knapsackOptimized(int[] values, int[] weights, int W, int n) {
int[] dp = new int[W+1];
for (int i = 0; i < n; i++) {
// Traverse right to left to avoid overwriting
for (int w = W; w >= weights[i]; w--) {
dp[w] = Math.max(dp[w],
values[i] + dp[w - weights[i]]);
}
}
return dp[W];
}
// Time: O(n*W), Space: O(W)
// Fractional Knapsack - Greedy
double fractionalKnapsack(int[] values, int[] weights, int W) {
// Sort by value/weight ratio
Item[] items = createItems(values, weights);
Arrays.sort(items, (a,b) ->
Double.compare(b.ratio, a.ratio));
double totalValue = 0;
for (Item item : items) {
if (W >= item.weight) {
W -= item.weight;
totalValue += item.value;
} else {
totalValue += item.value * ((double)W / item.weight);
break;
}
}
return totalValue;
}
// Time: O(n log n), Space: O(n)53. Explain the Longest Common Subsequence problem and its relationship to Edit Distance. How do you solve LCS using dynamic programming?
Difficulty: HardType: SubjectiveTopic: LCS and Edit Distance
The Longest Common Subsequence problem finds the longest sequence that appears in both strings in the same order, but not necessarily contiguously. For example, LCS of ABCDGH and AEDFHR is ADH with length 3. This is different from longest common substring which requires consecutive characters.
LCS exhibits optimal substructure. If the last characters of both strings match, the LCS length is 1 plus the LCS of the remaining strings. If they do not match, the LCS is the maximum of two possibilities: LCS excluding the last character of the first string, or LCS excluding the last character of the second string.
The DP solution uses a 2D table where dp of i of j represents the length of LCS of the first i characters of string 1 and the first j characters of string 2. The recurrence relation is: if s1 of i minus 1 equals s2 of j minus 1, then dp of i of j equals dp of i minus 1 of j minus 1 plus 1, meaning characters match so extend LCS. Otherwise, dp of i of j equals max of dp of i minus 1 of j and dp of i of j minus 1, meaning take best of excluding one character.
Base cases are dp of 0 of j equals 0 for all j, meaning empty string 1 has LCS length 0, and dp of i of 0 equals 0 for all i, meaning empty string 2 has LCS length 0. The final answer is dp of m of n where m and n are the string lengths.
Time complexity is O of m times n as we fill an m plus 1 by n plus 1 table with constant work per cell. Space complexity is O of m times n for the table, though it can be optimized to O of min of m comma n by keeping only the current and previous rows since we only look at adjacent cells.
To reconstruct the actual LCS sequence, not just its length, we backtrack through the DP table. Start at dp of m of n. If characters match, include this character and move diagonally to dp of i minus 1 of j minus 1. If characters do not match, move to the cell with larger value, either dp of i minus 1 of j or dp of i of j minus 1. Continue until reaching a cell with value 0.
Edit Distance, also called Levenshtein distance, is closely related to LCS. It finds the minimum number of operations insertions, deletions, or substitutions needed to transform one string into another. The relationship is: edit distance equals m plus n minus 2 times LCS length. This is because we need to delete characters from string 1 not in LCS and insert characters from string 2 not in LCS.
The Edit Distance DP is similar to LCS but tracks operation costs. dp of i of j represents minimum operations to transform first i characters of string 1 to first j characters of string 2. If characters match, dp of i of j equals dp of i minus 1 of j minus 1 with no operation needed. If they do not match, dp of i of j equals 1 plus min of dp of i minus 1 of j for deletion, dp of i of j minus 1 for insertion, and dp of i minus 1 of j minus 1 for substitution.
Applications of LCS include comparing DNA sequences in bioinformatics, finding similarities between text documents, version control systems to show file differences, and plagiarism detection. Edit Distance is used in spell checkers, DNA sequence analysis, speech recognition, and approximate string matching.
Example Code
// Longest Common Subsequence
int longestCommonSubsequence(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[][] dp = new int[m+1][n+1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i-1) == s2.charAt(j-1))
// Characters match, extend LCS
dp[i][j] = dp[i-1][j-1] + 1;
else
// Take max of two options
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m][n];
}
// Time: O(m*n), Space: O(m*n)
// Reconstruct LCS
String getLCS(String s1, String s2, int[][] dp) {
StringBuilder lcs = new StringBuilder();
int i = s1.length(), j = s2.length();
while (i > 0 && j > 0) {
if (s1.charAt(i-1) == s2.charAt(j-1)) {
lcs.append(s1.charAt(i-1));
i--; j--;
} else if (dp[i-1][j] > dp[i][j-1])
i--;
else
j--;
}
return lcs.reverse().toString();
}
// Edit Distance
int editDistance(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[][] dp = new int[m+1][n+1];
// Base cases
for (int i = 0; i <= m; i++) dp[i][0] = i;
for (int j = 0; j <= n; j++) dp[0][j] = j;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i-1) == s2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = 1 + Math.min(
dp[i-1][j], // Delete
Math.min(
dp[i][j-1], // Insert
dp[i-1][j-1] // Replace
)
);
}
}
return dp[m][n];
}54. What are Greedy Algorithms? Explain when they work and provide examples of problems that can and cannot be solved greedily.
Difficulty: MediumType: SubjectiveTopic: Greedy Algorithms
Greedy algorithms solve optimization problems by making the locally optimal choice at each step with the hope of finding a global optimum. Unlike dynamic programming which considers all possibilities, greedy algorithms commit to choices immediately without reconsidering them.
The greedy approach works when a problem exhibits two properties. First, greedy choice property means that a globally optimal solution can be arrived at by making locally optimal choices. At each step, we can make a choice that looks best at the moment without worrying about future consequences. Second, optimal substructure means that an optimal solution to the problem contains optimal solutions to subproblems.
The greedy algorithm strategy follows this pattern. Sort or organize the input if needed to identify the locally optimal choice at each step. Make the greedy choice based on some criterion like maximum value, minimum cost, earliest finish time, or highest ratio. Update the problem state after making the choice. Repeat until a solution is complete or no more choices are possible. Return the solution.
Advantages of greedy algorithms include simplicity as they are usually easy to understand and implement. They have efficiency with often linear or O of n log n time complexity. They use minimal space with typically O of 1 extra space. They are intuitive as the logic mirrors natural human decision-making.
Disadvantages include that they do not guarantee optimal solutions for all problems. They may get stuck in local optima missing the global optimum. They require proof of correctness which can be difficult. They cannot backtrack if a choice leads to suboptimal results.
Problems that CAN be solved optimally with greedy include Activity Selection where we select maximum non-overlapping activities by choosing earliest finish time. Huffman Coding creates optimal prefix codes by building tree from lowest frequency nodes. Dijkstra's Shortest Path finds shortest paths by always exploring nearest unvisited vertex. Fractional Knapsack maximizes value by taking items with highest value-to-weight ratio. Minimum Spanning Tree using Kruskal's or Prim's algorithm adds minimum weight edges avoiding cycles. Coin Change for certain coin systems like US coins where greedy gives optimal solutions.
Problems that CANNOT be solved optimally with greedy include 0 or 1 Knapsack where we cannot take fractions requiring DP. Coin Change for arbitrary coin systems like coins of 1, 3, 4 where greedy fails for amount 6. Traveling Salesman Problem where choosing nearest city repeatedly does not give optimal tour. Longest Path in a graph where greedy choices lead to local optima. Subset Sum where selecting largest elements first may miss optimal combinations.
To determine if greedy works for a problem, try the greedy approach and test with examples. Check if locally optimal choices lead to global optimum. Look for counterexamples where greedy fails. Prove the greedy choice property mathematically if possible. If greedy fails, consider dynamic programming or other approaches.
The Activity Selection problem is a classic greedy example. Given activities with start and finish times, select maximum non-overlapping activities. The greedy choice is to always pick the activity with the earliest finish time. This works because choosing earliest finish leaves maximum room for future activities. Sort by finish time, select first activity, then repeatedly select next activity that starts after previous finish.
Example Code
// Activity Selection - Greedy works!
int activitySelection(int[] start, int[] finish) {
// Sort by finish time
int n = start.length;
Activity[] activities = new Activity[n];
for (int i = 0; i < n; i++)
activities[i] = new Activity(start[i], finish[i]);
Arrays.sort(activities, (a,b) -> a.finish - b.finish);
int count = 1; // Select first
int lastFinish = activities[0].finish;
for (int i = 1; i < n; i++) {
if (activities[i].start >= lastFinish) {
count++;
lastFinish = activities[i].finish;
}
}
return count;
}
// Greedy: Always pick earliest finish
// Time: O(n log n), Space: O(n)
// Fractional Knapsack - Greedy works!
double fractionalKnapsack(int[] values, int[] weights, int W) {
int n = values.length;
Item[] items = new Item[n];
for (int i = 0; i < n; i++)
items[i] = new Item(values[i], weights[i]);
// Sort by value/weight ratio
Arrays.sort(items, (a,b) ->
Double.compare(b.ratio, a.ratio));
double totalValue = 0;
for (Item item : items) {
if (W >= item.weight) {
W -= item.weight;
totalValue += item.value;
} else {
totalValue += item.value * ((double)W / item.weight);
break;
}
}
return totalValue;
}
// Greedy: Highest value/weight ratio first
// 0/1 Knapsack - Greedy FAILS!
// Need DP instead55. Explain both the Coin Change problems: minimum coins needed and number of ways to make change. Why does greedy work for some coin systems but not others?
Difficulty: HardType: SubjectiveTopic: Coin Change Problem
There are two classic Coin Change problems. The first asks for the minimum number of coins needed to make a given amount. The second asks for the number of different ways to make the amount. Both require different approaches and have different properties.
The Minimum Coins problem gives you coin denominations and a target amount, and asks for the minimum number of coins needed to make that amount. This is an optimization problem requiring dynamic programming in the general case. The DP state is dp of i equals minimum coins needed to make amount i. The recurrence relation is: dp of i equals 1 plus min of dp of i minus coin for all coins where coin is less than or equal to i. Base case is dp of 0 equals 0 as zero coins make amount 0. Time complexity is O of n times amount where n is number of coin types. Space complexity is O of amount.
The greedy approach for minimum coins always picks the largest coin possible. For certain coin systems like US coins with denominations 1, 5, 10, 25, this greedy approach gives optimal solutions. For example, making 30 cents greedily gives 25 plus 5 equals 2 coins, which is optimal. However, for arbitrary coin systems, greedy may fail.
Consider coins 1, 3, 4 and amount 6. The greedy approach picks 4 plus 1 plus 1 equals 3 coins. But the optimal solution is 3 plus 3 equals 2 coins. This shows greedy does not work for all coin systems. The reason is that taking the largest coin first may prevent using combinations of smaller coins that sum to the optimal solution.
Canonical coin systems are those where greedy always gives optimal solutions. US coins are canonical. For a coin system to be canonical, it must satisfy certain mathematical properties related to how denominations relate to each other. Proving canonicity requires checking all possible amounts up to a certain threshold.
The Counting Ways problem asks for the number of different combinations of coins that sum to the target amount. Order does not matter, so 1 plus 2 and 2 plus 1 count as the same way. This is a counting problem also requiring DP. The DP state is dp of i equals number of ways to make amount i. The recurrence relation is: dp of i plus equals dp of i minus coin for all coins where coin is less than or equal to i. Base case is dp of 0 equals 1 as one way to make zero using no coins.
A crucial difference is the iteration order. To avoid counting duplicate combinations, we iterate over coins in the outer loop and amounts in the inner loop. This ensures each combination is counted once. If we iterate amounts in outer loop, we count permutations instead of combinations.
The unbounded version allows using each coin unlimited times. The bounded version limits how many times each coin can be used, requiring tracking both amount and coin counts.
Applications include making change in vending machines and stores, currency conversion and exchange, resource allocation problems where resources have different values, and optimizing payments in financial systems. Dynamic programming is essential for arbitrary coin systems to guarantee optimal or correct solutions.
Example Code
// Minimum Coins - DP Solution
int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1); // Initialize to impossible
dp[0] = 0; // Base case
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
// Time: O(n * amount), Space: O(amount)
// Example: coins=[1,3,4], amount=6
// dp[0]=0
// dp[1]=1 (1)
// dp[2]=2 (1+1)
// dp[3]=1 (3)
// dp[4]=1 (4)
// dp[5]=2 (4+1)
// dp[6]=2 (3+3) NOT 3 (4+1+1)
// Number of Ways - DP Solution
int coinChangeWays(int[] coins, int amount) {
int[] dp = new int[amount + 1];
dp[0] = 1; // One way to make 0
// Iterate coins in outer loop to avoid duplicates
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
// Time: O(n * amount), Space: O(amount)
// Example: coins=[1,2,3], amount=4
// Ways: [1,1,1,1], [1,1,2], [2,2], [1,3]
// Total: 4 ways
// Greedy (only works for canonical systems)
int coinChangeGreedy(int[] coins, int amount) {
Arrays.sort(coins); // Sort descending
int count = 0;
for (int i = coins.length - 1; i >= 0; i--) {
count += amount / coins[i];
amount %= coins[i];
}
return amount == 0 ? count : -1;
}
// Works for US coins [1,5,10,25]
// Fails for arbitrary systems56. Explain the Matrix Chain Multiplication problem and how dynamic programming solves it optimally.
Difficulty: HardType: SubjectiveTopic: Matrix Chain Multiplication
Matrix Chain Multiplication is a classic optimization problem where you need to find the most efficient way to multiply a sequence of matrices. The order of multiplication matters because matrix multiplication is associative but the number of scalar multiplications depends on the parenthesization.
Given matrices A1, A2, dot dot dot, An with dimensions, we want to fully parenthesize the product to minimize the total number of scalar multiplications. For example, multiplying matrices A with dimensions 10 by 30, B with 30 by 5, and C with 5 by 60 can be done as either A times B times C which is 10 times 30 times 5 plus 10 times 5 times 60 equals 1500 plus 3000 equals 4500 operations, or A times B times C which is 30 times 5 times 60 plus 10 times 30 times 60 equals 9000 plus 18000 equals 27000 operations. The first order is much more efficient.
The problem exhibits optimal substructure. The optimal way to multiply matrices from i to j includes an optimal split at some k, where we optimally multiply matrices from i to k, matrices from k plus 1 to j, and then multiply the two results. We try all possible splits and choose the one with minimum cost.
The DP solution uses a 2D table where dp of i of j represents the minimum number of scalar multiplications needed to multiply matrices from i to j. The recurrence relation is: dp of i of j equals min over all k from i to j minus 1 of dp of i of k plus dp of k plus 1 of j plus cost of multiplying resulting matrices. The cost of multiplying two matrices with dimensions p times q and q times r is p times q times r.
Base cases are dp of i of i equals 0 for all i, as multiplying a single matrix costs nothing. The evaluation order is critical. We cannot fill the table row by row or column by column because dp of i of j depends on values in the same row to the left and same column below. Instead, we fill by chain length. First compute all chains of length 1, then length 2, and so on. This ensures dependencies are computed before needed.
The algorithm stores matrix dimensions in an array where matrix i has dimensions dimensions of i minus 1 by dimensions of i. For chain length len from 2 to n, for each starting position i from 1 to n minus len plus 1, compute ending position j equals i plus len minus 1. Try all split positions k from i to j minus 1. For each k, compute cost equals dp of i of k plus dp of k plus 1 of j plus dimensions of i minus 1 times dimensions of k times dimensions of j. Update dp of i of j to minimum cost found.
Time complexity is O of n cubed because we have O of n squared subproblems, each requiring O of n work to try all splits. Space complexity is O of n squared for the DP table.
To reconstruct the optimal parenthesization, we maintain an auxiliary table split of i of j that stores the optimal split point for matrices i to j. After filling the DP table, we can recursively build the parenthesization using these split points.
The algorithm can be extended to print the optimal solution as a string with parentheses. Starting from split of 1 of n, recursively construct left and right subproblems until reaching base cases.
Applications include optimizing database query execution where operations can be reordered, optimizing expression evaluation in compilers, and any scenario involving associative operations where order affects cost. The problem demonstrates the power of DP for problems with optimal substructure where trying all possibilities directly would be exponential.
Example Code
// Matrix Chain Multiplication - DP
int matrixChainMultiplication(int[] dims) {
int n = dims.length - 1; // Number of matrices
int[][] dp = new int[n+1][n+1];
int[][] split = new int[n+1][n+1]; // For reconstruction
// Base case: single matrix costs 0
for (int i = 1; i <= n; i++)
dp[i][i] = 0;
// Fill by chain length
for (int len = 2; len <= n; len++) {
for (int i = 1; i <= n - len + 1; i++) {
int j = i + len - 1;
dp[i][j] = Integer.MAX_VALUE;
// Try all split points
for (int k = i; k < j; k++) {
// Cost = left + right + merge
int cost = dp[i][k] + dp[k+1][j] +
dims[i-1] * dims[k] * dims[j];
if (cost < dp[i][j]) {
dp[i][j] = cost;
split[i][j] = k;
}
}
}
}
return dp[1][n];
}
// Time: O(n^3), Space: O(n^2)
// Reconstruct optimal parenthesization
String getParenthesization(int[][] split, int i, int j) {
if (i == j)
return "A" + i;
return "(" +
getParenthesization(split, i, split[i][j]) +
" x " +
getParenthesization(split, split[i][j]+1, j) +
")";
}
// Example: Matrices with dimensions
// A1: 10x30, A2: 30x5, A3: 5x60
// dims = [10, 30, 5, 60]
//
// DP table:
// 1 2 3
// 1 0 1500 4500
// 2 0 0 9000
// 3 0 0 0
//
// Optimal: ((A1 x A2) x A3) = 4500 operations57. What are common optimization techniques in dynamic programming? Explain space optimization and when to apply it.
Difficulty: HardType: SubjectiveTopic: DP Optimization Techniques
Dynamic programming solutions often use significant memory, but many problems allow space optimization. Understanding these techniques is crucial for efficient implementations, especially with large inputs or memory constraints.
The most common space optimization is reducing dimensions when the current state depends only on a fixed number of previous states. In Fibonacci, the standard DP uses an array of size n, but since F of i depends only on F of i minus 1 and F of i minus 2, we can use just two variables, reducing space from O of n to O of 1.
For 2D DP problems, if row i depends only on row i minus 1, we can use two 1D arrays instead of a 2D array, alternating between them. This reduces space from O of n times m to O of m. For example, in Longest Common Subsequence, we only need the current and previous rows.
Further optimization uses a single 1D array by carefully choosing the iteration order. If we process columns from right to left, we avoid overwriting values we still need. The 0 or 1 Knapsack problem demonstrates this: iterating capacity from high to low allows using one array.
Sliding window optimization applies when the DP state depends only on a fixed-size window of previous states. Instead of storing all states, maintain only the window. This is useful in problems involving sequences or arrays.
State compression uses bitmasking for problems with small sets. Instead of storing multi-dimensional state, compress it into a single integer. Traveling Salesman Problem uses this to represent visited cities as bits, allowing DP of position of visited set instead of exponential states.
Matrix exponentiation optimizes linear recurrence relations like Fibonacci. Instead of iterating n times, represent the recurrence as matrix multiplication and use fast exponentiation to compute in O of log n time. This reduces time from O of n to O of log n.
Memoization with hash maps provides space optimization for sparse DP tables where most entries are unused. Instead of allocating the full table, store only computed states in a hash map. This is efficient when the state space is large but only a small fraction is accessed.
Bottom-up DP often allows better optimization than top-down because the iteration order is explicit. We can carefully choose the order to enable space reuse. Top-down with memoization typically requires storing all states.
When to apply space optimization depends on several factors. If memory is limited and the problem has large state space, optimization is essential. If the DP solution uses nested loops where inner states depend only on adjacent outer states, dimension reduction works well. If you need to reconstruct the solution path, full tables may be necessary as reconstruction requires tracing through states.
Trade-offs exist between space and other factors. Some optimizations increase code complexity. Reconstruction becomes harder or impossible with reduced storage. Debugging is more difficult without seeing the full table. Cache performance may change as data locality is affected.
Best practices include implementing the standard solution first to ensure correctness, then optimize if needed. Measure memory usage to determine if optimization is necessary. Test optimized code thoroughly as subtle bugs can occur. Document optimization techniques used for code maintainability. Consider whether reconstruction is needed before optimizing away the full table.
Common patterns include 1D array for Fibonacci-like sequences depending on constant previous values, two rows for 2D grid problems depending on previous row, one array with reverse iteration for knapsack-type problems, and sliding window for problems with fixed-window dependencies.
Example Code
// Example: 0/1 Knapsack Space Optimization
// Standard DP - O(n * W) space
int knapsackStandard(int[] val, int[] wt, int W, int n) {
int[][] dp = new int[n+1][W+1];
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= W; w++) {
if (wt[i-1] <= w)
dp[i][w] = Math.max(val[i-1] + dp[i-1][w-wt[i-1]],
dp[i-1][w]);
else
dp[i][w] = dp[i-1][w];
}
}
return dp[n][W];
}
// Two rows - O(2 * W) space
int knapsackTwoRows(int[] val, int[] wt, int W, int n) {
int[][] dp = new int[2][W+1];
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= W; w++) {
int curr = i % 2, prev = 1 - curr;
if (wt[i-1] <= w)
dp[curr][w] = Math.max(val[i-1] + dp[prev][w-wt[i-1]],
dp[prev][w]);
else
dp[curr][w] = dp[prev][w];
}
}
return dp[n % 2][W];
}
// One array - O(W) space
int knapsackOneArray(int[] val, int[] wt, int W, int n) {
int[] dp = new int[W+1];
for (int i = 0; i < n; i++) {
// Iterate RIGHT TO LEFT to avoid overwriting
for (int w = W; w >= wt[i]; w--) {
dp[w] = Math.max(dp[w], val[i] + dp[w - wt[i]]);
}
}
return dp[W];
}
// Fibonacci space optimization
int fibOptimized(int n) {
if (n <= 1) return n;
int prev2 = 0, prev1 = 1;
for (int i = 2; i <= n; i++) {
int curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
// Space: O(1) instead of O(n)58. Which of the following strings is a palindrome?
Difficulty: EasyType: MCQTopic: Palindrome
A palindrome reads the same forward and backward. 'level' satisfies this because reversing it gives the same word. Palindrome checking is a common interview problem requiring two-pointer or reverse-string logic.
Correct Answer: level
Example Code
boolean isPalindrome(String s){
int i=0,j=s.length()-1;
while(i<j){
if(s.charAt(i)!=s.charAt(j)) return false;
i++; j--; }
return true; }
// Input: level -> true59. Two strings are anagrams if:
Difficulty: MediumType: MCQTopic: Anagram
- They have same set of characters in any order
- They have same length only
- They start with same letter
- They contain vowels only
Anagrams have identical characters with identical counts but possibly different orders. For example, 'listen' and 'silent' are anagrams. Sorting or frequency counting is used to check this efficiently.
Correct Answer: They have same set of characters in any order
Example Code
boolean isAnagram(String a,String b){
if(a.length()!=b.length()) return false;
int[] count=new int[26];
for(char c:a.toCharArray()) count[c-'a']++;
for(char c:b.toCharArray()) count[c-'a']--;
for(int x:count) if(x!=0) return false;
return true; }60. What is the time complexity of the naive substring search algorithm for text of length n and pattern of length m?
Difficulty: MediumType: MCQTopic: Substring Search
The naive substring search checks for pattern match starting at each position in the text, leading to O(n*m) time in the worst case. More efficient algorithms like KMP reduce this to O(n+m).
Correct Answer: O(n*m)
Example Code
int search(String text,String pat){
int n=text.length(),m=pat.length();
for(int i=0;i<=n-m;i++){
int j=0; while(j<m && text.charAt(i+j)==pat.charAt(j)) j++;
if(j==m) return i; }
return -1; }61. What is the main advantage of the KMP algorithm over the naive pattern matching approach?
Difficulty: HardType: MCQTopic: KMP Algorithm
- It uses extra memory
- It avoids re-examining previously matched characters
- It performs sorting before matching
- It works only for equal-length strings
The Knuth-Morris-Pratt algorithm preprocesses the pattern to create a longest prefix-suffix table, allowing it to skip characters that have already been matched. This reduces the time complexity to O(n+m).
Correct Answer: It avoids re-examining previously matched characters
Example Code
void computeLPS(String pat,int[] lps){
int len=0; lps[0]=0; int i=1;
while(i<pat.length()){
if(pat.charAt(i)==pat.charAt(len)) lps[i++]=++len;
else if(len!=0) len=lps[len-1];
else lps[i++]=0; }
}
// KMP avoids backtracking text index.62. Which concept does the Rabin–Karp algorithm use for pattern matching?
Difficulty: MediumType: MCQTopic: Rabin-Karp
- Hashing
- Binary search
- Recursion
- Stack
Rabin–Karp uses rolling hash to compare hash values of pattern and text substrings. If hash values match, it verifies the substring directly. This approach improves average performance for multiple pattern matches.
Correct Answer: Hashing
Example Code
int search(String text,String pat){
int n=text.length(),m=pat.length(),q=101;
int p=0,t=0,h=1,d=256;
for(int i=0;i<m-1;i++) h=(h*d)%q;
for(int i=0;i<m;i++){ p=(d*p+pat.charAt(i))%q; t=(d*t+text.charAt(i))%q; }
for(int i=0;i<=n-m;i++){
if(p==t){ int j; for(j=0;j<m;j++) if(text.charAt(i+j)!=pat.charAt(j)) break;
if(j==m) return i; }
if(i<n-m){ t=(d*(t-text.charAt(i)*h)+text.charAt(i+m))%q; if(t<0)t+=q; }
}
return -1; }63. What data structure is commonly used to find the longest substring without repeating characters efficiently?
Difficulty: MediumType: MCQTopic: Longest Substring
- Stack
- Queue
- HashSet
- Binary Tree
A HashSet helps track unique characters within a sliding window. When a duplicate is found, the window start moves ahead. This achieves O(n) time for longest non-repeating substring problems.
Correct Answer: HashSet
Example Code
int lengthOfLongestSubstring(String s){
Set<Character> set=new HashSet<>();
int left=0,max=0;
for(int right=0;right<s.length();right++){
while(set.contains(s.charAt(right))) set.remove(s.charAt(left++));
set.add(s.charAt(right));
max=Math.max(max,right-left+1);
}
return max; }64. Which algorithm is best suited for multiple pattern matching in a large text?
Difficulty: HardType: MCQTopic: Pattern Matching
- KMP
- Rabin–Karp
- Aho–Corasick
- Naive
The Aho–Corasick algorithm builds a finite state automaton combining all patterns. It finds all occurrences of multiple patterns simultaneously in linear time relative to text length.
Correct Answer: Aho–Corasick
Example Code
// Aho–Corasick combines all patterns in a trie with failure links.
// Example: Patterns {he, she, hers}
// Trie built once, traverse text once.
// Time: O(n + total pattern length)
// Used in text search engines and intrusion detection.65. Write a program to reverse a string. Explain both iterative and recursive methods.
Difficulty: EasyType: SubjectiveTopic: String Reversal
To reverse a string iteratively, use two pointers from start and end, swapping characters until they meet. Recursively, reverse the substring excluding the first character and append the first character at the end. Both approaches have O(n) time complexity. Iterative uses O(1) space, recursive uses O(n) stack space.
Example Code
// Iterative
String reverse(String s){
char[] arr=s.toCharArray();
int i=0,j=arr.length-1;
while(i<j){ char t=arr[i]; arr[i]=arr[j]; arr[j]=t; i++; j--; }
return new String(arr); }
// Recursive
String revRec(String s){ if(s.length()<=1) return s;
return revRec(s.substring(1))+s.charAt(0); }66. Explain how to find the longest palindromic substring in a string.
Difficulty: MediumType: SubjectiveTopic: Longest Palindromic Substring
Expand Around Center is the most intuitive O(n²) approach. For each character, expand outward for both odd and even length palindromes and keep track of the longest one. Dynamic programming also works with O(n²) time and space. The best optimized method, Manacher’s algorithm, finds it in O(n).
Example Code
String longestPalindrome(String s){
int start=0,end=0;
for(int i=0;i<s.length();i++){
int len1=expand(s,i,i);
int len2=expand(s,i,i+1);
int len=Math.max(len1,len2);
if(len>end-start){ start=i-(len-1)/2; end=i+len/2; }
}
return s.substring(start,end+1); }
int expand(String s,int l,int r){
while(l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){ l--; r++; }
return r-l-1; }67. What is the Edit Distance problem? Explain its dynamic programming solution.
Difficulty: HardType: SubjectiveTopic: Edit Distance
Edit Distance, or Levenshtein Distance, measures the minimum operations (insert, delete, replace) needed to convert one string into another. The DP solution builds a matrix where dp[i][j] represents operations to convert first i chars of word1 to first j chars of word2. Recurrence: if chars equal, dp[i][j]=dp[i-1][j-1]; else dp[i][j]=1+min(insert,delete,replace). Time and space: O(m*n).
Example Code
int editDistance(String a,String b){
int m=a.length(),n=b.length();
int[][] dp=new int[m+1][n+1];
for(int i=0;i<=m;i++) dp[i][0]=i;
for(int j=0;j<=n;j++) dp[0][j]=j;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(a.charAt(i-1)==b.charAt(j-1)) dp[i][j]=dp[i-1][j-1];
else dp[i][j]=1+Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]));
}
}
return dp[m][n]; }68. Explain the dynamic programming approach for finding the longest common subsequence between two strings.
Difficulty: MediumType: SubjectiveTopic: Longest Common Subsequence
LCS is the longest sequence that appears in both strings, not necessarily contiguous. DP approach uses a 2D table dp[i][j] where dp[i][j] is the LCS length of prefixes of lengths i and j. Recurrence: if same character, dp[i][j]=1+dp[i-1][j-1]; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]). Time and space: O(m*n).
Example Code
int LCS(String a,String b){
int m=a.length(),n=b.length();
int[][] dp=new int[m+1][n+1];
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(a.charAt(i-1)==b.charAt(j-1)) dp[i][j]=1+dp[i-1][j-1];
else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[m][n]; }69. How do you check if one string is a rotation of another?
Difficulty: MediumType: SubjectiveTopic: String Rotation
Concatenate the first string with itself. If the second string appears as a substring in this concatenated string, it is a rotation. For example, 'erbottlewat' is a rotation of 'waterbottle'. This works in O(n) time with efficient substring search.
Example Code
boolean isRotation(String s1,String s2){
if(s1.length()!=s2.length()) return false;
String concat=s1+s1;
return concat.contains(s2); }
// waterbottle + waterbottle -> contains erbottlewat70. Explain how to count all distinct substrings of a string efficiently.
Difficulty: HardType: SubjectiveTopic: Substring Counting
Naively, generating all substrings takes O(n²) and checking uniqueness takes extra time. Efficient methods use suffix trees or suffix arrays with LCP (Longest Common Prefix) array. The number of distinct substrings equals n*(n+1)/2 minus the sum of LCP values. Time complexity: O(n log n) for suffix array method.
Example Code
// Distinct substrings = n*(n+1)/2 - sum(LCP)
// Example: s = 'aba'
// Suffixes: a, aba, ba
// Sorted: a, aba, ba
// LCP = [1,0] => sum=1
// Distinct substrings = 3*(4)/2 - 1 = 5
// Substrings: a, ab, aba, b, ba
71. Which data structure gives expected O(1) average time for insert, delete and lookup operations?
Difficulty: EasyType: MCQTopic: Hash Table Basics
- Binary Search Tree
- Hash Table
- Linked List
- Stack
A hash table uses a hash function to map keys to buckets, enabling average constant time for insert, delete and lookup under good hash & load conditions. The other structures do not guarantee O(1) for all these operations.
Correct Answer: Hash Table
Example Code
Map<Key,Value> map = new HashMap<>(); map.put(key, value); map.get(key); map.remove(key);
72. Which approach efficiently finds the longest consecutive elements sequence in an unsorted array of integers?
Difficulty: MediumType: MCQTopic: Longest Consecutive Sequence
- Sort and scan O(n log n)
- Hash set + scan O(n)
- Nested loops O(n²)
- Binary search for each element
Using a hash set you can check for each number whether it is a sequence start (num‐1 absent) then count forwards. This yields O(n) average time. Sorting would take O(n log n).
Correct Answer: Hash set + scan O(n)
Example Code
Set<Integer> s = new HashSet<>(Arrays.asList(nums)); int longest=0; for(int n:nums){ if(!s.contains(n-1)){ int cur=n; while(s.contains(cur)) cur++; longest = Math.max(longest, cur-n); } }73. In the Two Sum problem (find two indices whose values sum to target), what’s the optimal time solution using extra space?
Difficulty: EasyType: MCQTopic: Two Sum Problem
- O(n²)
- O(n log n)
- O(n)
- O(log n)
Using a hash map to store value→index while iterating allows one‐pass O(n). For each element check if target−value exists in map, then insert current value into map.
Correct Answer: O(n)
Example Code
Map<Integer,Integer> m = new HashMap<>(); for(int i=0;i<nums.length;i++){ int need=target-nums[i]; if(m.containsKey(need)) return new int[]{m.get(need), i}; m.put(nums[i], i); }74. What is the efficient way to count number of set bits (1s) in a 32‐bit integer?
Difficulty: MediumType: MCQTopic: Count Bits
- Loop each bit O(32)
- Divide by 2 repeatedly
- Use Brian Kernighan’s trick
- Convert to string then count
Brian Kernighan’s algorithm repeatedly does x = x & (x-1) which clears the lowest set bit each time. This runs in O(k) where k = number of set bits, often much less than 32.
Correct Answer: Use Brian Kernighan’s trick
Example Code
int count=0; while(x!=0){ x &= (x-1); count++; } return count;75. Given n numbers in range [0,n] with one missing, how do you find the missing number in O(n) time and O(1) space?
Difficulty: HardType: MCQTopic: Missing Number XOR
- Sum formula n(n+1)/2
- Sort and scan
- Use XOR of all indices and values
- Use hash set
XORing all numbers from 0 to n and XORing all present numbers yields the missing number since x^x=0 and x^0=x. This gives O(n) time and O(1) space without overflow risk of sum.
Correct Answer: Use XOR of all indices and values
Example Code
int res=0; for(int i=0;i<=n;i++) res ^= i; for(int num:nums) res ^= num; return res;
76. Explain how to count sub-arrays whose sum equals K in an integer array (with positive and negative values).
Difficulty: MediumType: SubjectiveTopic: Subarray Sum = K
Use prefix‐sum and hash map: as you iterate, maintain sum so far. For each index j, you want i where prefixSum[j]−prefixSum[i] = K ⇒ prefixSum[i] = prefixSum[j]−K. So check map for prefixSum[j]−K and increment count by value. Store/update current prefixSum in map. Time O(n), space O(n). Handles negatives and positives.
Example Code
Map<Integer,Integer> map=new HashMap<>(); map.put(0,1); int sum=0,count=0; for(int x:arr){ sum+=x; if(map.containsKey(sum-K)) count += map.get(sum-K); map.put(sum, map.getOrDefault(sum,0)+1); } return count;77. Explain how to check whether an integer is a power of two using bit manipulation.
Difficulty: EasyType: SubjectiveTopic: Bit Manipulation Trick
An integer >0 is a power of two if exactly one bit is set. So x>0 and (x & (x-1))==0. This clears the lowest set bit, so if only one bit was set it becomes zero. Time O(1).
Example Code
boolean isPowerOfTwo(int x){ return x>0 && (x & (x-1))==0; }78. How to count unique pairs in an array whose XOR equals a given value K? Outline an efficient method.
Difficulty: HardType: SubjectiveTopic: Two Sum Unique Pairs
Use a hash map or set: For each number x you want y = x ^ K. If y in set and pair-not-seen then count it. Mark x and y as used to avoid duplicates. Overall O(n) time, O(n) space. Bit-wise XOR property exploited instead of sum. Useful when K is large and sum collisions differ.
Example Code
Set<Integer> seen=new HashSet<>(); int count=0; for(int x:arr){ int y = x ^ K; if(seen.contains(y)){ count++; } seen.add(x); } return count;79. Describe how you would implement an LRU cache with O(1) get and put operations, using hashing and a doubly linked list.
Difficulty: MediumType: SubjectiveTopic: LRU Cache
Use a hash map from key→node and a doubly linked list storing nodes with most recently used at head and least at tail. On get: if key exists move its node to head. On put: if full remove tail node and map entry, then insert new node at head and into map. Hashing gives O(1) lookup, list gives O(1) insertion/removal. Common interview system design for caching.
Example Code
class Node{int key,val; Node prev, next;} class LRU{ Map<Integer,Node> map; Node head,tail; int cap; LRU(int c){cap=c; map=new HashMap<>(); head=new Node(); tail=new Node(); head.next=tail; tail.prev=head;} int get(int k){ if(!map.containsKey(k)) return -1; Node n=map.get(k); remove(n); insertToHead(n); return n.val;} void put(int k,int v){ if(map.containsKey(k)){ Node n=map.get(k); n.val=v; remove(n); insertToHead(n); } else { if(map.size()==cap){ Node lru=tail.prev; remove(lru); map.remove(lru.key);} Node n=new Node(k,v); map.put(k,n); insertToHead(n);} } void remove(Node n){ n.prev.next=n.next; n.next.prev=n.prev;} void insertToHead(Node n){ n.next=head.next; head.next.prev=n; head.next=n; n.prev=head;} }80. Explain how bit masking can be used to generate all subsets of a set of size n, and show time complexity.
Difficulty: HardType: SubjectiveTopic: Bit Masking
Each subset corresponds to a bit‐mask from 0 to (1<<n)−1. For mask in [0..2ⁿ−1], iterate bits from 0..n-1 and include element i if bit i in mask is set. This generates all 2ⁿ subsets in O(n·2ⁿ) time and O(n·2ⁿ) space for storing them or O(1) extra if streaming. Useful in small n search/backtracking and when bit operations are fast.
Example Code
for(int mask=0; mask<(1<<n); mask++){ List<int> subset=new ArrayList<>(); for(int i=0;i<n;i++){ if((mask & (1<<i))!=0) subset.add(arr[i]); } // process subset }