Monthly Archives: December 2014

Count bounded slices

Problem:
Return the pair of indices that forms the slice where the difference between the maximum and minimum in the slice <= k. Pair of indices shouldn’t be like (i,i).
Consider k is 2. And the array is 3 5 7 6 3.
Output: (0,1) (1,2) (1,3) (2,3)

Analysis:
A brute-force idea is to recursively find max/min of all indices. Once finding the max/min, output the result. And use hashmap store the history results to reduce duplicate calculation. Because it iterates all possible indices, the time/space complexity is optimized.
This idea is to maintain a ascend queue. Queue front stores the min value. Queue end stores the max valule. Each time, add new element into the sorted queue. Check the max-min. If it is smaller than k, print the results with new element. If max-min is greater than k, we need to adjust the queue before print the results.
It is similar to max value in a sliding widow. But the difference is that in this case, the queue maintain both min value in the front, max value in the end. And max in sliding window only store a max value(or min value).
I provide the following process for understanding:


There are N elements. For each element, it takes O(logn) to insert into the queue, and O(n) to output the result. So the total time complexity is O(n*(n+logn)), which is O(n^2). Not considering result output, it is O(nlogn).
Complete code is following:

  1. import java.util.ArrayList;
  2. import java.util.Collections;
  3. import java.util.Comparator;
  4. public class CountBoundedSlices {
  5.     public static void main(String[] args) {
  6.         int[] arr = {1, 3, 2, 4, 5, 1, 6, 7, 9};
  7.         countBoundedSlices(arr, 2);
  8.     }
  10.     public static void countBoundedSlices(int[] arr, int k){
  11.         BoundedSlicesSData curr = new BoundedSlicesSData(arr[0],0);
  12.         ArrayList queue = new ArrayList();
  13.         queue.add(curr);
  14.         for(int i=1;i < arr.length;i++){
  15.             curr = new BoundedSlicesSData(arr[i], i);
  16.             queue.add(curr);
  17.             Collections.sort(queue, new BoundedSlicesSDataComparator());    //add current element into queue.
  18.             BoundedSlicesSData front = queue.get(0);
  19.             BoundedSlicesSData end = queue.get(queue.size()-1);
  20.             if(end.value-front.value>k&&curr.value==end.value){
  21.                 //Got a larger value at queue end. It makes max-min>k. So modify the queue front.
  22.                 while(end.value-front.value>k){
  23.                     int front_time = front.position;
  24.                     queue.remove(0);
  25.                     front = queue.get(0);
  26.                     while(front.position < front_time){    //delete those elements, which are earlier inserted than front
  27.                         queue.remove(0);
  28.                         front = queue.get(0);
  29.                     }//while
  30.                 }//while
  31.                 for(int j=0;j < queue.size()-1;j++){
  32.                     printResult(queue.get(j).position, end.position);
  33.                 }
  34.             }
  35.             else if(end.value-front.value>k&&curr.value==front.value){
  36.                 //Got a smaller value at queue front. It makes max-min>k. So modify the queue end.
  37.                 while(end.value-front.value>k){
  38.                     int end_time = end.position;
  39.                     queue.remove(queue.size()-1);
  40.                     end = queue.get(queue.size()-1);
  41.                     while(end.position < end_time){    //delete those elements, which are earlier inserted than front
  42.                         queue.remove(queue.size()-1);
  43.                         end = queue.get(queue.size()-1);
  44.                     }//while
  45.                 }//while
  46.                 for(int j=queue.size()-1;j>0;j–){
  47.                     printResult(queue.get(j).position, front.position);
  48.                 }
  49.             }//if
  50.             else{
  51.                 //insertation of curr doesn’t affect max, min. Print result with curr
  52.                 for(int j=0;j < queue.size();j++){
  53.                     BoundedSlicesSData printAux = queue.get(j);
  54.                     if(printAux.position==curr.position){
  55.                         continue;
  56.                     }
  57.                     printResult(printAux.position, curr.position);
  58.                 }
  59.             }//if
  60.         }//for
  61.     }
  63.     public static void printResult(int i, int j){
  64.         if(i < j){
  65.             System.out.println(“(“+i+”,”+j+”)”);
  66.         }
  67.         else{
  68.             System.out.println(“(“+j+”,”+i+”)”);
  69.         }
  70.     }
  71. }
  72. /*
  73.  * The queue should store both value and position. So create this class for convinent.
  74.  */
  75. class BoundedSlicesSData{
  76.     int value;
  77.     int position;
  78.     public BoundedSlicesSData(){}
  79.     public BoundedSlicesSData(int value, int position){
  80.         this.value = value;
  81.         this.position = position;
  82.     }
  83. }
  84. /*
  85.  * help to sort the BoundedSlicesSData queue
  86.  */
  87. class BoundedSlicesSDataComparator implements Comparator < BoundedSlicesSData>{
  88.     public int compare(BoundedSlicesSData b1, BoundedSlicesSData b2){
  89.         return b1.value – b2.value;
  90.     }
  91. }

Sort according to another array

Problem:

The input is a sequence x1,x2,…,xn of integers in an arbitrary order, and another sequence a1,a2,..,an of distinct integers from 1 to n (namely a1,a2,…,an is a permutation of 1, 2,…, n). Both sequences are given as arrays. Design an 0(n logn) algorithm to order the first sequence according to the order imposed by the permutation. In other words, for each i, Xi should appear in the position given in ai.

