Please enable JavaScript.

Coggle requires JavaScript to display documents.

Grokking algorithms 2 (Chapter 5: Hash Tables (hash functions (A hash…

- - - - • Your hash function is really important. Your hash function mapped all the keys to a single slot. Ideally, your hash function would map keys evenly all over the hash.
      - • If those linked lists get long, it slows down your hash table a lot. But they won’t get long if you use a good hash function!
  - - - • A low load factor
        
        The load factor of a hash table
        is easy to calculate.:
        
        A good rule of thumb is, resize when your load factor is greater than 0.7.
      - • A good hash function
        
        A good hash function distributes values in the array evenly. and
        
        A bad hash function groups values together and produces a lot of
        collisions.
        
        If you’re really curious, look up the SHA function (there’s a short description of it in the last chapter). You could use that as your hash function.
- - - - If you’re before him in the queue, you get on the bus first
      - The queue is called a FIFO data structure
      - a stack is a LIFO data structure
  - - - O(V+E)
        (V for number of nodes, E for number of edges).
- - - - Pick the station that covers the most states that haven’t been covered yet. It’s OK if the station covers some states that have been covered already.
      - Repeat until all the states are covered.
  - - - But if you want to find the shortest path that connects several points, that’s the traveling-salesperson problem, which is NP-complete
    - - Jonah can use the same approximation algorithm to create his team:
        
        Find the player who fulfills the most abilities that haven’t been
        fulfilled yet.
        
        Repeat until the team fulfills all abilities (or you run out of space
        on the team).
    - - • 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.
      - • If your problem involves a sequence (such as a sequence of cities, like traveling salesperson), and it’s hard to solve, it might be NP-complete.
      - • If your problem involves a set (like a set of radio stations) and it’s hard to solve, it 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.