Skip to content
DSA hashing 11 min read

Hashing Exercises: Answer Sheet & Worked Solutions

This is the answer sheet for the hashing exercises. Each solution gives the key idea, the optimal complexity, the code in all four languages (use the switcher), and common pitfalls. Try the problems first — then check your work here.

Q1. Count frequencies

Idea: One pass over the array, incrementing a hash map keyed by value. A missing key starts at zero, so freq[x]++ just works.

Complexity: O(n) time, O(k) space for k distinct values.

#include <unordered_map>
#include <vector>

std::unordered_map<int,int> countFreq(const std::vector<int>& a) {
    std::unordered_map<int,int> freq;
    for (int x : a) freq[x]++;
    return freq;
}

Pitfall: In C++, freq[x]++ silently inserts x with value 0 first — fine here, but watch for accidental inserts when you only mean to read a key.

Q2. Contains duplicate

Idea: Walk once, adding each value to a hash set. The moment you meet a value already in the set, you have a duplicate.

Complexity: O(n) time, O(n) space.

#include <unordered_set>
#include <vector>

bool containsDuplicate(const std::vector<int>& a) {
    std::unordered_set<int> seen;
    for (int x : a) {
        if (seen.count(x)) return true;
        seen.insert(x);
    }
    return false;
}

Pitfall: Comparing len(set(a)) != len(a) also works but always scans the whole array; the early-exit loop stops at the first repeat.

Q3. Two Sum

Idea: For each element x, the value that completes the target is need = target - x. Keep a map of value → index of everything seen so far; if need is already there, you have the pair. One pass.

Complexity: O(n) time, O(n) space.

#include <unordered_map>
#include <vector>

std::vector<int> twoSum(const std::vector<int>& nums, int target) {
    std::unordered_map<int,int> seen;
    for (int i = 0; i < (int)nums.size(); i++) {
        int need = target - nums[i];
        if (seen.count(need)) return {seen[need], i};
        seen[nums[i]] = i;
    }
    return {};
}

Pitfall: Insert x after the complement check. Inserting first lets a single element pair with itself (e.g. target 6 with a lone 3).

Q4. Group anagrams

Idea: Anagrams share the same multiset of letters, so their sorted letters form an identical signature. Use that signature as a map key and append each word to its group.

Complexity: O(n · k log k) time for n words of length up to k; O(n · k) space.

#include <unordered_map>
#include <vector>
#include <string>
#include <algorithm>

std::vector<std::vector<std::string>> groupAnagrams(const std::vector<std::string>& words) {
    std::unordered_map<std::string, std::vector<std::string>> groups;
    for (const auto& w : words) {
        std::string key = w;
        std::sort(key.begin(), key.end());
        groups[key].push_back(w);
    }
    std::vector<std::vector<std::string>> out;
    for (auto& [k, v] : groups) out.push_back(v);
    return out;
}

Pitfall: A 26-letter count vector (e.g. "a2b1...") is a faster O(k) signature than sorting, but sorting is simpler to get right and plenty fast for interviews.

Q5. First non-repeating character

Idea: Two passes. First count every character’s frequency; then scan left to right and return the index of the first character whose count is 1.

Complexity: O(n) time, O(1) space (the alphabet is bounded).

#include <unordered_map>
#include <string>

int firstUniqChar(const std::string& s) {
    std::unordered_map<char,int> freq;
    for (char c : s) freq[c]++;
    for (int i = 0; i < (int)s.size(); i++)
        if (freq[s[i]] == 1) return i;
    return -1;
}

Pitfall: Returning the first key with count 1 from the map gives the wrong answer — map order is not string order. Scan the original string for the index.

Q6. Subarray sum equals K

Idea: Let prefix be the running sum up to index i. A subarray (j, i] sums to k exactly when prefix - k equaled some earlier prefix. Keep a map of prefixSum → how many times it occurred and, at each step, add the count of prefix - k. Seed the map with {0: 1} so subarrays starting at index 0 are counted.

Complexity: O(n) time, O(n) space.

#include <unordered_map>
#include <vector>

int subarraySum(const std::vector<int>& nums, int k) {
    std::unordered_map<int,int> count{{0, 1}};
    int prefix = 0, result = 0;
    for (int x : nums) {
        prefix += x;
        auto it = count.find(prefix - k);
        if (it != count.end()) result += it->second;
        count[prefix]++;
    }
    return result;
}

Pitfall: A sliding window does not work here because values can be negative. And you must read count[prefix - k] before incrementing count[prefix], or a zero-valued k would over-count.

Q7. Longest consecutive sequence

Idea: Put every value in a hash set for O(1) membership. A number starts a run only if x - 1 is not in the set; from each such start, walk x, x+1, x+2, … while they exist and measure the run. Each value is visited at most twice, so it is O(n) — no sorting.

Complexity: O(n) time, O(n) space.

#include <unordered_set>
#include <vector>
#include <algorithm>

int longestConsecutive(const std::vector<int>& nums) {
    std::unordered_set<int> s(nums.begin(), nums.end());
    int best = 0;
    for (int x : s) {
        if (s.count(x - 1)) continue;      // not a run start
        int len = 1, cur = x;
        while (s.count(cur + 1)) { cur++; len++; }
        best = std::max(best, len);
    }
    return best;
}

Pitfall: Without the if x - 1 in s guard you would re-walk every run from every member, making it O(n²). The guard ensures each run is counted exactly once, from its smallest element.

That’s the full answer sheet. Back to the hashing exercises or continue to recursion.

Last updated June 25, 2026
Was this helpful?