For example, if x = 17, 5, 1,9, and a = 3, 2, 4, 1, then the outcome should be x = 9, 5, 17, 1. The algorithm should be in-place, so you cannot use an additional array.

Take the following analysis:



I use the seq[] to store the position indicating where the element should put. After visited a element i, I change the seq[i] to negative. By checking if the seq[i] is negative, I can know if this element has ever been visited or no.
Code:

  1. public class SortAccordingToAnArray {
  2.     public static void main(String[] args) {
  3.         int[] arr = { 5, 12, 14, 27, 3, 2, 13, 17, 7, 21 };
  4.         int[] index = { 3, 6, 2, 9, 7, 1, 4, 8, 5, 10 };
  5.         System.out.println(“Values: ” + Arrays.toString(arr));
  6.         System.out.println(” Index: ” + Arrays.toString(index));
  7.         putRightPosition(arr, index);
  8.         System.out.println(“Values: ” + Arrays.toString(arr));
  9.     }
  11.     public static void putRightPosition(int[] num, int[] seq){
  12.         for(int i=0;i
  13.             if(seq[i]<0){
  14.                 continue;
  15.             }
  16.             int curr_value = num[i];
  17.             int next_pos = seq[i]-1;
  18.             seq[i] = -seq[i];
  19.             while(true){
  20.                 int tmp = num[next_pos];
  21.                 num[next_pos] = curr_value;
  22.                 curr_value = tmp;
  23.                 tmp = next_pos;
  24.                 next_pos = seq[next_pos]-1;
  25.                 if(next_pos<0){
  26.                     break;
  27.                 }
  28.                 seq[tmp] = -seq[tmp];
  29.             }//while
  30.         }//for
  31.     }
  32. }

Crack razzle adventure game – dfs, backtrack implementation

My mother-in-law likes a game in ipad. It is called Ruzzle Adventure. The idea is to find the word in a letter matrix. The longer the word is, the higher score you will have. For example, in the following letter arrays, you can find a ‘gates’ word.

Today, I think of cracking this game, find the potiential words it has.

The idea is to traverse each letter to its neighbor, go on and on, and see what word it can reach. And design a dictionary, get word from the dictionary.

I define some parameters to help.
puzzleCharArray[][], stores the characters of the puzzle game:

  1.     public static char[][] puzzleCharArrzy = {
  2.         {‘s’, ‘t’, ‘s’, ‘t’},
  3.         {‘w’, ‘o’, ‘p’, ‘h’},
  4.         {‘h’, ‘r’, ‘e’, ‘t’},
  5.         {‘a’, ‘d’, ‘t’, ‘o’}
  6.     };

stepHis[][], is to avoid duplicately visit to a puzzle letter. When I do backtrack, this stores what letters has already visited.

The most important is the dfs function. The boundary of it includes:
1. the (x,y) position should be within the array. i.e. can’t go to (-1,0)
2. The visited (x,y) shouldn’t be visited for 2nd time, which is helped by stepHis[][]
The return policies are:
If the current word is not found, then return.
If the current word is a prefix of a word, go on searching its neighbor.
If the current word is found in dictionary, add it to result list, and go on searching its neighbor.
The dfs code and comments are showed below:

  1.     /*
  2.      * Use dfs to find the possible word. Save the result in ArrayList result.
  3.      * (x,y) indicate the current position in charPuzzle
  4.      */
  5.     public static void dfsWord(String word, int wordPos, int x, int y, boolean[][] stepHis, ArrayList result){
  6.         if(x<0||x>=puzzleCharArrzy.length||y<0||y>=puzzleCharArrzy[0].length||stepHis[x][y]==true){
  7.             return;    //if (x,y) is in wrong position, or (x,y) is already traversed before, then return.
  8.         }
  9.         stepHis[x][y] = true;    //mark this (x,y) as traversed.
  10.         String currWord = word.substring(0, wordPos) + puzzleCharArrzy[x][y];    //update the current word
  11.         int foundResult = searchWord(currWord);    //find find in dictionary
  12.         if(foundResult==NOT_FOUND){    //not found, then return
  13.             stepHis[x][y] = false;
  14.             return;
  15.         }
  16.         if(foundResult==WORD_FOUND&&wordPos!=0){
  17.             result.add(currWord);    //if found, then add to result list. Besides, it can go on finding the larger word
  18.         }
  19.         dfsWord(currWord, wordPos+1, x-1, y-1, stepHis, result);
  20.         dfsWord(currWord, wordPos+1, x-1, y, stepHis, result);
  21.         dfsWord(currWord, wordPos+1, x-1, y+1, stepHis, result);
  22.         dfsWord(currWord, wordPos+1, x, y-1, stepHis, result);
  23.         dfsWord(currWord, wordPos+1, x, y+1, stepHis, result);
  24.         dfsWord(currWord, wordPos+1, x+1, y-1, stepHis, result);
  25.         dfsWord(currWord, wordPos+1, x+1, y, stepHis, result);
  26.         dfsWord(currWord, wordPos+1, x+1, y+1, stepHis, result);
  27.         stepHis[x][y] = false;    //unmark the step.
  28.     }

