Monday, July 10, 2017

Mini Cassandra - LintCode



https://github.com/zxqiu/leetcode-lintcode/blob/master/system%20design/Mini_Cassandra.java
Cassandra is a NoSQL storage. The structure has two-level keys.
Level 1: raw_key. The same as hash_key or shard_key.
Level 2: column_key.
Level 3: column_value
raw_key is used to hash and can not support range query. let's simplify this to a string.
column_key is sorted and support range query. let's simplify this to integer.
column_value is a string. you can serialize any data into a string and store it in column value.
implement the following methods:
insert(raw_key, column_key, column_value)
query(raw_key, column_start, column_end) // return a list of entries
Example
insert("google", 1, "haha")
query("google", 0, 1)
>> [(1, "haha")]
解:
使用HashMap来定位raw_key,每个raw_key对应一个TreeMap。
利用TreeMap自排序特征(基于红黑树)来对column_key排序。
/**
 * Definition of Column:
 * public class Column {
 *     public int key;
 *     public String value;
 *     public Column(int key, String value) {
 *         this.key = key;
 *         this.value = value;
 *    }
 * }
 */
public class MiniCassandra {
   
    HashMap<String, TreeMap<Integer, String>> store;

    public MiniCassandra() {
        store = new HashMap<String, TreeMap<Integer, String>>();
    }
   
    /**
     * @param raw_key a string
     * @param column_start an integer
     * @param column_end an integer
     * @return void
     */
    public void insert(String raw_key, int column_key, String column_value) {
        TreeMap<Integer, String> data;
        if (store.containsKey(raw_key)) {
            data = store.get(raw_key);
        } else {
            data = new TreeMap<Integer, String>();
        }
       
        data.put(column_key, column_value);
        store.put(raw_key, data);
    }

    /**
     * @param raw_key a string
     * @param column_start an integer
     * @param column_end an integer
     * @return a list of Columns
     */
    public List<Column> query(String raw_key, int column_start, int column_end) {
        List<Column> ret = new ArrayList<Column>();
       
        if (!store.containsKey(raw_key)) {
            return ret;
        }
       
        TreeMap<Integer, String> data = store.get(raw_key);
        for (Map.Entry<Integer, String> entry : data.subMap(column_start, true, column_end, true).entrySet()) {
            ret.add(new Column(entry.getKey(), entry.getValue()));
        }
       
        return ret;
    }

Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts