LintCode-502: Mini Cassandra (System Design題)

Lintcode 502. Mini Cassandra

Description

中文

English

Cassandra is a NoSQL database (a.k.a key-value storage). One individual data entry in cassandra constructed by 3 parts:

row_key. (a.k.a hash_key, partition key or sharding_key.)

column_key.

value

row_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.

value is a string. You can serialize any data into a string and store it in value.

Implement the following methods:

insert(row_key, column_key, value)

query(row_key, column_start, column_end) return a list of entries

Have you met this question in a real interview?

Example

Example 1:

Input:

insert(“google”, 1, “haha”)

query(“google”, 0, 1)

Output: [(1, “haha”)]

Example 2:

Input:

insert(“google”, 1, “haha”)

insert(“lintcode”, 1, “Good”)

insert(“google”, 2, “hehe”)

query(“google”, 0, 1)

query(“google”, 0, 2)

query(“go”, 0, 1)

query(“lintcode”, 0, 10)

Output:

[(1, “haha”)]

[(1, “haha”),(2, “hehe”)]

[]

[(1, “Good”)]

解法1：

這題注意query傳回的vector必須是按column_key排好序的，是以最好用map< int, string >來存，因為C++裡面的map自動按key來排序。用vector的話比較麻煩，因為Column類不能修改。

/**
 * Definition of Column:
 * class Column {
 * public:
 *     int key;
 *     String value;
 *     Column(int key, string value) {
 *         this->key = key;
 *         this->value = value;
 *    }
 * }
 */


class MiniCassandra {
public:
    MiniCassandra() {
        // do intialization if necessary
    }

    /*
     * @param raw_key: a string
     * @param column_key: An integer
     * @param column_value: a string
     * @return: nothing
     */
    void insert(string &raw_key, int column_key, string &column_value) {
        hashmap[raw_key][column_key] = column_value;
    }

    /*
     * @param raw_key: a string
     * @param column_start: An integer
     * @param column_end: An integer
     * @return: a list of Columns
     */
    vector<Column> query(string &raw_key, int column_start, int column_end) {
        vector<Column> sol;
        
        if (hashmap.find(raw_key) == hashmap.end()) return sol;
        
        for (auto c : hashmap[raw_key]) {
            if ((c.first >= column_start) && (c.first <= column_end)) {
                sol.push_back(Column(c.first, c.second));
            }      
        }
        
        return sol;
    }
    
private:
    map<string, map<int, string>> hashmap;
};