Design the dictionary. Read the dictionary into a String[] array. Design a searchWord() function to check is a word is in the dictionary. The return result can be 3 types:
int WORD_FOUND=1, the word is in the dictionary.
int NOT_FOUNC=2, the word doesn’t exist in dictionary.
int PREFIX_FOUND=0, the word is a prefix of a certain word in the dictionary. For example, ‘appl’ is a prefix of ‘apple’.

I downloaded a txt file dictionary. It has alphebatic order. Load the dictionary to the String[].

The result is like below.
Input array:
public static char[][] puzzleCharArrzy = {
{‘s’, ‘t’, ‘s’, ‘t’},
{‘w’, ‘o’, ‘p’, ‘h’},
{‘h’, ‘r’, ‘e’, ‘t’},
{‘a’, ‘d’, ‘t’, ‘o’}
};

Output of top 10:
potsherd
sported
stored
sorted
stored
sorted
spored
whored
posher
ported

The complete code is here:

  1. package wordpuzzle;
  2. import java.io.BufferedReader;
  3. import java.io.FileReader;
  4. import java.util.ArrayList;
  5. import java.util.Collections;
  6. import java.util.Comparator;
  8. public class WordUtil {
  10.     public static String[] dict;
  11.     public static final int DICT_LENGTH = 109583; //the word length of the dictionary
  12.     public static final String DICT_PATH = “C:/Users/lipeng/Work Space/WordPuzzle/wordsEn.txt”;
  13.     public static final int PREFIX_FOUND = 0;
  14.     public static final int WORD_FOUND = 1;
  15.     public static final int NOT_FOUND = 2;
  16.     public static final String puzzleChars = “hahalritudeanreutkdepdvit”;
  17.     public static final int puzzleLen = 5;
  18.     public static char[][] puzzleCharArrzy = {
  19.         {‘s’, ‘t’, ‘s’, ‘t’},
  20.         {‘w’, ‘o’, ‘p’, ‘h’},
  21.         {‘h’, ‘r’, ‘e’, ‘t’},
  22.         {‘a’, ‘d’, ‘t’, ‘o’}
  23.     };
  25.     public static void main(String[] args) {
  26.         WordUtil.Init();
  27.         ArrayList result = findWord();
  28.         result = arraySort(result);
  29.         printTop10(result);
  30.     }
  32.     /*
  33.      * sort the result descend
  34.      */
  35.     public static ArrayList arraySort(ArrayList result){
  36.         ArrayList returnResult = new ArrayList();
  37.         while(!result.isEmpty()){
  38.             int maxPos = -1;
  39.             int maxLen = Integer.MIN_VALUE;
  40.             String curr;
  41.             for(int i=0;i < result.size();i++){
  42.                 curr = result.get(i);
  43.                 if(curr.length()>maxLen){
  44.                     maxLen = curr.length();
  45.                     maxPos = i;
  46.                 }
  47.             }
  48.             curr = result.remove(maxPos);
  49.             returnResult.add(curr);
  50.         }
  51.         return returnResult;
  52.     }
  54.     public static void printResult(ArrayList result){
  55.         for(int i=0;i < result.size();i++){
  56.             System.out.println(result.get(i));
  57.         }
  58.     }
  60.     /*
  61.      * print the top 10 result
  62.      */
  63.     public static void printTop10(ArrayList result){
  64.         for(int i=0;i
  65.             System.out.println(result.get(i));
  66.         }
  67.     }
  69.     /*
  70.      * traverse all the position, try to find the word.
  71.      * Use stepHis to record if a position has been traversed before.
  72.      */
  73.     public static ArrayList findWord(){
  74.         boolean[][] stepHis = new boolean[puzzleCharArrzy.length][puzzleCharArrzy[0].length];
  75.         ArrayList result = new ArrayList();
  76.         for(int i=0;i < puzzleCharArrzy.length;i++){
  77.             for(int j=0;j < puzzleCharArrzy[0].length;j++){
  78.                 dfsWord(“”, 0, i, j, stepHis, result);
  79.             }
  80.         }
  81.         return result;
  82.     }
  84.     /*
  85.      * Use dfs to find the possible word. Save the result in ArrayList result.
  86.      * (x,y) indicate the current position in charPuzzle
  87.      */
  88.     public static void dfsWord(String word, int wordPos, int x, int y, boolean[][] stepHis, ArrayList result){
  89.         if(x<0||x>=puzzleCharArrzy.length||y<0||y>=puzzleCharArrzy[0].length||stepHis[x][y]==true){
  90.             return;    //if (x,y) is in wrong position, or (x,y) is already traversed before, then return.
  91.         }
  92.         stepHis[x][y] = true;    //mark this (x,y) as traversed.
  93.         String currWord = word.substring(0, wordPos) + puzzleCharArrzy[x][y];    //update the current word
  94.         int foundResult = searchWord(currWord);    //find find in dictionary
  95.         if(foundResult==NOT_FOUND){    //not found, then return
  96.             stepHis[x][y] = false;
  97.             return;
  98.         }
  99.         if(foundResult==WORD_FOUND&&wordPos!=0){
  100.             result.add(currWord);    //if found, then add to result list. Besides, it can go on finding the larger word
  101.         }
  102.         dfsWord(currWord, wordPos+1, x-1, y-1, stepHis, result);
  103.         dfsWord(currWord, wordPos+1, x-1, y, stepHis, result);
  104.         dfsWord(currWord, wordPos+1, x-1, y+1, stepHis, result);
  105.         dfsWord(currWord, wordPos+1, x, y-1, stepHis, result);
  106.         dfsWord(currWord, wordPos+1, x, y+1, stepHis, result);
  107.         dfsWord(currWord, wordPos+1, x+1, y-1, stepHis, result);
  108.         dfsWord(currWord, wordPos+1, x+1, y, stepHis, result);
  109.         dfsWord(currWord, wordPos+1, x+1, y+1, stepHis, result);
  110.         stepHis[x][y] = false;    //unmark the step.
  111.     }
  113.     public static int searchWord(String word){
  114.         return binarySearch(word, 0, DICT_LENGTH-1);
  115.     }
  117.     /*
  118.      * use binarysearch to find the word in the dict.
  119.      */
  120.     public static int binarySearch(String word, int start, int end){
  121.         if(start>end){    //time to result result
  122.             if(dict[start].length()>=word.length()&&dict[start].subSequence(0, word.length()).equals(word)){
  123.                 return PREFIX_FOUND;    //the word is a part of word in dict. it can still go on searching
  124.             }
  125.             if(dict[end].length()>=word.length()&&dict[end].subSequence(0, word.length()).equals(word)){
  126.                 return PREFIX_FOUND;    //the word is a part of word in dict. it can still go on searching
  127.             }
  128.             return NOT_FOUND;
  129.         }
  130.         int mid = (start+end)/2;
  131.         int cmp = dict[mid].compareTo(word);
  132.         if(cmp<0){
  133.             return binarySearch(word, mid+1, end);
  134.         }
  135.         else if(cmp>0){
  136.             return binarySearch(word, start, mid-1);
  137.         }
  138.         else{
  139.             return WORD_FOUND;
  140.         }
  142.     }
  144.     public static void Init(){
  145.         dict = readFile(DICT_PATH);
  146.     }
  148.     /*
  149.      * to initial the puzzleChar by inputting a string.
  150.      */
  151.     public static void Init2(){
  152.         puzzleCharArrzy = new char[puzzleLen][puzzleLen];
  153.         for(int i=0;i<  puzzleLen;i++){
  154.             for(int j=0;j < puzzleLen;j++){
  155.                 puzzleCharArrzy[i][j] = puzzleChars.charAt(puzzleLen*i+j);
  156.             }
  157.         }
  158.         dict = readFile(DICT_PATH);
  159.     }
  161.     /*
  162.      * read the dict file from dict.txt
  163.      */
  164.     public static String[] readFile(String file){
  165.         String[] dict = new String[DICT_LENGTH];
  166.         try{
  167.             BufferedReader br = new BufferedReader(new FileReader(file));
  168.             String line;
  169.             int i=0;
  170.             while ((line = br.readLine()) != null) {
  171.                 dict[i] = line;
  172.                 i++;
  173.             }
  174.             br.close();
  175.         }catch(Exception e){
  176.             e.printStackTrace();
  177.         }
  178.         return dict;
  179.     }
  180. }

