Algorithm Templates: Data Structure Design

Data structure design problems are among the most popular interview questions at top tech companies. This page provides complete, tested Java implementations for LRU/LFU cache, Trie, time-based key-value store, and other classic design patterns. The key insight for most of these problems is combining two or more simple structures to achieve the required time complexity.

Design problems test your ability to compose data structures. The trick is almost always combining a hash map with another structure (linked list, heap, array) to get O(1) for multiple operations.

Beginner’s Guide: LeetCode Beginner’s Guide
Summary

| Pattern | Signal Phrases | Structures Used | |—|—|—| | Min Stack | “min in O(1)” | Two stacks | | LRU Cache | “least recently used” | Hash map + doubly linked list | | LFU Cache | “least frequently used” | Hash map + frequency buckets | | Trie | “prefix search”, “autocomplete” | Tree of character nodes | | Time-based KV | “get value at timestamp” | Hash map + binary search |

Stack-based Design
LRU Cache
LFU Cache
Trie
Time-based Key-Value Store
Design Patterns

Stack-based Design

When to use: “get min/max in O(1)”, “design a stack with extra operations”, or when you need to track additional state alongside the primary data.

Min Stack

Maintain a primary stack for data and an auxiliary stack to track the minimum value at each state.

ID	Title	Link	Solution
155	Min Stack	Link	Solution

// import java.util.*;
class MinStack {
    Deque<Integer> stk, minStk;
    public void push(int val) {
        stk.offer(val);
        if (minStk.length == 0) minStk.offer(val);
        else minStk.offer(Math.min(minStk.peek(), val));
    }
    public void pop() { stk.poll(); minStk.poll(); }
        public int top() { return stk.peek(); }
        public int getMin() { return minStk.peek(); }
}

ID	Title	Link	Solution
155	Min Stack	Link	Solution

LRU Cache

When to use: “least recently used”, “design a cache with O(1) get and put”, or any eviction policy based on access recency.

Least Recently Used cache using hash map + doubly linked list.

Thread-Safe LRU Cache

Thread-safe version using mutex for concurrent access.

ID	Title	Link	Solution
146	LRU Cache	Link	Solution

// import java.util.*;
class LRUCache {
        int capacity_;
    LinkedList<Integer> keyList_ = new LinkedList<Integer>();
    unordered_map<int, pair<int, LinkedList<Integer>::iterator>> hashMap_;

    public void insert(int key, int value) {
        keyList_.add(key);
        hashMap_[key] = new int[] {value, --keyList_.end(});
    }
    LRUCache(int capacity) {
    }
        public int get(int key) {
        var it = hashMap_.find(key);
        if(it != hashMap_.iterator()) {
            /* move to end */, keyList_, it[1].second);
            return it[1][0];
        }
        return -1;
    }

    public void put(int key, int value) {
        if(get(key) != -1) {
            hashMap_[key].first = value;
            return;
        }
        if(hashMap_.size() < capacity_) {
            insert(key, value);
        } else {
            int removeKey = keyList_.get(0);
            keyList_.removeFirst();
            hashMap_.remove(removeKey);
            insert(key, value);
        }
    }
}
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache = new new(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

Thread-Safe LRU Cache

Thread-safe version using mutex for concurrent access.

// import java.util.*;

class ThreadSafeLRUCache {
        int capacity_;
    LinkedList<Integer> keyList_ = new LinkedList<Integer>();
    unordered_map<int, pair<int, LinkedList<Integer>::iterator>> hashMap_;
    mutable shared_mutex mtx_; // Use shared_mutex for read-write lock

    void insert(int key, int value) {
        keyList_.add(key);
        hashMap_[key] = new int[] {value, --keyList_.end(});
    }

    boolean exists(int key) {
        return hashMap_.find(key) != hashMap_.iterator();
    }
    ThreadSafeLRUCache(int capacity) {
    }

    int get(int key) {
         // Exclusive lock for read+modify
        var it = hashMap_.find(key);
        if(it != hashMap_.iterator()) {
            /* move to end */, keyList_, it[1].second);
            return it[1][0];
        }
        return -1;
    }

    void put(int key, int value) {
         // Exclusive lock for write
        if(exists(key)) {
            hashMap_[key].first = value;
            /* move to end */, keyList_, hashMap_[key].second);
            return;
        }
        if(hashMap_.size() < capacity_) {
            insert(key, value);
        } else {
            int removeKey = keyList_.get(0);
            keyList_.removeFirst();
            hashMap_.remove(removeKey);
            insert(key, value);
        }
    }

    size_t size() {
        shared_lock<shared_mutex> lock(mtx_);
        return hashMap_.size();
    }
}
// Example usage:
// ThreadSafeLRUCache cache = new ThreadSafeLRUCache(2);
// cache.put(1, 1);
// cache.put(2, 2);
// int val = cache.get(1); // returns 1
// cache.put(3, 3); // evicts key 2

