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

This question comes from geekforgeek: http://www.geeksforgeeks.org/find-k-such-that-all-elements-in-kth-row-are-0-and-kth-column-are-1-in-a-boolean-matrix/

Given a square boolean matrix mat[n][n], find k such that all elements in k’th row are 0 and all elements in k’th column are 1. The value of mat[k][k] can be anything (either 0 or 1).  If no such k exists, return -1. Do it in O(n) time.

Note there is only one such k can satisfy the rules.

Simple way is to do that is to find a kth row that all values are 0s except the kth element. Then check the kth column if all values are 1s except the kth element. This requires us to check all of the element. Time complexity: O(n*n)

Another way to travel from top-left corner, we start with 0th row:
go right if the element is 0, if we reach the end of row, then that means: 1) this rth row is potential candidate; 2) the columns/rows from r+1 to n-1 are not candidate; And we check kth row/col values.
go down if the element is 1, for the current row is no longer qualifies.

Since we either go right or go down, then time complexity is O(n)

     public static int findKthRow(int[][] mat){
        int n = mat.length;
        int row = 0;
        while(row<n-1){
            int col = row + 1;
            //move from left to right at current row
            while(col<n && mat[row][col] == 0){
                col++;
            }
           
            /*
             * if we reach the last column of current row, then
             *    this row is candidate and
             *    rest of rows are not candidates
             * otherwise
             *     we go down one row below   
             */       
            if(col == n){
                //check if this row is qualified
                return checkKthRowCol(mat, row)?row:-1;
            }else{
                row++;
            }
        }
       
        return checkKthRowCol(mat, row)?row:-1;
    }
   
    private static boolean checkKthRowCol(int[][] mat, int k){
        int n = mat.length;
        for(int i = 0; i<n; i++){
            if(i==k)
                continue;
            else{
                if(mat[k][i]==1 || mat[i][k]==0)
                    return false;
            }
        }
        return true;
    }

a simple regular expression implementation

Implement a simple regular expression based string match. 

. - any character
* - match 0 or more times of previous character

/**
     *
     * @param target
     * @param regex
     * @return
     */
    public static boolean isMatch(String target, String regex){
        assert !target.isEmpty() && !regex.isEmpty();
        int p1 = 0;
        int p2 = 0;
        int len1 = target.length();
        int len2 = regex.length();
        char pre = '\0', c1, c2 = '\0';
       
        while(p1<len1 && p2<len2){
            c1 = target.charAt(p1);
            c2 = regex.charAt(p2);
           
            if(c2 == '.'){
                p1++;p2++;
                pre = '.';
            }else if(c2 == '*'){               
                if(pre == '\0'){
                    return false;
                }
                else if(pre == '.' || pre == c1){
                    p1++;
                }else{
                    p2++;
                    pre = '\0';
                }
            }else{
                if(c1 == c2){
                    pre = c1;
                    p1++; p2++;
                }else{
                    if(p2+1<len2 && regex.charAt(p2+1) == '*'){
                        p2++;p2++;
                    }else
                        return false;
                }
                   
            }
        }
       
        if(p1 == len1)
            return true;
        else
            return false;
    }

Least recently used cache (LRU) implementation

One of the leetcode questions is to implement a least recently used cache. Basically a cache has to combine two kinds of data structures: a hash table so we can get/set item and a linked list so we can maintain the order of entries.

In JDK there is LinkedHashMap, which does the above, its implement a special Map.Entry class which only has key and value, but also maintain pointer to the next and previous Map.Entry.

Here are couple of my implementations:

1. Use LinkedHapMap directly:

public class SimpleLRUCache {
    private int capacity;
    LinkedHashMap<Object, Object> map;
   
    public SimpleLRUCache(final int capacity){
        this.capacity = capacity;
      
        map = new LinkedHashMap<Object, Object>(12, 0.76f, true){
            protected boolean removeEldestEntry(Map.Entry<Object,Object> eldest){
                return this.size() == capacity;              
            }
        };
      
    }
}

2. Use HashMap and LinkedList:

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    public static class Node{
Object key;
Object value;
Node pre;
Node next;
}

Map<Object, Node> map;

int capacity;

//head points to the oldest entry
Node head;
Node tail;

public LRUCache (int c){
this.capacity = c;
this.map = new HashMap<Object, Node>();
}

public Object get(Object key){
if(map.containsKey(key)){
Node n = map.get(key);
remove(n);
addLast(n);
return n.value;
}else
return null;

}

public void set(Object key, Object value){
if(map.containsKey(key)){
Node n = map.get(key);
remove(n);
addLast(n);
return;
}

if(map.size() == this.capacity){
map.remove(head.key);
remove(head);
}

Node n = new Node();
n.key = key;
n.value = value;

addLast(n);

map.put(key, n);

}

public void addLast(Node n){
if(head==null){
head = n;
tail = n;
}else{
tail.next = n;
n.pre = tail;
tail = n;
}
}


public void remove(Node n){
if(n.pre == null){
head = n.next;

}else{
n.pre.next = n.next;
}

if(n.next == null){
tail = n.pre;
}else
n.next.pre = n.pre;

//set the pointer so n can be gc'd
n.pre = n.next = null;
}
}

3. Synchronized LRU

import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

/*
 * a thread-safe LRUCache implementation using lock
 *
 * note only most important methods are implemented
 */
public class SynchronizedLRUCache<K, V> implements Map<K,V> {

    private final Map<K, V> cache;
   
    public SynchronizedLRUCache(final int maxSize, final int initSize, final float lf){  
        this.cache = new LinkedHashMap<K ,V>(initSize, lf){
            private static final long serialVersionUID = -1218440011343946609L;

            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> oldest){
                return size() > maxSize;
            }
        };
    }
   
    public SynchronizedLRUCache(final int maxSize, final int initSize){  
        this(maxSize, initSize, 0.75f);
    }
   
    public SynchronizedLRUCache(final int maxSize){  
        this(maxSize, 1<<4, 0.75f);
    }
   

    public int size() {
        synchronized(cache){
            return cache.size();
        }      
    }

   
    public boolean isEmpty() {
        synchronized(cache){
            return cache.isEmpty();
        }
    }

   
    public boolean containsKey(Object key) {
        synchronized(cache){
            return cache.containsKey(key);
        }
    }

   
    public V put(K key, V value) {
        synchronized(cache){
            return cache.put(key, value);
        }
    }
   
   
    public V get(Object key) {
        synchronized(cache){
            return cache.get(key);
        }
    }
   
   
    public void putAll(Map<? extends K, ? extends V> m) {
        synchronized(cache){
            cache.putAll(m);
        }
      
    }
   
   
    public boolean containsValue(Object value) {
        // TODO Auto-generated method stub
        return false;
    }
   

    public V remove(Object key) {
        // TODO Auto-generated method stub
        return null;
    }  

   
    public void clear() {
        // TODO Auto-generated method stub
      
    }

   
    public Set<K> keySet() {
        // TODO Auto-generated method stub
        return null;
    }

   
    public Collection<V> values() {
        // TODO Auto-generated method stub
        return null;
    }

   
    public Set<java.util.Map.Entry<K, V>> entrySet() {
        // TODO Auto-generated method stub
        return null;
    }

   

}