Monthly Archives: January 2015

Adjust a positive array to be sorted with minimum cost

Problem: Given an array A of positive integers. Convert it to a sorted array with minimum cost. The only valid operation are:
1) Decrement with cost = 1
2) Delete an element completely from the array with cost = value of element
For example, input array is [10, 3, 11, 12]. The sorted array with minimum cost will be [10, 11, 12]. Cost is 3.

This problem confused me for a long time, until Junmin gave out the answer. The explanation is copied form Junmin:
The idea is that the final sorted array will always end up with one of the original numbers appear in the array. then all of the larger numbers before this number will be decremented,  dp(i, j), i is the index of the original array a[], j is the index of the sorted array b[] of unique numbers in the array
dp(i, j) = min(dp(i-1, 0), dp(i-1, 2), … dp(i-1, j)) + cost_of_convert(a[i], b[j]).

Based on that, my code also output the final sorted array.

  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.List;
  4. import java.util.Set;
  5. import java.util.TreeSet;
  6. public class LowestCostToSort {
  7.     public static void main(String[] args) {
  8.         int[] num = { 1, 5, 2, 2 };
  9.         System.out.println(“input array:\t” + Arrays.toString(num));
  10.         int cost = getLowestCostToSort(num);
  11.         System.out.println(“total cost:\t” + cost);
  12.     }
  13.     public static int getLowestCostToSort(int[] num) {
  14.         Set<Integer> uniqueSet = new TreeSet<Integer>();
  15.         for (int i : num) {
  16.             uniqueSet.add(i);
  17.         }
  18.         Integer[] uniqueNum = (Integer[]) uniqueSet
  19.                 .toArray(new Integer[uniqueSet.size()]);
  20.         CostTrack[][] dp = new CostTrack[num.length][uniqueNum.length];
  21.         // initial dp[0][]
  22.         for (int i = 0; i < uniqueNum.length; i++) {
  23.             if (num[0] >= uniqueNum[i]) {
  24.                 dp[0][i] = new CostTrack(num[0] – uniqueNum[i], -1);
  25.                 continue;
  26.             }
  27.             dp[0][i] = new CostTrack(0, -1);
  28.         }
  29.         for (int i = 1; i < num.length; i++) {
  30.             for (int j = 0; j < uniqueNum.length; j++) {
  31.                 // Considering adding num[i] to the sorted array,
  32.                 int diff = (num[i] >= uniqueNum[j]) ? (num[i] – uniqueNum[j])
  33.                         : num[i];
  34.                 dp[i][j] = new CostTrack(Integer.MAX_VALUE, -1);
  35.                 for (int k = 0; k <= j; k++) {
  36.                     if (dp[i – 1][k].cost + diff < dp[i][j].cost) {
  37.                         dp[i][j].cost = dp[i – 1][k].cost + diff;
  38.                         dp[i][j].from = k;
  39.                     }
  40.                 }
  41.             }
  42.         }
  43.         // print result
  44.         int result = -1, result_cost = Integer.MAX_VALUE;
  45.         for (int i = 0; i < uniqueNum.length; i++) {
  46.             if (dp[num.length – 1][i].cost < result_cost) {
  47.                 result_cost = dp[num.length – 1][i].cost;
  48.                 result = i;
  49.             }
  50.         }
  51.         List<Integer> result_list = new ArrayList<Integer>();
  52.         for (int i = num.length – 1; i >= 0; i–) {
  53.             if (num[i] >= uniqueNum[result]) {
  54.                 result_list.add(0, uniqueNum[result]);
  55.                 result = dp[i][result].from;
  56.             }
  57.         }
  58.         System.out.println(“sorted array:\t” + result_list.toString());
  59.         return result_cost;
  60.     }
  61.     static class CostTrack {
  62.         int cost;
  63.         int from;
  64.         public CostTrack(int cost, int from) {
  65.             this.cost = cost;
  66.             this.from = from;
  67.         }
  68.     }
  69. }

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

Weekly challenge2 – DescendPrint

package weeklychallenge1;