ID	Title	Link	Solution
146	LRU Cache	Link	Solution

LFU Cache

When to use: “least frequently used”, “evict the element used fewest times”, or cache designs where frequency matters more than recency.

Least Frequently Used cache.

ID	Title	Link	Solution
460	LFU Cache	Link	Solution

// import java.util.*;
class LFUCache {
        int capacity, minFreq;
    HashMap<Integer, int[]> keyValFreq = new HashMap<Integer, int[]>(); // key . new int[] {value, frequency}
    HashMap<Integer, LinkedList<Integer>> freqKeys = new HashMap<>(); // frequency . list of keys
    unordered_map<int, LinkedList<Integer>::iterator> keyIter; // key . iterator in freqKeys list

    void updateFreq(int key) {
        int freq = keyValFreq[key].second;
        freqKeys[freq].erase(keyIter[key]);

        if (freqKeys[freq].empty() && freq == minFreq) {
            minFreq++;
        }

        freq++;
        keyValFreq[key].second = freq;
        freqKeys.computeIfAbsent(freq, k.new ArrayList<>()).add(key);
        keyIter.put(key, --freqKeys[freq].end());
    }
    LFUCache(int capacity) {}

    int get(int key) {
        if (keyValFreq.find(key) == keyValFreq.iterator()) return -1;
        updateFreq(key);
        return keyValFreq[key].first;
    }

    void put(int key, int value) {
        if (capacity == 0) return;

        if (keyValFreq.find(key) != keyValFreq.iterator()) {
            keyValFreq[key].first = value;
            updateFreq(key);
        } else {
            if (keyValFreq.size() >= capacity) {
                int evictKey = freqKeys[minFreq].front();
                freqKeys[minFreq].pop_front();
                keyValFreq.remove(evictKey);
                keyIter.remove(evictKey);
            }

            keyValFreq.put(key, new int[] {value, 1});
            freqKeys.computeIfAbsent(1, k.new ArrayList<>()).add(key);
            keyIter.put(key, --freqKeys[1].end());
            minFreq = 1;
        }
    }
}

ID	Title	Link	Solution
460	LFU Cache	Link	Solution

Trie

When to use: “prefix search”, “autocomplete”, “word dictionary with wildcards”, or any problem requiring efficient prefix lookups over a set of strings.

Prefix tree for efficient string operations.

ID	Title	Link	Solution
208	Implement Trie (Prefix Tree)	Link	-
211	Design Add and Search Words Data Structure	Link	-

class Trie {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd;
    }

    private final TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return false;
            node = node.children[idx];
        }
        return node.isEnd;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return false;
            node = node.children[idx];
        }
        return true;
    }
}

ID	Title	Link	Solution
208	Implement Trie (Prefix Tree)	Link	-
211	Design Add and Search Words Data Structure	Link	-

Time-based Key-Value Store

When to use: “get value at timestamp”, “versioned storage”, or when you need to retrieve the most recent value at or before a given time.

