[LeetCode] LRU Cache

One of straightforward implementation of LRUCache is to use JDK's LinkedHashMap. However to implement it correctly, overriding its removeOldestEntry() method is not enough.

We need to use the correct LinkedHashMap constructor with correct arguments to make sure it behaves as LRU cache. Below is the doc from JDK:

"A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). "

And here is the code which passed the LeetCode tests and beat 90% Java implementation in terms of the runtime.

Longest Valid Parentheses

There is the longest valid parentheses problem definition.

We are given a string containing just parentheses of character ')' and '(' only, find the length of the longest valid (well-formed) parentheses substring. For example, for "(()", the longest valid parentheses substring is "()", output is 2. Anther example is ")()())", the longest valid parentheses substring is "()()", which has length of 4.

Approach I: dynamic programming

As usual many of the string related problems can be solved by dynamic problem. Given a substring from index at i to j, how can we find out the longest valid parentheses substring, which is not easy to construct the dynamic function. But we can convert this problem to another problem, that is, given substring S from index i to j, find out if all of the parentheses in the substring S form valid pair.

Here is how we construct isValid dynamic function based on index i and j, which is to break the substring(i,j) to two part: i,k and k+1, j. in which k = i+1, i+3, i+5, ..., j-2.

if(isValid(i,k) && isValid(k+1,j)) then isValid(i,j) = true.

Here is the java code:

public static int longestValidParentheses(String str){
int len = str.length();
boolean[][] isValid = new boolean[len][len];
int maxLen = 0;
for(int i =0; i< len-1; i++){
if(str.charAt(i)=='(' && str.charAt(i+1) == ')'){
isValid[i][i+1] = true;
maxLen = 2;
}
}

for(int step=3; step<len; step=step+2){ for(int i=0; i+step<len; i++){ int j = i+step;
if(isValid[i+1][j-1]&&isValid(str,i,j)) isValid[i][j] = true; for(int k=i+1; k<=j-2; k=k+2){ if(isValid[i][k] && isValid[k+1][j]) isValid[i][j] = true; if(isValid[i][j]){ maxLen = Math.max(maxLen, j - i + 1); break; } } } }
return maxLen;
}

private static boolean isValid(String str, int i, int j){
return str.charAt(i) == '(' && str.charAt(j) == ')';
}

Approach II: using stack

Stack is great data structure, the difference between stack and queue is that you update and query from the same place: the back, while in queue you have two places to update: insert at back, remove at front. That is the reason we can use stack is constructed data structure like max/min stack and max/min queue, in this case, the queue is built on top of stack, as well.

static class Node {
        int pos;
        char c;
        Node(int p, char c){
            this.pos = p;
            this.c = c;
        }
    }
    public static int maxValidParenthesis(String input){
        int max = 0;
        Stack<Node> s = new Stack<Node>();
        for(int i=0, j= input.length(); i<j; i++){
            char c = input.charAt(i);
            if(s.isEmpty() || c == '(' || s.peek().c == ')')
                s.push(new Node(i, c));
            else{
                s.pop();
                max = Math.max(i - (s.isEmpty()?-1:s.peek().pos), max);
            }
        }
        return max;
    }

 

Trie implementation and related string search problems

Trie is special purpose tree to store set of strings to solve a specific set of problems. In stead of storing the characters in the nodes, it is stored on the edges. The string can be constructed by concatenating all the characters found in the path.

For example it can store a dictionary contains a set of words, then it can answer the questions such as:

1. Does word S exist in the dictionary?
2. Given a string S, find all of the words which has the prefix equals to S. Think about design a data structure to support a auto-complete search box.

The followings are Java implementation of Trie to store the set of words from dictionary and support word search in the dictionary.

/*

* trie node definition

* it assumes the character are ascii chacaters

* each word in the dictionary is stored at leaf level

*/

public class TrieNode {

        private final static ALPHABET_SIZE = 256;

        TrieNode[] children = new SuffixNode[ALPHABET_SIZE];

boolean isLeaf;

String word;

}

/*

* suffix tree class

* it defines couple operations to support string search in a dictionary 

* 

*/

