Daily Archives: June 24, 2015

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);
    }
}