Erudiax
Data Structures45 min read

Data Structures Interview Questions: 50 Essential Questions for Developers

Comprehensive collection of 50 essential Data Structures interview questions covering arrays, linked lists, trees, graphs, hash tables, and algorithm complexity.

Robert Kim
December 16, 2025
0.0k0

This comprehensive guide covers 50 essential Data Structures interview questions that every developer should know. These questions cover fundamental data structures, their operations, time/space complexity, and when to use each structure commonly asked in technical interviews.

Arrays & Lists

Arrays are fundamental data structures. These questions test your knowledge of array operations, dynamic arrays, and list implementations.

Linked Lists

Linked lists provide dynamic memory allocation. Master these questions to demonstrate your understanding of singly/doubly linked lists, operations, and trade-offs.

Stacks & Queues

Stacks and queues are linear data structures with specific access patterns. These questions cover LIFO/FIFO principles, implementations, and use cases.

Trees & Binary Trees

Trees are hierarchical data structures. These questions cover binary trees, BST, AVL trees, traversals, and tree operations.

Graphs & Hash Tables

Graphs represent relationships, hash tables provide fast lookups. These questions cover graph representations, traversal algorithms, and hash table implementations.

#Data Structures#Interview#Algorithms#Arrays#Trees

Common Questions & Answers

Q1

What is a data structure?

A

Data structure is way of organizing and storing data in computer memory for efficient access and modification. Examples: arrays, linked lists, stacks, queues, trees, graphs, hash tables. Choice affects algorithm performance.

Q2

What is the difference between array and linked list?

A

Array: contiguous memory, fixed/dynamic size, O(1) access, O(n) insert/delete. Linked list: non-contiguous, dynamic size, O(n) access, O(1) insert/delete. Array: better cache locality, random access. Linked list: efficient insertion/deletion, no size limit.

python
RunExplain
# Array
arr = [1, 2, 3, 4]
arr[2]  # O(1) access
arr.insert(1, 5)  # O(n) shift elements

# Linked List
# O(n) to find, O(1) to insert/delete at position
Q3

What is time complexity?

A

Time complexity describes how algorithm runtime grows with input size. Big O notation: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n²) quadratic, O(2ⁿ) exponential. Worst-case analysis.

python
RunExplain
# O(1) - Constant
def get_first(arr):
    return arr[0]

# O(n) - Linear
def find_max(arr):
    max_val = arr[0]
    for num in arr:
        if num > max_val:
            max_val = num
    return max_val

