Course4all

Design Phone Directory

Expert Answer & Key Takeaways

# 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)O(1) read and O(N)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)O(1) caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - HashMap: Provides O(1)O(1) lookups for keys to their corresponding nodes. - DLL: Provides O(1)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)O(1), and "flipping" elements to another stack happens only when necessary, averaging O(1)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 NN 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)O(N) for get and O(1)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)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)O(1) get) and a HashSet to store current available numbers (for O(1)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); }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionDesign Twitter
Next Question →Data Stream as Disjoint Intervals