Uncategorized

Steps to answer

  1. Listen carefully.
    • Pay very close attention to any information.
  2. Draw an example.
    1. Specific. Sufficiently large. Not a special case.
  3. State a brute force
    1. The initial solution may be terrible. Explain the space/time complexity.
  4. Optimize
    1. Look for any unused information
    2. Use a fresh example
    3. Solve it incorrectly.
    4. Make time vs. space tradeoff
    5. Precompute
    6. Use a hash table
    7. Think about the best conceivable runtime
    8. Walk through with Bottleneck, Unnecessary work and Duplicated work
  5. Implement
  6. Test

 

Techniques

  1. BUD
  2. DIY
  3. Simplify and generalize
  4. Base case and build
  5. Data structure brainstorm
  6. BCR

 

Uncategorized

Hash Table

That’s implemented as “map” class which we are really using for fast ‘key’/’value’ extraction.

We need a good hash function which evenly and randomly maps ‘key’ to an index.¬†And handling of collision is required in case that two separate keys are mapped to a single index. It can be done by such as separate chain (may be implemented as linked list) and open¬†addressing (linear probing, quadratic probing). Open addressing can cause clustering. (An index is visited repeatedly) Double hashing can avoid this issue. But a good (fast, even distribution) hash function is always needed.

Code below is a real implementation in android java, copied from Android/Sdk/sources/android-23/java/util/Collections.java.

private static int secondaryHash(int h) {
    // Spread bits to regularize both segment and index locations,
    // using variant of single-word Wang/Jenkins hash.
    h += (h <<  15) ^ 0xffffcd7d;
    h ^= (h >>> 10);
    h += (h <<   3);
    h ^= (h >>>  6);
    h += (h <<   2) + (h << 14);
    return h ^ (h >>> 16);
}

And collision is handled by a linked list of HashMapEntry.