Hash Maps and Key Values

In this section, we cover the use of hash maps and hash tables. A hash table/map is a data structure that maps keys to values using a hash function to compute an index of buckets.

It gets an entire section for itself given how commonly you'll use them in real-world solutions. We also start introducing you to a powerful technique, dynamic programming, which can be used to solve some of the more challenging interview questions.

Section Menu

How do I use this section?

1. LESSON

Implement an LFU Cache

In this tutorial, we'll discuss implementing an LFU (Least Frequently Used) cache. Here's what we'll cover: What is an LFU Cache? A brief overview of how an LFU cache works and why it's useful. How is it Different from LRU Cache? We'll explain the difference between LFU and LRU caching strategies. Required Operations The key ope...

2. LESSON

Feature: Solving the Target Sum problem with dynamic programming and more

This lesson was originally featured at Solving the Target Sum problem with dynamic programming and more. It has been republished here with permission from Fabian Terh. Previously, I wrote about [solving the 0--1 Knapsack Problem using dynami...

3. CHALLENGE

Single Lonely Number

In a given array of numbers, one element will show up once and the others will each show up twice. Can you find the number that only appears once in O(n) linear time? Bonus points if you can do it in O(1) space as well. <img src="https://storage.googleapis.com/algodailyrandomassets/curriculum/arrays/lonely-number.png?bust=1" c...

4. CHALLENGE

Implement a Hash Map

Arrays are amazing for looking up elements at specific indices as all elements in memory are contiguous, allowing for O(1) or constant time lookups. But often we don't, or can't, perform lookups via indices. Hash maps and hash tables are a way around this, enabling us to lookup via keys instead. Can you implement the Map cl...

5. CHALLENGE

Targets and Vicinities

You're playing a game with a friend called Target and Vicinity. Target and Vicinity consists of one person thinking up a number in their head, and the other guessing that number. Sounds simple enough-- the caveat is that we also want to credit close guesses. To estimate the proximity of the guess to the actual number, we u...

6. CHALLENGE

Design A Least Recently Used (LRU) Cache

A cache (pronounced cash) is a place of storage that allows for faster data retrieval. Separate from the main data storage, it's usually faster memory that houses frequently accessed values. With a cache in place, when a client application needs to access data, it'll check the cache first before going to main memory. As an e...

7. CHALLENGE

N Most Frequent Elements

Consider that you are given an integer array nums and an integer n. Find the n most frequent elements in the nums array. If two numbers have the same frequency, then the number with a larger value should be given preference. ![image](https://storage.googleapis.com/algodailyrandomassets/curriculum/medium-arrays/N%20Most%20...