# O(n²) - Quadratic
def bubble_sort(arr):
    for i in range(len(arr)):
        for j in range(len(arr) - 1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
Q4

What is space complexity?

A

Space complexity describes how algorithm memory usage grows with input size. Includes input space and auxiliary space. O(1) constant, O(n) linear, O(n²) quadratic. Important for memory-constrained systems.

python
RunExplain
# O(1) space
def sum_array(arr):
    total = 0
    for num in arr:
        total += num
    return total

# O(n) space
def reverse_array(arr):
    result = []
    for i in range(len(arr) - 1, -1, -1):
        result.append(arr[i])
    return result
Q5

What is a stack?

A

Stack is LIFO (Last In First Out) data structure. Operations: push (add top), pop (remove top), peek (view top), isEmpty. O(1) for all operations. Uses: function calls, expression evaluation, undo/redo, backtracking.

python
RunExplain
class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        self.items.append(item)  # O(1)
    
    def pop(self):
        return self.items.pop()  # O(1)
    
    def peek(self):
        return self.items[-1]  # O(1)
    
    def is_empty(self):
        return len(self.items) == 0
Q6

What is a queue?

A

Queue is FIFO (First In First Out) data structure. Operations: enqueue (add rear), dequeue (remove front), front, isEmpty. O(1) for all operations. Uses: task scheduling, BFS, print queues, request handling.

python
RunExplain
from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()
    
    def enqueue(self, item):
        self.items.append(item)  # O(1)
    
    def dequeue(self):
        return self.items.popleft()  # O(1)
    
    def front(self):
        return self.items[0]  # O(1)
    
    def is_empty(self):
        return len(self.items) == 0
Q7

What is a binary tree?

A

Binary tree is tree where each node has at most 2 children (left, right). Root at top, leaves at bottom. Height: longest path from root to leaf. Full: all nodes have 0 or 2 children. Complete: all levels filled except last.

python
RunExplain
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# Example tree
#       1
#      / \
#     2   3
#    / \
#   4   5
Q8

What is a binary search tree (BST)?

A

BST is binary tree where left subtree < node < right subtree. Enables O(log n) search, insert, delete (balanced). Inorder traversal gives sorted order. Worst case O(n) if unbalanced. Self-balancing: AVL, Red-Black trees.

python
RunExplain
class BSTNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def search(root, val):
    if not root or root.val == val:
        return root
    if val < root.val:
        return search(root.left, val)
    return search(root.right, val)  # O(log n) average
Q9

What are tree traversals?

A

Tree traversals visit all nodes: Inorder (left, root, right) - sorted for BST. Preorder (root, left, right) - copy tree. Postorder (left, right, root) - delete tree. Level-order (BFS) - level by level. All O(n) time.

python
RunExplain
def inorder(root):
    if root:
        inorder(root.left)
        print(root.val)
        inorder(root.right)

def preorder(root):
    if root:
        print(root.val)
        preorder(root.left)
        preorder(root.right)

def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.val)
Q10

What is a hash table?

A

Hash table stores key-value pairs using hash function. O(1) average insert, search, delete. Hash function maps key to index. Collision handling: chaining (linked list), open addressing (linear/quadratic probing). Load factor affects performance.

python
RunExplain
# Python dict is hash table
hash_map = {}
hash_map["key1"] = "value1"  # O(1) average
value = hash_map.get("key1")  # O(1) average

# Custom implementation
class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def hash(self, key):
        return hash(key) % self.size
Q11

What is a graph?

A

Graph is collection of vertices (nodes) and edges (connections). Directed: edges have direction. Undirected: bidirectional edges. Weighted: edges have weights. Representations: adjacency matrix (O(V²) space), adjacency list (O(V+E) space).

python
RunExplain
# Adjacency list representation
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

# Weighted graph
weighted_graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('D', 5)],
    'C': [('A', 2), ('D', 1)],
    'D': [('B', 5), ('C', 1)]
}
Q12

What is BFS (Breadth-First Search)?

A

BFS explores graph level by level using queue. Visits all neighbors before moving to next level. Finds shortest path in unweighted graphs. O(V+E) time, O(V) space. Uses: shortest path, level-order traversal, social networks.

python
RunExplain
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
Q13

What is DFS (Depth-First Search)?

A

DFS explores as far as possible before backtracking using stack (recursion). Visits deep before wide. O(V+E) time, O(V) space. Uses: path finding, cycle detection, topological sort, maze solving. Variants: preorder, inorder, postorder.

python
RunExplain
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start)
    print(start)
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
Q14

What is a heap?

A

Heap is complete binary tree with heap property. Min heap: parent ≤ children. Max heap: parent ≥ children. Root is min/max. O(log n) insert, O(log n) delete, O(1) get min/max. Uses: priority queue, heap sort, Dijkstra's algorithm.

python
RunExplain
import heapq

# Min heap
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
min_val = heapq.heappop(heap)  # 1

# Max heap (negate values)
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
max_val = -heapq.heappop(max_heap)  # 3
Q15

What is a trie?

A

Trie (prefix tree) stores strings with common prefixes sharing nodes. Root to leaf path represents string. O(m) search/insert where m is string length. Uses: autocomplete, spell checker, IP routing, dictionary. Space: O(ALPHABET_SIZE * N * M).

python
RunExplain
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 char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
Q16