import java.util.ArrayList;
import java.util.Collections;
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 <char, count> in hashMap. This costs O(n) time, O(n) space
* Step2, put all <char, count> to hashTree, as <count, List<char>>. This costs O(nlogn), O(n) space
* Step3, print result from hashTree
* Total time, O(n + nlogn) = O(nlogn)
* Total space, O(n + n) = O(n)
*/
public static void descendPrint(String str){
if(str==null||str.length()==0){
return;
}
//put char count to hashMap
Map<Character, Integer> hm = new HashMap<Character, Integer>();
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);
}
//dump <K,V> from hashmap to treeMap, as <V, Set(K)>
Map<Integer, ArrayList<Character>> tm = new TreeMap<Integer, ArrayList<Character>>(Collections.reverseOrder());
Iterator<Entry<Character, Integer>> itr = hm.entrySet().iterator();
while(itr.hasNext()){
Entry<Character, Integer> hmItem = itr.next();
char ch = hmItem.getKey();
int times = hmItem.getValue();
ArrayList<Character> tmItem = tm.get(times);
if(tmItem==null){    //a new character
tmItem = new ArrayList<Character>();
tmItem.add(ch);
tm.put(times, tmItem);
continue;
}
tmItem.add(ch);
}
//Print result
Set<Entry<Integer, ArrayList<Character>>> resultSets = tm.entrySet();
for(Entry<Integer, ArrayList<Character>> set:resultSets){
int times = set.getKey();
for(char ch:set.getValue()){
for(int i=0;i<times;i++){
System.out.print(ch);
}
}
}
}

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

Weekly challenge1 – Find the char which repeats most

package weeklychallenge1;

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

/*
* Given a string, find the char which repeats most.
*/
public class MostRepeatedChar {

/*
* Use a static 65535 to store the appeared times of each char.
* Iterate chs[] one time. Use extra int[65535] space for record char times.
* Time complexity O(n), space complexity O(1)
*/
public static char findMostRepeatedChar1(String str){
if(str==null||str.length()==0){
throw new RuntimeException(“invalid input”);
}
int[] rec = new int[65535];
int bigPos = 0;
for(int i=0;i<str.length();i++){
rec[str.charAt(i)]++;
bigPos = rec[str.charAt(i)]>rec[bigPos]?str.charAt(i):bigPos;
}
return (char)bigPos;
}

/*
* Use hashmap.
* Time complexity O(n), space complexity O(1)
*/
public static char findMostRepeatedChar2(String str){
if(str==null||str.length()==0){
throw new RuntimeException(“invalid input”);
}
Map<Character, Integer> hm = new HashMap<Character, Integer>();
char result = str.charAt(0);
for(int i=0;i<str.length();i++){
if(!hm.containsKey(str.charAt(i))){
hm.put(str.charAt(i), 1);
continue;
}
int currTimes = hm.get(str.charAt(i));
result = (++currTimes>hm.get(result))?str.charAt(i):result;
hm.put(str.charAt(i), ++currTimes);
}
return result;
}

/*
* If the most repeated char appears more than half times in char[]
* Iterate chs 1 time. Use 2 extra integers.
* Time complexity O(n), space complexity O(1)
*/
public static char findMostRepeatedChar3(String str){
if(str==null||str.length()==0){
throw new RuntimeException(“invalid input”);
}
char result = str.charAt(0);
int times = 1;
for(int i = 1; i<str.length(); i++){
if(str.charAt(i)==result){
times++;
continue;
}
times–;
if(times<0){
times = 1;
result = str.charAt(i);
}
}
return result;
}

public static void main(String[] args) {
String str = “12abaa11a”;
char result = findMostRepeatedChar3(str);
System.out.println(result);
}

}

Segment tree2

