Grokking Algorithms - Deepstash

# Andrei Hodoroaga's Key Ideas from Grokking Algorithmsby Aditya Bhargava

Ideas, facts & insights covering these topics:

3 ideas

·

8

Explore the World's Best Ideas

Join today and uncover 100+ curated journeys from 50+ topics. Unlock access to our mobile app with extensive features.

## Hash Tables Under The Hood

In a slightly simplified explanation, hash tables are just arrays that with the keys mapped to the indexes. A key is transformed in an index through a hash function.

A good hash function must be:

• consistent: it should always produce the same output for the same key
• collision-free: it should minimize the number of keys that are mapped to the same number

In case the hash function still causes collisions (e.g. for memory reasons), it could be changed so that an entry in the array no longer contains a single value, but a new data structure (such as a linked list or even a new hash table).

28

## On Graph Algorithms

Breadth-first search is used to find the shortest path in an unweighted graph.

Dijkstra’s Algorithm is used to find the shortest path in a directed, acyclic graph (DAG).

The topological sort of a directed graph is the set of nodes ordered such that if u->v is an edge, then u comes before v in the sorting.

31

## NP-completeness

There’s no easy way to tell if a problem is NP-complete. Here are some giveaways:

• Your algorithm runs quickly with a handful of items but really slows down with more items.
• “All combinations of X” usually point to an NP-complete problem.
• Do you have to calculate “every possible version” of X because you can’t break it down into smaller sub-problems? Might be NP-complete.
• Can you restate your problem as the set-covering problem or the traveling-salesperson problem? Then your problem is definitely NP-complete.

28

IDEAS CURATED BY

CURATOR'S NOTE

The book covers algorithms at a basic level. I knew most of the stuff, so here are only so brief notes I took.

## Discover Key Ideas from Books on Similar Topics

9 ideas

The Programmer's Brain

Felienne Hermans

20 ideas

Clean Code

Robert C. Martin

10 ideas

20x Faster

without
deepstash

with
deepstash

with

deepstash

Personalized microlearning

100+ Learning Journeys

Unlimited idea saving

Unlimited history

Unlimited listening to ideas