A good interview question

Today I want to share this question that from leetcode about design hashmap. It is about to design a hashmap without using the standard library.

I think it is a good question since it drives discussion pretty quickly as most developers are familiar with this data structure. You can discuss on hash function first. Then on the implementation side, especially with cpp, you can do it with old looping way, or using std::find_if function and iterator correctly, test on the ability to initialize variable correctly, etc. For example, when I write the code below, I try to push a little on some modern cpp concept my previous team mates always try to stand up with.

class MyHashMap {
public:
    const int MAP_SIZE = 2096;
    vector<list<pair<int, int>>> _table;
    MyHashMap() : _table((list<pair<int, int>>(), MAP_SIZE)) {
    }
    
    void put(int key, int value) {
        int pos = key % MAP_SIZE;
        auto it = std::find_if(_table[pos].begin(), _table[pos].end(), [key](const pair<int, int>& p){
            return p.first == key;
        });
        if (it != _table[pos].end()) it->second = value;
        else _table[pos].emplace_back(key, value);
    }
    
    int get(int key) {
        int pos = key % MAP_SIZE;
        auto it = std::find_if(_table[pos].begin(), _table[pos].end(), [key](const pair<int, int>& p) {
            return p.first == key;
        });
        if(it != _table[pos].end()) return it->second;
        return -1;
    }
    
    void remove(int key) {
        int pos = key % MAP_SIZE;
        auto it = std::find_if(_table[pos].begin(), _table[pos].end(), [key](const pair<int, int>& p) {
            return p.first == key;
        });
        if(it != _table[pos].end()) _table[pos].remove(*it);
    }
};

Some points that I want to emphasize on:

• Use of link list is not quite offen in daily job. It is more efficient for insert and removal comparing to vector.
• You cannot initlize the _table as it is non-static at declaration stage, And you cannot change the constructor as requirement, then you have to use initlization list, which has some discussion points.
• using function find_if to make code more clear and clean.

Hope you guys can try it yourself. Keep learning everyday!