public class Trie {

TrieNode root;

public Trie(){

root = new TrieNode();

}

/*

* insert a string into suffix tree

*/

public void insert(String s){

insertHelper(s, 0, root);

}

private void insertHelper(String s, int index, TrieNode node){

if(index == s.length()){

node.isLeaf = true;

node.word = s;

return;

}

TrieNode trieNode = node.children[s.charAt(index)];

if(trieNode==null)

trieNode = new TrieNode();

insertHelper(s, index+1, trieNode);

}

/*

* check if string is prefix of one of the words contained in the tree

*/

public boolean containsPrefix(String s){

return containsPrefix(s, 0, root);

}

private boolean containsPrefix(String s, int index, TrieNode node){

if(index == s.length())

return true;

TrieNode trieNode = node.children[s.charAt(index)];

if(trieNode != null)

return containsPrefix(s, index+1, trieNode);

else

return false;

}

/*

* check if the string is a word existing in the suffix tree

*/

public boolean isWord(String s){

return isWordHelper(s, 0, root);

}

private boolean isWordHelper(String s, int index, TrieNode node){

if(index == s.length())

return node.isLeaf; //the current node must be leaf node

TrieNode trieNode = node.children[s.charAt(index)];

if(trieNode != null)

return isWordHelper(s, index+1, trieNode);

else

return false;

}

/*

* find if the word is prefix of any words contained in the trie tree

* and return the last node which contains the word

*/

public TrieNode searchFor(String s){

return searchFor(s, 0, root);

}

private TrieNode searchFor(String s, int index, TrieNode node){

if(index == s.length())

return node;

TrieNode trieNode = node.children[s.charAt(index)];

if(trieNode != null)

return searchFor(s, index+1, trieNode);

return null;

}

}

Construct Tree from given Inorder and Preorder traversals

Problem:
Give two strings representing the inorder and preorder traversals of binary tree, construct the tree.

The key here is that preorder traversal, the first char is the tree root. And then based on that char, find the its position in inorder string, then its left portion of in order string is the left subtree, right portion is the right subtree.

And do it recursively, make it simpler.

public static Node constructTree(String pre, String in){

if(pre.isEmpty())

return null;

if(pre.length() == 1)

return new Node(pre.charAt(0));

Node root = new Node(pre.charAt(0));

String[] ins = splitStringBy(in, pre.charAt(0));

                root.left = constructTree(pre.substring(1, ins[0].length()+1), ins[0]);

root.right = constructTree(pre.substring(ins[0].length()+1), ins[1]);

return root;

}

public static String[] splitStringBy(String str, char root){

String[] re = new String[2];

re[0] = str.substring(0, str.indexOf(root));

re[1] = str.substring(str.indexOf(root)+1);

return re;

}

Permutations for digits represented by Phone Number

This is a stackoverflow question: http://stackoverflow.com/questions/1851239/permutations-for-digits-represented-by-phone-number

This can be done by dynamic programming and just need to keep track of the previous result list and build result based on it.

public static List<String> allWordsFromPhonePad(int number){

HashMap<Integer, String > h = new HashMap<Integer, String>(){{

        put(1,"");

        put(2, "ABC");

        put(3, "DEF");

        put(4, "GHI");

        put(5, "JKL");

        put(6, "MNO");

        put(7, "PQRS");

        put(8, "TUV");

        put(9, "WXYZ");

        put(0, "");

    }};

    List<String> result = new ArrayList<String>();

    result.add("");

    while(number>0){

    int last = number%10;

    List<String> temp = new ArrayList<String>();

   

    for(String s: result){

    String map = h.get(last);

    for(char c : map.toCharArray()){

    temp.add(String.valueOf(c) + s);

    }

    }    

    number = (number-last)/10;

    if(!temp.isEmpty())

    result = temp;

    }

   

    return result;

}

Convert Binary Search Tree to Sorted Doubly-linked list

This is very interesting problem. And most of solutions are recursive approach which will cause stack overflow.

The below is my solution, which does in-place and iteratively.

The idea is to in-order traverse the tree and use head pointer referencing the head of the linked list and pre pointers referencing the previous node during traverse.

public static Node isBSTAndTreeToDLL(Node root){

if(root==null)

return null;

Stack<Node> s = new Stack<Node>();

Node head = null;

Node n = root;

Node pre = null;

while(!s.isEmpty() || n!=null){

if(n!=null){

s.push(n);

n = n.left;

}

else{

Node p = s.pop();

//this is the left most node

if(head == null)

head = p;

if(pre!=null){

pre.right = p;

p.left = pre;

}

pre=p;

n = p.right;

}

}

//handle the last node

pre.right = head;

head.left = pre;

return head;

}

Find Longest Common Subsequence Length of two strings

Problem:
Given two strings: "AGGTAB", "GXTXAYB", find the length of the longest common subsequence.

