# 10 Data Structure Coding Interview Questions and Answers

Prepare for your next technical interview with our comprehensive guide on data structure coding questions and answers to boost your problem-solving skills.

Prepare for your next technical interview with our comprehensive guide on data structure coding questions and answers to boost your problem-solving skills.

Data structures are fundamental to computer science and software engineering, forming the backbone of efficient algorithm design and problem-solving. Mastery of data structures such as arrays, linked lists, trees, and graphs is crucial for optimizing performance and managing data effectively. Understanding these concepts is essential for tackling complex coding challenges and building robust applications.

This article offers a curated selection of data structure coding questions designed to test and enhance your understanding. By working through these examples, you will gain the confidence and proficiency needed to navigate technical interviews and demonstrate your problem-solving abilities.

To rotate an array by `k`

positions, use slicing to efficiently split and concatenate the array in reversed order.

Example:

def rotate_array(arr, k): n = len(arr) k = k % n # Adjust k if it's greater than the array length return arr[-k:] + arr[:-k] # Example usage arr = [1, 2, 3, 4, 5, 6, 7] k = 3 rotated_arr = rotate_array(arr, k) print(rotated_arr) # Output: [5, 6, 7, 1, 2, 3, 4]

To detect a cycle in a singly linked list, use Floyd’s Cycle-Finding Algorithm with two pointers: a slow pointer and a fast pointer. If they meet, a cycle exists.

class ListNode: def __init__(self, value=0, next=None): self.value = value self.next = next def has_cycle(head): slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False # Example usage: # Creating a cycle for testing node1 = ListNode(1) node2 = ListNode(2) node3 = ListNode(3) node4 = ListNode(4) node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node2 # Creates a cycle print(has_cycle(node1)) # Output: True

To design a stack that supports push, pop, and retrieving the minimum element in constant time, use an auxiliary stack to track minimum elements.

class MinStack: def __init__(self): self.stack = [] self.min_stack = [] def push(self, x): self.stack.append(x) if not self.min_stack or x <= self.min_stack[-1]: self.min_stack.append(x) def pop(self): if self.stack: if self.stack[-1] == self.min_stack[-1]: self.min_stack.pop() return self.stack.pop() def get_min(self): if self.min_stack: return self.min_stack[-1] # Example usage: min_stack = MinStack() min_stack.push(3) min_stack.push(5) print(min_stack.get_min()) # Output: 3 min_stack.push(2) min_stack.push(1) print(min_stack.get_min()) # Output: 1 min_stack.pop() print(min_stack.get_min()) # Output: 2

To find the first non-repeating character in a string, use a hash table to count character occurrences, then identify the first character with a count of one.

def first_non_repeating_char(s): char_count = {} # Build the hash table for char in s: if char in char_count: char_count[char] += 1 else: char_count[char] = 1 # Find the first non-repeating character for char in s: if char_count[char] == 1: return char return None # Example usage print(first_non_repeating_char("swiss")) # Output: 'w' print(first_non_repeating_char("teeter")) # Output: 'r'

The “maximum subarray sum” problem can be solved using dynamic programming by iterating through the array and updating the maximum sum at each step.

def max_subarray_sum(nums): if not nums: return 0 max_current = max_global = nums[0] for num in nums[1:]: max_current = max(num, max_current + num) if max_current > max_global: max_global = max_current return max_global # Example usage: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] print(max_subarray_sum(nums)) # Output: 6

Deleting a node from a binary search tree involves handling three cases: the node is a leaf, has one child, or has two children. Replace the node with its in-order successor or predecessor if it has two children.

class TreeNode: def __init__(self, key): self.left = None self.right = None self.val = key def deleteNode(root, key): if not root: return root if key < root.val: root.left = deleteNode(root.left, key) elif key > root.val: root.right = deleteNode(root.right, key) else: if not root.left: return root.right elif not root.right: return root.left temp = minValueNode(root.right) root.val = temp.val root.right = deleteNode(root.right, temp.val) return root def minValueNode(node): current = node while current.left: current = current.left return current

Dijkstra’s algorithm finds the shortest path in a weighted graph by iteratively selecting the node with the smallest tentative distance and updating its neighbors’ distances.

import heapq def dijkstra(graph, start): distances = {node: float('infinity') for node in graph} distances[start] = 0 priority_queue = [(0, start)] while priority_queue: current_distance, current_node = heapq.heappop(priority_queue) if current_distance > distances[current_node]: continue for neighbor, weight in graph[current_node].items(): distance = current_distance + weight if distance < distances[neighbor]: distances[neighbor] = distance heapq.heappush(priority_queue, (distance, neighbor)) return distances graph = { 'A': {'B': 1, 'C': 4}, 'B': {'A': 1, 'C': 2, 'D': 5}, 'C': {'A': 4, 'B': 2, 'D': 1}, 'D': {'B': 5, 'C': 1} } print(dijkstra(graph, 'A')) # {'A': 0, 'B': 1, 'C': 3, 'D': 4}

A trie, or prefix tree, is used to store associative data structures. Each node represents a character, and the path from the root to a node represents a prefix.

class TrieNode: def __init__(self): self.children = {} self.is_end_of_word = False class Trie: def __init__(self): self.root = TrieNode() def insert(self, word): node = self.root for char in word: if char not in node.children: node.children[char] = TrieNode() node = node.children[char] node.is_end_of_word = True def search(self, word): node = self.root for char in word: if char not in node.children: return False node = node.children[char] return node.is_end_of_word def startsWith(self, prefix): node = self.root for char in prefix: if char not in node.children: return False node = node.children[char] return True

Breadth-First Search (BFS) and Depth-First Search (DFS) are fundamental graph traversal algorithms. BFS uses a queue, while DFS uses a stack or recursion.

BFS Example:

from collections import deque def bfs(graph, start): visited = set() queue = deque([start]) visited.add(start) while queue: vertex = queue.popleft() print(vertex, end=" ") for neighbor in graph[vertex]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) graph = { 'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['F'], 'F': [] } bfs(graph, 'A') # Output: A B C D E F

DFS Example:

def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start) print(start, end=" ") for neighbor in graph[start]: if neighbor not in visited: dfs(graph, neighbor, visited) graph = { 'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['F'], 'F': [] } dfs(graph, 'A') # Output: A B D E F C

The Union-Find data structure supports two operations: Find, to determine which subset an element is in, and Union, to join two subsets. It uses path compression and union by rank to optimize these operations.

class UnionFind: def __init__(self, size): self.parent = list(range(size)) self.rank = [1] * size def find(self, p): if self.parent[p] != p: self.parent[p] = self.find(self.parent[p]) # Path compression return self.parent[p] def union(self, p, q): rootP = self.find(p) rootQ = self.find(q) if rootP != rootQ: if self.rank[rootP] > self.rank[rootQ]: self.parent[rootQ] = rootP elif self.rank[rootP] < self.rank[rootQ]: self.parent[rootP] = rootQ else: self.parent[rootQ] = rootP self.rank[rootP] += 1 # Example usage: uf = UnionFind(10) uf.union(1, 2) uf.union(3, 4) uf.union(2, 4) print(uf.find(1)) # Output: 3 print(uf.find(3)) # Output: 3