I used LinkedHashSet alone to address this problem, which guarantees O(1) get operation. For HashSet, retrieving the first element is slow because the internal hash table array is filled with hashed values, and some of the slots are still empty, to find an non empty slot containing an element, you have to iterate the array slots to find an element. This could be slow if the array is very sparse.

However, for LinkedHashSet, internally, it has a linked list to chain all existing elements, so that retrieving the first element is guaranteed to be an O(1) operation because it will iterate using the linked list instead of the hash table array. 20% faster compared to using HashSet as the Set implementation in the program in my submissions.

At the same time, instead of using a for loop and break from it, I used Iterator to retrieve the first element, I don't do any detailed comparison, but the HashSet implementation can get AC too in my submission.

class PhoneDirectory { private Set<Integer> numbers; /** Initialize your data structure here @param maxNumbers - The maximum numbers that can be stored in the phone directory. */ public PhoneDirectory(int maxNumbers) { numbers = new LinkedHashSet<>(); for (int i = 0; i < maxNumbers; i++) { numbers.add(i); } } /** Provide a number which is not assigned to anyone. @return - Return an available number. Return -1 if none is available. */ public int get() { if (!numbers.isEmpty()) { Iterator<Integer> iter = numbers.iterator(); int number = iter.next(); iter.remove(); return number; } else { return -1; } } /** Check if a number is available or not. */ public boolean check(int number) { return numbers.contains(number); } /** Recycle or release a number. */ public void release(int number) { numbers.add(number); } }