Design Phone Directory

Design Phone Directory is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Design Patterns pattern, in the Design (General/Specific) subpattern.

Problem statement

You are given an integer maxNumbers representing the total number of phone numbers in a directory, numbered from 0 to maxNumbers - 1. Design a system that manages the assignment and recycling of these phone numbers. Implement a class PhoneDirectory with the following methods:

- PhoneDirectory(int maxNumbers): Initializes the directory with maxNumbers available phone numbers. - int get(): Provides an available phone number and marks it as assigned. Returns the number if available; otherwise, returns -1 if none are available. - bool check(int number): Returns true if the given number is available; otherwise, returns false. - void release(int number): Recycles or releases the given number, making it available for assignment again if it was previously assigned.

You must ensure that each number is assigned to at most one user at a time, and that released numbers can be reassigned. Implement the class to efficiently support up to 2 10^4 calls to the above methods.

Topics and companies

Topics: Array, Hash Table, Linked List, Design, Queue.

Reported in interviews at Google.

How to practise Design Phone Directory on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(1) per operation (get, check, release). All operations use direct access or queue operations, which are O(1). time and O(N), where N is maxNumbers. We store a boolean vector of size N and a queue that can hold up to N numbers. space.

Open Design Phone Directory in the code editor, or read the Design Phone Directory editorial for a worked solution with its approach and complexity analysis.

Where Design Phone Directory sits in the DSA pattern sheet

Problems related to Design Phone Directory

Other problems that use the same Design (General/Specific) and Design Patterns techniques:

Preparing this workspace.