Arrays and Hashing

These are the data structures and techniques that appear in nearly every coding problem. For each one, the goal is to know what it does, what each operation costs, and why.

This course assumes some CS background, and is not intended as a substitute for general programming knowledge. It aims to be frugal with your time, acting as a crash course and refresher for fundamental data structures, and a repository you can look back on to remind yourself of the most immediately relevant details and intuitions for using them.

What it covers

• Arrays: fixed-size and dynamic (resizable) arrays, and the cost of indexing, appending, and resizing.
• Strings: how they are stored, why they are usually immutable, and character-frequency counting.
• Hash sets and hash maps: where average O(1) lookup comes from, and what collisions and resizing cost.
• Stacks, queues, and deques: LIFO and FIFO access, and the circular buffer behind a queue.
• Techniques: two pointers, sliding window, prefix sums, binary search, sorting, bit manipulation, and 2D grids.