group sort

This post is responding to my friend Li Peng's page. http://allenlipeng47.com/PersonalPage/index/view/173/nkey

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 counting sort like sort algorithms are the ones can be done in O(n).

public static char[] sort(char[] strs, char[] comp){

char[] sorted = new char[strs.length];

int[] count = new int[256]; 

for(char s : strs){

count[s]++;

}

int index = 0;

for(char c : comp){

int num = count[c];

while(num-->0)

sorted[index++] = c;

}

return sorted;

}

if it is required to sort in place:

public static char[] sort(char[] strs, char[] comp){

int[] count = new int[256]; 

for(char s : strs){

count[s]++;

}

int index = 0;

for(char c : comp){

int num = count[c];

while(num-->0)

strs[index++] = c;

}

return strs;

}

Sort the Double linked list in place:

/*

* in place sort DLL of Rs, Gs and Bs, so that Rs in front, followed by Gs and Bs

* assume DLL has the sentinel node to separate the head and tail

*/

public static void sortDLL(DLL head, DLL sentinel){
final char[] setOfChars= new char[]{'R', 'G', 'B'};

DLL curr, p;
curr = p = head;

//push all R to the front

while(p != sentinel){
if(p.data == 'R'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.next;
}
p = p.next;
}

 

curr = p = head.pre.pre;

//push all B to the back

while(p != sentinel){
if(p.data == 'B'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.pre;
}
p = p.pre;
}
}

How about Singled LinkedList?

//here I use DLL node to represent the SLL

//in this case DLL.pre = null

void sortSLL(DLL head){
DLL curr = head, p = head;

//push all Rs to the front

while(p != null){
if(p.data == 'R'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.next;
}
p = p.next;
}

//now all Rs at front and curr points at candidate 

//position for next char which is G

//push all Gs to the front

p = curr;
while(p != null){
if(p.data == 'G'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.next;
}
p = p.next;
}
}

Calculate maximum qaz value of a number array

This problem can be found at careercup site: http://www.careercup.com/question?id=5649103830646784

Qaz value for each element in a number array is defined as the number of elements whose both value and index are larger than current element. Maximum qaz value of array is the maximum of the qaz values.

Many answers from careercup site use mergeSort algorithm, which is pretty awesome. Since the time complexity requirement is O(nlgn), I assume other sorting approach will work too. Here I use order statistics binary search tree. To better understand order statistics binary search tree, please see my blog here: http://blueocean-penn.blogspot.com/2015/01/order-statistics-binary-search-tree.html

What is the caveat of the following implementation? I will leave it to readers. ;)

Calculate Qaz using binary search tree.

public static class QNode{

int val;

int size;

QNode left, right;

QNode(int v, int s){val = v; size = s;}

//time complexity O(n), n is the tree height 

void insert(int target){

size++;

if(target<=this.val){//smaller or equal goes left

if(this.left==null)

this.left = new QNode(target, 1);

else

this.left.insert(target);

}else{

if(this.right==null)

this.right = new QNode(target, 1);

else

this.right.insert(target);

}

}

//time complexity O(n), n is the tree height 

int findIndexFor(int value){

int passed = 0;

QNode curr = this;

while(curr!=null){

if(curr.val == value){

return (curr.left==null?0:curr.left.size) + passed;

}else if(curr.val > value){

curr = curr.left;

}else{

passed += (curr.left==null?0:curr.left.size) + 1;

curr = curr.right;

}

}

return -1;

}

}

public static int maxQAZ(int[] nums){

assert(nums != null);

int len = nums.length;

QNode root = new QNode(nums[len-1], 1);

int max = 0;

for(int i=len-2; i>=0; i--){

root.insert(nums[i]);

max = Math.max(max, i- root.findIndexFor(nums[i]));

}

return max;

}

An alternative solution is to modify merge sort to calculate qaz for an array.

//find QAZ using merge sort

public static class Qaz{

int v; int qaz;

public Qaz(int v){this.v = v;}

public String toString(){

return v + "-" + qaz;

}

}

public static void qazBymergeSort(int[] nums){

int len = nums.length;

Qaz[] objs = new Qaz[len];

for(int i = 0; i< len; i++){

objs[i] = new Qaz(nums[i]);

}

mergeSort(objs, 0, len-1);

System.out.println(Arrays.toString(objs));

}

