Monthly Archives: June 2015

Group sort

I saw the original problem from G4G. Given an array of strings with R, G & B as characters. Sort the array such that all R comes first, followed by Gs & followed by Bs. Do it in O(n) time complexity. (Paper Code)
For example:
 I/P: G G R B R B B G R B R
 O/P: R R R R G G G B B B B

I developed this problem to a generic problem. Given an array of string, and sequence. Sort the array according to the given sequence.
For example:
String str = “DCBAEECCAAABBAEEE”; String sequence = “ABCDE”;
output should be: AAAAABBBCCCDEEEEE

The basic idea is similar to quick sort by an uncertain pivot: http://allenlipeng47.com/PersonalPage/index/view/95/nkey

Because this algorithm require to compare the sequence order, so we use hashmap to store char and sqeuence mapping. In this way, we can get sequence of a char in O(1) time. And we need to save the number of each element in sequence array.

Below is one step how we operate element ‘A’.

package com.pli.project.algorithm.sort;

import java.util.HashMap;

/**
 * Created by lipeng on 2015/6/23.
 * Original problem is from g4g. http://www.geeksforgeeks.org/microsoft-interview-experience-set-54-for-sde/
 * Developed this problem to more generic one:
 String str = "BCDEAAA"; String sequence = "ABCDE";
 output should be: AAABCDE
 */
public class GroupSort {

    public static void groupSort(char[] str, char[] sequence){
        if(str==null||str.length<2||sequence==null||sequence.length<1||sequence.length > str.length){
            return;
        }
        int[] lenArr = new int[sequence.length];   //stores number of each element in sequence array
        // initilization
        HashMap chrOrder = new HashMap();   //char order
        for(int i = 0; ilength; i++){
            chrOrder.put(sequence[i], i);
            if(str[0]==sequence[i]){
                lenArr[i]++;    //initialize the chr[0]
            }
        }
        for(int i=1;ilength;i++){
            int pos = i;
            boolean found = false;
            for(int j=lenArr.length-1 ;j>0 && pos>0;j--){
                if(chrOrder.get(str[pos])>=chrOrder.get(str[pos-1])){   //compare sequence order
                    lenArr[chrOrder.get(str[pos])]++;
                    found = true;
                    break;
                }
                else{
                    // exchange element with previous one
                    char tmp = str[pos];
                    str[pos] = str[pos - lenArr[j]];
                    str[pos - lenArr[j]] = tmp;
                    pos -= lenArr[j];
                } //if
            } //for j
            if(!found){
                //case could be: BBBCCCCDDDA, when next one is A, in this way, A won't be matched in above if clause
                lenArr[chrOrder.get(str[0])]++;
            }
        } //for i
    }

    public static void main(String[] args) {
        String str = "DCBAEECCAAABBAEEE";
        String sequence = "ABCDE";
        char[] chs = str.toCharArray();
        groupSort(chs, sequence.toCharArray());
        System.out.println(chs);
    }
}

Consistent Hashing Algorithm

I’ve been thinking this problem for a long time. HashMap brings an amortized O(1) time for insertion/lookup data. But let’s say we do rehash when we have million records already. We can’t neglect this rehash process, and say it is amortized O(1) time. This will lead a remapping disaster to whole server.

So, I found the solution is to use Consistent Hashing and Multiple Markers in Consistent Hashing. This will only result K/n keys to remapped on average, where K is the number of keys, and n is the cache slots.

This is a great post to explain consistent hashing: https://ihong5.wordpress.com/2014/08/19/consistent-hashing-algorithm/


Expand the storage by adding a new node:

ssh-keygen

1. In any server, we can use ssh-keygen command to generate a pair of public/private key.
ssh-keygen -t rsa -b 4096

Then, we will see “id_rsa”, “id_rsa.pub”.

2. Copy “id_rsa.pub” to the “~/.ssh” folder on machineA where we want to log in. We need to rename to “authorized_keys“.

3. Copy “id_rsa” to the “~/.ssh” folder on machineB where we want to log from.

4. In machineB, run “ssh user@machineA”

Debug:
Private key has too open authority. Then, we should run “chmod 600 ~/.ssh/privateKey”, or “chmod 700 ~/.ssh/privateKey”
Public key should has name “authorized_keys” under “~/.ssh” folder.

Maven, make a fat jar 

<plugin>
    <groupId>org.apache.maven.plugins</groupId>
    <artifactId>maven-shade-plugin</artifactId>
    <version>2.3</version>
    <executions>
        <execution>
            <phase>package</phase>
            <goals>
                <goal>shade</goal>
            </goals>
            <configuration>
                <transformers>
                    <transformer implementation="org.apache.maven.plugins.shade.resource.ManifestResourceTransformer">
                        <mainClass>foo.bar.App</mainClass>
                    </transformer>
                </transformers>
            </configuration>
        </execution>
    </executions>
</plugin>

Simple easymock example

EasyMock can mock an interface, or class. In this way, we can test our code without implementing them. In order to use the static functions in easyMock, we can either extend it, or use “import static” key word. I think using “import static” key word is more general. Let’s start review the code.

main/java — foo.bar.MyInterface

package foo.bar;

