# Daily Archives: January 18, 2015

## Weekly challenge2 – DescendPrint3

Considering the string has millions of chars. We should optimize the solution.
This time, I didn’t use ArrayList, charAt() etc. Instead, only array is allowed.
A char has 16 bits, which means maximum size is 65536. Compared to millions of chars, assume 65536 is a small size. I use a CharCount class to store the count of a char. So, there are 65536 number of CharCount. Assume the input is char[] chs
Step1, count the char in chs[]. Store the value in CharCount[].
Step2, we assume there are many 0 counted chars, so we iterate charCount[] for one time, filter the 0 counted elements.
Step3, do median of median quicksort on CharCount[].
Step4, print result.

1. package weeklychallenge1;
2. /*
3.  * Given a string, sort its chars by their number of
4.  * appearance in descending order. e.g. input: abcbaa, output: aaabbc.
5.  */
6. public class DescendPrint2 {
7.     /*
8.      * Median of median quicksort on charCount[]
9.      */
10.     public static void quickSortCharCount(CharCount[] charCount, int lo, int hi) {
11.         int i = lo;
12.         int j = hi;
13.         int pivot = findKthCharCount(charCount, lo, hi, (hi – lo + 2) >> 1);
14.         while (i <= j) {
15.             while (charCount[i].count > charCount[pivot].count) {
16.                 i++;
17.             }
18.             while (charCount[j].count < charCount[pivot].count) {
19.                 j–;
20.             }
21.             if (i <= j) {
22.                 CharCount tmp = charCount[i];
23.                 charCount[i] = charCount[j];
24.                 charCount[j] = tmp;
25.                 i++;
26.                 j–;
27.             }
28.         }
29.         if (lo < j)
30.             quickSortCharCount(charCount, lo, j);
31.         if (i < hi)
32.             quickSortCharCount(charCount, i, hi);
33.     }
34.     /*
35.      * Find the kth element in charCount[start,…,end]
36.      */
37.     public static int findKthCharCount(CharCount[] charCount, int start,
38.             int end, int k) {
39.         CharCount tmp = null;
40.         if (end – start < 5) {
41.             // Bubble sort arr[start,…,end] for k times, the arr[start] is the
42.             // median
43.             for (int count = 0; count < k; count++, start++) {
44.                 for (int j = end; j > start; j–) {
45.                     if (charCount[j – 1].count > charCount[j].count) {
46.                         tmp = charCount[j – 1];
47.                         charCount[j – 1] = charCount[j];
48.                         charCount[j] = tmp;
49.                     }
50.                 }
51.             }
52.             start–;
53.             return start;
54.         }
55.         int groupSize = (end – start + 1) / 5;
56.         int subStart = 0, subEnd = 0;
57.         for (int i = 0; i < groupSize; i++) {
58.             subStart = start + i * 5;
59.             subEnd = start + i * 5 + 4;
60.             subEnd = (subEnd > end) ? end : subEnd;
61.             int groupMedian = findKthCharCount(charCount, subStart, subEnd,
62.                     (subEnd – subStart + 2) >> 1);
63.             tmp = charCount[start + i];
64.             charCount[start + i] = charCount[groupMedian];
65.             charCount[groupMedian] = tmp;
66.         }
67.         return findKthCharCount(charCount, start, start + groupSize – 1,
68.                 (groupSize + 1) >> 1);
69.     }
70.     public static void descendPrint3(char[] chs) {
71.         final int MAX_CHAR_SIZE = 65535;
72.         // Calculate count of each char
73.         CharCount[] charCount = new CharCount[MAX_CHAR_SIZE];
74.         for (int i = 0; i < MAX_CHAR_SIZE; i++) {
75.             charCount[i] = new CharCount((char) i, 0);
76.         }
77.         for (int i = 0; i < chs.length; i++) {
78.             charCount[chs[i]].count++;
79.         }
80.         // It is believed that there are many 0 count in charCount[].
81.         // Move the char with 0 count to the right side.
82.         int start = 0, end = MAX_CHAR_SIZE – 1;
83.         while (start < end) {
84.             while (charCount[start].count != 0 && start < end) {
85.                 start++;
86.             }
87.             while (charCount[end].count == 0 && start < end) {
88.                 charCount[end] = null;
89.                 end–;
90.             }
91.             if (start < end) {
92.                 charCount[start] = charCount[end];
93.                 charCount[end] = null;
94.                 start++;
95.                 end–;
96.             }
97.         }
98.         // Do median-of-median quicksort to charCount[0,…,start-1]
99.         quickSortCharCount(charCount, 0, start – 1);
100.         for (int i = 0; i < start; i++) {
101.             for (int j = 0; j < charCount[i].count; j++) {
102.                 System.out.print(charCount[i].ch);
103.             }
104.         }
105.     }
106.     public static void main(String[] args) {
107.         String str = “abcccbbaaa”;
108.         char[] chs = str.toCharArray();
109.         descendPrint3(chs);
110.     }
111. }
112. class CharCount {
113.     char ch;
114.     int count;
115.     public CharCount(char ch, int count) {
116.         this.ch = ch;
117.         this.count = count;
118.     }
119. }

## Weekly challenge2 – DescendPrint2

Based on the DescendPrint link, this one improved by directly sorting the HashMap.Entry in ArrayList.

package weeklychallenge1;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.Map.Entry;

/*
* Given a string, sort its chars by their number of
* appearance in descending order. e.g. input: abcbaa, output: aaabbc.
*/
public class DescendPrint {

/*
* Step1, put all in hashMap. This costs O(n) time, O(n) space
* Step2, initial List. Put Entry to this list. Step3,
* sort the list according to value. This costs O(nlogn) time, it doesn’t
* cost extra space. Step3, print result from hashTree Total time, O(n +
* nlogn) = O(nlogn) Total space, O(n)
*/
public static void descendPrint2(String str) {
if (str == null || str.length() == 0) {
return;
}
// put char count to hashMap
Map hm = new HashMap();
for (int i = 0; i < str.length(); i++) {
if (!hm.containsKey(str.charAt(i))) {
hm.put(str.charAt(i), 1);
continue;
}
int count = hm.get(str.charAt(i));
hm.put(str.charAt(i), ++count);
}
// Sort hashMap according to value.
Set < Entry < Character, Integer > >  set = hm.entrySet();
ArrayList < Entry < Character, Integer > >  list = new ArrayList < Entry < Character, Integer > > ( set);
Collections.sort(list, new DescendComparator());
// Print result
for (Entry entry : list) {
char ch = entry.getKey();
int count = entry.getValue();
for (int i = 0; i < count; i++) {
System.out.print(ch);
}
}
}

public static void main(String[] args) {
String str = “abcccbbaaa”;
descendPrint2(str);
}
}

class DescendComparator implements Comparator> {
public int compare(Entry entry1,
Entry entry2) {
int count1 = entry1.getValue();
int count2 = entry2.getValue();
return count2 – count1;
}
}