Buttercola: Fast ID Generator

Buttercola: Fast ID Generator
已知一个叫get_ids()的API能够耗时1s并返回100个各不相同的id（第二次call返回的和第一次的也不会有任何重复），有个待实现的函数叫get_one_id()，每秒最多被call 100次，每次call要能返回一个新的id。题目就是利用get_ids()实现get_one_id()，follow up是保证每次call get_one_id()不能等待超过1s
Use a queue to store 100 IDs. Once the queue is empty, refill the queue by calling the get_ids(). 

  Queue<Integer> queue;

   

  public Solution() {

    queue = new LinkedList<>();

  }

   

   

  public Integer get_one_id() {

    // Take 1 sec

    if (queue.isEmpty()) {

      List<Integer> ids = get_ids();

      for (Integer id : ids) {

        queue.offer(id);

      }

    }

     

    return queue.poll();

  }

   

  public List<Integer> get_ids() {

    List<Integer> result = new ArrayList<>();

    Random randomGenerator = new Random();

     

    // Generate 100 ids which takes 1 sec

    for (int i = 0; i < 100; i++) {

      result.add(randomGenerator.nextInt(1000));

    }

     

    // Sleep 1 sec

    try {

      Thread.sleep(1000);                 //1000 milliseconds is one second.

    } catch(InterruptedException ex) {

      Thread.currentThread().interrupt();

    }

     

    return result;

  }

Follow-up: What if each time we call get_one_id(), the waiting time is on longer than 1s?
In the previous solution, if the queue is empty, we have to call get_ids() to get 100 ids which takes 1s. In order to shorten the waiting time, we need to overlap those two processes. 

The idea is to use two threads. One thread calls get_one_id(), which consumes the IDs, another thread call get_ids(), which feeds the queue. The threshold is 100, i.e., when the queue has 100 IDs, the get_ids() will be triggered and feed 100 IDs into the queue. Since get_one_id() is called no more than 100 times per second, in this way calling the get_one_id() will not be blocked any more. 

In fact, this is a classic producer/consumer problem. 

  public static void main(String[] args) {

    BlockingQueue bq = new BlockingQueue();

    Producer p1 = new Producer(bq);

    Consumer c1 = new Consumer(bq);

     

    p1.start();

    c1.start();

  }

}

class BlockingQueue {

  private Queue<Integer> queue;

  private int threshold = 100;

   

  public BlockingQueue() {

    queue = new LinkedList<>();

    // feed 100 ids first

    List<Integer> ids = get_ids();

    for (Integer id : ids) {

      queue.offer(id);

    }

  }

   

  public synchronized void put() throws InterruptedException {

    while (queue.size() != threshold) {

      wait();

    }

     

    // feed 100 ids

    List<Integer> ids = get_ids();

    for (Integer id : ids) {

      queue.offer(id);

    }

     

    notifyAll();

  }

   

  public synchronized Integer take() throws InterruptedException {

    while (queue.size() == 0) {

      wait();

    }

     

    Integer result = queue.poll();

    notifyAll();

     

    return result;

  }

   

  public List<Integer> get_ids() {

    List<Integer> result = new ArrayList<>();

    Random randomGenerator = new Random();

     

    // Generate 100 ids which takes 1 sec

    for (int i = 0; i < 100; i++) {

      result.add(randomGenerator.nextInt(1000));

    }

     

    // Sleep 1 sec

    try {

      Thread.sleep(1000);                 //1000 milliseconds is one second.

    } catch(InterruptedException ex) {

      Thread.currentThread().interrupt();

    }

     

    return result;

  }

}

class Consumer extends Thread {

  private BlockingQueue bq;

  public Consumer(BlockingQueue bq) {

    this.bq = bq;

  }

   

  public void run() {

    // print 500 ids

    for (int i = 0; i < 1000; i++) {

      try {

        Integer result = bq.take();

        System.out.println(result);

      } catch (InterruptedException ex) {

        Thread.currentThread().interrupt();

      }

    }

  }

}

class Producer extends Thread {

  private BlockingQueue bq;

   

  public Producer(BlockingQueue bq) {

    this.bq = bq;

  }

   

  public void run() {

    try {

      bq.put();

    } catch (InterruptedException ex) {

      Thread.currentThread().interrupt();

    }

  }

Read full article from Buttercola: Fast ID Generator