10 Data Structure Coding Interview Questions and Answers

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.

Data Structure Coding Interview Questions and Answers

1. Write a function to rotate an array by k positions.

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]

2. Implement a function to detect a cycle in a singly linked list.

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

3. Design a stack that supports push, pop, and retrieving the minimum element in constant time.

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

4. Write a function to find the first non-repeating character in a string using a hash table.

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'

5. Solve the “maximum subarray sum” problem using dynamic programming.

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

6. Implement a function to delete a node from a binary search tree.

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

7. Implement Dijkstra’s algorithm for finding the shortest path in a weighted graph.

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}

8. Design a trie that supports insert, search, and startsWith operations.

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

9. Implement breadth-first search (BFS) and depth-first search (DFS) for graph traversal.

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

10. Explain the Union-Find data structure and implement its basic operations.

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