class MapSum {
public:
/** Initialize your data structure here. */
void insert(string key, int val) {
mp[key] = val;
}
int sum(string prefix) {
int sum = 0, n = prefix.size();
for (auto it = mp.lower_bound(prefix); it != mp.end() && it>first.substr(0, n) == prefix; it++)
sum += it>second;
return sum;
}
private:
map<string, int> mp;
};
C++, Easy solution, ordered map



@zestypanda Hard to say for sure without knowing the nature of the input data and overhead caused by suboptimal implementations. But yeah, interviewers are probably looking for a 'trie' answer here.

@zestypanda Using unordered_map ran faster for me (i.e. only 3ms). It depends on the data of course. unordered_set insertions are faster always. Lookups are mixed. Overall I think unordered_set might be better.

@algorithmic It is a tradeoff. For unordered_map, sum is O(n), insert is O(1); For map, insert is O(logn), sum is O(logn+k), k is total valid words.
In summary, the worst case for unordered_map is O(n), for map is O(log n). So in real world and interviews, map is better. But Trie is best.

@rizkaz said in C++, Easy solution, ordered map:
trie
One can break out of map much early. Map keys are sorted, so if we find prefix once, we can break out if map key does not have prefix.