Evolved from segment tree1, this segment tree can find not only the segments, but also individual points. The code is quite similar to segment tree1, please refer here link.
Below is my code:

  1. package util;
  2. public class IntervalTree {
  3.     SegIntervalNode[] segNodes;
  4.     public IntervalTree(int left, int right) {
  5.         int diff = right – left + 1; // diff is actually number of leaf.
  6.         // Calculate the size of array according to diff
  7.         int index = (int) Math.ceil(Math.log(diff) / Math.log(2));
  8.         int space = (int) Math.pow(2, index) * 2;
  9.         segNodes = new SegIntervalNode[space];
  10.         constructSeg(1, left, right);
  11.     }
  12.     /*
  13.      * Construct a SegNode, with range [left, right]. Put it to segNodes[index].
  14.      */
  15.     private void constructSeg(int index, int left, int right) {
  16.         SegIntervalNode node = new SegIntervalNode(index, left, right);
  17.         segNodes[index] = node;
  18.         if (left < right) {
  19.             int mid = (left + right) >> 1;
  20.             constructSeg(index * 2, left, mid);
  21.             constructSeg(index * 2 + 1, mid + 1, right);
  22.         }
  23.     }
  24.     /*
  25.      * Add a segment [left, right] to segment tree
  26.      */
  27.     public void add(int left, int right) {
  28.         if (left > right) {
  29.             return;
  30.         }
  31.         addUtil(1, left, right);
  32.     }
  33.     private void addUtil(int index, int left, int right) {
  34.         SegIntervalNode node = segNodes[index];
  35.         if (left <= node.left && right >= node.right) {
  36.             node.cover++;
  37.             return;
  38.         }
  39.         int mid = (node.left + node.right) >> 1;
  40.         if (left <= mid) {
  41.             addUtil(index * 2, left, right);
  42.         }
  43.         if (right > mid) {
  44.             addUtil(index * 2 + 1, left, right);
  45.         }
  46.     }
  47.     /*
  48.      * Delete a segment [left, right] from segment tree
  49.      */
  50.     public void delete(int left, int right) {
  51.         if (left > right) {
  52.             return;
  53.         }
  54.         deleteUtil(1, left, right);
  55.     }
  56.     private void deleteUtil(int index, int left, int right) {
  57.         SegIntervalNode node = segNodes[index];
  58.         if (left <= node.left && right >= node.right) {
  59.             node.cover–;
  60.             return;
  61.         }
  62.         int mid = (node.left + node.right) >> 1;
  63.         if (left <= mid) {
  64.             deleteUtil(index * 2, left, right);
  65.         }
  66.         if (right > mid) {
  67.             deleteUtil(index * 2 + 1, left, right);
  68.         }
  69.     }
  70.     /*
  71.      * Print all covered segments
  72.      */
  73.     public void print() {
  74.         printUtil(1, segNodes[1].left, segNodes[1].right);
  75.     }
  76.     public void printUtil(int index, int left, int right) {
  77.         SegIntervalNode node = segNodes[index];
  78.         if (node.cover != 0) {
  79.             System.out.println(“[” + left + “, ” + right + “]\t” + node.cover);
  80.             return;
  81.         }
  82.         if (left >= right) {
  83.             return;
  84.         }
  85.         int mid = (node.left + node.right) >> 1;
  86.         if (left <= mid) {
  87.             printUtil(index * 2, left, mid);
  88.         }
  89.         if (right > mid) {
  90.             printUtil(index * 2 + 1, mid + 1, right);
  91.         }
  92.     }
  93.     public static void main(String[] args) {
  94.         IntervalTree tree = new IntervalTree(0, 7);
  95.         tree.add(3, 6);
  96.         tree.print();
  97.         System.out.println();
  98.     }
  99. }
  100. class SegIntervalNode {
  101.     int index;
  102.     int left;
  103.     int right;
  104.     int cover;
  105.     public SegIntervalNode() {
  106.     }
  107.     public SegIntervalNode(int index, int left, int right) {
  108.         this.index = index;
  109.         this.left = left;
  110.         this.right = right;
  111.     }
  112. }

Segment tree1

