Datastructures where Add, Get kth largest are O(log n) and O(1)

Question

Give a data structure that stores comparable objects and supports add() and get(k) operations [get(k) returns the kth smallest element in the data structure (1 <= k <= n)]. get(k) must be O(1) and add() must be O(log n) where n is the number of objects added to the data structure. Give another structure where get(k) is O(log n) and add is O(1)

Answer 1

If I got this interview question I would respond by saying that I am unaware of any such data structures, and suspect that they don't exist. However I suspect that the data structures that the interviewer is thinking of are "sorted array" and "skip list" respectively.

I would then explain that retrieving any element of an array by position is O(1). Figuring out where to insert it is O(log(n)). However the actual insertion is O(n) due to having to move the rest of the array. However the O(n) piece comes with very good constants.

For the skip list, retrieving is O(log(n)). Inserting involves half of the time only modifying one element, 1/4 of the time editing 2, 1/8 of the time editing 3 and so on, which is an average of 2 elements. That's O(1). However you cannot insert an element without figuring where to put it. And that lookup is O(log(n)). (To make the insert truly O(1) you either need to collect O(log(n)) data on the lookup that you make available to the insert, or you need to create the moral equivalent of a doubly linked skip list.)

Answer 2

There's no way to build a deterministic comparison-based data structure with amortized O(1)-time adds and worst-case O(log n)-time gets. The other configuration cannot be ruled out by an information-theoretic lower bound, but I seriously doubt that anyone knows how to do it.

For the experts: the adversary first adds n items, answering the algorithm's O(n) comparisons in such a way as to leave an antichain of size at least log² n. It then chooses k in such a way that computing get(k) forces the algorithm to do selection on the antichain, incurring a cost of Ω(log² n).

Why can the adversary force such a large antichain? Suppose that the algorithm always left no antichain of more than log² n elements. By Dilworth's theorem, the elements can be partitioned into at most log² n chains, which can be merged using O(n log log n) comparisons, giving a sorting algorithm that uses o(n log n) comparisons and thus a contradiction.

What could your interviewer have meant? It's conceivable to me that if both operations are amortized, then there's a solution. This is a non-canonical relaxation of the requirements, however.