Data Structures That Appear in 80% of Tech Interviews

aloalgo

Knowing when to use which data structure is half the battle in coding interviews. The right choice can turn an O(n²) solution into O(n), or make an impossible problem trivial. This guide covers the essential data structures, their operations, complexities, and when to reach for each one.

Based on interview data from top tech companies:

The most fundamental data structure. Arrays store elements in contiguous memory, enabling O(1) random access by index.

You need fast access by index
The size is fixed or grows only at the end
You're iterating through elements sequentially
Memory efficiency matters (no pointer overhead)

Hash maps provide O(1) average-case lookup, insert, and delete. They're the secret weapon for optimizing brute force solutions.

You need fast lookups by key
Counting frequencies of elements
Checking for duplicates
Caching/memoization
Two Sum and its variations

When you only need to track presence (not key-value pairs), use a set. Same O(1) operations as hash maps.

Last-In-First-Out (LIFO). Think of a stack of plates - you can only add or remove from the top.

Matching parentheses/brackets
Undo operations
DFS (iterative implementation)
Expression evaluation
Monotonic stack problems (next greater element)

Deep dive: Stack Patterns: More Than Just LIFO

First-In-First-Out (FIFO). Like a line at a store - first person in line is first to be served.

BFS (level-order traversal)
Processing in order of arrival
Sliding window maximum (with deque)
Task scheduling

Nodes connected by pointers. Unlike arrays, elements aren't contiguous in memory, enabling O(1) insertions and deletions once you have a reference to the node.

Frequent insertions/deletions at arbitrary positions
Unknown size that grows/shrinks frequently
Implementing other data structures (stacks, queues, LRU cache)
When the problem explicitly uses ListNode

Deep dive: Linked Lists - Why Use Them Instead of Arrays and Common Patterns

Hierarchical data structures with a root node and children. Binary trees have at most two children per node.

Hierarchical relationships (file systems, org charts)
BST for sorted data with O(log n) operations
Recursive problem structure
Expression parsing

Deep dive: Every Binary Tree Pattern, Finally Explained

A complete binary tree where each parent is smaller (min-heap) or larger (max-heap) than its children. Provides O(log n) insert and O(1) access to min/max.

Find K largest/smallest elements
Merge K sorted lists
Find median from data stream
Dijkstra's shortest path
Task scheduling by priority

Deep dive: Priority Queue Patterns: Top-K and Beyond

Nodes (vertices) connected by edges. Can be directed or undirected, weighted or unweighted. Represented as adjacency list or matrix.

Network/connection problems
Shortest path
Dependency resolution (topological sort)
Grid problems (implicit graph)
Social networks, maps, web crawling

Deep dive: Graph Algorithms Made Simple: BFS, DFS, Dijkstra

Specialized tree for storing strings where each node represents a character. Enables O(m) prefix lookups where m is the word length.

Autocomplete
Spell checking
IP routing
Word search in grid
Prefix matching problems

Deep dive: What Is a Trie? No, That's Not a Typo

* Average case, O(n) worst case for hash collisions
** O(1) with reference to the node, O(n) to find it first

Real problems often combine multiple data structures:

LRU Cache: Hash Map + Doubly Linked List
Find Median: Two Heaps (min + max)
Graph BFS/DFS: Graph + Queue/Stack + Hash Set
Dijkstra: Graph + Min Heap + Hash Map
Top K Frequent: Hash Map + Heap
Word Search II: Trie + DFS on Grid

Was this helpful?

Study plan All problems

Resources Cheat Sheet DSA Glossary

Data Structures That Appear in 80% of Tech Interviews

Company

Practice

Learn