Hash Tables

Given two strings ransomNote and magazine, return true if ransomNote can be constructed using the letters of magazine, where each letter in magazine may be used at most once.

Design a RandomizedSet class that supports the following operations in average O(1) time: insert(val) (adds val, returns false if it was already present), remove(val) (removes val, returns false if it wasn't present), and getRandom() (returns a uniformly random current element). The trick: combine a Map<number, index> with a number[] — on remove, swap the target with the last element and pop, so the array stays compact.

Design a TimeMap class that supports two operations:

• set(key, value, timestamp) — stores key -> value at timestamp. All timestamps for a given key are strictly increasing.
• get(key, timestamp) — returns the value set for key at the largest timestamp_prev <= timestamp, or "" if none exists.

Use a per-key sorted list of (timestamp, value) and binary-search inside get.

Calculate the dot product of two sparse vectors, which are vectors where most elements are zero, by efficiently identifying and multiplying non-zero elements.