public static void mergeSort(Qaz[] nums, int start, int end){

if(start>=end)

return;

int mid = (start+end)>>>1;

mergeSort(nums, start, mid);

mergeSort(nums, mid+1, end);

merge(nums, start, mid, end);

}

public static void merge(Qaz[] nums, int start, int mid, int end){

Qaz[] temp = new Qaz[end-start+1];

int start2 = mid+1;

int k = temp.length-1;

int add = 0;

while(start<=mid && start2<=end){

if(nums[mid].v<nums[end].v){

temp[k--] = nums[end--];

add++;

}

else{

temp[k] = nums[mid--];

temp[k].qaz = temp[k].qaz + add;

k--;

}

}

while(start<=mid){

temp[k] = nums[mid--];

temp[k].qaz = temp[k].qaz + add;

k--;

}

while(start2<=end)

temp[k--] = nums[end--];

  System.arraycopy(temp, 0, nums, start, temp.length);

}

Minimum cost of sorting an array of positive numbers

This is a Facebook interview problem which can be found at http://www.careercup.com/question?id=9333968.

Here is the problem statement from the site:
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

Most of array problem can be solved by 1) dynamic programming which usually has time complexity of O(n^2) or above, 2) sliding window which has time complexity of O(n). Then mixing with these two approach there will be various data structures or algorithms can be used, notably, binary search, stack, queue.

My first try is greedy algorithm:

Start from index at 0, using a sliding window, keep on expanding the window until find a the number which is larger than the previous number.
note the numbers in sliding window are sorted except the last one, supposed its value is k
using binary search to find the minimum index of the item larger than k in the sliding windows
now to make the sliding window completely sorted, we have two choices: 1) delete the last one, 2) decrease all of the items from the minimum index to end of sliding window to k. We can calculate the costs of these two choices, choose the one is minimum and then make change to the array

now we can expanding the sliding window again and repeat the above steps until reaching the end of array

However the above solution is not quite right, per Peng Li's comment below.

My second try is dynamic programming:

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])

Final answer: min(dp(a.len-1, 0), dp(a.len-1, 1)..., dp(a.len-1, b.len-1)

public static int minSortCostDP(int[] nums){

Set<Integer> unique = new HashSet<Integer>();

for(int i:nums)

unique.add(i);

Set<Integer> sortedSet = new TreeSet<Integer>(unique);

Integer[] sorted = (Integer[]) sortedSet.toArray();

int lenA = nums.length,  lenB = sorted.length;

int[][] table = new int[lenA][lenB];

//first row

for(int col = 0; col<lenB; col++)

table[0][col] = Math.max(0, nums[0]-sorted[col]);

for(int row = 1; row<lenA; row++){

 for(int col = 0; col<lenB; col++){

  //either deletion or decrement

  int cost_of_convert = nums[row]>=sorted[col]? nums[row]-sorted[col]:nums[row];

  table[row][col] = Integer.MAX_VALUE;

  for(int k=0; k<=col; k++){

table[row][col] = Math.min(table[row-1][k]+cost_of_convert, table[row][col]);

  }

 }

}

int minCost = Integer.MAX_VALUE;

//last row

for(int col = 0; col<lenB; col++){

minCost = Math.min(table[lenA-1][col], minCost);

}

return minCost;

}

//Greedy algorithm approach which is not quite right

package org.blueocean;

public class FacebookQ {

//http://www.careercup.com/question?id=9333968

//find the min index of the item in array which large than k

public static int binarySearch(int[] nums, int start, int end, int k){

while(end-start>1){

int mid = (end+start)>>>1;

if(nums[mid]>k)

end = mid;

else

start = mid;

}

return nums[start]>k? start : end;

}

//greedy algorithm

public static int minSortCost(int[] nums){

int cost = 0;

int start = 0;

int end = 1;

int len = nums.length;

while(end<len){

while(end<len && nums[end]>=nums[end-1]){

end++;

}

if(end<len){

int index = binarySearch(nums, start, end-1, nums[end]);

int cost1 = nums[end];//deletion

int cost2 = 0;

for(int j = index; j<=end-1; j++)

cost2 += nums[j]-nums[end];//decrement

if(cost1<=cost2){

//delete item at index of end by shifting the rest of numbers after end

System.arraycopy(nums, end+1, nums, end, len-1-end);

len--;

cost += cost1;

}else{

for(int j = index; j<=end-1; j++)

nums[j] = nums[end];

cost += cost2;

}

}

end++;

}

return cost;

}

}