Amazon Interview Question: Bar raiser Given a NumberPool... | Glassdoor

Interview Question

Software Development Engineer I Interview Seattle, WA

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.
Answer

Interview Answer

1 Answer

1

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)).

Interview Candidate on May 24, 2011

Add Answers or Comments

To comment on this, Sign In or Sign Up.