Problem description:
Given a range [0, n]. Then given some of sections in [0, n], find the total sections in [0, n]
For example, given [0,8]. Then given section sets [2, 4], [3, 5], [6, 7].
The result should be [2, 5], [6, 7].
A brute force solution is to go over each section sets, find the overlapping part and return the result.
The following segment tree can achieve a O(logn) time query.
The following is my code:

  1. package util;
  2. public class SegmentTree {
  3.     SegIntervalNode[] segNodes;
  4.     public SegmentTree(int left, int right) {
  5.         int diff = right – left; // diff is actually number of leaf.
  6.         // Calculate the size of array according to diff
  7.         int index = (int) Math.ceil(Math.log(diff) / Math.log(2));
  8.         int space = (int) Math.pow(2, index) * 2;
  9.         segNodes = new SegIntervalNode[space];
  10.         constructSeg(1, left, right);
  11.     }
  12.     /*
  13.      * Construct a SegNode, with range [left, right]. Put it to segNodes[index].
  14.      */
  15.     private void constructSeg(int index, int left, int right) {
  16.         SegIntervalNode node = new SegIntervalNode(index, left, right);
  17.         segNodes[index] = node;
  18.         if (left + 1 < right) {
  19.             int mid = (left + right) >> 1;
  20.             constructSeg(index * 2, left, mid);
  21.             constructSeg(index * 2 + 1, mid, right);
  22.         }
  23.     }
  24.     /*
  25.      * Add a segment [left, right] to segment tree
  26.      */
  27.     public void add(int left, int right) {
  28.         if (left >= right) {
  29.             return;
  30.         }
  31.         addUtil(1, left, right);
  32.     }
  33.     private void addUtil(int index, int left, int right) {
  34.         SegIntervalNode node = segNodes[index];
  35.         if (left <= node.left && right >= node.right) {
  36.             node.cover++;
  37.             return;
  38.         }
  39.         int mid = (node.left + node.right) >> 1;
  40.         if (left < mid) {
  41.             addUtil(index * 2, left, right);
  42.         }
  43.         if (right > mid) {
  44.             addUtil(index * 2 + 1, left, right);
  45.         }
  46.     }
  47.     /*
  48.      * Delete a segment [left, right] from segment tree
  49.      */
  50.     public void delete(int left, int right) {
  51.         if (left >= right) {
  52.             return;
  53.         }
  54.         deleteUtil(1, left, right);
  55.     }
  56.     private void deleteUtil(int index, int left, int right) {
  57.         SegIntervalNode node = segNodes[index];
  58.         if (left <= node.left && right >= node.right) {
  59.             node.cover–;
  60.             return;
  61.         }
  62.         int mid = (node.left + node.right) >> 1;
  63.         if (left < mid) {
  64.             deleteUtil(index * 2, left, right);
  65.         }
  66.         if (right > mid) {
  67.             deleteUtil(index * 2 + 1, left, right);
  68.         }
  69.     }
  70.     /*
  71.      * Print all covered segments
  72.      */
  73.     public void print() {
  74.         printUtil(1, segNodes[1].left, segNodes[1].right);
  75.     }
  76.     public void printUtil(int index, int left, int right) {
  77.         SegIntervalNode node = segNodes[index];
  78.         if (node.cover != 0) {
  79.             System.out.println(“[” + left + “, ” + right + “]\t” + node.cover);
  80.             return;
  81.         }
  82.         if (left + 1 >= right) {
  83.             return;
  84.         }
  85.         int mid = (node.left + node.right) >> 1;
  86.         if (left < mid) {
  87.             printUtil(index * 2, left, mid);
  88.         }
  89.         if (right > mid) {
  90.             printUtil(index * 2 + 1, mid, right);
  91.         }
  92.     }
  93.     public static void main(String[] args) {
  94.         SegmentTree tree = new SegmentTree(0, 8);
  95.         tree.add(3, 6);
  96.         tree.print();
  97.         System.out.println();
  98.     }
  99. }
  101. class SegIntervalNode {
  102.     int index;
  103.     int left;
  104.     int right;
  105.     int cover;
  106.     public SegIntervalNode() {
  107.     }
  108.     public SegIntervalNode(int index, int left, int right) {
  109.         this.index = index;
  110.         this.left = left;
  111.         this.right = right;
  112.     }
  113. }

