30 Foundational Hash Table Problems

A Roadmap to Mastering Hash Tables

Oct 03, 2024

Hash tables are one of the most fundamental and powerful data structures in computer science. They provide efficient insertion, deletion, and lookup operations, typically in constant time, making them invaluable for solving a wide array of problems. This is why hash tables are part of most coding interview problems.

In this guide, I've curated 30 foundational hash table problems specifically designed for beginners. These problems will help you understand how to effectively use hash tables to solve problems efficiently. The problems start with very basic concepts and gradually increase in difficulty, helping you build your skills incrementally.

How to Approach This List

Start from the Beginning: The problems are ordered from easiest to more challenging.
Think About the Approach: Try to devise a solution on your own before seeking hints.
Prioritize Hash Tables: Some of the problems can be solved without hash tables. Always try to find a solution involving hash tables.

The Problems

1. Word Counting

Problem Statement: Given a list of words, count how many times each word appears.

Sample Input:

words = ["apple", "banana", "apple", "orange", "banana", "apple"]

Sample Output:

{ "apple": 3, "banana": 2, "orange": 1 }

2. Character Frequency

Problem Statement: Given a string s, count the frequency of each character in the string.

Sample Input:

s = "hello world"

Sample Output:

{ "h": 1, "e": 1, "l": 3, "o": 2, " ": 1, "w": 1, "r": 1, "d": 1 }

3. Remove Duplicates from List

Problem Statement: Given a list of integers, remove duplicates in-place.

Sample Input:

nums = [1, 2, 2, 3, 4, 4, 5]

Sample Output:

[1, 2, 3, 4, 5]

4. Character Position Mapping

Problem Statement: Given a string s, create a dictionary mapping each character to a list of positions where it appears in the string.

Sample Input:

s = "hello"

Sample Output:

{ "h": [0], "e": [1], "l": [2, 3], "o": [4] }

5. Find Duplicates

Problem Statement: Given a list of integers, find all elements that appear more than once.

Sample Input:

nums = [1, 2, 3, 2, 4, 5, 5]

Sample Output:

[2, 5]

6. Character Mapping Between Strings

Problem Statement: Given two strings of equal length, create a mapping from characters in the first string to characters in the second string.

Sample Input:

s1 = "abc", s2 = "def"

Sample Output:

{ "a": "d", "b": "e", "c": "f" }

7. Common Elements

Problem Statement: Given two lists, find the common elements between them.

Sample Input:

list1 = [1, 2, 3, 4], list2 = [3, 4, 5, 6]

Sample Output:

[3, 4]

8. Find Missing Number

Problem Statement: Given a list of integers from 1 to N with one number missing, find the missing number.

Sample Input:

nums = [1, 2, 4, 5], N = 5

Sample Output:

9. Find Extra Element

Problem Statement: Given two lists where the second list is the first list with one extra element, find the extra element.

Sample Input:

list1 = [10, 20, 30, 40] list2 = [10, 20, 30, 40, 50]

Sample Output:

10. Group Words by Length

Problem Statement: Given a list of words, group them by their length.

Sample Input:

words = ["cat", "dog", "elephant", "tiger", "lion"]

Sample Output:

{ 3: ["cat", "dog"], 5: ["tiger", "lion"], 8: ["elephant"] }

11. Maximum Number of Occurrences

Problem Statement: Given a list of integers, find the number that appears the most times.

Sample Input:

nums = [1, 3, 2, 1, 4, 1]

Sample Output:

12. Sum of Pairs

Problem Statement: Given a list of integers and a target sum, find all pairs of numbers that add up to the target sum.

Sample Input:

nums = [2, 4, 3, 5, 7], target = 7

Sample Output:

[[2, 5], [4, 3]]

13. Find Repeated DNA Sequences

Problem Statement: Given a string s that represents a DNA sequence, find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

Sample Input:

s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

Sample Output:

["AAAAACCCCC", "CCCCCAAAAA"]

14. Check Anagrams

Problem Statement: Given two strings, determine if they are anagrams of each other (contain the same letters in any order).

Sample Input:

str1 = "listen", str2 = "silent"

Sample Output:

True

15. Find Common Elements in Three Lists

Problem Statement: Given three lists of integers, find the common elements that appear in all three lists.

Sample Input:

list1 = [1, 2, 3, 4, 5] list2 = [3, 4, 5, 6, 7] list3 = [5, 6, 7, 8, 9]

Sample Output:

[5]

16. Word Occurrences in Sentence

Problem Statement: Given a sentence, count how many times each word appears.

