Data structures form the backbone of computer science and are crucial for efficient problem-solving in software development. As you prepare for coding interviews, especially for top tech companies like FAANG (Facebook, Amazon, Apple, Netflix, Google), understanding and mastering common data structures is essential. In this comprehensive guide, we’ll explore the most frequently asked data structures in coding interviews, their implementations, and real-world applications.

1. Arrays

Arrays are the most fundamental data structure and are often the building blocks for more complex structures. They store elements of the same data type in contiguous memory locations.

Key Characteristics:

  • Fixed size (in most languages)
  • Constant-time access to elements by index
  • Efficient for random access

Common Operations:

  • Insertion: O(n) – worst case when inserting at the beginning
  • Deletion: O(n) – worst case when deleting from the beginning
  • Search: O(n) for unsorted array, O(log n) for sorted array using binary search
  • Access: O(1)

Example Implementation (in Python):

# Creating an array
my_array = [1, 2, 3, 4, 5]

# Accessing elements
print(my_array[2])  # Output: 3

# Modifying elements
my_array[1] = 10
print(my_array)  # Output: [1, 10, 3, 4, 5]

# Appending elements
my_array.append(6)
print(my_array)  # Output: [1, 10, 3, 4, 5, 6]

# Removing elements
my_array.pop()
print(my_array)  # Output: [1, 10, 3, 4, 5]

Interview Questions:

  • Two Sum
  • Container With Most Water
  • Rotate Array

2. Linked Lists

Linked lists are linear data structures where elements are stored in nodes. Each node contains a data field and a reference (or link) to the next node in the sequence.

Key Characteristics:

  • Dynamic size
  • Efficient insertion and deletion at any position
  • No random access

Common Operations:

  • Insertion: O(1) at the beginning, O(n) at the end
  • Deletion: O(1) at the beginning, O(n) at the end
  • Search: O(n)
  • Access: O(n)

Example Implementation (in Python):

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Usage
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.display()  # Output: 1 -> 2 -> 3 -> None

Interview Questions:

  • Reverse a Linked List
  • Detect Cycle in a Linked List
  • Merge Two Sorted Linked Lists

3. Stacks

Stacks are linear data structures that follow the Last-In-First-Out (LIFO) principle. Elements are added and removed from the same end, called the top of the stack.

Key Characteristics:

  • LIFO order
  • Supports push (add) and pop (remove) operations
  • Used in function call management, undo mechanisms, and expression evaluation

Common Operations:

  • Push: O(1)
  • Pop: O(1)
  • Peek (Top): O(1)
  • IsEmpty: O(1)

Example Implementation (in Python):

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def peek(self):
        if not self.is_empty():
            return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

# Usage
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # Output: 3
print(stack.peek())  # Output: 2
print(stack.size())  # Output: 2

Interview Questions:

  • Valid Parentheses
  • Implement Queue using Stacks
  • Evaluate Reverse Polish Notation

4. Queues

Queues are linear data structures that follow the First-In-First-Out (FIFO) principle. Elements are added at the rear and removed from the front of the queue.

Key Characteristics:

  • FIFO order
  • Supports enqueue (add) and dequeue (remove) operations
  • Used in breadth-first search, task scheduling, and buffer management

Common Operations:

  • Enqueue: O(1)
  • Dequeue: O(1)
  • Front: O(1)
  • IsEmpty: O(1)

Example Implementation (in Python):

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.popleft()

    def front(self):
        if not self.is_empty():
            return self.items[0]

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

# Usage
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue())  # Output: 1
print(queue.front())  # Output: 2
print(queue.size())  # Output: 2

Interview Questions:

  • Implement Stack using Queues
  • Design Circular Queue
  • Sliding Window Maximum

5. Hash Tables

Hash tables, also known as hash maps or dictionaries, are data structures that store key-value pairs. They use a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Key Characteristics:

  • Fast lookup, insertion, and deletion
  • Implemented using an array and a hash function
  • Handles collisions through chaining or open addressing

Common Operations:

  • Insert: O(1) average case, O(n) worst case
  • Delete: O(1) average case, O(n) worst case
  • Search: O(1) average case, O(n) worst case

