Design Phone Directory

# System & Data Structure Design Design problems in DSA interviews test your ability to translate requirements into a functional, efficient, and maintainable class structure. Unlike standard algorithmic problems, the focus here is on **State Management** and **API Design**. ### Core Principles 1. **Encapsulation:** Keep data private and expose functionality through well-defined methods. 2. **Trade-offs:** Every design choice has a cost. Is it better to have $O(1)$ read and $O(N)$ write, or vice versa? 3. **State Consistency:** Ensure that your internal data structures (e.g., a Map and a List) stay in sync after every operation. ### Common Design Patterns #### 1. HashMap + Doubly Linked List (DLL) The "Gold Standard" for $O(1)$ caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - **HashMap:** Provides $O(1)$ lookups for keys to their corresponding nodes. - **DLL:** Provides $O(1)$ addition/removal of nodes at both ends, maintaining the order of access. #### 2. Amortized Analysis (Rebalancing) Commonly used in **Queue using Stacks** or **Dynamic Arrays**. - Instead of doing heavy work on every call, we batch it. Pushing to a stack is $O(1)$, and "flipping" elements to another stack happens only when necessary, averaging $O(1)$ per operation. #### 3. Ring Buffers (Circular Arrays) Used for fixed-size memory management (e.g., **Circular Queue**, **Hit Counter**). ```text [0] [1] [2] [3] [4] [5] ^ ^ ^ Head (Data) Tail (Pops) (Next Push) ``` - Use `(index + 1) % capacity` to wrap around the array. #### 4. Concurrency & Thread Safety For "Hard" design problems (e.g., **Bounded Blocking Queue**). - Use **Mutexes** (Locks) to prevent data races. - Use **Condition Variables** (`wait`/`notify`) to manage producer-consumer logic efficiently without busy-waiting. ### How to Approach a Design Problem 1. **Identify the API:** What methods do you need to implement? (`get`, `put`, `push`, etc.) 2. **Define the State:** What variables represent the current state? (Size, Capacity, Pointers). 3. **Choose the Data Structures:** Select the combination that minimizes time complexity for the most frequent operations. 4. **Dry Run:** Trace the state changes through a sequence of operations based on your chosen structure.

Design Phone Directory

Design a Phone Directory that supports get, check, and release operations for a fixed set of $N$ numbers.

Requirement

get(): Returns an available number or -1.
check(num): Returns true if a number is available.
release(num): Makes a number available again.

Medium

Examples

Input: ["PhoneDirectory", "get", "get", "check", "get", "check", "release", "check"]
[[3], [], [], [2], [], [2], [2], [2]]
Output: [null, 0, 1, true, 2, false, null, true]

Approach 1

Level I: Boolean Array (Simple Scan)

Intuition

Use a boolean[] of size maxNumbers to track which numbers are used. For get, scan the array from the beginning to find the first false index. This is $O(N)$ for get and $O(1)$ for others.

⏱ Get: O(N), Check/Release: O(1).💾 O(N).

Detailed Dry Run

Array: [F, F, F]. Get() -> finds index 0, sets to T. Array: [T, F, F].

java

class PhoneDirectory {
    boolean[] used; int max;
    public PhoneDirectory(int max) { this.max = max; used = new boolean[max]; }
    public int get() {
        for(int i=0; i<max; i++) if(!used[i]) { used[i] = true; return i; }
        return -1;
    }
    public boolean check(int n) { return n >= 0 && n < max && !used[n]; }
    public void release(int n) { if(n >= 0 && n < max) used[n] = false; }
}

Approach 2

Level II: BitSet (Space Optimized)

Intuition

Use a BitSet to track availability. Finding the next available number is $O(N)$ in the bitset, but space is reduced dramatically.

⏱ Get: O(N), Check/Release: O(1).💾 O(N/64).

java

class PhoneDirectory {
    BitSet bs;
    public PhoneDirectory(int max) { bs = new BitSet(max); bs.set(0, max); }
    public int get() { int i = bs.nextSetBit(0); if(i != -1) bs.clear(i); return i; }
    public boolean check(int n) { return bs.get(n); }
    public void release(int n) { bs.set(n); }
}

Approach 3

Level III: Queue + HashSet

Intuition

Use a Queue to store available numbers (for $O(1)$ get) and a HashSet to store current available numbers (for $O(1)$ check). When release is called, add back to both if it wasn't already available.

⏱ O(1) for all operations.💾 O(N).

java

class PhoneDirectory {
    Queue<Integer> q = new LinkedList<>();
    Set<Integer> set = new HashSet<>();
    public PhoneDirectory(int max) {
        for (int i = 0; i < max; i++) { q.add(i); set.add(i); }
    }
    public int get() {
        if (q.isEmpty()) return -1;
        int res = q.poll(); set.remove(res); return res;
    }
    public boolean check(int n) { return set.contains(n); }
    public void release(int n) { if (set.add(n)) q.add(n); }
}

← Previous QuestionDesign Twitter

Next Question →Data Stream as Disjoint Intervals

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.