What is the difference between array and dynamic array?

A

Array: fixed size, allocated at creation. Dynamic array: resizable, doubles capacity when full. Dynamic array: O(1) amortized append, O(n) worst-case when resizing. Python list is dynamic array. Trade-off: memory vs flexibility.

python
RunExplain
# Dynamic array (Python list)
arr = []
arr.append(1)  # O(1) amortized
arr.append(2)
arr.append(3)  # May trigger resize O(n)

# Fixed array (numpy)
import numpy as np
fixed_arr = np.array([1, 2, 3])  # Fixed size
Q17

What is a doubly linked list?

A

Doubly linked list has nodes with data, next, and prev pointers. Can traverse both directions. O(1) insert/delete at known position, O(n) search. More memory than singly linked list. Uses: browser history, undo/redo, LRU cache.

python
RunExplain
class DoublyNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    
    def append(self, val):
        new_node = DoublyNode(val)
        if not self.head:
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
Q18

What is a circular linked list?

A

Circular linked list has last node pointing to first (singly) or both ends connected (doubly). No null pointers. O(1) access to head and tail. Uses: round-robin scheduling, multiplayer games, buffer implementation.

python
RunExplain
class CircularNode:
    def __init__(self, val):
        self.val = val
        self.next = None

class CircularList:
    def __init__(self):
        self.head = None
    
    def append(self, val):
        new_node = CircularNode(val)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
        else:
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node
            new_node.next = self.head
Q19

What is a priority queue?

A

Priority queue stores elements with priorities, highest priority dequeued first. Implemented with heap. O(log n) insert, O(log n) delete, O(1) peek. Uses: task scheduling, Dijkstra's algorithm, Huffman coding, event simulation.

python
RunExplain
import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []
    
    def push(self, item, priority):
        heapq.heappush(self.heap, (priority, item))
    
    def pop(self):
        return heapq.heappop(self.heap)[1]
    
    def peek(self):
        return self.heap[0][1] if self.heap else None
Q20

What is an AVL tree?

A

AVL tree is self-balancing BST where height difference between left and right subtrees ≤ 1. Maintains O(log n) operations through rotations. More balanced than BST, faster lookups. Trade-off: more complex insert/delete with rotations.

python
RunExplain
class AVLNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1

def get_balance(node):
    if not node:
        return 0
    return get_height(node.left) - get_height(node.right)

def rotate_right(y):
    x = y.left
    T2 = x.right
    x.right = y
    y.left = T2
    return x
Q21

What is a red-black tree?

A

Red-black tree is self-balancing BST with color property (red/black). Properties: root is black, red nodes have black children, equal black nodes on all paths. O(log n) operations. Used in C++ std::map, Java TreeMap. Simpler than AVL.

python
RunExplain
class RBNode:
    RED = True
    BLACK = False
    
    def __init__(self, val):
        self.val = val
        self.color = RBNode.RED
        self.left = None
        self.right = None
        self.parent = None
Q22

What is a segment tree?

A

Segment tree supports range queries and updates in O(log n). Stores intervals, leaf nodes are array elements. Query: sum/min/max in range. Update: modify element. O(n) space, O(log n) query/update. Uses: range sum, range minimum, interval problems.

python
RunExplain
class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.size = 2 * self.n
        self.tree = [0] * self.size
        self.build(arr)
    
    def build(self, arr):
        for i in range(self.n):
            self.tree[self.n + i] = arr[i]
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2*i] + self.tree[2*i + 1]
Q23

What is a Fenwick tree (Binary Indexed Tree)?

A

Fenwick tree supports prefix sum queries and point updates in O(log n). More memory efficient than segment tree. Uses bit manipulation. O(n) space, O(log n) query/update. Uses: range sum queries, inversion count, frequency tables.

python
RunExplain
class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (size + 1)
    
    def update(self, index, delta):
        index += 1
        while index <= self.n:
            self.tree[index] += delta
            index += index & -index
    
    def query(self, index):
        index += 1
        result = 0
        while index > 0:
            result += self.tree[index]
            index -= index & -index
        return result
Q24

What is a disjoint set (Union-Find)?

A

Disjoint set tracks elements in disjoint sets. Operations: find (which set), union (merge sets). O(α(n)) amortized with path compression and union by rank. Uses: Kruskal's algorithm, connected components, dynamic connectivity.

python
RunExplain
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    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):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            else:
                self.parent[root_y] = root_x
                if self.rank[root_x] == self.rank[root_y]:
                    self.rank[root_x] += 1
Q25

What is a suffix tree?

A

Suffix tree stores all suffixes of string in compressed trie. O(m) construction, O(m) search for pattern. Space: O(m). Uses: string matching, longest common substring, DNA sequence analysis, text indexing. More space than suffix array.

python
RunExplain
# Suffix tree is complex, here's concept
# Stores all suffixes: "banana" -> "banana", "anana", "nana", "ana", "na", "a"
# Enables O(m) pattern search where m is pattern length
Q26

What is the difference between B-tree and BST?

A

B-tree is multi-way search tree (multiple keys per node), optimized for disk I/O. BST is binary (2 children). B-tree: O(log n) operations, better for large datasets on disk. BST: simpler, good for memory. B-tree used in databases, file systems.

python
RunExplain
# B-tree node has multiple keys and children
# Example: B-tree of order 3 can have 2 keys and 3 children per node
# Better for disk-based storage due to fewer disk reads
Q27

What is a skip list?

A

Skip list is probabilistic alternative to balanced trees. Multiple linked lists at different levels. O(log n) search/insert/delete average, O(n) worst case. Simpler than balanced trees. Uses: Redis sorted sets, concurrent data structures.

python
RunExplain
# Skip list has multiple levels
# Level 0: all elements
# Level 1: subset of elements
# Level 2: smaller subset
# Enables "skipping" elements for faster search
Q28

What is a bloom filter?

A

Bloom filter is probabilistic data structure for membership testing. O(1) insert/query, O(k) space per element. May have false positives, no false negatives. Uses: cache filtering, spell checkers, network routers, distributed systems.

python
RunExplain
from bitarray import bitarray
import mmh3

class BloomFilter:
    def __init__(self, size, hash_count):
        self.size = size
        self.hash_count = hash_count
        self.bit_array = bitarray(size)
        self.bit_array.setall(0)
    
    def add(self, item):
        for i in range(self.hash_count):
            index = mmh3.hash(item, i) % self.size
            self.bit_array[index] = 1
    
    def contains(self, item):
        for i in range(self.hash_count):
            index = mmh3.hash(item, i) % self.size
            if not self.bit_array[index]:
                return False
        return True  # May be false positive
Q29

What is a deque (double-ended queue)?

A

Deque allows insertion/deletion at both ends. O(1) operations at both ends. Combines stack and queue. Uses: sliding window, palindrome checking, undo/redo, task scheduling. Python collections.deque is implementation.

python
RunExplain
from collections import deque

dq = deque()
dq.append(1)      # Add right
dq.appendleft(2)  # Add left
dq.pop()          # Remove right
dq.popleft()      # Remove left
Q30

What is the difference between array and list?

A

Array: fixed size, same data type, contiguous memory, faster access. List: dynamic size, mixed types, non-contiguous, more flexible. Array: better performance, memory efficient. List: easier to use, more features. Python list is dynamic array.

python
RunExplain
# Array (numpy - fixed type)
import numpy as np
arr = np.array([1, 2, 3])  # All same type

# List (Python - mixed types)
lst = [1, "hello", 3.14, True]  # Mixed types allowed
Q31

What is collision in hash table?

A

Collision occurs when two keys hash to same index. Handling methods: chaining (linked list at index), open addressing (find next empty slot - linear/quadratic probing), double hashing. Load factor (n/m) affects performance. Keep < 0.75.

