系统设计

这里面我总结的系统设计题大部分来自于lintcode，因为leetcode上面只有一道tiny url。系统设计不一定要多么会写代码吧个人觉得，写出来代码只是帮助更好的理解这个过程。不是说leetcode就不行了，虽然有很多题leetcode都没有。但是最近发现leetcode还是有很多我以前没有关注过的有用的内容的，比如说数据库的分类，好好刷题吧，很多东西都需要学。

535. Encode and Decode TinyURL

第一种解法，最朴素的方式。

public class Codec {

    Map<String, String> shortToLong = new HashMap<>();
    Map<String, String> longToShort = new HashMap<>();

    // Encodes a URL to a shortened URL.
    public String encode(String url) {
        if (longToShort.containsKey(url)) {
            return longToShort.get(url);
        }
        while (true) {
            String shortUrl = generate(url);
            if (!shortToLong.containsKey(shortUrl)) {
                longToShort.put(url, shortUrl);
                shortToLong.put(shortUrl, url);
                return shortUrl;
            }
        }
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String url) {
        if (!shortToLong.containsKey(url)) return null;

        return shortToLong.get(url);
    }

    private String generate(String url) {
        String allowed = "1234567890" + "qwertyuiopasdfghjklzxcvbnm"
                + "QWERTYUIOPASDFGHJKLZXCVBNM";
        StringBuilder sb = new StringBuilder();
        sb.append("http://tiny.url/");
        Random r = new Random();
        for (int i = 0; i < 6; ++i) {
            int index = r.nextInt(62);
            sb.append(allowed.charAt(index));
        }
        return sb.toString();
    }
}

Tiny Url II

public class TinyUrl2 {
    private HashMap<Long, String> id2url = new HashMap<Long, String>();
    private HashMap<String, Long> url2id = new HashMap<String, Long>();

    private HashMap<String, String> custom_s2l = new HashMap<String, String>();
    private HashMap<String, String> custom_l2s = new HashMap<String, String>();

    private final String tinyUrl = "http://tiny.url/";
    private static long GLOBAL_ID = 0;

    private String getShortKey(String short_url) {
        return short_url.substring(tinyUrl.length(), short_url.length());
    }
    private long shortKeytoID(String shortKey) {
        long id = 0;
        for (int i = 0; i < shortKey.length(); ++i) {
            if ('a' <= shortKey.charAt(i) && shortKey.charAt(i) <= 'z')
                id = id * 62L + (long)(shortKey.charAt(i) - 'a');
            if ('A' <= shortKey.charAt(i) && shortKey.charAt(i) <= 'Z')
                id = id * 62L + (long)(shortKey.charAt(i) - 'A' + 26);
            if ('0' <= shortKey.charAt(i) && shortKey.charAt(i) <= '9')
                id = id * 62L + (long)(shortKey.charAt(i) - '0' + 52);
        }
        return id;
    }
    private String idToShortKey(long n) {
        StringBuffer shortKey = new StringBuffer();
        char[] c = new char[62];
        c = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789".toCharArray();
        while (n > 0) {
            shortKey.append(c[(int)(n % 62)]);
            n = n / 62L;
        }
        while (shortKey.length() < 6) {
            shortKey.append("a");
        }
        return shortKey.reverse().toString();
    }

    private boolean isNormalKey(String short_key) {
        if (short_key.length() != 6) {
            return false;
        }
        for (int i = 0; i < 6; i++) {
            char c = short_key.charAt(i);
            if (c >= '0' && c <= '9') {
                continue;
            }
            if (c >= 'a' && c <= 'z') {
                continue;
            }
            if (c >= 'A' && c <= 'Z') {
                continue;
            }
            return false;
        }
        return true;
    }
    String createCustom(String long_url, String short_key) {
        String short_url = tinyUrl + short_key;
        if (isNormalKey(short_key)) {
            long id = shortKeytoID(short_key);
            if (id2url.containsKey(id) && !id2url.get(id).equals(long_url)) {
                return "error";
            }

            if (url2id.containsKey(long_url) && url2id.get(long_url) != id) {
                return "error";
            }

            if (id2url.containsKey(id) || url2id.containsKey(long_url))
                return short_url;
        }

        if (custom_s2l.containsKey(short_url) && 
                !custom_s2l.get(short_url).equals(long_url)) {
            return "error";
        }

        if (custom_l2s.containsKey(long_url) && 
                !custom_l2s.get(long_url).equals(short_url)) {
            return "error";
        }

        custom_s2l.put(short_url, long_url);
        custom_l2s.put(long_url, short_url);
        return short_url;
    }
    public String longToShort(String long_url) {
        if (custom_l2s.containsKey(long_url)) {
            return custom_l2s.get(long_url);
        }

        if (url2id.containsKey(long_url)) {
            long id = url2id.get(long_url);
            return tinyUrl + idToShortKey(id);
        }

        GLOBAL_ID++;
        id2url.put(GLOBAL_ID, long_url);
        url2id.put(long_url, GLOBAL_ID);
        return tinyUrl + idToShortKey(GLOBAL_ID);
    }
    public String shortToLong(String short_url) {
        if (custom_s2l.containsKey(short_url))
            return custom_s2l.get(short_url);

        String short_key = getShortKey(short_url);
        long id = shortKeytoID(short_key);
        return id2url.get(id);
    }
}

