For an example of one of those not-easiest problems: create an array with "virtual initialization". That is, for an array of size n, accessing any uninitialized element e should return some default value v and set e to it in O(1) time. Make use of your free coefficients in your Big-O.