download the dictionary here: link

Partition an array by an uncertain pivot, only by one trip

Toady, I read about bolts and nuts problem. The method is similar to quicksort. But one difference is that, we should partition the array by an uncertain pivot. It means we don’t know where the pivot is in the array.
The normal way should be traverse the array for one time, and found the position of pivot. Then do quicksort as usual. By that, it can finish it in O(n) time, yet with traversal on the array for 2 times.

But I believe there is way that it only traverse for one time. After done hours research, I found this method. Which I should thank kartik kukreja for providing me this idea, link. By this method, we can finish it by one trip on the array.

The idea is that we keep a ‘higher group’ in the traversal, which means those elements which are larger than the pivot. And we record the start position of the ‘higher group’. Let me take an example:
Assume we want to partition the following array by a pivot of 5. If current array is:
3 9 7 6 2 1 5 4 8
Always maintain the ‘higher group’ in the one trip.
Next, we need to judge 2. Since 2 is less than 5, so we swap 2 with the first element of the higher group. So the next array is:
3 2 7 6 9 1 5 4 8
By this, higher group moves forward by 1. We should record the 1st element position in higher group.
Then next:
3 2 1 6 9 7 5 4 8
When we encounter the pivot 5, we swap it with the last element. So the next is:
3 2 1 6 9 7 8 4 5
After we’ve done with 2nd to last element, it is like this:
3 2 1 4 9 7 8 6 5
Now, we swap the last element(pivot) with 1st element position in higher group. The final result would be:
3 2 1 4 5 7 8 6 9 

This is the code:

public static int partition(int[] arr, int low, int high, int pivot) {
    int i = low;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot){
            swap(arr, i, j);
            i++;
        } else if(arr[j] == pivot){
            swap(arr, j, high);
            j--;
        }
    }
    swap(arr, i, high);
    return i;
}
public static void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

Find median or Kth number in 2 sorted array