ID	Title	Link	Solution
981	Time Based Key-Value Store	Link	-
362	Design Hit Counter	Link	Solution
1146	Snapshot Array	Link	Solution

// import java.util.*;
class TimeMap {
    unordered_map<String, List<int[]>> store;
    TimeMap() {}

    void set(String key, String value, int timestamp) {
        store.computeIfAbsent(key, k.new ArrayList<>()).add(new int[] {timestamp, value});
    }

    String get(String key, int timestamp) {
        if (store.find(key) == store.iterator()) return "";

        var pairs = store[key];
        int left = 0, right = pairs.size() - 1;
        String result = "";

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (pairs[mid].first <= timestamp) {
                result = pairs[mid].second;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result;
    }
}

ID	Title	Link	Solution
981	Time Based Key-Value Store	Link	-
362	Design Hit Counter	Link	Solution
1146	Snapshot Array	Link	Solution

Design Patterns

When to use: “random with weight”, “design tic-tac-toe”, “iterator”, or other custom data structure problems that combine multiple techniques.

Random Pick with Weight

Design Tic-Tac-Toe

ID	Title	Link	Solution
528	Random Pick with Weight	Link	Solution
348	Design Tic-Tac-Toe	Link	Solution
1275	Find Winner on a Tic Tac Toe Game	Link	Solution
398	Random Pick Index	Link	Solution
2043	Simple Bank System	Link	Solution
281	Zigzag Iterator	Link	Solution
1206	Design Skiplist	Link	Solution
341	Flatten Nested List Iterator	Link	Solution
1115	Print FooBar Alternately	Link	Solution
1188	Design Bounded Blocking Queue	Link	Solution

class Solution {
    List<Integer> prefixSum = new ArrayList<>();
    Solution(int[] w) {
        prefixSum.add(0);
        for (int weight : w) {
            prefixSum.add(prefixSum.get(prefixSum.size() - 1) + weight);
        }
    }
        public int pickIndex() {
        int target = new Random().nextInt() % prefixSum.get(prefixSum.size() - 1);
        return binary search (upper bound)(prefixSum /* elements of prefixSum */, target) - prefixSum.iterator() - 1;
    }
}

Design Tic-Tac-Toe

class TicTacToe {
    int[]rows, cols;
        int diagonal, antiDiagonal;
        int n;
    TicTacToe(int n) {}

    int move(int row, int col, int player) {
        int add = (player == 1) ? 1 : -1;

        rows.put(row, rows.getOrDefault(row, 0) + add;
        cols.put(col, cols.getOrDefault(col, 0) + add;

        if (row == col) diagonal += add;
        if (row + col == n - 1) antiDiagonal += add;

        if (abs(rows[row]) == n || abs(cols[col]) == n ||
            abs(diagonal) == n || abs(antiDiagonal) == n) {
            return player;
        }

        return 0;
    }
}

ID	Title	Link	Solution
528	Random Pick with Weight	Link	Solution
348	Design Tic-Tac-Toe	Link	Solution
1275	Find Winner on a Tic Tac Toe Game	Link	Solution
398	Random Pick Index	Link	Solution
2043	Simple Bank System	Link	Solution
281	Zigzag Iterator	Link	Solution
1206	Design Skiplist	Link	Solution
341	Flatten Nested List Iterator	Link	Solution
1115	Print FooBar Alternately	Link	Solution
1188	Design Bounded Blocking Queue	Link	Solution

More templates

Data structures (Trie, segment tree): Data Structures & Core Algorithms
Master index: Categories & Templates

Robina Li

Algorithm Templates: Data Structure Design

Summary

Contents

Stack-based Design

Min Stack

LRU Cache

Thread-Safe LRU Cache

Thread-Safe LRU Cache

LFU Cache

Trie

Time-based Key-Value Store

Design Patterns

Random Pick with Weight

Design Tic-Tac-Toe

Design Tic-Tac-Toe

More templates

Related Posts

Recent Posts