| Data Structure | Operations Time Complexity | Frequently Asked Algorithms | Popularity (out of 5) |
|---|---|---|---|
| Arrays | Access: O(1), Search: O(n), Insertion/Deletion (end): O(1), Insertion/Deletion (start/middle): O(n) | Sorting, Searching, Two Pointer Technique | 5 |
| Strings | Access: O(1), Search: O(n) | Substring Search, Palindromes, String Manipulation | 4 |
| Linked Lists | Search: O(n), Insertion/Deletion: O(1) at known position | Reversal, Cycle Detection, Merge Sort | 4 |
| Stacks | Push/Pop: O(1), Search: O(n) | Balanced Parentheses, Nearest Greater Element | 4 |
| Queues | Enqueue/Dequeue: O(1), Search: O(n) | Queue using Stacks, Circular Queue | 3 |
| Hash Tables | Search/Insertion/Deletion: Average O(1), Worst O(n) | Two Sum Problem, Count Distinct Elements | 5 |
| Binary Trees | Search/Insertion/Deletion: Average O(log n), Worst O(n) | Traversals (Inorder, Preorder, Postorder), Level Order | 4 |
| Binary Search Trees (BST) | Search/Insertion/Deletion: Average O(log n), Worst O(n) | Validation of BST, Find Kth Smallest Element | 4 |
| Heaps | Search: O(n), Insertion: O(log n), Deletion (root): O(log n) | Heap Sort, Find Kth Largest Element, Merge K Sorted Lists | 4 |
| Graphs | Varies with representation: Add Vertex: O(1), Add Edge: O(1) for Adjacency List; Add Edge: O(1), Add Vertex: O(V^2) for Adjacency Matrix | DFS, BFS, Dijkstra’s, Bellman-Ford, Floyd-Warshall | 5 |
| Tries | Insert/Search: O(length of word), Deletion: O(length of word) | Prefix Matching, Auto-suggestions | 3 |
| Dynamic Arrays | Access: O(1), Insertion/Deletion: Average O(1), Worst O(n) (resizing) | Implementing Dynamic Arrays, Resizing Strategy | 4 |
| Dynamic Programming Table | Insert/Search: O(1) | Memoization Techniques, DP on Grids | 3 |
| Algorithm | Category | Problem Solved | Time Complexity | Space Complexity | Popularity (out of 5) |
|---|---|---|---|---|---|
| Quick Sort | Divide and Conquer | Sorting arrays | Average: O(n log n) | O(log n) | 5 |
| Merge Sort | Divide and Conquer | Sorting large datasets, stable sort | O(n log n) | O(n) | 5 |
| Binary Search | Divide and Conquer | Searching in sorted arrays | O(log n) | O(1) | 5 |
| DFS | Graph Traversal | Tree and graph traversal | O(V + E) | O(V) | 5 |
| BFS | Graph Traversal | Tree and graph traversal | O(V + E) | O(V) | 5 |
| Dijkstra’s Algorithm | Greedy Algorithm | Shortest path in weighted graphs | O(V^2) or O(E + V log V) | O(V) | 5 |
| Bellman-Ford Algorithm | Dynamic Programming | Shortest paths with negative weights | O(VE) | O(V) | 4 |
| Floyd-Warshall Algorithm | Dynamic Programming | All pairs shortest paths | O(V^3) | O(V^2) | 4 |
| Kruskal’s Algorithm | Greedy Algorithm | Minimum spanning tree | O(E log E) | O(V + E) | 4 |
| Prim’s Algorithm | Greedy Algorithm | Minimum spanning tree | O(V^2) or O(E + V log V) | O(V) | 4 |
| A* Search Algorithm | Heuristic Search | Pathfinding with heuristic | Depends on heuristic | Depends on heuristic | 4 |
| Union-Find Algorithm | Disjoint Set | Network connectivity, set operations | O(α(n)) per operation | O(V) | 4 |
| Sliding Window Technique | Technique | Subarray problems | O(n) | O(1) | 5 |
| Fibonacci Series (DP) | Dynamic Programming | Dynamic Programming introduction | O(n) with memoization | O(n) | 3 |
| Knapsack Problem (DP) | Dynamic Programming | Subset optimization | O(nW) | O(nW) | 4 |
| Longest Common Subsequence | Dynamic Programming | Subsequence problems | O(mn) | O(mn) | 4 |
| Bubble Sort | Simple Sort | Simple sorting | O(n^2) | O(1) | 3 |
| Insertion Sort | Simple Sort | Sorting small datasets, insertion | O(n^2) | O(1) | 3 |
| Selection Sort | Simple Sort | Selection and sorting | O(n^2) | O(1) | 3 |
| Question | Popularity |
|---|---|
| Reverse a linked list | 5 |
| Detect cycle in a linked list | 4 |
| Implement depth-first search (DFS) and breadth-first search (BFS) in a graph | 5 |
| Find the "Kth" max/min element of an array | 4 |
| Implement a binary search | 5 |
| Find the lowest common ancestor in a binary search tree or binary tree | 4 |
| Implement a trie (prefix tree) and its operations | 3 |
| Solve the knapsack problem using dynamic programming | 4 |
| Implement quicksort and mergesort | 5 |
| Find the longest consecutive sequence in an array | 4 |
| Check if a given binary tree is a valid binary search tree | 4 |
| Implement a hash map from scratch | 4 |
| Find the longest substring without repeating characters | 5 |
| Implement an LRU (Least Recently Used) cache | 4 |
| Calculate the maximum subarray sum (Kadane’s algorithm) | 5 |
| Find all subsets of a set (power set) | 3 |
| Solve the "N-Queens" problem | 3 |
| Find the shortest path in a grid/maze (using BFS/DFS or Dijkstra’s) | 4 |
| Merge K sorted lists | 4 |
| Implement a stack using queues and vice versa | 3 |
| Find all permutations of a string/array | 3 |
| Check for balanced parentheses in an expression | 5 |
| Approach/Algorithm | When to Use | Hints/Indicators |
|---|---|---|
| Dynamic Programming | When a problem can be divided into overlapping subproblems | - Overlapping subproblems - Optimal substructure |
| Greedy Algorithms | When making locally optimal choices can lead to a global optimum | - Problems involving "minimum", "maximum", "shortest", "longest" |
| Divide and Conquer | When a problem can be broken down into smaller instances of the same problem | - Recursively breaking a problem into two or more subproblems |
| Backtracking | When you need to explore all possible solutions and eliminate invalid ones | - Problems requiring the exploration of all configurations - Constraint satisfaction |
| Graph Algorithms | When dealing with problems modeled as graphs | - Problems mentioning "networks", "connections", "relationships" |
| Bit Manipulation | When solving problems more efficiently using bits | - Problems involving integers, bitwise operations, and optimization |
| Breadth-First Search (BFS) | When finding the shortest path or level order traversal | - Shortest path in unweighted graph - Level order traversal in trees |
| Depth-First Search (DFS) | When exploring all branches of a path or when detecting cycles | - Exploring mazes or puzzles - Cycle detection in graphs |
| Binary Search | When the dataset is sorted and you're searching for an element | - Sorted array - Finding an element or the closest value in a sorted collection |
| Sorting Algorithms | When data needs to be ordered or rearranged | - Sorting data for easier access or manipulation - Preprocessing for other algorithms |
| Heap/Priority Queue | When needing quick access to the "next" element based on a priority | - Finding the smallest/largest element - Implementing schedulers |
| # | Category | Questions | Skills Developed | Popularity (out of 5) | Time Complexity | Space Complexity |
|---|---|---|---|---|---|---|
| 1 | Array and String | Find the maximum product of two integers in an array. | Array manipulation, problem-solving | 3 | O(n) | O(1) |
| 2 | Implement an algorithm to rotate an array. | Array manipulation, understanding rotations | 4 | O(n) | O(1) | |
| 3 | Compress a string with repeated characters. | String manipulation, compression algorithms | 2 | O(n) | O(1) | |
| 4 | Linked Lists | Reverse a linked list. | Understanding of pointers, recursion | 5 | O(n) | O(1) |
| 5 | Merge two sorted linked lists. | Problem-solving, working with linked lists | 4 | O(n + m) | O(1) | |
| 6 | Detect a cycle in a linked list. | Cycle detection, two pointer technique | 4 | O(n) | O(1) | |
| 7 | Stacks and Queues | Implement a stack using queues and vice versa. | Abstract Data Type (ADT) implementation | 3 | O(n) for some ops | O(n) |
| 8 | Evaluate an arithmetic expression (Reverse Polish Notation). | Understanding stack operations | 3 | O(n) | O(n) | |
| 9 | Implement a function to sort a stack. | Sorting, stack manipulation | 2 | O(n^2) | O(n) | |
| 10 | Trees and Graphs | Implement tree traversals (inorder, preorder, postorder). | Tree traversal techniques | 4 | O(n) | O(h) |
| 11 | Find the lowest common ancestor in a binary tree. | Tree manipulation, depth-first search | 3 | O(n) | O(h) | |
| 12 | Implement DFS and BFS on a graph. | Graph traversal, understanding graph theory | 4 | O(V + E) | O(V) | |
| 13 | Sorting and Searching | Implement merge sort and quicksort. | Sorting algorithms, divide and conquer | 4 | O(n log n) | O(n) |
| 14 | Search in a rotated sorted array. | Binary search, array manipulation | 3 | O(log n) | O(1) | |
| 15 | Find the kth largest/smallest element in an array. | Quickselect, heaps | 4 | O(n) average | O(1) | |
| 16 | Dynamic Programming | Solve the 0/1 knapsack problem. | Dynamic programming, optimization | 5 | O(nW) | O(nW) |
| 17 | Find the longest increasing subsequence in an array. | DP, patience sorting | 4 | O(n log n) | O(n) | |
| 18 | Compute the edit distance between two strings. | DP, string manipulation | 4 | O(mn) | O(mn) | |
| 19 | Hashing | Implement a hash map from scratch. | Understanding hashing, collision resolution | 2 | O(1) average | O(n) |
| 20 | Find the first non-repeating character in a string. | Hashing, string analysis | 4 | O(n) | O(1) | |
| 21 | Group anagrams from a list of strings. | Hashing, sorting, string manipulation | 4 | O(nk log k) | O(nk) | |
| 22 | Advanced Data Structures | Implement a trie (prefix tree) and its operations. | Trie implementation, auto-completion features | 3 | O(L) for L length | O(L) for L length |
| 23 | Design and implement an LRU cache. | Cache design, linked lists, hashing | 4 | O(1) for all ops | O(capacity) | |
| 24 | Implement a segment tree for range sum query. | Segment tree, lazy propagation | 3 | O(log n) for ops | O(n) | |
| 25 | Greedy Algorithms | Schedule jobs to maximize job completion. | Greedy algorithms, scheduling problems | 3 | O(n log n) | O(n) |
| 26 | Find the minimum number of platforms required for a railway station. | Greedy algorithms, interval scheduling | 3 | O(n log n) | O(n) | |
| 27 | Graph Algorithms | Implement Dijkstra’s algorithm for the shortest path in a graph. | Graph theory, shortest path problem | 5 | O((V+E) log V) | O(V) |
| 28 | Solve the "Course Schedule" problem (topological sort). | Graph theory, cycle detection, scheduling | 4 | O(V + E) | O(V + E) | |
| 29 | Find the number of islands using DFS/BFS (grid as a graph representation). | Graph traversal, connected components | 4 | O(mn) | O(min(m,n)) | |
| 30 | Bit Manipulation | Count the number of 1 bits in an integer. | Bitwise operations | 3 | O(1) | O(1) |
| 31 | Reverse bits of a given integer. | Bit manipulation, reverse operations | 2 | O(1) | O(1) | |
| 32 | Find the single non-repeated element in an array where every element repeats. | Bit manipulation, XOR operation | 4 | O(n) | O(1) | |
| 33 | Backtracking | Solve the N-Queens problem. | Backtracking, problem-solving | 4 | O(n!) | O(n) |
| 34 | Generate all permutations of a given string/array. | Backtracking, generating permutations | 3 | O(n!) | O(n) | |
| 35 | Implement Sudoku solver. | Backtracking, puzzle solving | 5 | O(9^(n^2)) | O(n^2) |
# Category: Array and String
# Question: Find the maximum product of two integers in an array.
def max_product(nums):
"""
Find the maximum product of two integers in an array.
Args:
nums: List[int] -- list of integers
Returns:
int -- the maximum product of two integers in the list
"""
# Sort the array to have the largest numbers at the end
nums.sort()
# The maximum product can be the product of the two largest numbers
# or the product of the two smallest numbers (if they are negative)
return max(nums[0] * nums[1], nums[-1] * nums[-2])
# Sample Input
nums = [-10, -3, 5, 6, -2]
# Sample Output
print(max_product(nums)) # 30# Category: Array and String
# Question: Implement an algorithm to rotate an array.
def rotate_array(nums, k):
"""
Rotate an array to the right by k steps.
Args:
nums: List[int] -- list of integers
k: int -- number of steps to rotate the array
Returns:
None -- The input list is modified in-place
"""
n = len(nums)
# Ensure k is within the bounds of the array's length
k %= n
# Reverse the entire array, reverse the first k elements,
# and then reverse the rest
nums[:] = nums[::-1]
nums[:k] = nums[:k][::-1]
nums[k:] = nums[k:][::-1]
# Sample Input
nums = [1, 2, 3, 4, 5, 6, 7]
k = 3
# Rotate and print output
rotate_array(nums, k)
print(nums) # [5, 6, 7, 1, 2, 3, 4]# Category: Array and String
# Question: Compress a string with repeated characters.
def compress_string(s):
"""
Compress a string such that 'AAABCCDDDD' becomes 'A3BC2D4'.
Only compress the string if it becomes smaller than the original.
Args:
s: str -- input string
Returns:
str -- compressed string or original string if compression doesn't reduce the size
"""
# Initialize variables
compressed = []
count = 1
# Iterate over the string
for i in range(1, len(s) + 1):
if i < len(s) and s[i] == s[i-1]:
count += 1
else:
# Append the current character and its count if more than 1
compressed.append(s[i-1] + (str(count) if count > 1 else ''))
count = 1
# Convert list back to string
compressed_string = ''.join(compressed)
# Return the original string if compression doesn't reduce the size
return compressed_string if len(compressed_string) < len(s) else s
# Sample Input
s = "AAABCCDDDD"
# Sample Output
print(compress_string(s)) # A3BC2D4# Category: Linked Lists
# Question: Reverse a linked list.
class ListNode:
"""Definition for singly-linked list."""
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_linked_list(head):
"""
Reverse a linked list.
Args:
head: ListNode -- head node of the linked list
Returns:
ListNode -- head node of the reversed linked list
"""
prev = None
current = head
while current:
next_node = current.next # Store next node
current.next = prev # Reverse current node's pointer
prev = current # Move pointers one position ahead
current = next_node
return prev
# Sample Input: [1, 2, 3, 4, 5]
# Sample Output: 5 -> 4 -> 3 -> 2 -> 1# Category: Linked Lists
# Question: Merge two sorted linked lists.
def merge_two_lists(l1, l2):
"""
Merge two sorted linked lists and return it as a new sorted list.
Args:
l1: ListNode -- head of the first linked list
l2: ListNode -- head of the second linked list
Returns:
ListNode -- head of the merged and sorted linked list
"""
prehead = ListNode(-1)
prev = prehead
while l1 and l2:
if l1.val <= l2.val:
prev.next = l1
l1 = l1.next
else:
prev.next = l2
l2 = l2.next
prev = prev.next
prev.next = l1 if l1 is not None else l2
return prehead.next
# Sample Input: L1 = [1, 2, 4], L2 = [1, 3, 4]
# Sample Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4# Category: Linked Lists
# Question: Detect a cycle in a linked list.
def has_cycle(head):
"""
Determine if a linked list has a cycle in it.
Args:
head: ListNode -- head node of the linked list
Returns:
bool -- True if there is a cycle, False otherwise
"""
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
# Sample Input: A linked list where the tail connects to the second node.
# Sample Output: True# Category: Stacks and Queues
# Question: Implement a stack using queues.
# Approach: Use two queues, where one queue is used to store the entire stack and another is used temporarily during the push operation.
from collections import deque
class StackUsingQueues:
def __init__(self):
"""
Initialize your data structure here.
"""
self.queue = deque()
def push(self, x):
"""
Push element x onto stack.
"""
temp_queue = deque([x])
while self.queue:
temp_queue.append(self.queue.popleft())
self.queue = temp_queue
def pop(self):
"""
Removes the element on top of the stack and returns that element.
"""
return self.queue.popleft()
def top(self):
"""
Get the top element.
"""
return self.queue[0]
def empty(self):
"""
Returns whether the stack is empty.
"""
return not self.queue
# Sample Output:
# Top element: 3
# Pop element: 3
# Is empty: False# Category: Stacks and Queues
# Question: Evaluate an arithmetic expression given in Reverse Polish Notation (Postfix Expression).
# Approach: Use a stack to keep track of numbers. When an operator is encountered, pop two numbers, apply the operation, and push the result back.
def eval_rpn(tokens):
"""
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Args:
tokens: List[str] -- list of tokens
Returns:
int -- the result of the expression
"""
stack = []
for token in tokens:
if token in "+-*/":
b, a = stack.pop(), stack.pop()
if token == '+': result = a + b
elif token == '-': result = a - b
elif token == '*': result = a * b
elif token == '/': result = int(a / b)
stack.append(result)
else:
stack.append(int(token))
return stack.pop()
# Sample Output: RPN Evaluation: 9# Category: Stacks and Queues
# Question: Implement a function to sort a stack.
# Approach: Use a temporary stack to sort the elements in descending order, and then push everything back to the original stack to maintain ascending order.
def sort_stack(stack):
"""
Sort a stack in ascending order (with the smallest items on top).
Args:
stack: List[int] -- input stack represented as a list
Returns:
None -- The input stack is sorted in-place
"""
temp_stack = []
while stack:
temp = stack.pop()
while temp_stack and temp_stack[-1] > temp:
stack.append(temp_stack.pop())
temp_stack.append(temp)
while temp_stack:
stack.append(temp_stack.pop())
# Sample Output: Sorted stack: [3, 23, 31, 34, 92, 98]# Category: Trees and Graphs
# Question: Implement tree traversals (inorder, preorder, postorder).
# Approach: Use recursion to visit nodes in the correct order for each type of traversal.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorder_traversal(root):
if not root:
return []
return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)
def preorder_traversal(root):
if not root:
return []
return [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right)
def postorder_traversal(root):
if not root:
return []
return postorder_traversal(root.left) + postorder_traversal(root.right) + [root.val]
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print("Inorder Traversal:", inorder_traversal(root)) # Output: [4, 2, 5, 1, 3]
print("Preorder Traversal:", preorder_traversal(root)) # Output: [1, 2, 4, 5, 3]
print("Postorder Traversal:", postorder_traversal(root)) # Output: [4, 5, 2, 3, 1]# Category: Trees and Graphs
# Question: Find the lowest common ancestor in a binary search tree or binary tree.
# Approach: Use properties of BST or binary tree to navigate and find the lowest common ancestor.
def lowest_common_ancestor(root, p, q):
if not root:
return None
if root.val < p.val and root.val < q.val:
return lowest_common_ancestor(root.right, p, q)
elif root.val > p.val and root.val > q.val:
return lowest_common_ancestor(root.left, p, q)
else:
return root
p = TreeNode(2)
q = TreeNode(5)
lca = lowest_common_ancestor(root, p, q)
print("Lowest Common Ancestor:", lca.val) # Assuming p = 2 and q = 5 for the given sample tree, Output: 2# Category: Trees and Graphs
# Question: Implement DFS and BFS on a graph.
# Approach for DFS: Use a stack or recursion to explore nodes, marking visited ones.
# Approach for BFS: Use a queue to explore nodes level by level, marking visited ones.
from collections import deque
def dfs(graph, start):
visited = set()
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
stack.extend(graph[vertex] - visited)
return visited
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
queue.extend(graph[vertex] - visited)
return visited
# Sample Output:
# DFS: {'F', 'E', 'C', 'A', 'B', 'D'}
# BFS: {'F', 'E', 'C', 'A', 'B', 'D'}# Category: Sorting and Searching
# Question: Implement merge sort.
# Approach: Divide the array into halves, sort each half, and then merge them together.
def merge_sort(arr):
"""
Sort an array using the merge sort algorithm.
Args:
arr: List[int] -- the array to sort
"""
if len(arr) > 1:
mid = len(arr) // 2 # Find the midpoint of the array
L = arr[:mid] # Dividing the array elements into 2 halves
R = arr[mid:]
merge_sort(L) # Sorting the first half
merge_sort(R) # Sorting the second half
i = j = k = 0
# Copy data to temp arrays L[] and R[]
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# Checking if any element was left
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
# Sample Input: [38, 27, 43, 3, 9, 82, 10]
# Sample Output: Merge Sorted: [3, 9, 10, 27, 38, 43, 82]# Category: Sorting and Searching
# Question: Implement quicksort.
# Approach: Choose a pivot, partition the array around the pivot, and recursively sort the partitions.
def quick_sort(arr):
"""
Quick sort algorithm implementation.
Args:
arr: List[int] -- the array to be sorted
Returns:
List[int] -- the sorted array
"""
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # Selecting the middle element as pivot
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# Sample Input: [38, 27, 43, 3, 9, 82, 10]
# Sample Output: Quick Sorted: [3, 9, 10, 27, 38, 43, 82]# Category: Sorting and Searching
# Question: Search in a rotated sorted array.
# Approach: Use binary search with additional conditions to determine the sorted part of the array.
def search_rotated_array(arr, target):
"""
Search in a rotated sorted array.
Args:
arr: List[int] -- the rotated sorted array
target: int -- the target value to search for
Returns:
int -- the index of target if found, -1 otherwise
"""
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
if arr[left] <= arr[mid]: # Left half is sorted
if arr[left] <= target < arr[mid]:
right = mid - 1
else:
left = mid + 1
else: # Right half is sorted
if arr[mid] < target <= arr[right]:
left = mid + 1
else:
right = mid - 1
return -1
# Sample Input: [4,5,6,7,0,1,2], target = 0
# Sample Output: Index of target in rotated array: 4# Category: Sorting and Searching
# Question: Find the kth largest element in an array.
# Approach: Use a sorting algorithm and then access the kth element from the end for the kth largest.
def find_kth_largest(nums, k):
"""
Find the kth largest element in an unsorted array.
Args:
nums: List[int] -- the array to search
k: int -- the "kth" largest element to find
Returns:
int -- the kth largest element in the array
"""
nums.sort(reverse=True) # Sort the array in descending order
return nums[k-1] # Access the kth largest element
# Sample Input: [3,2,3,1,2,4,5,5,6], k = 4
# Sample Output: Kth largest element: 4# Category: Dynamic Programming
# Question: Solve the 0/1 knapsack problem.
# Approach: Use dynamic programming to build up a table `dp` where `dp[i][w]` represents the maximum value that can be achieved with the first i items and a weight limit of w.
def knapsack(values, weights, W):
n = len(values)
dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, W + 1):
if weights[i-1] <= w:
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
else:
dp[i][w] = dp[i-1][w]
return dp[n][W]
# Sample Output: Knapsack Problem: 220# Category: Dynamic Programming
# Question: Find the longest increasing subsequence.
# Approach: Use dynamic programming where `dp[i]` represents the length of the longest increasing subsequence ending with the ith element.
def length_of_lis(nums):
if not nums:
return 0
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# Sample Output: Longest Increasing Subsequence: 4# Category: Dynamic Programming
# Question: Compute the edit distance between two strings.
# Approach: Use dynamic programming where `dp[i][j]` represents the edit distance between the first i characters of `word1` and the first j characters of `word2`.
def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0:
dp[i][j] = j # Min operations = j (all insertions)
elif j == 0:
dp[i][j] = i # Min operations = i (all deletions)
elif word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], # Delete
dp[i][j-1], # Insert
dp[i-1][j-1]) # Replace
return dp[m][n]
# Sample Output: Edit Distance: 3# Category: Hashing
# Question: Implement a hash map from scratch.
# Approach: Use an array to store values and a hash function to map keys to indices. Handle collisions using chaining (linked list).
class MyHashMap:
def __init__(self):
self.size = 1000
self.hash_table = [None] * self.size
def put(self, key, value):
index = key % self.size
if self.hash_table[index] == None:
self.hash_table[index] = ListNode(key, value)
else:
current = self.hash_table[index]
while True:
if current.pair[0] == key:
current.pair = (key, value) # Update value
return
if current.next == None: break
current = current.next
current.next = ListNode(key, value)
def get(self, key):
index = key % self.size
current = self.hash_table[index]
while current:
if current.pair[0] == key:
return current.pair[1]
current = current.next
return -1
def remove(self, key):
index = key % self.size
current = prev = self.hash_table[index]
if not current: return
if current.pair[0] == key:
self.hash_table[index] = current.next
else:
current = current.next
while current:
if current.pair[0] == key:
prev.next = current.next
break
current, prev = current.next, current
# Sample Output:
# Value at key 1: 1
# Value at key 3: -1
# Updated value at key 2: 1
# Value at key 2 after removal: -1# Category: Hashing
# Question: Find the first non-repeating character in a string.
# Approach: Use a hash table to count the occurrences of each character, then iterate through the string to find the first character that occurs only once.
def first_uniq_char(s):
count = {}
for char in s:
count[char] = count.get(char, 0) + 1
for i, char in enumerate(s):
if count[char] == 1:
return i
return -1
# Sample Output: First unique character index in 'leetcode': 0# Category: Hashing
# Question: Group anagrams from a list of strings.
# Approach: Use a hash table where the key is a tuple of sorted characters and the value is a list of strings that are anagrams.
def group_anagrams(strs):
anagrams = {}
for s in strs:
sorted_str = tuple(sorted(s))
if sorted_str in anagrams:
anagrams[sorted_str].append(s)
else:
anagrams[sorted_str] = [s]
return list(anagrams.values())
# Sample Output: Grouped anagrams: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]# Category: Advanced Data Structures
# Question: Implement a trie (prefix tree) and its operations like insert, search, and startsWith.
# Approach: Each node stores a dict of its children and a flag indicating the end of a word. Traverse the trie based on the input string for each operation.
class TrieNode:
# Initialize your data structure here.
def __init__(self):
self.children = {}
self.isEndOfWord = False
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = TrieNode()
def insert(self, word):
"""
Inserts a word into the trie.
"""
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.isEndOfWord = True
def search(self, word):
"""
Returns if the word is in the trie.
"""
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.isEndOfWord
def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
# Sample operations
trie = Trie()
trie.insert("apple")
print("Search 'apple':", trie.search("apple")) # Output: True
print("Search 'app':", trie.search("app")) # Output: False
print("StartsWith 'app':", trie.startsWith("app")) # Output: True# Category: Advanced Data Structures
# Question: Design and implement an LRU (Least Recently Used) cache.
# Approach: Use a hashmap for O(1) lookups and a doubly linked list to maintain insertion order ie. Combine a hashmap and a doubly linked list to achieve O(1) time complexity for all operations. The hashmap tracks the nodes, while the doubly linked list maintains the order.
class LRUCache:
class DoublyLinkedListNode:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
def __init__(self, capacity: int):
self.cache = {}
self.head = self.DoublyLinkedListNode()
self.tail = self.DoublyLinkedListNode()
self.head.next = self.tail
self.tail.prev = self.head
self.capacity = capacity
self.size = 0
# Class definitions for LRUCache, DoublyLinkedListNode, and associated methods would be repeated here.
# Let's proceed to a simple demonstration of using the LRUCache.
# Sample operations
lruCache = LRUCache(2)
lruCache.put(1, 1)
lruCache.put(2, 2)
print("Get 1:", lruCache.get(1)) # Output: 1
lruCache.put(3, 3) # Evicts key 2
print("Get 2:", lruCache.get(2)) # Output: -1# Category: Advanced Data Structures
# Question: Implement a segment tree for range sum query.
# Approach: The segment tree is built as a binary tree where each node represents an interval sum. Leaf nodes represent individual elements, and internal nodes represent the sum of intervals.
class SegmentTree:
# Initialization and methods to build the tree, update a value,
def __init__(self, nums):
"""
Initializes the segment tree with a list of integers.
"""
self.n = len(nums)
self.tree = [0] * (4 * self.n) # Allocate memory for the segment tree
self.buildTree(nums, 0, 0, self.n - 1)
def buildTree(self, nums, treeIndex, lo, hi):
"""
Recursively builds the segment tree.
"""
if lo == hi: # Leaf node
self.tree[treeIndex] = nums[lo]
return
mid = (lo + hi) // 2 # Midpoint of current segment
self.buildTree(nums, 2 * treeIndex + 1, lo, mid) # Build left subtree
self.buildTree(nums, 2 * treeIndex + 2, mid + 1, hi) # Build right subtree
self.tree[treeIndex] = self.tree[2 * treeIndex + 1] + self.tree[2 * treeIndex + 2] # Sum of left and right children
def update(self, index, val):
"""
Updates the value at a specific index in the array and rebuilds the tree accordingly.
"""
self.updateHelper(0, 0, self.n - 1, index, val)
def updateHelper(self, treeIndex, lo, hi, index, val):
if lo == hi: # Leaf node
self.tree[treeIndex] = val
return
mid = (lo + hi) // 2 # Midpoint of current segment
if index <= mid:
self.updateHelper(2 * treeIndex + 1, lo, mid, index, val) # Update left subtree
else:
self.updateHelper(2 * treeIndex + 2, mid + 1, hi, index, val) # Update right subtree
self.tree[treeIndex] = self.tree[2 * treeIndex + 1] + self.tree[2 * treeIndex + 2] # Update current node
def sumRange(self, i, j):
"""
Returns the sum of the elements of nums between indices i and j (i ≤ j), inclusive.
"""
return self.sumRangeHelper(0, 0, self.n - 1, i, j)
def sumRangeHelper(self, treeIndex, lo, hi, i, j):
if lo > j or hi < i: # Segment completely outside range
return 0
if i <= lo and hi <= j: # Segment completely inside range
return self.tree[treeIndex]
mid = (lo + hi) // 2 # Midpoint of current segment
if j <= mid: # Target segment is fully in the left child
return self.sumRangeHelper(2 * treeIndex + 1, lo, mid, i, j)
if i > mid: # Target segment is fully in the right child
return self.sumRangeHelper(2 * treeIndex + 2, mid + 1, hi, i, j)
# Target segment is partially in both children
return self.sumRangeHelper(2 * treeIndex + 1, lo, mid, i, j) + self.sumRangeHelper(2 * treeIndex + 2, mid + 1, hi, i, j)
# Demonstration of Segment Tree for Range Sum Query
nums = [1, 3, 5, 7, 9, 11]
segmentTree = SegmentTree(nums)
print("Sum of range (1, 3):", segmentTree.sumRange(1, 3)) # Output: 15 (3 + 5 + 7)
segmentTree.update(1, 10) # Update index 1 to value 10
print("Sum of range (1, 3) after update:", segmentTree.sumRange(1, 3)) # Output: 22 (10 + 5 + 7)# Category: Greedy Algorithms
# Question: Schedule jobs to maximize job completion considering their start time, end time, and profit.
# Approach: Sort the jobs by their end times. Use dynamic programming to track the maximum profit up to each job, considering the inclusion and exclusion of the current job based on profit.
import bisect
def jobScheduling(startTime, endTime, profit):
"""
Find the maximum profit from non-overlapping jobs using a greedy approach.
Args:
startTime: List[int]
endTime: List[int]
profit: List[int]
Returns:
int: Maximum profit achievable.
"""
jobs = sorted(zip(startTime, endTime, profit), key=lambda v: v[1])
dp = [[0, 0]] # [endTime, profit] starting with a dummy job
for start, end, cur_profit in jobs:
# Find the latest job that doesn't conflict
i = bisect.bisect_left(dp, [start + 1]) - 1
if dp[i][1] + cur_profit > dp[-1][1]:
dp.append([end, dp[i][1] + cur_profit])
return dp[-1][1]
# Sample Input/Output
startTime = [1, 2, 3, 4]
endTime = [3, 5, 10, 6]
profit = [20, 20, 100, 70]
print("Maximized Job Completion Profit:", jobScheduling(startTime, endTime, profit))
# Output: 150 (Choosing jobs starting at 1 and 3)# Category: Greedy Algorithms
# Question: Find the minimum number of platforms required for a railway station given arrival and departure times of all trains.
# Approach: Sort the arrival and departure times separately. Use two pointers for arrivals and departures to track the count of platforms needed at any moment, maintaining the maximum count throughout.
def findPlatform(arr, dep):
"""
Calculate the minimum number of platforms required for the railway station.
Args:
arr: List[int] -- Arrival times of trains.
dep: List[int] -- Departure times of trains.
Returns:
int: Minimum number of platforms required.
"""
arr.sort()
dep.sort()
n = len(arr)
plat_needed = 1
result = 1
i = 1
j = 0
while i < n and j < n:
if arr[i] <= dep[j]:
plat_needed += 1
i += 1
elif arr[i] > dep[j]:
plat_needed -= 1
j += 1
result = max(result, plat_needed)
return result
# Sample Input/Output
arr = [900, 940, 950, 1100, 1500, 1800]
dep = [910# Category: Graph Algorithms
# Question: Implement Dijkstra’s algorithm to find the shortest path from a source node to all other nodes in a weighted graph without negative weights.
# Approach: Use a priority queue to keep track of the minimum distance from the source node to each node. Update the distances as shorter paths are found.
import heapq
def dijkstra(graph, start):
"""
Finds the shortest paths from start to all other nodes in the graph.
Args:
graph: Dict[int, List[Tuple[int, int]]] -- The graph represented as adjacency list where the key is the node and the value is a list of pairs (neighbor, weight).
start: int -- The starting node.
Returns:
Dict[int, int] -- Shortest distance from start to each node.
"""
# Initialize distances from start to node as infinity
distances = {node: float('infinity') for node in graph}
distances[start] = 0
# Priority queue: (distance, node)
queue = [(0, start)]
while queue:
current_distance, current_node = heapq.heappop(queue)
# If this distance was already found to be larger, skip processing
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node]:
distance = current_distance + weight
# If a shorter path is found
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances
# Sample Input/Output
graph = {
0: [(1, 4), (2, 1)],
1: [(3, 1)],
2: [(1, 2), (3, 5)],
3: []
}
start = 0
print("Shortest paths from node 0:", dijkstra(graph, start))# Category: Graph Algorithms
# Question: Implement the Bellman-Ford algorithm to find the shortest path from a source node to all other nodes in a graph, supporting negative weights.
# Approach: Relax all edges N-1 times (where N is the number of vertices). Check for negative weight cycles by attempting a Nth relaxation.
def bellman_ford(edges, V, start):
"""
Finds the shortest paths from start to all other nodes, even with negative weights.
Args:
edges: List[Tuple[int, int, int]] -- List of edges represented as tuples (source, destination, weight).
V: int -- Number of vertices in the graph.
start: int -- The starting node.
Returns:
List[int] -- Distance to all nodes from start. Inf for unreachable nodes, 'Negative Cycle' if a negative cycle is detected.
"""
# Initialize distances from start
distance = [float('infinity')] * V
distance[start] = 0
# Relax all edges V-1 times
for _ in range(V - 1):
for source, destination, weight in edges:
if distance[source] != float('infinity') and distance[source] + weight < distance[destination]:
distance[destination] = distance[source] + weight
# Check for negative-weight cycles
for source, destination, weight in edges:
if distance[source] != float('infinity') and distance[source] + weight < distance[destination]:
return "Graph contains a negative-weight cycle"
return distance
# Sample Input/Output
edges = [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5)]
V = 4
start = 0
print("Shortest paths from node 0:", bellman_ford(edges, V, start))# Category: Graph Algorithms
# Question: Implement the A* Search algorithm to find the shortest path from a start node to a target node, using heuristics to guide the search.
# Approach: A* Search uses a priority queue and combines the actual cost from the start node to the current node and a heuristic estimate from the current node to the target to prioritize nodes. It guarantees the shortest path under certain conditions on the heuristic.
import heapq
def a_star_search(graph, start, target, heuristic):
"""
A* search algorithm to find the shortest path from start to target.
Args:
graph: Dict[int, List[Tuple[int, int]]] -- Graph represented as adjacency list where each node points to a list of (neighbor, cost).
start: int -- The starting node.
target: int -- The target node.
heuristic: Dict[int, int] -- Heuristic estimates from each node to the target.
Returns:
int: Total cost of the shortest path from start to target.
"""
open_set = [(0 + heuristic[start], 0, start)] # (F-score, G-score, Node)
came_from = {} # For path reconstruction
g_score = {node: float('infinity') for node in graph}
g_score[start] = 0
while open_set:
_, current_g, current = heapq.heappop(open_set)
if current == target:
return current_g
for neighbor, cost in graph[current]:
tentative_g_score = current_g + cost
if tentative_g_score < g_score[neighbor]:
came_from[neighbor] = current
g_score[neighbor] = tentative_g_score
f_score = tentative_g_score + heuristic[neighbor]
heapq.heappush(open_set, (f_score, tentative_g_score, neighbor))
return "Path not found"
# Sample heuristic function for A* (example: Manhattan distance if applicable)
heuristic = {0: 10, 1: 8, 2: 5, 3: 7, 4: 3, 5: 6, 6: 0} # Example heuristic values to the target
# Sample graph input and execution
graph = {
0: [(1, 4), (2, 2)],
1: [(3, 5)],
2: [(1, 1), (3, 8), (4, 10)],
3: [(5, 3), (6, 5)],
4: [(5, 6)],
5: [(6, 1)],
6: []
}
start = 0
target = 6
print("A* Search Cost from Node 0 to 6:", a_star_search(graph, start, target, heuristic))# Category: Graph Algorithms
# Question: Given a Directed Acyclic Graph (DAG), find all possible paths from a given start node to a target node.
# Approach: Use Depth-First Search (DFS) to explore all paths. Since the graph is acyclic, we can safely explore each path without worrying about infinite loops.
def findAllPaths(graph, start, end):
"""
Finds all paths from start to end in a given DAG.
Args:
graph: Dict[int, List[int]] -- Graph represented as adjacency list.
start: int -- Starting node.
end: int -- Ending node.
Returns:
List[List[int]]: All paths from start to end.
"""
def dfs(node, path):
if node == end:
paths.append(path)
return
for next_node in graph.get(node, []):
dfs(next_node, path + [next_node])
paths = []
dfs(start, [start])
return paths
# Sample graph and execution
graph = {
0: [1, 2],
1: [3],
2: [3],
3: [4],
4: []
}
start = 0
end = 4
print("All paths from Node 0 to 4:", findAllPaths(graph, start, end))# Category: Bit Manipulation
# Question: Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).
# Approach: Iterate through each bit of the number. Use the bitwise AND operation to check if a bit is set (1) and increment a count. Right shift the number in each iteration until the number becomes 0.
def hammingWeight(n):
"""
Count the number of 1 bits in an unsigned integer.
Args:
n: int -- Unsigned integer
Returns:
int -- Number of '1' bits
"""
count = 0
while n:
count += n & 1
n >>= 1
return count
# Sample Input/Output
n = 11 # Binary representation: 1011
print("Number of '1' bits in 11:", hammingWeight(n))
# Output: 3# Category: Bit Manipulation
# Question: Reverse bits of a given 32 bits unsigned integer.
# Approach: Iterate through each bit of the number from right to left. For each bit, shift it to its reverse position and use bitwise OR to combine it into the result.
def reverseBits(n):
"""
Reverse bits of a given 32 bits unsigned integer.
Args:
n: int -- Unsigned integer
Returns:
int -- Reversed bits integer
"""
result = 0
for i in range(32):
bit = (n >> i) & 1
result |= bit << (31 - i)
return result
# Sample Input/Output
n = 43261596 # Binary: 00000010100101000001111010011100
print("Reversed bits:", reverseBits(n))
# Output for reversed: 964176192 (Binary: 00111001011110000010100101000000)# Category: Bit Manipulation
# Question: Given a non-empty array of integers, every element appears twice except for one. Find that single one.
# Approach: Use XOR operation across all elements. The property of XOR is that it returns 0 for two identical numbers and the number itself for a number XORed with 0. Since the array has every element twice except one, the result will be that single number.
def singleNumber(nums):
"""
Find the element that appears only once in an array where every other element appears twice.
Args:
nums: List[int] -- List of integers
Returns:
int -- The single number
"""
single = 0
for num in nums:
single ^= num
return single
# Sample Input/Output
nums = [4, 1, 2, 1, 2]
print("Single non-repeated element:", singleNumber(nums))
# Output: 4# Category: Backtracking
# Question: The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle.
# Approach: Use backtracking to place queens one by one in different rows. Before placing a queen, check for safety (no other queen can attack the placed queen). Recur for the next row after a queen is placed in a safe position.
# Shifting focus to Backtracking, this technique is a refined brute-force approach, used for solving optimization and decision problems. It incrementally builds candidates to the solutions and abandons a candidate ("backtracks") as soon as it determines that this candidate cannot possibly lead to a final solution.
def solveNQueens(n):
"""
Solves the N-Queens problem and returns all distinct solutions.
Args:
n: int -- Size of the chessboard and number of queens.
Returns:
List[List[str]] -- All distinct solutions where each solution contains a list of strings representing the chessboard.
"""
def createBoard(state):
board = []
for row in state:
board.append(''.join('Q' if c == row else '.' for c in range(n)))
return board
def isSafe(state, row, col):
for r in range(len(state)):
c = state[r]
if c == col or abs(r - len(state)) == abs(c - col):
return False
return True
def backtrack(state):
if len(state) == n:
solutions.append(createBoard(state))
return
for col in range(n):
if isSafe(state, len(state), col):
backtrack(state + [col])
solutions = []
backtrack([])
return solutions
# Sample Input/Output
print("N-Queens Solutions for N=4:", solveNQueens(4))
# Output: 2 solutions for a 4x4 board# Category: Backtracking
# Question: Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
# Approach: Use backtracking to add either an opening or closing bracket on each step, maintaining the count of opening and closing brackets. Only add an opening bracket if not more than n, and a closing bracket if it does not exceed the number of opening brackets.
def generateParenthesis(n):
"""
Generates all combinations of n pairs of well-formed parentheses.
Args:
n: int -- Number of pairs of parentheses.
Returns:
List[str] -- All combinations of well-formed parentheses.
"""
def backtrack(s='', left=0, right=0):
if len(s) == 2 * n:
ans.append(s)
return
if left < n:
backtrack(s + '(', left + 1, right)
if right < left:
backtrack(s + ')', left, right + 1)
ans = []
backtrack()
return ans
# Sample Input/Output
print("Combinations for 3 pairs of parentheses:", generateParenthesis(3))
# Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
https://workat.tech/problem-solving/lists/most-asked-questions/practice?page=2