Problem
The idea of the solution is very easy: use binary search. But when I wrote it, it took me a long time to verify the code.
For example, find the 4th number from a=[2, 4, 6, 8] and b=[5,9]
The result should be 6.

Solution

Basic idea:
a=[0,…,a_start, …, a_mid,…,a_end,…,a.length-1]
b=[0,…,b_start, …, b_mid,…,b_end,…,b.length-1]
Let half_length be number of element in a[a_start,…,a_mid] and b[b_start,…,b_mid].
find the kth from a and b.
Assume a[a_mid] is larger than b[b_mid].
If k < half_length, then we know that kth number can’t be in higher part of a, a[a_mid,…,a_end]. So next, we search a[a_start,…,a_mid-1] and b[b_start,…,b_end]
If k>=half_length, then we know that kth number can’t be in lower part of b, b[b_start,…,b_mid]. So next, we search a[a_start, a_end] and b[b_mid+1,…,b_end]. Meanwhile, we should set new value to k. k=k-(b_mid-b_start+1)

Return result when:
if(a_start>a_end){
return b[b_start+k-1];
}
if(b_start>b_end){
return a[a_start+k-1];
}

Case analysis1

a[a_mid]
half_length = 3
k>=half_length, so cut off lower part of a[], and k should deduct 2, which is 1, 3

1

b[] is out of bound, return a[a_s+k-1], which is 5

Case analysis2

a[a_mid]>b[b_mid]
half_length = 5
k>=half_length, so cut off lower part of b[], and k should deduct 3, which is 2, 4

a[a_mid]half_length = 4
k

b[] is out of bound, return a[a_s+k-1]=a[0+3-1], which is 5

My code is below:

  1. public class MedianIn2SortedArray {
  3.     public static void main(String[] args) {
  4.         int[] a = {1,3,5,9,10};
  5.         int[] b = {2,4,6,8};
  6.         int median = findMedian(a,b);
  7.         System.out.println(median);
  8.     }
  10.     public static int findMedian(int[] a, int[] b){
  11.         int k = (a.length + b.length)/2;
  12.         return findK(a, b, k, 0, a.length-1, 0, b.length-1);
  14.     }
  16.     public static int findK(int[] a, int[] b, int k, int a_start, int a_end, int b_start, int b_end){
  17.         if(a_start>a_end){
  18.             return b[b_start+k-1];
  19.         }
  20.         if(b_start>b_end){
  21.             return a[a_start+k-1];
  22.         }
  23.         int a_mid = a_start+(a_end-a_start)/2;
  24.         int b_mid = b_start+(b_end-b_start)/2;
  25.         int half_len = a_mid-a_start+b_mid-b_start+2;
  26.         if(a[a_mid]>b[b_mid]){
  27.             if(k
  28.                 //cut off the high part of large array, which is high of a[]
  29.                 return findK(a, b, k, a_start, a_mid-1, b_start, b_end);
  30.             }
  31.             else{
  32.                 //cut off the low part of small array, which is low of b[]
  33.                 return findK(a, b, k-(b_mid-b_start+1),a_start, a_end, b_mid+1, b_end);
  34.             }
  35.         }
  36.         else{
  37.             if(k
  38.                 //cut off the high part of large array, which is high of b[]
  39.                 return findK(a, b, k, a_start, a_end, b_start, b_mid-1);
  40.             }
  41.             else{
  42.                 //cut off the low part of small array, which is low of a[]
  43.                 return findK(a, b, k-(a_mid-a_start+1), a_mid+1, a_end, b_start, b_end);
  44.             }
  45.         }
  46.     }
  47. }

Balance server capacity

Problem description:
There are at most eight servers in a data center. Each server has got a capacity/memory limit. There can be at most 8 tasks that need to be scheduled on those servers. Each task requires certain capacity/memory to run, and each server can handle multiple tasks as long as the capacity limit is not hit. Write a program to see if all of the given tasks can be scheduled or not on the servers?

Ex:
Servers capacity limits: 8, 16, 8, 32
Tasks capacity needs: 18, 4, 8, 4, 6, 6, 8, 8
For this example, the program should say ‘true’.

Ex2:
Server capacity limits: 1, 3
Task capacity needs: 4
For this example, program should return false.

Solution:
First impression would be using greedy algorith. Each time, put the max task in the max capacity server. But it won’t find the best answer for a lot of times. An counter-example is: Server capacity [4, 3], task[3, 2, 2].

So the solution should be use recursion to traverse the whole result possibilities. The sample code is following. It is a easy recursion case, no comment :)

  1. public class ServerCapacityBalancer {
  3.     public static void main(String[] args) {
  4.         int[] server = {8, 16, 8, 32};
  5.         int[] task = {18,8,8,8,6,6,4,4};
  6.         int[] result = balanceServer(server, task);
  7.         System.out.println(Arrays.toString(result));
  9.     }
  12.     public static int[] balanceServer(int[] server, int[] task){
  13.         if(server==null||task==null){
  14.             return null;
  15.         }
  16.         int[] result = new int[task.length];
  17.         for(int i=0;i
  18.             result[i] = -1;
  19.         }
  20.         balanceServerUtil(server, task, 0, result);
  21.         return result;
  22.     }
  24.     //put task[n] in the server, and save the result
  25.     public static boolean balanceServerUtil(int[] server, int[] task, int n, int[] result){
  26.         if(n>=task.length){
  27.             return true;
  28.         }
  29.         for(int i=0;i
  30.             if(server[i]>=task[n]){
  31.                 server[i] -= task[n];
  32.                 result[n] = i;
  33.                 if(balanceServerUtil(server, task, n+1, result)){
  34.                     return true;
  35.                 }
  36.                 server[i] += task[n];
  37.                 result[n] = -1;
  38.             }
  39.         }
  40.         return false;
  41.     }
  42. }