/**
 * Created by lipeng on 6/8/2015.
 */
public interface MyInterface {
    int getNum();
}

test/java — foo.bar.TestDrive

package foo.bar;

import static org.easymock.EasyMock.*;  //import static functions
import static org.junit.Assert.*;   //import static functions
import org.junit.Before;
import org.junit.Test;

/**
 * Created by lipeng on 6/5/2015.
 */
public class TestDrive {

    private MyInterface myInterface;

    @Before
    public void setUp(){
        myInterface = createNiceMock(MyInterface.class);
    }

    @Test
    public void testCalc1(){
        expect(myInterface.getNum()).andReturn(100);
        replay(myInterface);    //make mock object ready to use
        assertEquals(100, myInterface.getNum());
    }

}

Find two strings which can group into palindrome

Problem: Given n strings, check if exist 2 of strings which can group a palindrome.
For example, for strings ‘aaa’, ‘aac’, ‘ab’, ‘acblb’, ‘ac’, ‘ddcaa’.
‘aac’ and ‘ddcaa’ can group into palindrome; ‘acblb’ and ‘ac’ can group into palindrome.

We can solve this problem using trie and rolling hash queue. For example, below is when first 4 words in trie:

Next, check word ‘ca’ in reverse sequence. Search it in trie. And it ends in string first. Then, we check any descendant of last node contains a palindrome. And we found b-l-b is a palindrome. So, we conclude word ‘acblb’ and ‘ca’ can group to a palindrome string.

Next, check word ‘ddcaa’ in reverse sequence. Search it in trie. And it ends in trie first. Then, we check if rest string in ‘ddcaa’ is palindrome, which is ‘dd’. And we found ‘dd’ is palindrome. So, we conclude word ‘aac’ and ‘ddcaa’ can group to a palindrome string.

I’m a bit lazy to write the trie code. It would a kinda long code. So, I summarized the basic idea of the solution. But this requires how to find a palindrome in tree, which is talked in my last post http://allenlipeng47.com/PersonalPage/index/view/165/nkey

Find palindrome in Tree

This is an application for rolling hash queue. In the picture below, let’s find the palindrome in binary tree. So, the right answer should be 1-2-3-2-1.

In order to do that, I recursively visit each node. And I maintain 2 rolling hash queues during recursion. When it goes to a leaf node, check the rolling hash of two queues first. If the rolling hash are the same, then check if the queue elements are the same. By rolling hash, it saves a lot of comparison.

Please visit my previous page to get the rolling hash class: http://allenlipeng47.com/PersonalPage/index/view/157/nkey

package tree;

import util.RollingHashQueue;
import util.Tree;

/**
 * Created by PLi on 6/4/2015.
 */
public class FindPalindromeInTree {

    static boolean findPalindromeInTree(Tree tree){
        if(tree == null){
            return false;
        }
        TpData data = new TpData();
        data.q1.addFirst(tree.value);
        data.q2.addFirst(tree.value);
        data.depth++;
        if(tree.left!=null && findPalindromeInTreeUtil(tree.left, data)){
            return true;
        }
        if(tree.right !=null && findPalindromeInTreeUtil(tree.right, data)){
            return true;
        }
        return false;
    }


    static boolean findPalindromeInTreeUtil(Tree tree, TpData data){
        /* Modify first queue and second queue depending on odd/even of depth */
        data.depth++;
        if(data.depth % 2 == 1){
            data.q1.addLast(data.q2.getLast());
            data.q2.addFirst(tree.value);
        }
        else{
            data.q2.removeLast();
            data.q2.addFirst(tree.value);
        }
        /* Check q1 and q2 by rolling hash */
        if(tree.left==null && tree.right==null && data.depth > 1 && data.q1.equals(data.q2)){
            System.out.println(data.q1);
            return  true;
        }
        /* Find palindrome in left, right tree */
        if(tree.left!=null && findPalindromeInTreeUtil(tree.left, data)){
            return true;
        }
        if(tree.right !=null && findPalindromeInTreeUtil(tree.right, data)){
            return true;
        }
        /* No palindrome found in both left, right, backtrace */
        if(data.depth % 2 == 1) {
            data.q1.removeLast();
            data.q2.removeFirst();
        }
        else {
            data.q2.removeFirst();
            data.q2.addLast(data.q1.getLast());
        }
        data.depth--;
        return false;
    }

    /** TreePalindromeData**/
    static class TpData {
        RollingHashQueue q1;
        RollingHashQueue q2;
        int depth;
        public TpData(){
            q1 = new RollingHashQueue();
            q2 = new RollingHashQueue();
            depth = 0;
        }
    }

    public static void main(String[] args) {
        Tree t1 = new Tree(1);
        Tree t2 = new Tree(6);
        Tree t3 = new Tree(4);
        Tree t4 = new Tree(2);
        Tree t5 = new Tree(3);
        Tree t6 = new Tree(2);
        Tree t7 = new Tree(5);
        Tree t8 = new Tree(1);
        t1.left = t2; t1.right = t4;
        t2.right = t3;
        t4.right = t5;
        t5.right = t6;
        t6.left = t7; t6.right = t8;
        findPalindromeInTree(t1);
    }
}