Kalanand's July 2014 Log

July 21st

Simple hash table example

• Hash table: an array of 128 elements (key-value pairs). Key is stored to distinguish between key-value pairs with the same hash.
• Hash function: remainder of division by 128.
• Collisions resolved using linear probing

struct Hash {
      int key;
      int value;

      Hash(int k, int v) { key = k; value = v; }
      int getKey() { return key; }
      int getValue() { return value; }
};


//Hash Map class implementation 
const int TABLE_SIZE = 128;

class HashMap {
private:
      Hash **table;

public:
      HashMap() {  
            table = new Hash*[TABLE_SIZE];
            for (int i = 0; i < TABLE_SIZE; ++i) {
                  table[i] = NULL;
             }
      }

      int get(int key) {
           int hash = (key % TABLE_SIZE);

            while (table[hash] != NULL && table[hash]->getKey() != key) {
                  hash = (hash + 1) % TABLE_SIZE;
            }
            if (table[hash] == NULL) return -1;
            return table[hash]->getValue();
      }

 
      void put(int key, int value) {
            int hash = (key % TABLE_SIZE);

            while (table[hash] != NULL && table[hash]->getKey() != key) {
                  hash = (hash + 1) % TABLE_SIZE;
             }

            if (table[hash] != NULL) delete table[hash];
            table[hash] = new Hash(key, value);
      }     

 
      ~HashMap() {
            for (int i = 0; i < TABLE_SIZE; ++i) {
                  if (table[i] != NULL) delete table[i]; 
             }
            delete[] table;
      }
};

July 24th

Number of distinct ways to climb stairs in 1 or 2 steps at a time is a Fibonacci sequence!!!

Turns out the answer is simple but it takes a while to recognize the pattern. Let N_k be the number of ways to climb k stairs taking only 1 or 2 steps. We know that N₁ = 1 and N₂ = 2. Now, consider N_k for k ≥ 3. The first step will be of size 1 or 2. In the first case there are N_k−1 ways to finish. In the second case there areN_k−2 ways to finish. Thus

N_k = N_k−1 + N_k−2

This is Fibonacci sequence!

Generalization

Go to June's log