Section Menu

How do I use this section?

1. 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...

Difficulty: 3/10 Mark Completed

2. 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...

Difficulty: 3/10 Mark Completed

3. 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...

Difficulty: 6/10 Mark Completed

4. 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...

Difficulty: 7/10 Mark Completed

Cheat Sheet

• Quick summary: unordered collection that maps keys to values using hashing.
• Also known as: hash, hash map, map, unordered map, dictionary, associative array.
• Important facts:
  • Stores data as key-value pairs.
  • Can be seen as an evolution of arrays that removes the limitation of sequential numerical indices and allows using flexible keys instead.
  • For any given non-numeric key, hashing helps get a numeric index to look up in the underlying array.
  • If hashing two or more keys returns the same value, this is called a hash collision. To mitigate this, instead of storing actual values, the underlying array may hold references to linked lists that, in turn, contain all values with the same hash.
  • A set is a variation of a hash table that stores keys but not values.
• Pros:
  • Keys can be of many data types. The only requirement is that these data types are hashable.
  • Average search, insertion and deletion are O(1).
• Cons:
  • Worst-case lookups are O(n).
  • No ordering means looking up minimum and maximum values is expensive.
  • Looking up the value for a given key can be done in constant time, but looking up the keys for a given value is O(n).
• Notable uses:
  • Caching.
  • Database partitioning.
• Time complexity (worst case):
  • Access: O(n)
  • Search: O(n)
  • Insertion: O(n)
  • Deletion: O(n)
• See also:
  • Interview Problems: Hash Maps