Example Implementation (in Python):

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(self.size)]

    def _hash(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self._hash(key)
        for item in self.table[index]:
            if item[0] == key:
                item[1] = value
                return
        self.table[index].append([key, value])

    def get(self, key):
        index = self._hash(key)
        for item in self.table[index]:
            if item[0] == key:
                return item[1]
        raise KeyError(key)

    def remove(self, key):
        index = self._hash(key)
        for i, item in enumerate(self.table[index]):
            if item[0] == key:
                del self.table[index][i]
                return
        raise KeyError(key)

# Usage
ht = HashTable()
ht.insert("apple", 5)
ht.insert("banana", 7)
print(ht.get("apple"))  # Output: 5
ht.remove("apple")
try:
    print(ht.get("apple"))
except KeyError:
    print("Key not found")  # Output: Key not found

Interview Questions:

  • Two Sum
  • LRU Cache
  • Group Anagrams

6. Trees

Trees are hierarchical data structures consisting of nodes connected by edges. They are widely used for representing hierarchical relationships and for efficient searching and sorting.

Key Characteristics:

  • Hierarchical structure with a root node
  • Each node can have multiple children
  • No cycles

Common Types of Trees:

  • Binary Trees
  • Binary Search Trees (BST)
  • AVL Trees
  • Red-Black Trees
  • B-Trees

Example Implementation (Binary Search Tree in Python):

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if not self.root:
            self.root = TreeNode(value)
        else:
            self._insert_recursive(self.root, value)

    def _insert_recursive(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = TreeNode(value)
            else:
                self._insert_recursive(node.left, value)
        else:
            if node.right is None:
                node.right = TreeNode(value)
            else:
                self._insert_recursive(node.right, value)

    def search(self, value):
        return self._search_recursive(self.root, value)

    def _search_recursive(self, node, value):
        if node is None or node.value == value:
            return node
        if value < node.value:
            return self._search_recursive(node.left, value)
        return self._search_recursive(node.right, value)

# Usage
bst = BinarySearchTree()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(1)
bst.insert(9)

print(bst.search(7).value)  # Output: 7
print(bst.search(10))  # Output: None

Interview Questions:

  • Validate Binary Search Tree
  • Lowest Common Ancestor of a Binary Tree
  • Binary Tree Level Order Traversal

7. Heaps

Heaps are specialized tree-based data structures that satisfy the heap property. In a max heap, for any given node, the value of the node is greater than or equal to the values of its children. In a min heap, the value of the node is less than or equal to the values of its children.

Key Characteristics:

  • Complete binary tree
  • Efficient for finding the minimum or maximum element
  • Used in priority queues and sorting algorithms (e.g., heapsort)

Common Operations:

  • Insert: O(log n)
  • Delete: O(log n)
  • Get Min/Max: O(1)

Example Implementation (Min Heap in Python):

class MinHeap:
    def __init__(self):
        self.heap = []

    def parent(self, i):
        return (i - 1) // 2

    def left_child(self, i):
        return 2 * i + 1

    def right_child(self, i):
        return 2 * i + 2

    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def insert(self, key):
        self.heap.append(key)
        self._heapify_up(len(self.heap) - 1)

    def _heapify_up(self, i):
        parent = self.parent(i)
        if i > 0 and self.heap[i] < self.heap[parent]:
            self.swap(i, parent)
            self._heapify_up(parent)

    def extract_min(self):
        if len(self.heap) == 0:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
        min_val = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        return min_val

    def _heapify_down(self, i):
        min_index = i
        left = self.left_child(i)
        right = self.right_child(i)

        if left < len(self.heap) and self.heap[left] < self.heap[min_index]:
            min_index = left
        if right < len(self.heap) and self.heap[right] < self.heap[min_index]:
            min_index = right

        if min_index != i:
            self.swap(i, min_index)
            self._heapify_down(min_index)

# Usage
heap = MinHeap()
heap.insert(5)
heap.insert(3)
heap.insert(7)
heap.insert(1)

print(heap.extract_min())  # Output: 1
print(heap.extract_min())  # Output: 3

Interview Questions:

  • Kth Largest Element in an Array
  • Merge K Sorted Lists
  • Find Median from Data Stream

8. Graphs

Graphs are non-linear data structures consisting of vertices (or nodes) and edges that connect these vertices. They are used to represent networks, relationships, and various real-world scenarios.

Key Characteristics:

  • Consists of vertices and edges
  • Can be directed or undirected
  • Can be weighted or unweighted

Common Representations:

  • Adjacency Matrix
  • Adjacency List

Example Implementation (Adjacency List in Python):

from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def bfs(self, start):
        visited = set()
        queue = [start]
        visited.add(start)

        while queue:
            vertex = queue.pop(0)
            print(vertex, end=" ")

            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

    def dfs(self, start):
        visited = set()

        def dfs_util(v):
            visited.add(v)
            print(v, end=" ")

            for neighbor in self.graph[v]:
                if neighbor not in visited:
                    dfs_util(neighbor)

        dfs_util(start)

# Usage
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)

print("BFS starting from vertex 2:")
g.bfs(2)
print("\nDFS starting from vertex 2:")
g.dfs(2)

Interview Questions:

  • Number of Islands
  • Course Schedule
  • Network Delay Time

9. Trie (Prefix Tree)

A trie, also called a prefix tree, is a tree-like data structure used to store and retrieve strings efficiently. It is particularly useful for tasks involving string prefixes, such as autocomplete and spell checking.

Key Characteristics:

  • Each node represents a character in a string
  • The root represents an empty string
  • Efficient for prefix-based operations

Common Operations:

  • Insert: O(m), where m is the length of the string
  • Search: O(m)
  • StartsWith: O(m)

Example Implementation (in Python):

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 starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

# Usage
trie = Trie()
trie.insert("apple")
trie.insert("app")
print(trie.search("apple"))  # Output: True
print(trie.search("app"))    # Output: True
print(trie.search("appl"))   # Output: False
print(trie.starts_with("app"))  # Output: True
print(trie.starts_with("bana")) # Output: False

Interview Questions:

  • Implement Trie (Prefix Tree)
  • Word Search II
  • Design Add and Search Words Data Structure

Conclusion

Understanding these common data structures is crucial for success in coding interviews, especially when applying to top tech companies. Each data structure has its own strengths and use cases, and being familiar with their implementations and time complexities will help you choose the right tool for the job when solving algorithmic problems.

Remember that mastering these data structures requires practice. Implement them from scratch, solve problems that utilize them, and analyze their time and space complexities. As you gain more experience, you’ll develop an intuition for which data structure to use in different scenarios.

Keep in mind that while these are the most common data structures asked in interviews, there are others you might encounter, such as disjoint set union (DSU), segment trees, or advanced variations of the structures we’ve discussed. Always be prepared to learn and adapt to new concepts during your interview preparation.

Good luck with your interview preparation, and happy coding!