I had a similar interview question at Booking.com once. You can solve it in linear time with some extra space (worst case - linear) for two constant-time lookup structures.