Jaccard distance

This is to response Junmin Liu’s Jaccard distance problem.
For example:
two strings: adbc and adffg, result is 2 / 6
(size of intersect of chars in strings) / (size of union of chars in strings). and duplicate character can only count once.

I came up with 2 solutions:
1. O(m+n) time, O(m+n) space with hashset
2. O((m+n)log(m+n)) time, O(1) space by sorting.
Below is my code:

  1. import java.util.Arrays;
  2. import java.util.HashSet;
  3. public class Jaccard {
  4.     public static void main(String[] args) {
  5.         char[] str = {‘a’, ‘f’, ‘g’, ‘e’, ‘a’, ‘c’, ‘a’, ‘d’, ‘f’, ‘b’, ‘q’};
  6.         int pos = 5;
  7.         calJacDistance(str, pos);
  9.         char[] a = {‘a’, ‘b’, ‘c’, ‘d’,’e’,’g’};
  10.         char[] b = {‘a’, ‘d’, ‘f’, ‘f’, ‘g’};
  11.         calJacDistance2(a, b);
  12.     }
  14.     /*
  15.      * Time O(m+n), space O(m+n)
  16.      */
  17.     public static void calJacDistance2(char[] a, char[] b){
  18.         if(a==null||b==null||a.length<1||b.length<1){
  19.             return;    //lenght of b[] is zero.
  20.         }
  21.         HashSet hs1 = new HashSet();
  22.         HashSet hs2 = new HashSet();
  23.         for(int i=0;i
  24.             hs1.add(a[i]);
  25.         }
  26.         for(int i=0;i
  27.             hs2.add(b[i]);
  28.         }
  29.         //put elements from hs2 to hs1. During this process, record how many duplication it is.
  30.         int dup_num = 0;
  31.         for(char ch:hs2){
  32.             if(hs1.contains(ch)){
  33.                 dup_num++;
  34.             }
  35.             else{
  36.                 hs1.add(ch);
  37.             }
  38.         }
  39.         int union_num = hs1.size();
  40.         System.out.println((double)dup_num / (double)union_num);
  41.     }
  43.     /*
  44.      * The idea of this solution is to sort and find the duplicaitons.
  45.      * str[0,…,pos] is the a[], str[pos+1,…,len-1] is b[]
  46.      * time O[(m+n)log(m+n)], space O(1).
  47.      * time mostly is costed by sorting.
  48.      */
  49.     public static void calJacDistance(char[] str, int pos){
  50.         if(pos==str.length-1||pos<0){
  51.             return;    //lenght of b[] is zero.
  52.         }
  53.         Arrays.sort(str, 0, pos+1);
  54.         Arrays.sort(str, pos+1, str.length);
  55.         //below 2 for loop is to deduplicate a[] and b[] separately
  56.         int dup_num = 0;    //to record how many duplication are there in str.
  57.         for(int i=1;i<=pos;i++){
  58.             if(str[i]==str[i-1-dup_num]){
  59.                 dup_num++;
  60.             }
  61.             else{
  62.                 str[i-dup_num] = str[i];
  63.             }
  64.         }
  65.         str[pos+1-dup_num] = str[pos+1];
  66.         for(int i=pos+2;i
  67.             if(str[i]==str[i-1-dup_num]){
  68.                 dup_num++;
  69.             }
  70.             else{
  71.                 str[i-dup_num] = str[i];
  72.             }
  73.         }
  74.         Arrays.sort(str, 0, str.length -dup_num);    //sort the new array
  75.         //duplication number in str[0,…,len-dup_num-1] will be the intersection number
  76.         //str.len-dup_num-dup_num2 will be the union number
  77.         int dup_num2 = 0;
  78.         for(int i=1;i
  79.             if(str[i]==str[i-1-dup_num2]){
  80.                 dup_num2++;
  81.             }
  82.             else{
  83.                 str[i-dup_num2] = str[i];
  84.             }
  85.         }
  86.         int union_num = str.length – dup_num – dup_num2;
  87.         System.out.println((double)dup_num2 / (double)union_num);
  88.     }
  89. }