python
RunExplain
# Chaining
class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def insert(self, key, value):
        index = hash(key) % self.size
        self.table[index].append((key, value))
    
    def get(self, key):
        index = hash(key) % self.size
        for k, v in self.table[index]:
            if k == key:
                return v
        return None
Q32

What is a sparse matrix?

A

Sparse matrix has mostly zero elements. Stored efficiently: coordinate list (COO), compressed sparse row (CSR), dictionary of keys (DOK). Saves memory and computation. Uses: graph adjacency, scientific computing, machine learning.

python
RunExplain
from scipy.sparse import csr_matrix

# Dense matrix (wasteful for sparse)
dense = [[0, 0, 1], [0, 2, 0], [3, 0, 0]]

# Sparse matrix (efficient)
sparse = csr_matrix(dense)
print(sparse)  # Only stores non-zero elements
Q33

What is topological sort?

A

Topological sort orders vertices in directed acyclic graph (DAG) such that for every edge u→v, u comes before v. O(V+E) time. Uses: task scheduling, build systems, course prerequisites, dependency resolution. Algorithm: DFS or Kahn's algorithm.

python
RunExplain
def topological_sort(graph):
    visited = set()
    stack = []
    
    def dfs(node):
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(node)
    
    for node in graph:
        if node not in visited:
            dfs(node)
    
    return stack[::-1]
Q34

What is a minimum spanning tree (MST)?

A

MST connects all vertices with minimum total edge weight in connected weighted graph. Algorithms: Kruskal's (greedy, sort edges), Prim's (greedy, start from vertex). Both O(E log V). Uses: network design, clustering, approximation algorithms.

python
RunExplain
# Kruskal's algorithm concept
# 1. Sort all edges by weight
# 2. Add edges in order if they don't form cycle
# 3. Use Union-Find to detect cycles

def kruskal(edges, n):
    edges.sort(key=lambda x: x[2])  # Sort by weight
    uf = UnionFind(n)
    mst = []
    for u, v, w in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append((u, v, w))
    return mst
Q35

What is shortest path algorithm?

A

Shortest path finds minimum cost path between vertices. Dijkstra's: non-negative weights, O((V+E) log V). Bellman-Ford: handles negative weights, O(VE). Floyd-Warshall: all pairs, O(V³). BFS: unweighted graphs, O(V+E).

python
RunExplain
import heapq

def dijkstra(graph, start):
    dist = {v: float('inf') for v in graph}
    dist[start] = 0
    pq = [(0, start)]
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    
    return dist
Q36

What is the difference between tree and graph?

A

Tree: acyclic, connected, n-1 edges for n vertices, unique path between nodes. Graph: can have cycles, disconnected, no edge limit, multiple paths. Tree is special case of graph. All trees are graphs, not all graphs are trees.

python
RunExplain
# Tree: no cycles, connected
#       1
#      / \
#     2   3
#    / \
#   4   5

# Graph: can have cycles
#   1 -- 2
#   |    |
#   4 -- 3
Q37

What is a balanced tree?

A

Balanced tree maintains height difference between subtrees within limit. Ensures O(log n) operations. Types: AVL (height diff ≤ 1), Red-Black (color properties), B-tree (multi-way). Unbalanced tree can degrade to O(n) worst case.

python
RunExplain
# AVL tree maintains balance
# After insert/delete, check balance factor
# Rotate if imbalance > 1

def is_balanced(root):
    if not root:
        return True, 0
    left_balanced, left_height = is_balanced(root.left)
    right_balanced, right_height = is_balanced(root.right)
    balanced = left_balanced and right_balanced and abs(left_height - right_height) <= 1
    return balanced, 1 + max(left_height, right_height)
Q38

What is a trie vs hash table?

A

Trie: prefix-based, O(m) search where m is key length, ordered keys, good for autocomplete. Hash table: direct access, O(1) average, unordered, good for exact match. Trie: more space, hash table: faster lookups.

