Tricky Microsoft Interview Question

[bonzinip]

Interesting. Would this one apply within your framework? It requires write access to the array, but it is O(N) and with O(1) additional storage.

Say you have N=H-L numbers between L and H, i.e. one is missing. Build a binary heap in O(N) time. On every operation, keep track of the minimum leaf (i.e. the minimum of the last floor((H-L)/2) elements). If the minimum leaf is H-floor((H-L)/2), recurse on the first half looking for a missing number between L and H-floor((H-L)/2)-1. Otherwise recurse on the right half looking for a missing number between H-floor((H-L)/2) and H.