Find median out of 5 numbers

In quickselect, it requires to find the median out of the group of 5 numbers. Here I found a way from stackoverflow link. It requires 6 comparisons.

  1. Start a mergesort with the first 4 elements and order each pair (2 comparisons)
  2. Compare the two lower ones of each pair and eliminate the lowest one from the possibilities (3 comparisons)
  3. Add in the 5th number set aside to the number without a pair and compare the two (4 comparisons)
  4. Compare the two lowest of the two new pairs and eliminate the lower one (5 comparisons)
  5. Compare the one by itself and the lower of the last pair and the lower number is the medianThe possible median is within the parentesis

Find the closest leaf in a Binary Tree

Problem description:
Given a Binary Tree and a key ‘k’, find distance of the closest leaf from ‘k’.

              A
            /    \    
           B       C
                 /   \  
                E     F   
               /       \
              G         H
             / \       /
            I   J     K
Closest key to 'H' is 'K', so distance is 1 for 'H'
Closest key to 'C' is 'B', so distance is 2 for 'C'
Closest key to 'E' is either 'I' or 'J', so distance is 2 for 'E' 
Closest key to 'B' is 'B' itself, so distance is 0 for 'B'

Solution:
Find all the ancestry of the target node, and the min-depth of them. Distance from target to its ancestry, plus distance from ancestry to ancestry’s min-depth leaf is a potential result. Among them and the min-depth of the target node itself, find the smallest one.

The traversal process is:
For each node, it traverse the left and right sub-tree, and get the min-depth from each sub-tree. And it will return min-depth to its ancestry.
After traverse each sub-tree, if it found the target in either sub-tree, this node is treated as an ancestry of the target node. And the ancestry information should be stored.