Memcache

public class Memcache {

    class Node{
        private int value;
        private int time;

        public Node(int value, int time) {
            this.value = value;
            this.time = time;
        }
    }

    Map<Integer, Node> map;

    public Memcache() {
        map = new HashMap<>();
    }

    public int get(int curtTime, int key) {
        if (!map.containsKey(key)) return Integer.MAX_VALUE;
        Node node = map.get(key);
        if (node.time >= curtTime || node.time == -1) return node.value;
        else return Integer.MAX_VALUE;
    }

    public void set(int curtTime, int key, int value, int ttl) {
        int time;
        if (ttl == 0) time = -1;
        else time = curtTime + ttl - 1;
        Node node = new Node(value, time);
        map.put(key, node);
    }

    public void delete(int curtTime, int key) {
        if (!map.containsKey(key)) return;
        map.remove(key);
    }

    public int incr(int curtTime, int key, int delta) {
        if (get(curtTime, key) == Integer.MAX_VALUE) return Integer.MAX_VALUE;
        Node node = map.get(key);
        node.value += delta;
        return node.value;
    }

    public int decr(int curtTime, int key, int delta) {
        if (get(curtTime, key) == Integer.MAX_VALUE) return Integer.MAX_VALUE;
        Node node = map.get(key);
        node.value -= delta;
        return node.value;
    }
}

Consistent Hashing

public class Solution {
    /**
     * @param n a positive integer
     * @return n x 3 matrix
     */
    public List<List<Integer>> consistentHashing(int n) {
        // Write your code here
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();

        list.add(0);
        list.add(359);
        list.add(1);
        result.add(list);
        for (int i = 1; i < n; ++i) {
            int index = 0;
            for (int j = 1; j < i; ++j) {
                if (result.get(j).get(1) - result.get(j).get(0) + 1 >
                    result.get(index).get(1) - result.get(index).get(0) + 1) {

                    index = j;
                }
            }
            List<Integer> curt = result.get(index);

            int x = curt.get(0);
            int y = curt.get(1);
            int mid = (x + y) / 2;
            result.get(index).set(1, mid);

            List<Integer> newList = new ArrayList<>();
            newList.add(mid + 1);
            newList.add(y);
            newList.add(i + 1);
            result.add(newList);
        }
        return result;
    }
}

Consistent Hashing II

public class Solution {

    public int n;
    public int k;
    public Map<Integer, List<Integer>> map;
    public Set<Integer> set;

    // @param n a positive integer
    // @param k a positive integer
    // @return a Solution object
    public static Solution create(int n, int k) {
        // Write your code here
        Solution s = new Solution();
        s.n = n;
        s.k = k;
        s.map = new HashMap<>();
        s.set = new HashSet<>();
        return s;
    }

    // @param machine_id an integer
    // @return a list of shard ids
    public List<Integer> addMachine(int machine_id) {
        // Write your code here
        Random r = new Random();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < k; ++i) {
            int index = r.nextInt(n);
            while (set.contains(index)) index = r.nextInt(n);
            set.add(index);
            list.add(index);
        }
        Collections.sort(list);
        map.put(machine_id, list);
        return list;
    }

    // @param hashcode an integer
    // @return a machine id
    public int getMachineIdByHashCode(int hashcode) {
        // Write your code here
        int distance = n + 1;
        int machineId = 0;
        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            int key = entry.getKey();
            for (int node : entry.getValue()) {
                int d = node - hashcode;
                if (d < 0) d += n;
                if (d < distance) {
                    distance = d;
                    machineId = key;
                }
            }
        }
        return machineId;
    }
}

Mini Cassandra

/**
 * 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 {

    private Map<String, NavigableMap<Integer, String>> map;

    public MiniCassandra() {
        map = new HashMap<>();
    }

    /**
     * @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) {
        if (!map.containsKey(raw_key)) map.put(raw_key, new TreeMap<Integer, String>());

        map.get(raw_key).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) {
        List<Column> result = new ArrayList<>();
        if (!map.containsKey(raw_key)) return result;
        NavigableMap<Integer, String> columnMap = map.get(raw_key);
        for (Map.Entry<Integer, String> entry : columnMap.subMap(column_start, true, column_end, true).entrySet()) {
            Column co = new Column(entry.getKey(), entry.getValue());
            result.add(co);
        }
        return result;
    }
}

Mini Twitter

/**
 * Definition of Tweet:
 * public class Tweet {
 *     public int id;
 *     public int user_id;
 *     public String text;
 *     public static Tweet create(int user_id, String tweet_text) {
 *         // This will create a new tweet object,
 *         // and auto fill id
 *     }
 * }
 */
public class MiniTwitter {
    class Node {
        public int order;
        public Tweet tweet;
        public Node(int o, Tweet t) {
            this.order = o;
            this.tweet = t;
        }
    }

