java - 设计电话目录，为您提供从池中返回的号码

Question

我遇到了下面的面试问题，我能够想出以下解决方案:

Design a Phone Directory which supports the following operations:

get: Provide a number which is not assigned to anyone. check: Check if a number is available or not. release: Recycle or release a number..

Example: // Init a phone directory containing a total of 3 numbers: 0, 1, and 2.

PhoneDirectory directory = new PhoneDirectory(3);

// It can return any available phone number. Here we assume it returns 0.

directory.get();

// Assume it returns 1.

directory.get();

// The number 2 is available, so return true.

directory.check(2);

// It returns 2, the only number that is left.

directory.get();

// The number 2 is no longer available, so return false.

directory.check(2);

// Release number 2 back to the pool.

directory.release(2);

// Number 2 is available again, return true.

directory.check(2);

如果我们谈论的是 10 位真实电话号码并且初始化大约需要 o(n) 时间，面试官问这个解决方案的可扩展性如何。此外，如果我们非常频繁地删除，那么保留每个未使用的数字可能会浪费空间。他提到如果它也被用于多线程情况会发生什么。

这里有什么我们可以优化的吗？

public class PhoneDirectory {
  private final Set<Integer> used = new HashSet<Integer>();
  private final Queue<Integer> available = new LinkedList<Integer>();
  private final int max;

  public PhoneDirectory(int maxNumbers) {
    this.max = maxNumbers;
    for (int i = 0; i < maxNumbers; i++) {
      this.available.offer(i);
    }
  }

  public int get() {
    Integer ret = available.poll();
    if (ret == null) {
      return -1;
    }
    used.add(ret);
    return ret;
  }

  public boolean check(int number) {
    if (number >= max || number < 0) {
      return false;
    }
    return !used.contains(number);
  }

  public void release(int number) {
    if (used.remove(number)) {
      available.offer(number);
    }
  }
}

Answer 1

正如您的面试官所说，存储所有未使用的电话号码并不实际。我想从候选人那里看到一个很好的澄清问题是 get() 的频率是多少？和 release()电话。对于现实世界的使用，它们可能以大致相同的频率发生，因此以下方法将起作用:

我们可以通过观察是否使用了任何不可用的内容来优化您的解决方案，因此实际上没有必要存储这两种状态。因此，让我们只跟踪未使用的那些。

public class PhoneDirectory {
  private final Set<Integer> available = new HashSet<Integer>();

  public PhoneDirectory(int maxNumbers) {
    for (int i = 0; i < maxNumbers; i++) {
      this.available.add(i);
    }
  }

  public int get() {
    if (available.isEmpty()) {
      return -1;
    }
    int result = available.iterator().next();
    available.remove(result);
    return result;
  }

  public boolean check(int number) {
    return available.contains(number);
  }

  public void release(int number) {
    available.add(number);
  }
}

这给了我们一个摊销 O(1)除施工外的所有调用的操作。为了处理优化构造函数调用，我们可以做什么 Jason Armstrong提到并观察到我们可以跟踪迄今为止提供的最大数量，这意味着高于此数量的任何东西都可以提供。此外，如果它们存在，我们可以首先耗尽可用条目的稀疏集。看起来像这样

public class PhoneDirectory {
  private final Set<Integer> available = new HashSet<Integer>();
  private final int maxNumbers;
  private int largestOffered;

  public PhoneDirectory(int maxNumbers) {
    this.maxNumbers = maxNumbers;
    this.largestOffered = 0;
  }

  public int get() {
    if (available.isEmpty()) {
      return largestOffered < maxNumbers ? (++largestOffered) : -1;
    }
    int result = available.iterator().next();
    available.remove(result);
    return result;
  }

  public boolean check(int number) {
    return available.contains(number) || number > largestOffered;
  }

  public void release(int number) {
    available.add(number);
  }
}

这摆脱了我们的 O(n)构造函数。回到最初关于频率的假设，之所以可行，是因为如果 get()和 release()以相同的频率相对不可预测地发生，那么 available 的大小会保持相对稳定。这使数据结构的大小总体上保持相当高效。

如果调用的频率不同，例如我们预计 release()一次可以释放大块，那么这个问题就变得复杂了很多。我相信一般来说，这个问题可以归结为位图操作，而节省空间的做法本质上是位级压缩。

关于您的面试官提出的后续问题，他们可能希望对分布式哈希表进行一些讨论。您还可以优化 available.iterator().next()然后available.remove()可以通过对底层数据结构的一些访问来简化调用。