In my code, I define a AncestryInfo class, to restore the ancestry information:
class AncestryInfo{
int[] ancestry_record;    //records the ancestry nodes from target node. Target node is also included in position 0;
int[] ancestry_level;    //records the min deep of ancestry nodes.
int[] leaf;        //records the leaf which the ancestry nodes reach to the min deep
}

  1. public class FindNearestLeaf {
  3.     public static void main(String[] args) {
  4.         Tree tree = Tree.getTree();
  5.         findNearestLeaf(tree, 7);
  6.         System.out.println();
  7.     }
  9.     public static void findNearestLeaf(Tree tree, int value){
  10.         AncestryInfo ancestry = new AncestryInfo();
  11.         //traverse the tree, to find the relative information
  12.         findNearestLeafUtil(tree, value, ancestry, new MyInteger(), new MyInteger(), new MyBoolean());
  13.         int leaf = ancestry.leaf[0];
  14.         int distance = ancestry.ancestry_level[0];
  15.         for(int i=1;i
  16.             if(i-0+ancestry.ancestry_level[i]
  17.                 distance = i-0+ancestry.ancestry_level[i];
  18.                 leaf = ancestry.leaf[i];
  19.             }
  20.         }
  21.         distance–;
  22.         System.out.println(“Nearest Leaf:” + leaf + “\tDistance:” + distance);
  23.     }
  25.     public static void findNearestLeafUtil(Tree root, int value, AncestryInfo anc, MyInteger depth, MyInteger leaf, MyBoolean found){
  26.         if(root==null){
  27.             return;
  28.         }
  29.         MyInteger l_depth = new MyInteger(Integer.MAX_VALUE);
  30.         MyInteger r_depth = new MyInteger(Integer.MAX_VALUE);
  31.         MyBoolean l_found = new MyBoolean();
  32.         MyBoolean r_found = new MyBoolean();
  33.         MyInteger l_leaf = new MyInteger();
  34.         MyInteger r_leaf = new MyInteger();
  35.         if(root.left!=null){
  36.             findNearestLeafUtil(root.left, value, anc, l_depth, l_leaf, l_found);
  37.         }
  38.         if(root.right!=null){
  39.             findNearestLeafUtil(root.right, value, anc, r_depth, r_leaf, r_found);
  40.         }
  41.         if(root.left==null&&root.right==null){    // current node is a leaf
  42.             depth.i = 1;
  43.             leaf.i = root.value;
  44.         }
  45.         else{    //if current node is not a leaf, get the depth from information of 2 sub tress.
  46.             depth.i = Math.min(l_depth.i, r_depth.i) + 1;
  47.             leaf.i = l_depth.i
  48.         }
  49.         found.bool = l_found.bool||r_found.bool;
  50.         if(found.bool){
  51.             //if the target node is already found, then current node is treated as an ancestry. So store the ancestry information.
  52.             anc.ancestry_record = Arrays.copyOf(anc.ancestry_record, anc.ancestry_record.length+1);
  53.             anc.ancestry_record[anc.ancestry_record.length-1] = root.value;
  54.             anc.ancestry_level = Arrays.copyOf(anc.ancestry_level, anc.ancestry_level.length+1);
  55.             anc.ancestry_level[anc.ancestry_level.length-1] = depth.i;
  56.             anc.leaf = Arrays.copyOf(anc.leaf, anc.leaf.length+1);
  57.             anc.leaf[anc.leaf.length-1] = leaf.i;
  58.             return;
  59.         }
  60.         if(root.value==value){    //current node is the target, initial the ancestry information
  61.             found.bool = true;
  62.             anc.ancestry_record = new int[]{root.value};
  63.             anc.ancestry_level = new int[]{depth.i};
  64.             anc.leaf = new int[]{leaf.i};
  65.             return;
  66.         }
  67.         return;
  68.     }
  69. }
  71. class AncestryInfo{
  72.     int[] ancestry_record;    //records the ancestry nodes from target node. Target node is also included in position 0;
  73.     int[] ancestry_level;    //records the min deep of ancestry nodes.
  74.     int[] leaf;        //records the leaf which the ancestry nodes reach to the min deep
  75. }
  76. class MyBoolean {
  77.     public boolean bool;
  78.     public MyBoolean(boolean bool){
  79.         this.bool = bool;
  80.     }
  81.     public MyBoolean(){
  82.         this.bool = false;
  83.     }
  84.     public String toString(){
  85.         return String.valueOf(bool);
  86.     }
  87. }
  89. class MyInteger{
  90.     public int i = 0;
  91.     public MyInteger(int i){
  92.         this.i = i;
  93.     }
  94.     public MyInteger(){}
  96.     public String toString(){
  97.         return String.valueOf(i);
  98.     }
  99. }
  101. class Tree{
  102.     public Tree(int value){
  103.         this.value = value;
  104.     }
  105.     public Tree(String value){
  106.         this.valueString = value;
  107.     }
  108.     public Tree left;
  109.     public Tree right;
  110.     public int value;
  111.     public String valueString;
  112.     public static Tree getTree(){
  113.         Tree t18 = new Tree(18);
  114.         Tree t17 = new Tree(17);
  115.         Tree t16 = new Tree(16);
  116.         Tree t15 = new Tree(15);
  117.         Tree t14 = new Tree(14);
  118.         Tree t13 = new Tree(13);
  119.         Tree t12 = new Tree(12);
  120.         Tree t11 = new Tree(11);
  121.         Tree t10 = new Tree(10);
  122.         Tree t9 = new Tree(9);
  123.         Tree t8 = new Tree(8);
  124.         Tree t7 = new Tree(7);
  125.         Tree t6 = new Tree(6);
  126.         Tree t5 = new Tree(5);
  127.         Tree t4 = new Tree(4);
  128.         Tree t3 = new Tree(3);
  129.         Tree t2 = new Tree(2);
  130.         Tree t1 = new Tree(1);
  131.         t8.left = t9;
  132.         t6.left = t8;
  133.         t5.right = t7;
  134.         t4.left = t5;
  135.         t4.right = t6;
  136.         t2.left = t4;
  137.         t1.left = t2;
  138.         t1.right = t3;
  139.         t6.right = t10;
  140.         t3.left = t11;
  141.         t3.right = t12;
  142.         t12.left = t13;
  143.         t12.right = t14;
  144.         t13.left = t15;
  145.         t13.right = t16;
  146.         t16.right = t17;
  147.         t17.right = t18;
  148.         return t1;
  149.     }
  150. }

Patricia Tree

In the structure of my PatriciaTree, it has following parameters:
char c, indicate the char the node has.
HashMap<Character, PatriciaTree> children, indicate the children the node has.
String leftString, this a bit difficult to explain. So let me raise an example. If root only has a word “dog”. So the structure would be like:
.root…….
..\………
…d(og)….
But not:
.root…….
..\………
…d……..
….\…….
…..o……
……\…..
…….g….
So, in this case, I use the leftString to store the string after ‘d’, which is ‘og’. And I call the node d(og) string leaf.

is that I define 4 types of nodes:
1. STATE_ROOT, the root the patricia tree.
2. STATE_STRINGLEAF, it is a leaf, and it has left string in it. Like the example I showed above.
3. STATE_LEAF, it is a leaf, and it doesn’t has left string.
For example, the ‘g’ and ‘t’ nodes are both LEAF node, but not string leaf node.
.root………
..\………..
…d……….
….\………
…..o……..
…../.\…….
…g….t…..
4. STATE_MIDDLE, in the above case, the ‘d’ and ‘o’ are middle nodes.