Sample Input:

sentence = "the quick brown fox jumps over the lazy dog"

Sample Output:

{ "the": 2, "quick": 1, "brown": 1, "fox": 1, "jumps": 1, "over": 1, "lazy": 1, "dog": 1 }

17. First Non-Repeating Character

Problem Statement: Given a string, find the first character that does not repeat.

Sample Input:

s = "swiss"

Sample Output:

"w"

18. Group Emails by Domain

Problem Statement: Given a list of email addresses, group them by their domain names.

Sample Input:

emails = ["alice@example.com", "bob@test.com", "charlie@example.com"]

Sample Output:

{ "example.com": ["alice@example.com", "charlie@example.com"], "test.com": ["bob@test.com"] }

19. Second Most Frequent Element

Problem Statement: Given a list of elements, find the element with the second highest frequency.

Sample Input:

nums = [1, 2, 2, 3, 3, 3, 4]

Sample Output:

2 # Since '3' appears 3 times and '2' appears 2 times

20. Find Pairs with Given Difference

Problem Statement: Given a list of integers and a number k, find all pairs of numbers where the difference between the two numbers is k.

Sample Input:

nums = [1, 5, 3, 4, 2], k = 2

Sample Output:

[[1, 3], [3, 5], [2, 4]]

21. Frequency of Sums

Problem Statement: Given two lists of integers, compute the frequency of sums that can be formed by adding an element from the first list to an element from the second list.

Sample Input:

list1 = [1, 2], list2 = [3, 4]

Sample Output:

{
  4: 1, # 1+3
  5: 2, # 1+4, 2+3
  6: 1 # 2+4
}

22. Check if Two Strings are Isomorphic

Problem Statement: Given two strings, determine if they are isomorphic (there is a one-to-one mapping between every character of the first string to every character of the second string).

Sample Input:

s1 = "paper", s2 = "title"

Sample Output:

True

23. Common Characters in Strings

Problem Statement: Given a list of strings, find all characters that appear in all strings.

Sample Input:

strings = ["cool", "lock", "cook"]

Sample Output:

["c", "o"]

24. Rearrange String Based on Character Frequency

Problem Statement: Given a string s, rearrange it so that the same characters are at least distance d apart. If it's not possible, return an empty string.

Sample Input:

s = "aaabc", d = 2

Sample Output:

"abaca"

25. Group Anagrams Together

Problem Statement: Given a list of words, group the words that are anagrams of each other.

Sample Input:

words = ["listen", "silent", "enlist", "hello", "ohell"]

Sample Output:

[ ["listen", "silent", "enlist"], ["hello", "ohell"] ]

26. Longest Substring Without Repeating Characters

Problem Statement: Given a string, find the length of the longest substring without repeating characters.

Sample Input:

s = "abcabcbb"

Sample Output:

3 # The longest substring is "abc"

27. Subarray Sum Equals Target

Problem Statement: Given a list of integers and a target sum, find the number of continuous subarrays that sum up to the target.

Sample Input:

nums = [1, 1, 1], target = 2

Sample Output:

28. Top K Frequent Elements

Problem Statement: Given a list of integers, return the k most frequent elements.

Sample Input:

nums = [1, 1, 1, 2, 2, 3], k = 2

Sample Output:

[1, 2]

29. Find All Anagrams in a String

Problem Statement: Given a string s and a pattern p, find all the start indices of p's anagrams in s.

Sample Input:

s = "cbaebabacd", p = "abc"

Sample Output:

[0, 6]

30. Smallest Window in a String Containing All Characters of Another String

Problem Statement: Given two strings s and t, find the minimum window in s which will contain all the characters in t.

Sample Input:

s = "ADOBECODEBANC", t = "ABC"

Sample Output:

"BANC"

Need Help with Coding Interviews?

Are you struggling with coding problems or feeling unprepared for your upcoming interviews? You're not alone, and I'm here to help.

With years of experience as a coding interview coach, I offer personalized one-on-one sessions to:

Master problem-solving skills for coding and system design interviews
Boost your confidence for the big day
Develop effective strategies to level up your tech career

Ready to elevate your coding interview skills? Book a personalized 1:1 coaching session with me today!

Still have questions? Let's chat! You can book a free 30-minute consultation to discuss how I can help you achieve your goals.

Feel free to email me at nurbo.kusmagul@(google’s email service) or connect with me on LinkedIn.

Looking forward to helping you succeed!

Stay curious and happy coding!

Nurbo

Faangshui - Algorithms, Data Structures & Coding Interviews

Discussion about this post