新浪微博笔试题解

public String printMinVersion(String[] arr) {
    StringBuffer res = new StringBuffer();
    for (int i = 0; i < arr.length; i++) {
        if (i != arr.length - 1) {
            res.append(arr[i]).append(".");
        }else{
            res.append(arr[i]);
        }
    }
    return res.toString();
}

public String getMinVersion(String[] list) {
    String[][] arr = new String[list.length][];
    for (int i = 0; i < list.length; i++) {
        arr[i] = list[i].split("\\.");
    }
    Arrays.sort(arr, new Comparator<String[]>() {
        public int compare(String[] a, String[] b) {
            int i = 0;
            while (i < a.length && i < b.length) {
                if (Integer.valueOf(a[i]) > Integer.valueOf(b[i])) {
                    return 1;
                } else if (Integer.valueOf(a[i]) < Integer.valueOf(b[i])) {
                    return -1;
                }
                i++;
            }
            if (i < a.length) {
                return 1;
            }
            if (i < b.length) {
                return -1;
            }
            return 0;
        }
    });
    return this.printMinVersion(arr[0]);
}

public class LRUCache {

    class CacheNode {
        int key, value;
        CacheNode pre, next;
    }

    private Hashtable<Integer, CacheNode> ***Table = new Hashtable<Integer, CacheNode>();
    private int count;
    private CacheNode head, tail;
    private int capacity;

    public LRUCache(int capacity){
        this.count = 0;
        this.capacity = capacity;
        head = new CacheNode();
        tail = new CacheNode();
        head.pre = null;
        tail.next = null;

        head.next = tail;
        tail.pre = head;
    }

    private void moveToHead(CacheNode node) {
        this.removeNode(node);
        this.addNode(node);
    }

    private void addNode(CacheNode node) {
        node.next = this.head.next;
        node.pre = this.head;
        this.head.next.pre = node;
        this.head.next = node;
        ++count;
    }

    private CacheNode popTail() {
        if (count == 0) {
            return null;
        }
        CacheNode node = this.tail.pre;
        this.removeNode(node);
        return node;
    }

    private void removeNode(CacheNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        --count;
    }

    public int get(int key) throws Exception{
        CacheNode node = this.***Table.get(key);
        if (node == null) {
            throw new Exception("the element not found");
        }
        this.moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        CacheNode node = this.***Table.get(key);
        if (node != null) {
            node.value = value;
            this.moveToHead(node);
        }
        CacheNode newNode = new CacheNode();
        newNode.key = key;
        newNode.value = value;

        this.addNode(newNode);
        this.***Table.put(key, newNode);

        if (count > this.capacity) {
            CacheNode popNode = this.popTail();
            this.***Table.remove(popNode.key);
        }
    }

}