    class SortByOrder implements Comparator {     
        public int compare(Object obj1,Object obj2) {     
            Node node1 = (Node) obj1;     
            Node node2 = (Node) obj2;     
            if (node1.order < node2.order)
                return 1;
            else
                return -1;
        }
    }     

    private Map<Integer, Set<Integer>> friends;
    private Map<Integer, List<Node>> users_tweets;
    private int order;

    public List<Node> getLastTen(List<Node> tmp) {
        int last = 10;
        if (tmp.size() < 10)
            last = tmp.size();
        return tmp.subList(tmp.size() - last, tmp.size());
    }

    public List<Node> getFirstTen(List<Node> tmp) {
        int last = 10;
        if (tmp.size() < 10)
            last = tmp.size();
        return tmp.subList(0, last);
    }

    public MiniTwitter() {
        // initialize your data structure here.
        this.friends = new HashMap<Integer, Set<Integer>>();
        this.users_tweets = new HashMap<Integer, List<Node>>();
        this.order = 0;
    }

    // @param user_id an integer
    // @param tweet a string
    // return a tweet
    public Tweet postTweet(int user_id, String tweet_text) {
        //  Write your code here
        Tweet tweet = Tweet.create(user_id, tweet_text);
        if (!users_tweets.containsKey(user_id))
            users_tweets.put(user_id, new ArrayList<Node>());
        order += 1;
        users_tweets.get(user_id).add(new Node(order, tweet));
        return tweet;
    }

    // @param user_id an integer
    // return a list of 10 new feeds recently
    // and sort by timeline
    public List<Tweet> getNewsFeed(int user_id) {
        // Write your code here
        List<Node> tmp = new ArrayList<Node>();
        if (users_tweets.containsKey(user_id))
            tmp.addAll(getLastTen(users_tweets.get(user_id)));

        if (friends.containsKey(user_id)) {
            for (Integer user : friends.get(user_id)) {
                if (users_tweets.containsKey(user))
                    tmp.addAll(getLastTen(users_tweets.get(user)));
            }
        }

        Collections.sort(tmp, new SortByOrder());
        List<Tweet> rt = new ArrayList<Tweet>();
        tmp = getFirstTen(tmp);
        for (Node node : tmp) {
            rt.add(node.tweet);
        }
        return rt;
    }

    // @param user_id an integer
    // return a list of 10 new posts recently
    // and sort by timeline
    public List<Tweet>  getTimeline(int user_id) {
        // Write your code here
        List<Node> tmp = new ArrayList<Node>();
        if (users_tweets.containsKey(user_id))
            tmp.addAll(getLastTen(users_tweets.get(user_id)));

        Collections.sort(tmp, new SortByOrder());
        List<Tweet> rt = new ArrayList<Tweet>();
        tmp = getFirstTen(tmp);
        for (Node node : tmp)
            rt.add(node.tweet);
        return rt;
    }

    // @param from_user_id an integer
    // @param to_user_id an integer
    // from user_id follows to_user_id
    public void follow(int from_user_id, int to_user_id) {
        // Write your code here
        if (!friends.containsKey(from_user_id))
            friends.put(from_user_id, new HashSet<Integer>());

        friends.get(from_user_id).add(to_user_id);
    }

    // @param from_user_id an integer
    // @param to_user_id an integer
    // from user_id unfollows to_user_id
    public void unfollow(int from_user_id, int to_user_id) {
        // Write your code here
        if (friends.containsKey(from_user_id))
            friends.get(from_user_id).remove(to_user_id);
    }
}

Load Balancer

public class LoadBalancer {

    Map<Integer, Integer> map;
    List<Integer> list;

    public LoadBalancer() {
        map = new HashMap<>();
        list = new ArrayList<>();
    }

    public void add(int server_id) {
        int size = list.size();
        map.put(server_id, size);
        list.add(server_id);
    }

    public void remove(int server_id) {
        int prevSize = map.get(server_id);
        int curtSize = list.size();
        int lastMachine = list.get(curtSize - 1);
        map.put(lastMachine, prevSize);
        list.set(prevSize, lastMachine);
        list.remove(curtSize - 1);
        map.remove(server_id);
    }

    public int pick() {
        Random r = new Random();
        int num = Math.abs(r.nextInt()) % list.size();
        return list.get(num);
    } 
}

635. Design Log Storage System

class LogSystem {

    List<String[]> timestamps;
    List<String> time = Arrays.asList("Year", "Month", "Day", "Hour", "Minute", "Second");
    int[] indices = {4, 7, 10, 13, 16, 19};
    public LogSystem() {
        timestamps = new LinkedList<>();

    }

    public void put(int id, String timestamp) {
        timestamps.add(new String[] {Integer.toString(id), timestamp});
    }

    public List<Integer> retrieve(String s, String e, String gra) {
        List<Integer> result = new LinkedList<>();
        int index = indices[time.indexOf(gra)];
        for (String[] timestamp : timestamps) {
            if (timestamp[1].substring(0, index).compareTo(s.substring(0, index)) >= 0
               && timestamp[1].substring(0, index).compareTo(e.substring(0, index)) <= 0)                                                           result.add(Integer.parseInt(timestamp[0]));
        }
        return result;
    }
}