# Monthly Archives: September 2015

## Longest palindrome in a string

The problem is from a post on mitbbs: http://www.mitbbs.com/article_t/CS/31217531.html

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

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 tail;

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

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

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

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