Topological sorting by dfs

This is problem is from careerup link:

You have an vector like this
[JFK, LXA, SNA, RKJ, LXA, SNA]
each 2 group define a route. so,
JFK -> LXA
SNA -> RKJ
LXA -> SNA
Find the path from departure to destination. note: departure and destination are not known.
The final destination should be
JFK-> LXA -> SNA -> RKJ

In mycode, I use DFS for topological sorting. The advantage of it is that it won’t require the in-degree information, compared to BFS. Besides, I constructed the graph by using HashMap < String, AirNode > outgoing , instead of using self-defined graph class, which make the code easier.

  1. import java.util.HashMap;
  2. import java.util.HashSet;
  3. import java.util.Map;
  4. import java.util.Set;
  5. import java.util.Vector;
  6. public class TopogicalSorintDFS {
  7.     public static void main(String[] args) {
  8.         Vector airports = new Vector();
  9.         airports.add(“JFK”);
  10.         airports.add(“LAX”);
  11.         airports.add(“SNA”);
  12.         airports.add(“RKJ”);
  13.         airports.add(“LAX”);
  14.         airports.add(“SNA”);
  15.         Vector result = findPath(airports);
  16.         System.out.println(result.toString());
  17.     }
  18.     public static Vector findPath(Vector airports) {
  19.         Map nodes = new HashMap();
  20.         // construct graph
  21.         for (int i = 0; i < airports.size(); i += 2) {
  22.             String from = airports.get(i);
  23.             String to = airports.get(i + 1);
  24.             if (!nodes.containsKey(from)) {
  25.                 nodes.put(from, new AirNode(from));
  26.             }
  27.             if (!nodes.containsKey(to)) {
  28.                 nodes.put(to, new AirNode(to));
  29.             }
  30.             nodes.get(from).outgoing.add(nodes.get(to));
  31.         }
  32.         Vector result = new Vector();
  33.         HashSet visited = new HashSet();
  34.         //start the dfs on graph
  35.         for (AirNode node : nodes.values()) {
  36.             dfs(node, visited, result);
  37.         }
  38.         return result;
  39.     }
  40.     public static void dfs(AirNode node, HashSet visited,
  41.             Vector result) {
  42.         if (visited.contains(node.airport)) {
  43.             return;
  44.         }
  45.         visited.add(node.airport);
  46.         for (AirNode curr : node.outgoing) {
  47.             dfs(curr, visited, result);
  48.         }
  49.         result.insertElementAt(node.airport, 0);
  50.     }
  51. }
  52. class AirNode {
  53.     String airport;
  54.     Set outgoing;
  55.     public AirNode(String airport) {
  56.         this.airport = airport;
  57.         outgoing = new HashSet();
  58.     }
  59.     public boolean equals(Object obj) {
  60.         if (obj == null) {
  61.             return false;
  62.         }
  63.         if (this == obj) {
  64.             return true;
  65.         }
  66.         if (obj instanceof AirNode) {
  67.             AirNode node = (AirNode) obj;
  68.             return this.airport.equals(node.airport);
  69.         }
  70.         return false;
  71.     }
  72.     public int hashCode() {
  73.         return this.airport.hashCode();
  74.     }
  75. }

Find diameter trail

This is a practice for tree function. It returns the diameter trail of a tree by traversing each node only one time.
The process is similar to finding diameter. During traverse each node, keep track of the trail of from the furthest leaf to node itself.
For the following tree, it should return the diameter trail 1, 2, 3, 4, 5, 6


