Problems
Master hash tables by solving these carefully selected problems. Each problem demonstrates different hash table patterns and builds your data structure expertise progressively.
Ready to apply the hash table patterns you’ve learned? This section provides a structured progression from basic to advanced problems. Each problem includes a detailed explanation, visual representation, and complete multi-language solutions.
For reference, check out our code templates for reusable implementations across different languages.
Problem List
Easy Problems
1. Contains Duplicate
Brief: Determine if an array contains any duplicate values.
Why this pattern?: This is the classic “existence checking” problem where we need to track seen elements efficiently.
Key Insight: Use a Set to track elements we’ve already encountered. The first duplicate found means we can return true immediately.
Visual Flow:
flowchart TD
A[Start with empty Set] --> B[Process each element]
B --> C{Element in Set?}
C -->|Yes| D[Return true - duplicate found]
C -->|No| E[Add to Set]
E --> F{More elements?}
F -->|Yes| B
F -->|No| G[Return false - no duplicates]
function containsDuplicate(nums) {
const seen = new Set();
for (const num of nums) {
if (seen.has(num)) {
return true;
}
seen.add(num);
}
return false;
}def containsDuplicate(nums):
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return Falsepublic boolean containsDuplicate(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int num : nums) {
if (seen.contains(num)) {
return true;
}
seen.add(num);
}
return false;
}bool containsDuplicate(vector<int>& nums) {
unordered_set<int> seen;
for (int num : nums) {
if (seen.find(num) != seen.end()) {
return true;
}
seen.insert(num);
}
return false;
}func containsDuplicate(nums []int) bool {
seen := make(map[int]bool)
for _, num := range nums {
if seen[num] {
return true
}
seen[num] = true
}
return false
}def contains_duplicate(nums)
seen = Set.new
nums.each do |num|
return true if seen.include?(num)
seen.add(num)
end
false
end2. Two Sum
Brief: Find indices of two numbers that add up to a specific target.
Why this pattern?: This introduces the “complement search” pattern where we look for pairs that satisfy a condition.
Key Insight: For each number, calculate what value would complete the pair (complement), then check if we’ve seen it before.
Visual Flow:
flowchart TD
A[Initialize empty Map] --> B[Process each number]
B --> C[Calculate complement]
C --> D{Complement in Map?}
D -->|Yes| E[Return indices]
D -->|No| F[Store current number with index]
F --> G{More numbers?}
G -->|Yes| B
G -->|No| H[No solution found]
function twoSum(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement)) {
return [map.get(complement), i];
}
map.set(nums[i], i);
}
return [];
}def twoSum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
map.put(nums[i], i);
}
return new int[]{};
}vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (map.find(complement) != map.end()) {
return {map[complement], i};
}
map[nums[i]] = i;
}
return {};
}func twoSum(nums []int, target int) []int {
seen := make(map[int]int)
for i, num := range nums {
complement := target - num
if idx, exists := seen[complement]; exists {
return []int{idx, i}
}
seen[num] = i
}
return []int{}
}def two_sum(nums, target)
seen = {}
nums.each_with_index do |num, i|
complement = target - num
return [seen[complement], i] if seen.key?(complement)
seen[num] = i
end
[]
end3. Valid Anagram
Brief: Determine if one string is an anagram of another.
Why this pattern?: This demonstrates frequency counting where we need to track character occurrences.
Key Insight: Count character frequencies in both strings and compare. If they match exactly, the strings are anagrams.
Visual Flow:
flowchart TD
A[Count chars in s] --> B[Decrement counts for t]
B --> C{Any negative counts?}
C -->|Yes| D[Not anagrams]
C -->|No| E{All counts zero?}
E -->|Yes| F[Valid anagrams]
E -->|No| D
function isAnagram(s, t) {
if (s.length !== t.length) return false;
const count = new Map();
for (const char of s) {
count.set(char, (count.get(char) || 0) + 1);
}
for (const char of t) {
if (!count.has(char)) return false;
count.set(char, count.get(char) - 1);
if (count.get(char) < 0) return false;
}
return true;
}def isAnagram(s, t):
if len(s) != len(t):
return False
count = {}
for char in s:
count[char] = count.get(char, 0) + 1
for char in t:
if char not in count:
return False
count[char] -= 1
if count[char] < 0:
return False
return Truepublic boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
Map<Character, Integer> count = new HashMap<>();
for (char c : s.toCharArray()) {
count.put(c, count.getOrDefault(c, 0) + 1);
}
for (char c : t.toCharArray()) {
if (!count.containsKey(c)) return false;
count.put(c, count.get(c) - 1);
if (count.get(c) < 0) return false;
}
return true;
}bool isAnagram(string s, string t) {
if (s.length() != t.length()) return false;
unordered_map<char, int> count;
for (char c : s) {
count[c]++;
}
for (char c : t) {
if (count.find(c) == count.end()) return false;
count[c]--;
if (count[c] < 0) return false;
}
return true;
}func isAnagram(s string, t string) bool {
if len(s) != len(t) {
return false
}
count := make(map[rune]int)
for _, char := range s {
count[char]++
}
for _, char := range t {
if count[char] == 0 {
return false
}
count[char]--
}
return true
}def is_anagram(s, t)
return false if s.length != t.length
count = Hash.new(0)
s.each_char { |char| count[char] += 1 }
t.each_char { |char| count[char] -= 1 }
count.values.all? { |c| c == 0 }
endMedium Problems
4. Group Anagrams
Brief: Group anagrams from an array of strings together.
Why this pattern?: This showcases the “grouping by property” pattern where we categorize elements based on shared characteristics.
Key Insight: Sort each string to create a canonical form (key), then group strings with the same key together.
Visual Flow:
flowchart TD
A[Process each string] --> B[Sort characters to create key]
B --> C{Key exists in Map?}
C -->|No| D[Create new group]
C -->|Yes| E[Add to existing group]
D --> F[Store in Map]
E --> F
F --> G{More strings?}
G -->|Yes| A
G -->|No| H[Return all groups]
function groupAnagrams(strs) {
const groups = new Map();
for (const str of strs) {
const key = str.split('').sort().join('');
if (!groups.has(key)) {
groups.set(key, []);
}
groups.get(key).push(str);
}
return Array.from(groups.values());
}def groupAnagrams(strs):
groups = {}
for s in strs:
key = ''.join(sorted(s))
if key not in groups:
groups[key] = []
groups[key].append(s)
return list(groups.values())public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> groups = new HashMap<>();
for (String str : strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
}
return new ArrayList<>(groups.values());
}vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> groups;
for (const string& str : strs) {
string key = str;
sort(key.begin(), key.end());
groups[key].push_back(str);
}
vector<vector<string>> result;
for (auto& pair : groups) {
result.push_back(pair.second);
}
return result;
}func groupAnagrams(strs []string) [][]string {
groups := make(map[string][]string)
for _, str := range strs {
key := sortString(str)
groups[key] = append(groups[key], str)
}
result := [][]string{}
for _, group := range groups {
result = append(result, group)
}
return result
}
func sortString(s string) string {
chars := []rune(s)
sort.Slice(chars, func(i, j int) bool {
return chars[i] < chars[j]
})
return string(chars)
}def group_anagrams(strs)
groups = Hash.new { |h, k| h[k] = [] }
strs.each do |str|
key = str.chars.sort.join
groups[key] << str
end
groups.values
end5. Intersection of Two Arrays II
Brief: Find intersection of two arrays, including duplicates.
Why this pattern?: This combines frequency counting with intersection logic, showing how to handle multiple occurrences.
Key Insight: Count frequencies in one array, then iterate through the second array to find common elements while respecting occurrence counts.
Visual Flow:
flowchart TD
A[Count frequencies in nums1] --> B[Process nums2 elements]
B --> C{Element in frequency map?}
C -->|Yes and count > 0| D[Add to result, decrement count]
C -->|No or count = 0| E[Skip element]
D --> F{More elements?}
E --> F
F -->|Yes| B
F -->|No| G[Return result]
function intersect(nums1, nums2) {
const freq = new Map();
const result = [];
for (const num of nums1) {
freq.set(num, (freq.get(num) || 0) + 1);
}
for (const num of nums2) {
if (freq.has(num) && freq.get(num) > 0) {
result.push(num);
freq.set(num, freq.get(num) - 1);
}
}
return result;
}def intersect(nums1, nums2):
freq = {}
result = []
for num in nums1:
freq[num] = freq.get(num, 0) + 1
for num in nums2:
if num in freq and freq[num] > 0:
result.append(num)
freq[num] -= 1
return resultpublic int[] intersect(int[] nums1, int[] nums2) {
Map<Integer, Integer> freq = new HashMap<>();
List<Integer> result = new ArrayList<>();
for (int num : nums1) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
for (int num : nums2) {
if (freq.containsKey(num) && freq.get(num) > 0) {
result.add(num);
freq.put(num, freq.get(num) - 1);
}
}
return result.stream().mapToInt(Integer::intValue).toArray();
}vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> freq;
vector<int> result;
for (int num : nums1) {
freq[num]++;
}
for (int num : nums2) {
if (freq[num] > 0) {
result.push_back(num);
freq[num]--;
}
}
return result;
}func intersect(nums1 []int, nums2 []int) []int {
freq := make(map[int]int)
result := []int{}
for _, num := range nums1 {
freq[num]++
}
for _, num := range nums2 {
if freq[num] > 0 {
result = append(result, num)
freq[num]--
}
}
return result
}def intersect(nums1, nums2)
freq = Hash.new(0)
result = []
nums1.each { |num| freq[num] += 1 }
nums2.each do |num|
if freq[num] > 0
result << num
freq[num] -= 1
end
end
result
end6. Top K Frequent Elements
Brief: Return the k most frequent elements from an array.
Why this pattern?: This demonstrates advanced frequency counting combined with bucket sort for optimal O(n) time complexity.
Key Insight: Use bucket sort where each bucket represents a frequency count, allowing us to extract top k elements efficiently.
Visual Flow:
flowchart TD
A[Count frequencies] --> B[Create buckets by frequency]
B --> C[Fill buckets with elements]
C --> D[Extract from highest frequency]
D --> E{Got k elements?}
E -->|No| D
E -->|Yes| F[Return result]
function topKFrequent(nums, k) {
const freq = new Map();
const buckets = Array.from({length: nums.length + 1}, () => []);
for (const num of nums) {
freq.set(num, (freq.get(num) || 0) + 1);
}
for (const [num, count] of freq) {
buckets[count].push(num);
}
const result = [];
for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
if (buckets[i].length > 0) {
const remaining = k - result.length;
result.push(...buckets[i].slice(0, remaining));
}
}
return result;
}def topKFrequent(nums, k):
freq = {}
buckets = [[] for _ in range(len(nums) + 1)]
for num in nums:
freq[num] = freq.get(num, 0) + 1
for num, count in freq.items():
buckets[count].append(num)
result = []
for i in range(len(buckets) - 1, -1, -1):
if buckets[i]:
result.extend(buckets[i])
if len(result) >= k:
return result[:k]
return resultpublic int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
List<List<Integer>> buckets = new ArrayList<>();
for (int i = 0; i <= nums.length; i++) {
buckets.add(new ArrayList<>());
}
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
buckets.get(entry.getValue()).add(entry.getKey());
}
int[] result = new int[k];
int index = 0;
for (int i = buckets.size() - 1; i >= 0 && index < k; i--) {
for (int num : buckets.get(i)) {
result[index++] = num;
if (index == k) return result;
}
}
return result;
}vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> freq;
vector<vector<int>> buckets(nums.size() + 1);
for (int num : nums) {
freq[num]++;
}
for (auto& pair : freq) {
buckets[pair.second].push_back(pair.first);
}
vector<int> result;
for (int i = buckets.size() - 1; i >= 0 && result.size() < k; i--) {
for (int num : buckets[i]) {
result.push_back(num);
if (result.size() == k) return result;
}
}
return result;
}func topKFrequent(nums []int, k int) []int {
freq := make(map[int]int)
buckets := make([][]int, len(nums)+1)
for _, num := range nums {
freq[num]++
}
for num, count := range freq {
buckets[count] = append(buckets[count], num)
}
result := []int{}
for i := len(buckets) - 1; i >= 0 && len(result) < k; i-- {
for _, num := range buckets[i] {
result = append(result, num)
if len(result) == k {
return result
}
}
}
return result
}def top_k_frequent(nums, k)
freq = Hash.new(0)
buckets = Array.new(nums.length + 1) { [] }
nums.each { |num| freq[num] += 1 }
freq.each { |num, count| buckets[count] << num }
result = []
(buckets.length - 1).downto(0) do |i|
buckets[i].each do |num|
result << num
return result if result.length == k
end
end
result
endHard Problems
7. LRU Cache
Brief: Design a cache with O(1) get and put operations that evicts least recently used items.
Why this pattern?: This combines hash tables with linked lists to create a sophisticated data structure with specific ordering requirements.
Key Insight: Use a hash map for O(1) access and a doubly linked list for O(1) ordering operations. The head is most recent, tail is least recent.
Visual Flow:
flowchart TD
A[Get Operation] --> B[Check Hash Map]
B --> C{Key exists?}
C -->|No| D[Return -1]
C -->|Yes| E[Move to head of list]
E --> F[Return value]
G[Put Operation] --> H{Key exists?}
H -->|Yes| I[Update value, move to head]
H -->|No| J{At capacity?}
J -->|Yes| K[Remove tail node]
J -->|No| L[Create new node]
L --> M[Add to head, update map]
K --> M
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
this.head = new Node(0, 0);
this.tail = new Node(0, 0);
this.head.next = this.tail;
this.tail.prev = this.head;
}
get(key) {
if (!this.cache.has(key)) return -1;
const node = this.cache.get(key);
this._remove(node);
this._addToHead(node);
return node.value;
}
put(key, value) {
if (this.cache.has(key)) {
const node = this.cache.get(key);
node.value = value;
this._remove(node);
this._addToHead(node);
} else {
if (this.cache.size >= this.capacity) {
const tail = this._removeTail();
this.cache.delete(tail.key);
}
const node = new Node(key, value);
this._addToHead(node);
this.cache.set(key, node);
}
}
_remove(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
_addToHead(node) {
node.prev = this.head;
node.next = this.head.next;
this.head.next.prev = node;
this.head.next = node;
}
_removeTail() {
const node = this.tail.prev;
this._remove(node);
return node;
}
}
class Node {
constructor(key, value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = {}
self.head = Node(0, 0)
self.tail = Node(0, 0)
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_head(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def get(self, key):
if key not in self.cache:
return -1
node = self.cache[key]
self._remove(node)
self._add_to_head(node)
return node.value
def put(self, key, value):
if key in self.cache:
node = self.cache[key]
node.value = value
self._remove(node)
self._add_to_head(node)
else:
if len(self.cache) >= self.capacity:
tail = self.tail.prev
self._remove(tail)
del self.cache[tail.key]
node = Node(key, value)
self._add_to_head(node)
self.cache[key] = nodeclass Node {
int key, value;
Node prev, next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
class LRUCache {
private int capacity;
private Map<Integer, Node> cache;
private Node head, tail;
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
this.head = new Node(0, 0);
this.tail = new Node(0, 0);
this.head.next = this.tail;
this.tail.prev = this.head;
}
public int get(int key) {
if (!cache.containsKey(key)) return -1;
Node node = cache.get(key);
remove(node);
addToHead(node);
return node.value;
}
public void put(int key, int value) {
if (cache.containsKey(key)) {
Node node = cache.get(key);
node.value = value;
remove(node);
addToHead(node);
} else {
if (cache.size() >= capacity) {
Node tail = removeTail();
cache.remove(tail.key);
}
Node node = new Node(key, value);
addToHead(node);
cache.put(key, node);
}
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addToHead(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private Node removeTail() {
Node node = tail.prev;
remove(node);
return node;
}
}class Node {
public:
int key, value;
Node* prev;
Node* next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
class LRUCache {
private:
int capacity;
unordered_map<int, Node*> cache;
Node* head;
Node* tail;
void remove(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void addToHead(Node* node) {
node->prev = head;
node->next = head->next;
head->next->prev = node;
head->next = node;
}
Node* removeTail() {
Node* node = tail->prev;
remove(node);
return node;
}
public:
LRUCache(int capacity) {
this->capacity = capacity;
head = new Node(0, 0);
tail = new Node(0, 0);
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (cache.find(key) == cache.end()) return -1;
Node* node = cache[key];
remove(node);
addToHead(node);
return node->value;
}
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
Node* node = cache[key];
node->value = value;
remove(node);
addToHead(node);
} else {
if (cache.size() >= capacity) {
Node* tail = removeTail();
cache.erase(tail->key);
delete tail;
}
Node* node = new Node(key, value);
addToHead(node);
cache[key] = node;
}
}
};type Node struct {
key, value int
prev, next *Node
}
type LRUCache struct {
capacity int
cache map[int]*Node
head *Node
tail *Node
}
func Constructor(capacity int) LRUCache {
lru := LRUCache{
capacity: capacity,
cache: make(map[int]*Node),
head: &Node{0, 0, nil, nil},
tail: &Node{0, 0, nil, nil},
}
lru.head.next = lru.tail
lru.tail.prev = lru.head
return lru
}
func (this *LRUCache) remove(node *Node) {
node.prev.next = node.next
node.next.prev = node.prev
}
func (this *LRUCache) addToHead(node *Node) {
node.prev = this.head
node.next = this.head.next
this.head.next.prev = node
this.head.next = node
}
func (this *LRUCache) Get(key int) int {
if node, exists := this.cache[key]; exists {
this.remove(node)
this.addToHead(node)
return node.value
}
return -1
}
func (this *LRUCache) Put(key int, value int) {
if node, exists := this.cache[key]; exists {
node.value = value
this.remove(node)
this.addToHead(node)
} else {
if len(this.cache) >= this.capacity {
tail := this.tail.prev
this.remove(tail)
delete(this.cache, tail.key)
}
node := &Node{key, value, nil, nil}
this.addToHead(node)
this.cache[key] = node
}
}class Node
attr_accessor :key, :value, :prev, :next
def initialize(key, value)
@key = key
@value = value
@prev = nil
@next = nil
end
end
class LRUCache
def initialize(capacity)
@capacity = capacity
@cache = {}
@head = Node.new(0, 0)
@tail = Node.new(0, 0)
@head.next = @tail
@tail.prev = @head
end
def get(key)
return -1 unless @cache.key?(key)
node = @cache[key]
remove(node)
add_to_head(node)
node.value
end
def put(key, value)
if @cache.key?(key)
node = @cache[key]
node.value = value
remove(node)
add_to_head(node)
else
if @cache.size >= @capacity
tail = remove_tail
@cache.delete(tail.key)
end
node = Node.new(key, value)
add_to_head(node)
@cache[key] = node
end
end
private
def remove(node)
node.prev.next = node.next
node.next.prev = node.prev
end
def add_to_head(node)
node.prev = @head
node.next = @head.next
@head.next.prev = node
@head.next = node
end
def remove_tail
node = @tail.prev
remove(node)
node
end
end8. Longest Substring Without Repeating Characters
Brief: Find the length of the longest substring without repeating characters.
Why this pattern?: This combines hash tables with sliding window technique, showing how to track state efficiently.
Key Insight: Use a sliding window with a hash set to track characters in the current window. When a duplicate is found, shrink the window from the left.
Visual Flow:
flowchart TD
A[Initialize window] --> B[Expand right pointer]
B --> C{Character in set?}
C -->|No| D[Add to set, update max]
C -->|Yes| E[Shrink left pointer]
D --> F{End reached?}
E --> C
F -->|No| B
F -->|Yes| G[Return max length]
function lengthOfLongestSubstring(s) {
const seen = new Set();
let left = 0, maxLength = 0;
for (let right = 0; right < s.length; right++) {
while (seen.has(s[right])) {
seen.delete(s[left]);
left++;
}
seen.add(s[right]);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}def lengthOfLongestSubstring(s):
seen = set()
left = 0
max_length = 0
for right in range(len(s)):
while s[right] in seen:
seen.remove(s[left])
left += 1
seen.add(s[right])
max_length = max(max_length, right - left + 1)
return max_lengthpublic int lengthOfLongestSubstring(String s) {
Set<Character> seen = new HashSet<>();
int left = 0, maxLength = 0;
for (int right = 0; right < s.length(); right++) {
while (seen.contains(s.charAt(right))) {
seen.remove(s.charAt(left));
left++;
}
seen.add(s.charAt(right));
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}int lengthOfLongestSubstring(string s) {
unordered_set<char> seen;
int left = 0, maxLength = 0;
for (int right = 0; right < s.length(); right++) {
while (seen.find(s[right]) != seen.end()) {
seen.erase(s[left]);
left++;
}
seen.insert(s[right]);
maxLength = max(maxLength, right - left + 1);
}
return maxLength;
}func lengthOfLongestSubstring(s string) int {
seen := make(map[byte]bool)
left, maxLength := 0, 0
for right := 0; right < len(s); right++ {
for seen[s[right]] {
seen[s[left]] = false
left++
}
seen[s[right]] = true
maxLength = max(maxLength, right-left+1)
}
return maxLength
}
func max(a, b int) int {
if a > b {
return a
}
return b
}def length_of_longest_substring(s)
seen = Set.new
left = 0
max_length = 0
s.each_char.with_index do |char, right|
while seen.include?(char)
seen.delete(s[left])
left += 1
end
seen.add(char)
max_length = [max_length, right - left + 1].max
end
max_length
endRecommended Study Order
- Start with Easy Problems: Contains Duplicate → Two Sum → Valid Anagram
- Progress to Medium: Group Anagrams → Intersection of Two Arrays II → Top K Frequent Elements
- Tackle Hard Problems: LRU Cache → Longest Substring Without Repeating Characters
Common Patterns to Recognize
- Frequency counting → Map for counts, Set for uniqueness
- Complement search → Map for two sum, k sums
- Grouping by property → Map with array values
- Existence checking → Set for O(1) membership tests
- Caching → Map for LRU, LFU implementations
Interview Tips
- Choose between Map and Set - Map for key-value, Set for existence
- Handle collision in interviews - Understand chaining vs open addressing
- Consider time vs space - Sometimes arrays are faster for small datasets
- Implement custom hash functions - When using objects as keys
- Know built-in limitations - No ordering, possible hash conflicts
Remember: Hash tables provide excellent average performance but can have
O(n)