Monthly Archives: September 2015

Longest palindrome in a string

The problem is from a post on mitbbs:

For example, longest palindrome in “animal” is “ana”, then return 3. Longest palindrome of “sfinished” is “sinis”, so return 5.

This is actually a dp problem for longest common substring. We just easily find the longest common substring between “animal” with “lamina”, that will be the result.

Check my code on github: link

Find values at kth row are 0 and kth column in a 2D matrix are 1

This problem is from G4G:

The problem ask us to find a number k, where the kth row of is all 0, kth column is all 1 too. The value of [k, k] can be either 0 or 1. Take below array as example:

The kth row/column should be 3:

The trick of this problem is that if there is an result, there is only one zero-row. There mustn’t be more than 1 rows. Look at below array, it has 2 all-zero rows(green ones). But it won’t has valid all-one column.

In this way, we just find the potential all-zero row. And we don’t even need to look at the all-one column. As long as we found an potential k, then we check if it is the result.
I gave out a finding process. When it arrives step 4, we are already able to eliminate column 0, 1 and row 0, 1. Then we go on start at row 2, column 2.

Find  my code on github: link
This is the code from junmin, link. Our difference is that my code moves row faster than his code

LRU Cache by hashmap and doubly-linked-list

LRU can be implemented by map and doubly-linked-list.

The key idea is that:
1. Maintain a head and tail, which is not null initially,
2. In Node, we store both key and value,
3. Create pickUp and setHead functions.

public class LRUCache {

    class Node {
        int key;
        int val;
        Node pre;
        Node next;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;

    int capacity;
    HashMap<Integer, Node> hm;
    Node head;
    Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity; = new HashMap<>();
        this.head = new Node(-1, -1);
        this.tail = new Node(-1, -1); = tail;
        tail.pre = head;

    public int get(int key) {
        Node node = hm.get(key);
        if (node == null) {
            return -1;
        return node.val;

    public void set(int key, int value) {
        Node node = hm.get(key);
        if (node != null) {
            node.val = value;
        node = new Node(key, value);
        hm.put(key, node);
        if (hm.size() > capacity) {
   = tail;
            tail.pre = tail.pre.pre;

    public void pickNode(Node node) { =; = node.pre;

    private void setHead(Node node) {
        node.pre = head; =; = node; = node;