Wednesday, June 15, 2016

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

No comments:

Post a Comment

Labels

Review (554) System Design (293) System Design - Review (189) Java (178) Coding (75) Interview-System Design (65) Interview (60) Book Notes (59) Coding - Review (59) to-do (45) Knowledge (39) Linux (39) Interview-Java (35) Knowledge - Review (32) Database (30) Design Patterns (29) Product Architecture (28) Big Data (27) Soft Skills (27) Miscs (25) MultiThread (25) Concurrency (24) Cracking Code Interview (24) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Distributed (20) Interview Q&A (20) OOD Design (20) System Design - Practice (19) Security (17) Algorithm (15) How to Ace Interview (15) Brain Teaser (14) Google (13) Linux - Shell (13) Spark (13) Spring (13) Code Quality (12) How to (12) Interview-Database (12) Interview-Operating System (12) Redis (12) Tools (12) Architecture Principles (11) Company - LinkedIn (11) Testing (11) Resource (10) Solr (10) Amazon (9) Cache (9) Search (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Company - Uber (8) Interview - MultiThread (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Scalability (8) Cassandra (7) Git (7) Interview Corner (7) JVM (7) Java Basics (7) Machine Learning (7) NoSQL (7) C++ (6) Design (6) File System (6) Highscalability (6) How to Better (6) Kafka (6) Network (6) Restful (6) Trouble Shooting (6) CareerCup (5) Code Review (5) Company - Facebook (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Be Architect (4) Big Fata (4) C (4) Company Product Architecture (4) Data structures (4) Design Principles (4) Facebook (4) GeeksforGeeks (4) Generics (4) Google Interview (4) Hardware (4) JDK8 (4) Optimization (4) Product + Framework (4) Shopping System (4) Source Code (4) Web Service (4) node.js (4) Back-of-Envelope (3) Company - Pinterest (3) Company - Twiiter (3) Company - Twitter (3) Consistent Hash (3) GOF (3) Game Design (3) GeoHash (3) Growth (3) Guava (3) Interview-Big Data (3) Interview-Linux (3) Interview-Network (3) Java EE Patterns (3) Javarevisited (3) Map Reduce (3) Math - Probabilities (3) Performance (3) Puzzles (3) Python (3) Resource-System Desgin (3) Scala (3) UML (3) geeksquiz (3) AI (2) API Design (2) AngularJS (2) Behavior Question (2) Bugs (2) Coding Interview (2) Company - Netflix (2) Crawler (2) Cross Data Center (2) Data Structure Design (2) Database-Shard (2) Debugging (2) Docker (2) Elasticsearch (2) Garbage Collection (2) Go (2) Hadoop (2) Html (2) Interview - Soft Skills (2) Interview-Miscs (2) Interview-Web (2) JDK (2) Logging (2) POI (2) Papers (2) Programming (2) Project Practice (2) Random (2) Software Desgin (2) System Design - Feed (2) Thread Synchronization (2) Video (2) ZooKeeper (2) reddit (2) Ads (1) Advanced data structures (1) Algorithm - Review (1) Android (1) Approximate Algorithms (1) Base X (1) Bash (1) Books (1) C# (1) CSS (1) Chrome (1) Client-Side (1) Cloud (1) CodingHorror (1) Company - Yelp (1) Counter (1) DSL (1) Dead Lock (1) Difficult Puzzles (1) Distributed ALgorithm (1) Eclipse (1) Facebook Interview (1) Function Design (1) Functional (1) GoLang (1) How to Solve Problems (1) ID Generation (1) IO (1) Important (1) Internals (1) Interview - Dropbox (1) Interview - Project Experience (1) Interview Tips (1) Interview-Brain Teaser (1) Interview-How (1) Interview-Mics (1) Interview-Process (1) Jeff Dean (1) Joda (1) LeetCode - Review (1) Library (1) LinkedIn (1) LintCode (1) Mac (1) Micro-Services (1) Mini System (1) MySQL (1) Nigix (1) NonBlock (1) Process (1) Productivity (1) Program Output (1) Programcreek (1) Quora (1) RPC (1) Raft (1) RateLimiter (1) Reactive (1) Reading (1) Reading Code (1) Refactoring (1) Resource-Java (1) Resource-System Design (1) Resume (1) SQL (1) Sampling (1) Shuffle (1) Slide Window (1) Spotify (1) Stability (1) Storm (1) Summary (1) System Design - TODO (1) Tic Tac Toe (1) Time Management (1) Web Tools (1) algolist (1) corejavainterviewquestions (1) martin fowler (1) mitbbs (1)

Popular Posts