Pergunta de entrevista da empresa Amazon
Bar raiser Given a NumberPool containing number sequence of numbers from 1 to infinity. Implement an interface, essentially two functions- checkin(N): which adds number to the number pool and makes it available. checkout(): returns minimum number from the pool and makes it unavailable.
Resposta da entrevista
Sigiloso
24 de mai. de 2011
Gave 4 implementations using ArrayList (checkin: O(N), checkout: O(N lg N)), Binary Search Tree (checkin: O(lg N) + balancing cost, checkout: O(lg N)), Binary Heap (checkin: O(lg N) + heapify cost, checkout: O(1) + heapify cost) and Hash table (checkin: O(1), checkout: O(N)).
1