Data Structure using Python
Interview Questions with Answers

Website logo

Explore Our Courses

Data Analytics Using Python

Data Science & ML – Python

Full Stack Web Development

Cloud Computing & DevOPS

Java Full Stack

Digital Marketing

WordPress and Blogging

Social Media Marketing

Google Ads

Front-End Development

Back-End Development

Design Thinking & UI/UX

React Native

Business Analytics & Intelligence

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!

Start Practicing Now

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: True

16. 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.

Get Interview-Ready

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!

Enroll 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)
Note: The interview questions and answers provided on this page have been thoughtfully compiled by our academic team. However, as the content is manually created, there may be occasional errors or omissions. If you have any questions or identify any inaccuracies, please contact us at team@learn2earnlabs.com. We appreciate your feedback and strive for continuous improvement.