In the following code. it demonstrate how to build a patricia tree, and the method to find if a word exists in a patricia tree.

  1. import java.util.HashMap;
  2. public class PatriciaTree {
  3.     public static final int STATE_ROOT = 0;
  4.     public static final int STATE_LEAF = 1;
  5.     public static final int STATE_STRINGLEAF = 2;
  6.     public static final int STATE_MIDDLE = 3;
  8.     char c;
  9.     HashMap<Character, PatriciaTree> children;
  10.     int state;    //0 is root, 1 is leaf, 2 is leaf with string, 3 is middle
  11.     String leftString;    //if the node is leaf with string, it has a rest word
  12.     PatriciaTree parent;
  14.     //store word into this PatriciaTree, word starts from pos
  15.     public boolean addNode(String word, int pos, PatriciaTree parent){
  16.         if(word==null||pos>=word.length()){
  17.             return false;
  18.         }
  19.         PatriciaTree child;
  20.         if(state==STATE_ROOT||state==STATE_MIDDLE){
  21.             //if it is root, then find if it children have tree with character pos[0]
  22.             child = children.get(word.charAt(pos));
  23.             if(child==null){    //it doesn’t has word.charAt[pos], then create tree under it.
  24.                 child = new PatriciaTree(word, pos, this);
  25.                 children.put(word.charAt(pos), child);
  26.                 return true;
  27.             }
  28.             return child.addNode(word, pos+1, this);    //it has char, then create tree under its child.
  29.         }
  30.         if(state==STATE_LEAF){
  31.             //now it is leaf, and there is still chars, then just change it to a STRINGLEAF
  32.             this.state = STATE_STRINGLEAF;
  33.             this.leftString = word.substring(pos, word.length()-1);
  34.             return true;
  35.         }
  36.         if(state==STATE_STRINGLEAF){
  37.             if(word.charAt(pos)!=leftString.charAt(0)){
  38.                 //1st char of leftString doesn’t match word[pos], so create the tree under it.
  39.                 //And create leftString as its subtree.
  40.                 child = new PatriciaTree(word, pos, this);
  41.                 children.put(word.charAt(pos), child);
  42.                 child = new PatriciaTree(leftString, 0, this);
  43.                 children.put(leftString.charAt(0), child);
  44.                 this.state = STATE_MIDDLE;
  45.                 return true;
  46.             }
  47.             //1st char of leftString match word[pos], so break the stringleaf into middle,
  48.             //and create its child with char of the 1st leftString
  49.             this.state = STATE_MIDDLE;
  50.             child = new PatriciaTree(leftString, 0, this);
  51.             children.put(leftString.charAt(0), child);
  52.             this.leftString = “”;
  53.             child.addNode(word, pos+1, child);
  54.             return true;
  55.         }
  57.         return false;
  58.     }
  60.     public boolean findString(String word, int pos){
  61.         if(pos>=word.length()){
  62.             if(this.state==STATE_MIDDLE){
  63.                 return false;    //is in the middle, is not counted as found.
  64.             }
  65.             if(this.state==STATE_LEAF){
  66.                 return true;    //return true if this is leaf
  67.             }
  68.             return false;
  69.         }
  70.         PatriciaTree child;
  71.         if(this.state==STATE_ROOT||this.state==STATE_MIDDLE){
  72.             child = this.children.get(word.charAt(pos));
  73.             return child==null?false:child.findString(word, pos+1);
  74.         }
  75.         if(this.state==STATE_LEAF){
  76.             return false;    //the word is larger than the leaf string
  77.         }
  78.         if(this.state==STATE_STRINGLEAF){
  79.             String strInWord = word.substring(pos, word.length());
  80.             if(leftString.equals(strInWord)){
  81.                 return true;
  82.             }
  83.         }
  84.         return false;
  85.     }
  87.     public PatriciaTree(){
  88.         this.children = new HashMap<Character, PatriciaTree>();
  89.     }
  91.     public PatriciaTree(String word, int pos, PatriciaTree parent){
  92.         this.c = word.charAt(pos);
  93.         this.parent = parent;
  94.         this.state = STATE_LEAF;
  95.         this.children = new HashMap<Character, PatriciaTree>();
  96.         if(pos<word.length()-1){
  97.             this.state = STATE_STRINGLEAF;
  98.             this.leftString = word.substring(pos+1, word.length());
  99.         }
  100.     }
  102.     public static void main(String[] args) {
  103.         PatriciaTree root = new PatriciaTree();
  104.         root.state = STATE_ROOT;
  105.         String[] words = {“zebra”, “zero”, “dog”, “dot”, “ducks”, “duh”, “ducky”};
  106.         for(int i=0;i<words.length;i++){
  107.             root.addNode(words[i], 0, root);
  108.         }
  109.         System.out.println(root.findString(“dogg”, 0));
  110.     }
  111. }

Find weighted median in matrix

Evolve the problem to 2-dimension array.
There is a matrix, m x n. Several groups of people locate at some certain spots. In the following example, there are three groups and the number 4 indicates there are four people in this group. Now we want to find a meeting point in the matrix so that the cost of all groups moving to that point is the minimum.

The solution is that find the weighted median from x and y direction.
For example, the matrix is as follow:

Then, the sequence in x direction is 4 3 1 6 5, the sequence in y direction is 7 4 5 3. We find the weighted median both in x and y direction.

For the sequence 7 4 5 3, we think like this, there are 4 cities in a line, which continuously locate at 1, 2, 3, 4. The weight of them are 7, 4, 5, 3.
So the sequence is 1 1 1 1 1 1 1 2 2 2 2 3 3 3 3 3 4 4 4. So the median is 10th , which is 2, which symbolizes 4. By the same way, we can find the 10th element in 4 3 1 6 5 exists in 6. So the weighted median is array[3][1].