DSA

Hash Maps & Sets

Interview Prep · 6 entries

Frequency Counting

syntax

Build a map of element → count.
Useful for: most common element, anagrams, character counting, voting problems.

example

// JavaScript
function frequencyMap(arr) {
  const freq = new Map();
  for (const item of arr) {
    freq.set(item, (freq.get(item) || 0) + 1);
  }
  return freq;
}

function mostFrequent(arr) {
  const freq = frequencyMap(arr);
  let maxCount = 0, result = null;
  for (const [key, count] of freq) {
    if (count > maxCount) { maxCount = count; result = key; }
  }
  return result;
}

# Python
from collections import Counter

def frequency_map(arr):
    freq = {}
    for item in arr:
        freq[item] = freq.get(item, 0) + 1
    return freq

def most_frequent(arr):
    return Counter(arr).most_common(1)[0][0]

output

most_frequent([1,2,2,3,3,3]) → 3

Note Time O(n), Space O(k) where k is unique elements. Python's Counter is a powerful shortcut. In interviews, building the map manually shows understanding. Tie-breaking: clarify with interviewer what to return if multiple elements share max frequency.

frequency countcharacter countmost common elementcounterhash map

Two Sum Pattern (Hash Map)

syntax

For each element, check if (target - element) exists in the map.
Single pass: check then insert.

example

// JavaScript
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 [];
}

# Python
def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

output

two_sum([2, 7, 11, 15], 9) → [0, 1]

Note Time O(n), Space O(n). The classic interview opener. Single-pass approach works because we only need one pair. Edge cases: duplicate values, negative numbers, target is double of an element. For three-sum, sort + two pointers is preferred over triple hash map lookups.

two sumhash map paircomplement searchtarget sum

Group Anagrams

syntax

Use sorted string (or character frequency tuple) as hash map key.
All anagrams produce the same key.

example

// JavaScript
function groupAnagrams(words) {
  const groups = new Map();
  for (const word of words) {
    const key = word.split('').sort().join('');
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(word);
  }
  return Array.from(groups.values());
}

# Python
def group_anagrams(words):
    groups = {}
    for word in words:
        key = ''.join(sorted(word))
        groups.setdefault(key, []).append(word)
    return list(groups.values())

output

group_anagrams(['eat','tea','tan','ate','nat','bat'])
→ [['eat','tea','ate'], ['tan','nat'], ['bat']]

Note Sorting key: O(n * k log k) where k is max word length. Frequency key alternative: O(n * k) but more code. Interviewers may ask for the optimal approach — mention the frequency-tuple key to avoid k log k sorting per word.

group anagramsanagram groupinghash map groupingsorted key

Subarray Sum Equals K

syntax

Use prefix sum + hash map.
At each index, check if (currentPrefix - k) was seen before.
Store prefix sum frequencies in the map.

example

// JavaScript
function subarraySum(nums, k) {
  const prefixCount = new Map([[0, 1]]);
  let prefix = 0, count = 0;
  for (const num of nums) {
    prefix += num;
    if (prefixCount.has(prefix - k)) {
      count += prefixCount.get(prefix - k);
    }
    prefixCount.set(prefix, (prefixCount.get(prefix) || 0) + 1);
  }
  return count;
}

# Python
def subarray_sum(nums, k):
    prefix_count = {0: 1}
    prefix = 0
    count = 0
    for num in nums:
        prefix += num
        count += prefix_count.get(prefix - k, 0)
        prefix_count[prefix] = prefix_count.get(prefix, 0) + 1
    return count

output

subarray_sum([1,1,1], 2) → 2
subarray_sum([1,2,3], 3) → 2 (subarrays [1,2] and [3])

Note Time O(n), Space O(n). Initialize map with {0: 1} to handle subarrays starting at index 0. This pattern is reusable: subarray sum divisible by k, subarray with equal 0s and 1s. One of the most asked medium-level problems.

subarray sumprefix sum hash mapsubarray sum equals kcontiguous sum

Intersection of Collections

syntax

Convert one collection to a set, iterate the other and check membership.
For sorted arrays: use two pointers instead.

example

// JavaScript
function intersection(arr1, arr2) {
  const set1 = new Set(arr1);
  const result = [];
  const seen = new Set();
  for (const val of arr2) {
    if (set1.has(val) && !seen.has(val)) {
      result.push(val);
      seen.add(val);
    }
  }
  return result;
}

# Python
def intersection(arr1, arr2):
    return list(set(arr1) & set(arr2))

# With duplicates preserved:
def intersect_with_dupes(arr1, arr2):
    from collections import Counter
    c1, c2 = Counter(arr1), Counter(arr2)
    return list((c1 & c2).elements())

output

intersection([1,2,2,1], [2,2]) → [2]
intersect_with_dupes([1,2,2,1], [2,2]) → [2, 2]

Note Set approach: O(n + m) time, O(min(n,m)) space. Sorted two-pointer approach: O(n log n + m log m) time, O(1) extra space. Ask the interviewer: unique results or preserve duplicates? Are inputs sorted?

set intersectionarray intersectioncommon elementshash set

LRU Cache Concept

syntax

Least Recently Used cache: evict the oldest unused entry when at capacity.
Implement with: Hash Map + Doubly Linked List
- Map: key → node (O(1) lookup)
- DLL: maintains access order (O(1) move/remove)

example

// JavaScript — Simplified using Map (preserves insertion order)
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }
  get(key) {
    if (!this.cache.has(key)) return -1;
    const val = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, val); // move to end (most recent)
    return val;
  }
  put(key, value) {
    this.cache.delete(key);
    this.cache.set(key, value);
    if (this.cache.size > this.capacity) {
      const oldest = this.cache.keys().next().value;
      this.cache.delete(oldest);
    }
  }
}

# Python — Using OrderedDict
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    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)

output

cache = LRUCache(2)
cache.put(1, 1); cache.put(2, 2)
cache.get(1) → 1
cache.put(3, 3) → evicts key 2
cache.get(2) → -1

Note Both get and put must be O(1). In a real interview, they may want the DLL implementation from scratch — practice building a Node class with prev/next pointers. This is one of the most commonly asked design questions at top companies.

LRU cacheleast recently usedcache designhash map linked listordered dict