Design Phone Directory - Practice Coding Problems

Design Phone Directory - Problem

Design a phone directory that initially has maxNumbers empty slots that can store numbers. The directory should support storing numbers, checking if a certain slot is empty, and emptying a given slot.

Implement the PhoneDirectory class:

PhoneDirectory(int maxNumbers) - Initializes the phone directory with the number of available slots maxNumbers
int get() - Provides a number that is not assigned to anyone. Returns -1 if no number is available
bool check(int number) - Returns true if the slot number is available and false otherwise
void release(int number) - Recycles or releases the slot number

All operations should be performed efficiently to handle multiple queries.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["PhoneDirectory", "get", "check", "get", "check", "release", "check"], parameters = [[3], [], [2], [], [2], [2], [2]]

› Output: [null, 0, true, 1, false, null, true]

💡 Note: Initialize directory with 3 slots. get() returns 0 (first available). check(2) returns true (slot 2 available). get() returns 1. check(2) returns false (still available). release(2) has no effect. check(2) returns true.

Example 2 — Full Directory

$ Input: operations = ["PhoneDirectory", "get", "get", "get"], parameters = [[2], [], [], []]

› Output: [null, 0, 1, -1]

💡 Note: Directory with 2 slots. First get() returns 0, second returns 1, third returns -1 (no slots available).

Example 3 — Release and Reuse

$ Input: operations = ["PhoneDirectory", "get", "get", "release", "get"], parameters = [[2], [], [], [0], []]

› Output: [null, 0, 1, null, 0]

💡 Note: Get slots 0 and 1, release slot 0, then get() returns the released slot 0.

Constraints

1 ≤ maxNumbers ≤ 10⁴
0 ≤ number < maxNumbers
At most 2 × 10⁴ calls will be made to get, check, and release

Visualization

Tap to expand

Understanding the Visualization

Initialize

Create directory with maxNumbers available slots

Operations

get(), check(), release() operations on slots

Result

Efficient slot management with O(1) operations

Key Takeaway

🎯 Key Insight: Use a queue to store available slot numbers for O(1) get operations while maintaining a boolean array for quick status checks

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to maintain available slots in a separate data structure for efficient access. The queue-based approach provides O(1) time complexity for all operations by storing available slot numbers in a queue and using a boolean array for status checking. Time: O(1), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Queue-Based Approach	O(1)	O(n)	Use queue to store available slots for O(1) get operation
Linear Search Approach	O(n)	O(n)	Use boolean array and search linearly for available slots

Queue-Based Approach — Algorithm Steps

Step 1: Initialize queue with all slot numbers (0 to maxNumbers-1)
Step 2: For get(), pop from queue front and mark as used
Step 3: For check(), query boolean array directly
Step 4: For release(), mark as available and add back to queue

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Queue contains all available slot numbers

Get Operation

Pop front of queue for instant slot access

Result

Return slot number in O(1) time

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct {
    bool* available;
    int* queue;
    int front;
    int rear;
    int size;
    int maxNumbers;
} PhoneDirectory;

PhoneDirectory* phoneDirectoryCreate(int maxNumbers) {
    PhoneDirectory* obj = (PhoneDirectory*)malloc(sizeof(PhoneDirectory));
    obj->available = (bool*)malloc(maxNumbers * sizeof(bool));
    obj->queue = (int*)malloc(maxNumbers * sizeof(int));
    obj->front = 0;
    obj->rear = maxNumbers - 1;
    obj->size = maxNumbers;
    obj->maxNumbers = maxNumbers;
    
    for (int i = 0; i < maxNumbers; i++) {
        obj->available[i] = true;
        obj->queue[i] = i;
    }
    
    return obj;
}

int phoneDirectoryGet(PhoneDirectory* obj) {
    if (obj->size > 0) {
        int num = obj->queue[obj->front];
        obj->front = (obj->front + 1) % obj->maxNumbers;
        obj->size--;
        obj->available[num] = false;
        return num;
    }
    return -1;
}

bool phoneDirectoryCheck(PhoneDirectory* obj, int number) {
    if (number >= 0 && number < obj->maxNumbers) {
        return obj->available[number];
    }
    return false;
}

void phoneDirectoryRelease(PhoneDirectory* obj, int number) {
    if (number >= 0 && number < obj->maxNumbers && !obj->available[number]) {
        obj->available[number] = true;
        obj->rear = (obj->rear + 1) % obj->maxNumbers;
        obj->queue[obj->rear] = number;
        obj->size++;
    }
}

int main() {
    printf("[null,0,true,false,1,true]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

All operations (get, check, release) are constant time

✓ Linear Growth

Space Complexity

O(n)

Queue stores available slots plus boolean array for status tracking

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~25 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Queue-Based Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler