Data Structure using Python
Interview Questions with Answers
Explore Our Courses
1. What are the different data types in Python and how are they used in DS problems?
Answer:
Python has several built-in data types, commonly used in data structure problems:
Advanced types include collections.deque, defaultdict, Counter, OrderedDict for optimized DS operations.
Ace your Python DS interviews with confidence—practice the most asked questions today!
2. How is memory managed in Python during list and dictionary operations?
Answer:
Python uses automatic memory management via the Python Memory Manager, which includes:
- Private heap space: All objects and data structures are stored here.
- Dynamic resizing:
- Lists grow using over-allocation (extra space reserved).
- Dicts grow using rehashing and resizing as elements increase.
List Memory:
- Internally uses a resizable array.
- Amortized O(1) time for append due to geometric resizing.
Dictionary Memory:
- Uses a hash table.
- Keys are hashed, and collisions are resolved using open addressing.
Python automatically manages memory via:
- Reference counting
- Garbage collector for cyclic references
3. What is the difference between list, tuple, and set in Python?
Answer:
4. Explain the concept of mutability with respect to Python data structures.
Answer:
Mutability refers to whether the object’s content can be changed after creation.
Examples:
lst = [1, 2]; lst[0] = 5 # Mutable
tup = (1, 2); tup[0] = 5 # Error (immutable)
In DS problems:
- Use immutable types for hashable keys in sets/dicts.
- Use mutable types for dynamic updates.
5. How does Python manage references and garbage collection?
Answer:
Python uses reference counting and a cyclic garbage collector.
- Reference Counting: Each object keeps track of how many references point to it.
- When count = 0 → memory is deallocated.
- Garbage Collector (gc module):
- Detects and collects cyclic references (e.g., mutually referring lists).
- Uses generational GC:
- Objects are grouped in generations (0, 1, 2) based on age.
- Younger objects are collected more frequently.
Example:
import gc
gc.collect() # Manually trigger garbage collection
6. What are Python iterators and generators? How do they support DS operations?
Answer:
Iterator: Object with __iter__() and __next__() methods.
lst = [1, 2, 3]
it = iter(lst)
print(next(it)) # Output: 1
Generator: A special iterator using yield instead of return.
Benefits:
- Memory-efficient (lazy evaluation)
- Useful for large data streams (e.g., infinite series, tree traversal)
Example:
def countdown(n):
while n > 0:
yield n
n -= 1
Used in:
- Tree traversals
- Streaming data
- Efficient backtracking
7. What is the difference between is and == in Python?
Answer:
Use is
- To compare identity (e.g., is None)
- When checking for singleton objects
Use ==
- When comparing values/contents
8. Explain how slicing works in Python and give DS use cases.
Answer:
Slicing Syntax: sequence[start:stop:step]
Examples:
lst = [10, 20, 30, 40, 50]
lst[1:4] # [20, 30, 40]
lst[::-1] # [50, 40, 30, 20, 10] → reverse
Use Cases in DS:
- Reversing strings/lists
- Copying arrays (arr[:])
- Extracting subarrays or substrings
- Sliding window technique (arr[i:i+k])
9. How do you implement custom sorting using key and lambda in Python?
Answer:
Python’s sorted() and list.sort() accept a key argument for custom logic.
Examples:
# Sort by length
words = ['banana', 'apple', 'kiwi']
sorted_words = sorted(words, key=len)
# Sort by second element of tuple
pairs = [(1, 3), (2, 1), (5, 2)]
pairs.sort(key=lambda x: x[1])
Real-world DS Use:
- Sorting by frequency
- Custom comparators (e.g., sort by absolute value, sort strings by custom order)
10. Explain time complexity of built-in Python operations (append, pop, insert, sort).
Answer:
Note: Worst-case dict/set operations may degrade to O(n) due to hash collisions, but are rare with good hash functions.
11. Implement two-pointer approach to reverse a string in Python
Answer:
def reverse_string(s):
s = list(s) # Convert to list for in-place modification
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
return ''.join(s)
# Test
print(reverse_string("python")) # Output: "nohtyp"
12. How do you remove duplicates from a list while preserving order?
Answer:
def remove_duplicates(lst):
seen = set()
result = []
for item in lst:
if item not in seen:
seen.add(item)
result.append(item)
return result
# Test
print(remove_duplicates([1, 2, 2, 3, 1, 4])) # Output: [1, 2, 3, 4]
13. Given a rotated sorted array, write a function to search a target element
Answer:
def search_rotated_array(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# Left half is sorted
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
# Right half is sorted
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1 # Not found
# Test
print(search_rotated_array([4, 5, 6, 7, 0, 1, 2], 0)) # Output: 4
14. Implement Kadane’s algorithm to find the maximum subarray sum
Answer:
def max_subarray_sum(nums):
max_sum = current_sum = nums[0]
for num in nums[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
# Test
print(max_subarray_sum([-2,1,-3,4,-1,2,1,-5,4])) # Output: 6
15. Check if two strings are anagrams using Python dictionaries
Answer:
def are_anagrams(s1, s2):
if len(s1) != len(s2):
return False
count = {}
for c in s1:
count[c] = count.get(c, 0) + 1
for c in s2:
if c not in count:
return False
count[c] -= 1
if count[c] < 0:
return False
return True
# Test
print(are_anagrams("listen", "silent")) # Output: True16. How would you implement run-length encoding of a string?
Answer:
def run_length_encode(s):
if not s:
return ""
result = []
count = 1
prev = s[0]
for c in s[1:]:
if c == prev:
count += 1
else:
result.append(prev + str(count))
prev = c
count = 1
result.append(prev + str(count))
return ''.join(result)
# Test
print(run_length_encode("aaabbc")) # Output: "a3b2c1"
17. Implement string compression using counts of repeated characters
Answer:
def compress_string(s):
if not s:
return ""
compressed = []
count = 1
prev = s[0]
for c in s[1:]:
if c == prev:
count += 1
else:
compressed.append(prev + str(count))
prev = c
count = 1
compressed.append(prev + str(count))
result = ''.join(compressed)
# Return original if compression doesn't reduce size
return result if len(result) < len(s) else s
# Test
print(compress_string("aabcccccaaa")) # Output: "a2b1c5a3"
18. Given a list of numbers, return indices of two numbers that add to a target (Two Sum)
Answer:
def two_sum(nums, target):
index_map = {} # num → index
for i, num in enumerate(nums):
complement = target - num
if complement in index_map:
return [index_map[complement], i]
index_map[num] = i
return [] # No valid pair found
# Test
print(two_sum([2, 7, 11, 15], 9)) # Output: [0, 1]
19. Explain sliding window technique with an example problem
Answer:
Sliding Window is used to optimize problems with contiguous subarrays.
Example Problem: Find the maximum sum of any subarray of size k.
def max_sum_subarray_k(nums, k):
window_sum = sum(nums[:k])
max_sum = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k]
max_sum = max(max_sum, window_sum)
return max_sum
# Test
print(max_sum_subarray_k([1, 4, 2, 10, 2, 3, 1, 0, 20], 4)) # Output: 24
20. Implement group anagrams problem using Python
Answer:
from collections import defaultdict
def group_anagrams(strs):
anagrams = defaultdict(list)
for word in strs:
# Sort characters to form a key
key = ''.join(sorted(word))
anagrams[key].append(word)
return list(anagrams.values())
# Test
print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
# Output: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
Get closer to your dream job—master Data Structures in Python with real interview questions.
21. Implement a Singly Linked List in Python
Answer:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def insert_end(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
curr = self.head
while curr.next:
curr = curr.next
curr.next = new_node
def display(self):
curr = self.head
while curr:
print(curr.data, end=" -> ")
curr = curr.next
print("None")
22. Reverse a Linked List (Iterative and Recursive)
Answer:
Iterative Approach
def reverse_iterative(head):
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
Recursive Approach
def reverse_recursive(head):
if not head or not head.next:
return head
new_head = reverse_recursive(head.next)
head.next.next = head
head.next = None
return new_head
23. Detect a Cycle in a Linked List (Floyd’s Algorithm)
Answer:
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
24. Find the Middle of a Linked List
Answer:
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # Middle node
25. Merge Two Sorted Linked Lists
Answer:
def merge_sorted_lists(l1, l2):
dummy = Node(0)
tail = dummy
while l1 and l2:
if l1.data <= l2.data:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 or l2
return dummy.next
26. Remove the Nth Node from the End of a Linked List
Answer:
def remove_nth_from_end(head, n):
dummy = Node(0)
dummy.next = head
fast = slow = dummy
for _ in range(n):
fast = fast.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next
27. Check if a Linked List is a Palindrome
Answer:
def is_palindrome(head):
if not head or not head.next:
return True
# Find middle
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev = None
while slow:
next_node = slow.next
slow.next = prev
prev = slow
slow = next_node
# Compare halves
left, right = head, prev
while right:
if left.data != right.data:
return False
left = left.next
right = right.next
return True
28. Add Two Numbers Represented by Linked Lists
Answer:
def add_two_numbers(l1, l2):
dummy = Node(0)
curr = dummy
carry = 0
while l1 or l2 or carry:
v1 = l1.data if l1 else 0
v2 = l2.data if l2 else 0
total = v1 + v2 + carry
carry = total // 10
curr.next = Node(total % 10)
curr = curr.next
if l1: l1 = l1.next
if l2: l2 = l2.next
return dummy.next
29. Flatten a Multilevel Linked List
Answer:
Assume each node has next and child pointers (like a doubly linked list with children).
class MultiLevelNode:
def __init__(self, data):
self.data = data
self.next = None
self.child = None
def flatten(head):
if not head:
return head
dummy = MultiLevelNode(0)
stack = [head]
prev = dummy
while stack:
curr = stack.pop()
prev.next = curr
prev = curr
if curr.next:
stack.append(curr.next)
if curr.child:
stack.append(curr.child)
curr.child = None
return dummy.next
30. Sort a Linked List Using Merge Sort
Answer:
def merge_sort(head):
if not head or not head.next:
return head
# Split the list into two halves
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
left = merge_sort(head)
right = merge_sort(mid)
return merge_sorted_lists(left, right)
Note: merge_sorted_lists() is already defined in question 25.
31. Implement a Stack Using list and collections.deque
Answer:
Using list:
class StackList:
def __init__(self):
self.stack = []
def push(self, x):
self.stack.append(x) # O(1)
def pop(self):
return self.stack.pop() if self.stack else None # O(1)
def peek(self):
return self.stack[-1] if self.stack else None
def is_empty(self):
return not self.stack
Using collections.deque:
from collections import deque
class StackDeque:
def __init__(self):
self.stack = deque()
def push(self, x):
self.stack.append(x)
def pop(self):
return self.stack.pop() if self.stack else None
def peek(self):
return self.stack[-1] if self.stack else None
def is_empty(self):
return not self.stack
32. Evaluate a Postfix Expression Using Stack
Answer:
def evaluate_postfix(expression):
stack = []
for token in expression.split():
if token.isdigit():
stack.append(int(token))
else:
b = stack.pop()
a = stack.pop()
if token == '+': stack.append(a + b)
elif token == '-': stack.append(a - b)
elif token == '*': stack.append(a * b)
elif token == '/': stack.append(int(a / b)) # Truncate towards 0
return stack[0]
# Test
print(evaluate_postfix("2 3 1 * + 9 -")) # Output: -4
33. Implement a Queue Using Two Stacks
Answer:
class QueueTwoStacks:
def __init__(self):
self.in_stack = []
self.out_stack = []
def enqueue(self, x):
self.in_stack.append(x)
def dequeue(self):
if not self.out_stack:
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
return self.out_stack.pop() if self.out_stack else None
def peek(self):
if not self.out_stack:
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
return self.out_stack[-1] if self.out_stack else None
def is_empty(self):
return not self.in_stack and not self.out_stack
34. Design a Min-Stack (Retrieve Min in O(1))
Answer:
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
if self.stack:
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
def top(self):
return self.stack[-1] if self.stack else None
def get_min(self):
return self.min_stack[-1] if self.min_stack else None
35. Check for Balanced Parentheses Using Stack
Answer:
def is_balanced(expr):
stack = []
pairs = {')': '(', '}': '{', ']': '['}
for char in expr:
if char in '([{':
stack.append(char)
elif char in ')]}':
if not stack or stack[-1] != pairs[char]:
return False
stack.pop()
return not stack
# Test
print(is_balanced("{[()]}")) # Output: True
36. Implement an LRU Cache Using OrderedDict
Answer:
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key) # Recently used
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # Remove least recently used
37. Implement a Circular Queue in Python
Answer:
class CircularQueue:
def __init__(self, k):
self.queue = [None] * k
self.capacity = k
self.front = self.rear = -1
def enqueue(self, val):
if (self.rear + 1) % self.capacity == self.front:
return False # Full
if self.front == -1:
self.front = 0
self.rear = (self.rear + 1) % self.capacity
self.queue[self.rear] = val
return True
def dequeue(self):
if self.front == -1:
return False # Empty
if self.front == self.rear:
self.front = self.rear = -1
else:
self.front = (self.front + 1) % self.capacity
return True
def Front(self):
return -1 if self.front == -1 else self.queue[self.front]
def Rear(self):
return -1 if self.rear == -1 else self.queue[self.rear]
def is_empty(self):
return self.front == -1
def is_full(self):
return (self.rear + 1) % self.capacity == self.front
38. Solve the Sliding Window Maximum Using deque
Answer:
from collections import deque
def sliding_window_max(nums, k):
dq = deque()
result = []
for i in range(len(nums)):
while dq and dq[0] < i - k + 1:
dq.popleft()
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
# Test
print(sliding_window_max([1,3,-1,-3,5,3,6,7], 3)) # Output: [3,3,5,5,6,7]
39. What is the Difference Between collections.deque and queue.Queue?
Answer:
Use deque for single-threaded fast queue/stack.
Use queue.Queue for multi-threaded applications.
40. Simulate a Browser Back/Forward Feature Using Two Stacks
Answer:
class Browser:
def __init__(self):
self.back_stack = []
self.forward_stack = []
self.current = None
def visit(self, url):
if self.current:
self.back_stack.append(self.current)
self.current = url
self.forward_stack.clear()
def back(self):
if self.back_stack:
self.forward_stack.append(self.current)
self.current = self.back_stack.pop()
return self.current
def forward(self):
if self.forward_stack:
self.back_stack.append(self.current)
self.current = self.forward_stack.pop()
return self.current
# Test
b = Browser()
b.visit("A")
b.visit("B")
b.visit("C")
print(b.back()) # Output: B
print(b.back()) # Output: A
print(b.forward()) # Output: B
Crack coding rounds faster with expert-level Python DS interview prep—start now!
41. Implement In-order, Pre-order, and Post-order Traversal
Answer:
class TreeNode:
def __init__(self, val=0):
self.val = val
self.left = None
self.right = None
# In-order: Left → Root → Right
def inorder(root):
if root:
inorder(root.left)
print(root.val, end=' ')
inorder(root.right)
# Pre-order: Root → Left → Right
def preorder(root):
if root:
print(root.val, end=' ')
preorder(root.left)
preorder(root.right)
# Post-order: Left → Right → Root
def postorder(root):
if root:
postorder(root.left)
postorder(root.right)
print(root.val, end=' ')
42. Check if a Binary Tree is Balanced
Answer:
A binary tree is balanced if for every node, the difference between the heights of left and right subtrees is not more than 1.
def is_balanced(root):
def check(node):
if not node:
return 0
left = check(node.left)
if left == -1: return -1
right = check(node.right)
if right == -1: return -1
if abs(left - right) > 1: return -1
return max(left, right) + 1
return check(root) != -1
43. Find the Lowest Common Ancestor in a Binary Tree
Answer:
def lowest_common_ancestor(root, p, q):
if not root or root == p or root == q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
return root if left and right else left or right
44. Serialize and Deserialize a Binary Tree
Answer:
Preorder-based Serialization
class Codec:
def serialize(self, root):
def dfs(node):
if not node:
vals.append("X")
return
vals.append(str(node.val))
dfs(node.left)
dfs(node.right)
vals = []
dfs(root)
return ','.join(vals)
def deserialize(self, data):
def dfs():
val = next(vals)
if val == "X":
return None
node = TreeNode(int(val))
node.left = dfs()
node.right = dfs()
return node
vals = iter(data.split(','))
return dfs()
45. Convert a BST to a Sorted Doubly Linked List
Answer:
def bst_to_dll(root):
def inorder(node):
nonlocal prev, head
if not node:
return
inorder(node.left)
if prev:
prev.right = node
node.left = prev
else:
head = node
prev = node
inorder(node.right)
prev = head = None
inorder(root)
return head
46. Check if a Binary Tree is a Subtree of Another
Answer:
def is_subtree(s, t):
def is_same(a, b):
if not a and not b:
return True
if not a or not b or a.val != b.val:
return False
return is_same(a.left, b.left) and is_same(a.right, b.right)
if not s:
return False
if is_same(s, t):
return True
return is_subtree(s.left, t) or is_subtree(s.right, t)
47. Count the Number of Leaf Nodes in a Binary Tree
Answer:
def count_leaves(root):
if not root:
return 0
if not root.left and not root.right:
return 1
return count_leaves(root.left) + count_leaves(root.right)
48. Implement Level Order Traversal Using a Queue
Answer:
from collections import deque
def level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
node = queue.popleft()
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
49. Construct a Binary Tree from Inorder and Preorder Traversals
Answer:
def build_tree(preorder, inorder):
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
idx = inorder.index(preorder[0])
root.left = build_tree(preorder[1:idx+1], inorder[:idx])
root.right = build_tree(preorder[idx+1:], inorder[idx+1:])
return root
50. Validate if a Given Binary Tree is a Binary Search Tree (BST)
Answer:
def is_valid_bst(root):
def validate(node, low=float('-inf'), high=float('inf')):
if not node:
return True
if not (low < node.val < high):
return False
return validate(node.left, low, node.val) and validate(node.right, node.val, high)
return validate(root)
51. Implement BFS and DFS for a Graph in Python
Answer:
from collections import deque, defaultdict
# Assume graph is represented as an adjacency list: {node: [neighbors]}
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
visited.add(node)
print(node, end=' ')
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
if node not in visited:
visited.add(node)
print(node, end=' ')
for neighbor in graph[node]:
dfs(graph, neighbor, visited)52. Detect a Cycle in a Directed Graph Using DFS
python
CopyEdit
def has_cycle(graph):
visited = set()
rec_stack = set()
def dfs(node):
if node in rec_stack:
return True
if node in visited:
return False
visited.add(node)
rec_stack.add(node)
for neighbor in graph[node]:
if dfs(neighbor):
return True
rec_stack.remove(node)
return False
for node in graph:
if dfs(node):
return True
return False
53. Find the Shortest Path in an Unweighted Graph Using BFS
Answer:
def shortest_path(graph, start, target):
queue = deque([(start, [start])])
visited = set([start])
while queue:
node, path = queue.popleft()
if node == target:
return path
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return [] # No path
54. Implement Dijkstra’s Algorithm Using heapq
Answer:
import heapq
def dijkstra(graph, start):
dist = {node: float('inf') for node in graph}
dist[start] = 0
pq = [(0, start)] # (distance, node)
while pq:
curr_dist, node = heapq.heappop(pq)
if curr_dist > dist[node]:
continue
for neighbor, weight in graph[node]:
new_dist = curr_dist + weight
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))
return dist
55. Explain Union-Find and Implement It With Path Compression
Answer:
Union-Find (Disjoint Set) tracks connected components.
- Find(x): Returns the root of the set.
- Union(x, y): Merges two sets.
- Optimized with:
- Path Compression
- Union by Rank
class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
self.rank = [0] * size
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # Path Compression
return self.parent[x]
def union(self, x, y):
rootX, rootY = self.find(x), self.find(y)
if rootX == rootY:
return
if self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
elif self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
else:
self.parent[rootY] = rootX
self.rank[rootX] += 1
56. Implement Topological Sort (Kahn’s Algorithm)
Answer:
from collections import deque, defaultdict
def kahn_topological_sort(graph):
in_degree = {node: 0 for node in graph}
for neighbors in graph.values():
for neighbor in neighbors:
in_degree[neighbor] += 1
queue = deque([node for node in graph if in_degree[node] == 0])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(result) != len(graph):
return [] # Cycle detected
return result
57. Design a Trie for Prefix Search and Autocomplete
Answer:
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_end = True
def search(self, word):
node = self.root
for ch in word:
if ch not in node.children:
return False
node = node.children[ch]
return node.is_end
def starts_with(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children:
return []
node = node.children[ch]
return self._autocomplete(node, prefix)
def _autocomplete(self, node, prefix):
results = []
if node.is_end:
results.append(prefix)
for ch, child in node.children.items():
results.extend(self._autocomplete(child, prefix + ch))
return results
58. Find Connected Components in an Undirected Graph
Answer:
def connected_components(graph):
visited = set()
components = []
def dfs(node, component):
visited.add(node)
component.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor, component)
for node in graph:
if node not in visited:
component = []
dfs(node, component)
components.append(component)
return components
59. Explain and Implement a Segment Tree for Range Sum Query
Answer:
Segment Tree: Binary tree structure for fast range queries and updates.
class SegmentTree:
def __init__(self, arr):
self.n = len(arr)
self.tree = [0] * (4 * self.n)
self.build(arr, 0, 0, self.n - 1)
def build(self, arr, node, l, r):
if l == r:
self.tree[node] = arr[l]
else:
mid = (l + r) // 2
self.build(arr, 2*node+1, l, mid)
self.build(arr, 2*node+2, mid+1, r)
self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]
def query(self, node, l, r, ql, qr):
if ql > r or qr < l: return 0 # No overlap
if ql <= l and r <= qr: return self.tree[node] # Total overlap
mid = (l + r) // 2
return self.query(2*node+1, l, mid, ql, qr) + self.query(2*node+2, mid+1, r, ql, qr)
def range_sum(self, left, right):
return self.query(0, 0, self.n - 1, left, right)
60. What is a Heap in Python? Implement a Min/Max Heap Manually
Answer:
A heap is a binary tree where each node follows the heap property:
- Min-Heap: Parent ≤ Children
- Max-Heap: Parent ≥ Children
Python’s heapq supports min-heap by default.
Manual Min-Heap Implementation:
class MinHeap:
def __init__(self):
self.heap = []
def insert(self, val):
self.heap.append(val)
self._heapify_up(len(self.heap) - 1)
def extract_min(self):
if not self.heap:
return None
min_val = self.heap[0]
self.heap[0] = self.heap.pop()
self._heapify_down(0)
return min_val
def _heapify_up(self, i):
parent = (i - 1) // 2
if i > 0 and self.heap[i] < self.heap[parent]:
self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
self._heapify_up(parent)
def _heapify_down(self, i):
smallest = i
l, r = 2*i + 1, 2*i + 2
if l < len(self.heap) and self.heap[l] < self.heap[smallest]:
smallest = l
if r < len(self.heap) and self.heap[r] < self.heap[smallest]:
smallest = r
if smallest != i:
self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
self._heapify_down(smallest)