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

Question

我遇到了以下面试问题，我能够提出以下解决方案：

设计一个支持以下操作的电话簿：

get：提供一个未分配给任何人的号码。check：检查号码是否可用。释放：回收或释放一个数字..

示例： // 初始化一个电话簿，其中包含总共 3 个号码：0、1 和 2。

PhoneDirectory 目录 = new PhoneDirectory(3);

// 它可以返回任何可用的电话号码。这里我们假设它返回 0。

目录.get();

// 假设它返回 1。

目录.get();

// 数字 2 可用，所以返回 true。

目录.check(2);

// 它返回 2，唯一剩下的数字。

目录.get();

// 数字 2 不再可用，因此返回 false。

目录.check(2);

// 将 2 号释放回池中。

目录.release(2);

// 数字 2 再次可用，返回 true。

目录.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);
    }
  }
}

标签： javamultithreadingalgorithmdata-structures

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()thenavailable.remove()调用，因为可以通过对底层数据结构的一些访问来简化该调用。