Code:

  1. import java.util.ArrayList;
  2. import java.util.Iterator;
  3. public class FindDiameterTrail{
  5.     public static void main(String[] args) {
  6.         Tree t = Tree.getTree();
  7.         findDiameterTrail(t);
  8.     }
  10.     public static void findDiameterTrail(Tree t){
  11.         DiaData diaData = getDiameterUtil(t);
  12.         ArrayList result = diaData.leftTrail;
  13.         while(!result.isEmpty()){
  14.             Tree tree = result.remove(0);
  15.             System.out.println(tree.value);
  16.         }
  17.         System.out.println(diaData.lca.value);
  18.         result = diaData.rightTrail;
  19.         while(!result.isEmpty()){
  20.             Tree tree = result.remove(result.size()-1);
  21.             System.out.println(tree.value);
  22.         }
  23.     }
  25.     public static DiaData getDiameterUtil(Tree t){
  26.         if(t==null){
  27.             DiaData diameter = new DiaData(0, 0);
  28.             diameter.leafTrail = new ArrayList();
  29.             diameter.leftTrail = new ArrayList();
  30.             diameter.rightTrail = new ArrayList();
  31.             return diameter;
  32.         }
  33.         DiaData left = getDiameterUtil(t.left);
  34.         DiaData right = getDiameterUtil(t.right);
  35.         DiaData diameter = new DiaData();
  36.         //deal with the depth
  37.         if(left.depth>right.depth){
  38.             diameter.depth = left.depth + 1;
  39.             diameter.leafTrail = trailCopy(left.leafTrail);
  40.         }
  41.         else{
  42.             diameter.depth = right.depth + 1;
  43.             diameter.leafTrail = trailCopy(right.leafTrail);
  44.         }
  45.         diameter.leafTrail.add(t);
  46.         //deal with the diameter node.
  47.         if(left.depth+right.depth+1>Math.max(left.diameter, right.diameter)){
  48.             diameter.diameter = left.depth+right.depth+1;
  49.             diameter.leftTrail = left.leafTrail;
  50.             diameter.rightTrail = right.leafTrail;
  51.             diameter.lca = t;
  52.             return diameter;
  53.         }
  54.         if(left.diameter>right.diameter){
  55.             diameter.leftTrail = left.leftTrail;
  56.             diameter.rightTrail = left.rightTrail;
  57.             diameter.diameter = left.diameter;
  58.             diameter.lca = left.lca;
  59.         }
  60.         else{
  61.             diameter.leftTrail = right.leftTrail;
  62.             diameter.rightTrail = right.rightTrail;
  63.             diameter.diameter = right.diameter;
  64.             diameter.lca = right.lca;
  65.         }
  66.         return diameter;
  67.     }
  69.     public static ArrayList trailCopy(ArrayList t){
  70.         ArrayList result = new ArrayList();
  71.         if(t==null||t.isEmpty()){
  72.             return result;
  73.         }
  74.         Iterator itr = t.iterator();
  75.         while(itr.hasNext()){
  76.             result.add(itr.next());
  77.         }
  78.         return result;
  79.     }
  80. }
  81. class DiaData{
  82.     int depth;
  83.     int diameter;
  84.     ArrayList leftTrail;
  85.     ArrayList rightTrail;
  86.     Tree lca;
  87.     ArrayList leafTrail;
  88.     public DiaData(int depth, int diameter){
  89.         this.depth = depth;
  90.         this.diameter = diameter;
  91.     }
  92.     public DiaData(){}
  93. }
  94. class Tree{
  95.     public Tree(int value){
  96.         this.value = value;
  97.     }
  98.     public Tree(String value){
  99.         this.valueString = value;
  100.     }
  101.     public Tree left;
  102.     public Tree right;
  103.     public int value;
  104.     public String valueString;
  106.     public static Tree getTree(){
  107.         Tree t1 = new Tree(1);
  108.         Tree t2 = new Tree(2);
  109.         Tree t3 = new Tree(3);
  110.         Tree t4 = new Tree(4);
  111.         Tree t5 = new Tree(5);
  112.         Tree t6 = new Tree(6);
  113.         Tree t7 = new Tree(7);
  114.         Tree t8 = new Tree(8);
  115.         t7.left = t4; t7.right = t8;
  116.         t4.left = t3; t4.right = t5;
  117.         t3.left = t2;
  118.         t2.right = t1;
  119.         t5.right = t6;
  120.         return t7;
  121.     }
  122. }