The answer for the two strings is 4, "GTAB". Note subsequence is the substring of string with the characters appears in the order as they are in the string but not necessary contiguously.

Solution 1. 

Do it recursively

 /* do it recursively

* @param s1

* @param s2

* @return

*/

public static int findLongestCommonSubsequence(String s1, String s2){

if(s1.isEmpty() || s2.isEmpty())

return 0;

String substring1 = s1.substring(0, s1.length()-1);

String substring2 = s2.substring(0, s2.length()-1);

if(s1.charAt(s1.length()-1) == s2.charAt(s2.length()-1)) {

return 1+StringQ.findLongestCommonSubsequence(substring1, substring2);

} else{

return Math.max(StringQ.findLongestCommonSubsequence(s1, substring2), StringQ.findLongestCommonSubsequence(substring1, s2));

}

} 

Solution 2.

Do it iteratively:

       public static int findLongestCommonSubsequence2(String s1, String s2){

char[] cArray1 = s1.toCharArray();

char[] cArray2 = s2.toCharArray();

int[][] lcs = new int[s1.length()+1][s2.length()+1];

for(int i=0; i<cArray1.length; i++){

for(int j=0; j<cArray2.length; j++){

if(cArray1[i] == cArray2[j])

lcs[i+1][j+1] = lcs[i][j] + 1;

else

lcs[i+1][j+1] = Math.max(lcs[i+1][j], lcs[i][j+1]);

}

}

return lcs[s1.length()][s2.length()];

}

Longest Arithmetic Progression

Problem: 

 Given a set of numbers, find the Length of the Longest Arithmetic Progression (LLAP) in it.

The solution is to that using difference between two numbers in the list as key to store the maximum length for each difference. If the difference is already met before, then we can skip it.

Complexity: O(n^2) since there is n*(n-1) differences between the numbers in a list

public static List<Integer> findMaxArithmeticsSeq(int[] num){

int maxL = 0;

List<Integer> result = new ArrayList<Integer>();

//the difference between two numbers in the list defines the maxL of the sequence

//store the mapping will help to reduce the number of the iterations

Map<Integer, Integer> diff2Length = new HashMap<Integer, Integer>();

for(int i=0; i<num.length-1; i++){

for(int j=i+1; j<num.length; j++){

int diff = num[j]-num[i];

//we don't need to continue since max Length for this difference is already found

if(diff2Length.containsKey(diff))

continue;

List<Integer> found = new ArrayList<Integer>();

found.add(num[i]);

int pre = num[i];

for(int k=j; k<num.length; k++){

if(num[k] - pre == diff){

found.add(num[k]);

pre = num[k];

}

}

diff2Length.put(diff, found.size());

if(found.size() > maxL){

maxL = found.size();

result = found;

}

}

}

return result;

}

Permutations of list of numbers

Given a collection of numbers, return all possible permutations.

Problem description:

Input:
list of numbers: [8, 4, 13]

Output:
all permutations of the numbers in the list

[8, 4, 13]

[4, 8, 13]

[4, 13, 8]

[8, 13, 4]

[13, 8, 4]

[13, 4, 8]

Solution 1:

/**
* do it iteratively
*/

public static ArrayList<ArrayList<Integer>> getPermutations(int[] nums){
ArrayList<ArrayList<Integer>> result = new ArrayList<>();

  //start with an empty list
  result.add(new ArrayList<Integer>());
 
  for(int i=0; i<nums.length; i++){
ArrayList<ArrayList<Integer>> temp = new ArrayList<>();

//go through the list from previous round and add the number into the list
   for(ArrayList<Integer> each : result){
for(int index = 0; index<=each.size(); index++){
ArrayList<Integer> dest = new ArrayList<>(each); //make a copy of original list
dest.add(index, nums[i]); //insert the number into all possible positions
temp.add(dest);
}
}
  
// switch over to prepare for the next round
 result = temp;
}
return result;
}

Solution 2:

/**

 *  do it recursively

**/

public static List<List<Integer>> getPermutations(List<Integer> nums){

List<List<Integer>> result = new ArrayList<>();

if(nums.size()==0){

result.add(new ArrayList<Integer>());

return result;

}

Integer n = nums.remove(0);

List<List<Integer>> subResult = getPermutations(nums); //get the permutation for sub list

for(List<Integer> each : subResult){

for(int index = 0; index<=each.size(); index++){

ArrayList<Integer> dest = new ArrayList<>(each); //make a copy of original list

dest.add(index, n); //insert the number into all possible positions

result.add(dest);

}

}

return result;

}