LintCode 502 - Mini Cassandra

http://www.jianshu.com/p/94fe92ad945b

Cassandra is a NoSQL storage. The structure has two-level keys.

1. Level 1: raw_key. The same as hash_key or shard_key.
2. Level 2: column_key.
3. Level 3: column_value

raw_key is used to hash and can not support range query. let's simplify this to a string.
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.
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:

1. insert(raw_key, column_key, column_value)
2. query(raw_key, column_start, column_end) // return a list of entries

Example

insert("google", 1, "haha")
query("google", 0, 1)
>> [（1, "haha")]

用map<string, map<int, string>>的方式保存数据，由于map是根据key的大小排好序的hash表，所以遍历map<int, string>时，如果key已经大于column_end则退出。

/**
 * Definition of Column:
 * class Column {
 * public:
 *     int key;
 *     String value;
 *     Column(int key, string value) {
 *         this->key = key;
 *         this->value = value;
 *    }
 * }
 */
class MiniCassandra {
private:
    map<string, map<int, string>> ret;
public:
    MiniCassandra() {
        // initialize your data structure here.
    }

    /**
     * @param raw_key a string
     * @param column_start an integer
     * @param column_end an integer
     * @return void
     */
    void insert(string raw_key, int column_key, string column_value) {
        // Write your code here
        ret[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) {
        // Write your code here
        vector<Column> q;
        for(map<int, string>::iterator iter = ret[raw_key].begin(); iter != ret[raw_key].end(); iter++) {
            if (iter->first > column_end) {
                break;
            }

            if (column_start <= iter->first) {
                q.push_back(Column(iter->first, iter->second));
            }
        }

        return q;
    }
};

http://blog.csdn.net/jmspan/article/details/51749526
方法：使用哈希影射和有序影射。

* public class Column { * public int key; * public String value; * public Column(int key, String value) { * this.key = key; * this.value = value; * } * } */ public class MiniCassandra { private Map<String, TreeMap<Integer, String>> map = new HashMap<>(); public MiniCassandra() { // initialize your data structure here. } /** * @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) { // Write your code here TreeMap<Integer, String> tm = map.get(raw_key); if (tm == null) { tm = new TreeMap<>(); map.put(raw_key, tm); } tm.put(column_key, column_value); } /** * @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) { // Write your code here List<Column> results = new ArrayList<>(); TreeMap<Integer, String> tm = map.get(raw_key); if (tm == null) return results; Map<Integer, String> queried = tm.subMap(column_start, true, column_end, true); for(int key : queried.keySet()) { results.add(new Column(key, queried.get(key))); } return results; } }