python
RunExplain
# Trie: prefix search
trie = Trie()
trie.insert("apple")
trie.insert("app")
trie.search("app")  # True (prefix match)

# Hash table: exact match
hash_map = {"apple": 1, "app": 2}
hash_map.get("app")  # 2 (exact key)
Q39

What is a circular queue?

A

Circular queue (ring buffer) uses fixed-size array with wrap-around. Front and rear pointers. O(1) enqueue/dequeue. Efficient use of space. Uses: buffers, task scheduling, streaming data, producer-consumer problems.

python
RunExplain
class CircularQueue:
    def __init__(self, size):
        self.size = size
        self.queue = [None] * size
        self.front = self.rear = -1
    
    def enqueue(self, item):
        if (self.rear + 1) % self.size == self.front:
            return False  # Full
        if self.front == -1:
            self.front = 0
        self.rear = (self.rear + 1) % self.size
        self.queue[self.rear] = item
        return True
Q40

What is a suffix array?

A

Suffix array stores sorted array of all suffixes. O(n log n) construction, O(m log n) search. More space efficient than suffix tree. Uses: string matching, longest common substring, text compression, bioinformatics.

python
RunExplain
def build_suffix_array(text):
    suffixes = []
    for i in range(len(text)):
        suffixes.append((text[i:], i))
    suffixes.sort()
    return [idx for _, idx in suffixes]

# "banana" -> [5, 3, 1, 0, 4, 2] (sorted suffix indices)
Q41

What is a k-d tree?

A

K-d tree organizes points in k-dimensional space. Binary tree, alternates splitting dimensions. O(log n) average search, O(n) worst case. Uses: nearest neighbor search, range queries, spatial indexing, computer graphics, machine learning.

python
RunExplain
class KDNode:
    def __init__(self, point, left=None, right=None):
        self.point = point
        self.left = left
        self.right = right

def build_kdtree(points, depth=0):
    if not points:
        return None
    k = len(points[0])
    axis = depth % k
    points.sort(key=lambda x: x[axis])
    mid = len(points) // 2
    return KDNode(
        points[mid],
        build_kdtree(points[:mid], depth + 1),
        build_kdtree(points[mid+1:], depth + 1)
    )
Q42

What is a quadtree?

A

Quadtree partitions 2D space into quadrants recursively. Each node has 4 children. O(log n) average operations. Uses: image compression, collision detection, spatial indexing, game development, geographic information systems.

python
RunExplain
class QuadTreeNode:
    def __init__(self, x, y, width, height):
        self.bounds = (x, y, width, height)
        self.children = [None] * 4  # NW, NE, SW, SE
        self.points = []
    
    def subdivide(self):
        x, y, w, h = self.bounds
        w2, h2 = w // 2, h // 2
        self.children[0] = QuadTreeNode(x, y, w2, h2)  # NW
        self.children[1] = QuadTreeNode(x + w2, y, w2, h2)  # NE
        self.children[2] = QuadTreeNode(x, y + h2, w2, h2)  # SW
        self.children[3] = QuadTreeNode(x + w2, y + h2, w2, h2)  # SE
Q43

What is a rope data structure?

A

Rope stores large strings efficiently by splitting into smaller pieces. O(log n) insert/delete, O(log n) access. Better than string for large text editing. Uses: text editors, string processing, DNA sequences. Each node stores substring and length.

python
RunExplain
# Rope concept: binary tree of string fragments
# Leaf nodes: actual string pieces
# Internal nodes: length of left subtree
# Enables efficient insert/delete in large strings
Q44

What is a cache data structure?

A

Cache stores frequently accessed data for fast retrieval. LRU (Least Recently Used): evicts least recently used. LFU (Least Frequently Used): evicts least frequently used. O(1) operations with hash table + doubly linked list. Uses: CPU cache, web cache, database cache.

python
RunExplain
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity
    
    def get(self, key):
        if key in self.cache:
            self.cache.move_to_end(key)
            return self.cache[key]
        return -1
    
    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)
Q45

What is the difference between array and matrix?

A

Array: 1D linear collection. Matrix: 2D rectangular array (rows × columns). Matrix is 2D array. Operations: matrix multiplication, transpose, determinant. Arrays: simple indexing. Matrices: row/column operations. Both stored in memory similarly.

python
RunExplain
# Array (1D)
arr = [1, 2, 3, 4, 5]

# Matrix (2D array)
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

# Access
arr[2]        # 3
matrix[1][2]  # 6
Q46

What is a graph vs tree?

A

Tree: connected, acyclic, n-1 edges, unique path. Graph: can be disconnected, can have cycles, any number of edges, multiple paths. Tree is special graph. All trees are graphs. Graph is more general structure.

python
RunExplain
# Tree properties
# - Connected
# - No cycles
# - n nodes, n-1 edges
# - Unique path between nodes

# Graph properties
# - Can be disconnected
# - Can have cycles
# - Any number of edges
# - Multiple paths possible
Q47

What is a sparse graph vs dense graph?

A

Sparse graph: few edges relative to vertices (E ≈ V). Dense graph: many edges (E ≈ V²). Sparse: use adjacency list (O(V+E) space). Dense: use adjacency matrix (O(V²) space). Most real graphs are sparse.

python
RunExplain
# Sparse: E ≈ V
# Use adjacency list
sparse_graph = {
    'A': ['B'],
    'B': ['A', 'C'],
    'C': ['B']
}  # 3 vertices, 2 edges

# Dense: E ≈ V²
# Use adjacency matrix
dense_matrix = [
    [0, 1, 1, 1],
    [1, 0, 1, 1],
    [1, 1, 0, 1],
    [1, 1, 1, 0]
]  # 4 vertices, 6 edges (max 12)
Q48

What is a self-balancing tree?

A

Self-balancing tree automatically maintains balance after insert/delete. Prevents O(n) worst case. Types: AVL (strict balance), Red-Black (relaxed), Splay tree (move accessed to root), B-tree (multi-way). Trade-off: complexity vs performance.

python
RunExplain
# AVL tree automatically balances
# After insert:
# 1. Insert like BST
# 2. Update heights
# 3. Check balance factor
# 4. Rotate if needed

def insert_avl(root, val):
    # Insert
    if not root:
        return AVLNode(val)
    if val < root.val:
        root.left = insert_avl(root.left, val)
    else:
        root.right = insert_avl(root.right, val)
    
    # Balance
    balance = get_balance(root)
    if balance > 1:
        # Rotate
    return root
Q49

What is the difference between linear and non-linear data structures?

A

Linear: elements in sequence, single level (array, linked list, stack, queue). Non-linear: hierarchical/multi-level (tree, graph). Linear: O(n) traversal. Non-linear: various traversal methods. Linear: simpler, sequential access. Non-linear: complex relationships.

python
RunExplain
# Linear: array, linked list
linear = [1, 2, 3, 4, 5]  # Sequential

# Non-linear: tree, graph
#       1
#      / \
#     2   3
#    / \
#   4   5
Q50

What is Big O notation?

A

Big O describes upper bound of algorithm complexity. O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n²) quadratic, O(2ⁿ) exponential. Worst-case analysis. Helps compare algorithms, predict performance at scale.

python
RunExplain
# O(1) - Constant
def get_first(arr):
    return arr[0]

# O(log n) - Logarithmic (binary search)
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

# O(n) - Linear
def find_max(arr):
    return max(arr)

# O(n²) - Quadratic
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

More on Data Structures

Arrays and Linked Lists: Choosing the Right Structure

11 min0.0k

Stacks and Queues: LIFO and FIFO Data Structures

10 min0.0k

Binary Trees: Hierarchical Data Structures

13 min0.0k