Skip to content

379. Design Phone Directory 👎

  • Time: $O(1)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class PhoneDirectory {
 public:
  /** Initialize your data structure here
      @param maxNumbers - The maximum numbers that can be stored in the phone
     directory. */
  PhoneDirectory(int maxNumbers) : next(maxNumbers) {
    for (int i = 0; i < maxNumbers - 1; ++i)
      next[i] = i + 1;
    next.back() = 0;
  }

  /** Provide a number which is not assigned to anyone.
      @return - Return an available number. Return -1 if none is available. */
  int get() {
    if (next[number] == -1)
      return -1;

    const int ans = number;
    number = next[number];
    next[ans] = -1;  // Mark as used
    return ans;
  }

  /** Check if a number is available or not. */
  bool check(int number) {
    return next[number] != -1;
  }

  /** Recycle or release a number. */
  void release(int number) {
    if (next[number] != -1)
      return;

    next[number] = this->number;
    this->number = number;
  }

 private:
  int number = 0;    // Current possible available number
  vector<int> next;  // Next available number
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class PhoneDirectory {
  /**
   * Initialize your data structure here
   *
   * @param maxNumbers - The maximum numbers that can be stored in the phone
   *                   directory.
   */
  public PhoneDirectory(int maxNumbers) {
    next = new int[maxNumbers];
    for (int i = 0; i < maxNumbers - 1; ++i)
      next[i] = i + 1;
    next[maxNumbers - 1] = 0;
  }

  /**
   * Provide a number which is not assigned to anyone.
   *
   * @return - Return an available number. Return -1 if none is available.
   */
  public int get() {
    if (next[number] == -1)
      return -1;

    final int availableNum = number;
    number = next[number];
    next[availableNum] = -1; // Mark as used
    return ans;
  }

  /** Check if a number is available or not. */
  public boolean check(int number) {
    return next[number] != -1;
  }

  /** Recycle or release a number. */
  public void release(int number) {
    if (next[number] != -1)
      return;

    next[number] = this.number;
    this.number = number;
  }

  private int number; // Current possible available number
  private int[] next; // Next available number
}