Daily Archives: January 2, 2015

Find order of characters in alien language

This is a very interesting question from geeksforgeek. link
Problem: Given a sorted dictionary (array of words) of an alien language, find order of characters in the language.
Example
Input: words[] = {“baa”, “abcd”, “abca”, “cab”, “cad”}
Output: Order of characters is ‘b’, ‘d’, ‘a’, ‘c’ Note that words are sorted and in the given language “baa” comes before “abcd”, therefore ‘b’ is before ‘a’ in output. Similarly we can find other orders.

Solution:
For “baa”, “abcd”, “abca”, “cab”, “cad”, we can conclude: b->a, a->c
For “abcd”, “abca”, we can conclude: d->a
For “cab”, “cad”, we can conclude: b->d
Then do topological sorting on it.

Lowest cost to adjust integer array, adjacencies differ less than k

This problem frustrates me for a long time. Yesterday, I finally comprehended. Cheers!

Problem: Given an integer array, adjust each integers so that the difference of every adjcent integers are not greater than a given number k. If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|.

Solution: Find the max and min in A. So we know each of element, it is obvious to know that their change should be within [min, max]. So let’s say see A[0]. We change it to every number between [min, max], and record the cost.
Go to A[1]. We change A[1] to every number between [min,max]. It has a cost by itself. Besides, we should consider the cost from A[0]. Let’s say A[1] want to change to a certain number B[1]=bi, and b1 is between [min,max]. So, before b1, the A[0] could range from [b1-k,b1+k]. We want to choose the minimum cost. So the minimum cost of bi equals min{cost of A[0] changing to bi-k, cost of A[0] changing to bi-k+1,…,cost of A[0] changing to bi,…,cost of A[0] changing to bi+k} + (cost of A[1] changing to bi).
Then, we iterate A[2], A[3] and so on.
It requires a matrix to store it. Let’s say it is DP[max-min][A.length].
DP[i][j] means the minimum cost of changing A[0,…,j] to the target series when we changee A[j] to i.

Take the following as example, it is from careercup link:
On each number from the first to last, calculate the total cost up to this number with the ending number. Thus we calculate a matrix with column as the order of the number, row as ending number, cell value as a pair of total cost so far and row number of previous column to reach this cell(for path). The cell with the lowest cost in the last column is the result. From that cell, we can get the cell on each column to reach this last cell. The row and column indices for cells on the path make the result sequences.
For example:
input : 1, 4, 2, 3
matrix:
1 2 3 4
1 (0, -1) (3, 1) (4, 1) (6, 1)
2 (1, -1) (2, 1) (2, 2) (3, 2)
3 (2, -1) (2, 2) (3, 2) (2, 2)
4 (3, -1) (2, 3) (4, 3) (4, 3)
So the last cell[3,4] has lowest cost of 2, the previous cell is [2,3] with cost 2, then previous is [2,2] with cost 2 and then [1,1]. The result sequence is ( 1, 2, 2, 3) . This result has the same cost as the sequence of (2,3,2,3).

Count bounded slices 2 – O(n) solution

This is the O(n) solution, without result permutation output. Thanks to the answer from careerup link. I wrote my understanding and analysis.
The basic idea is that we start with arr[0] and then see how many more elements you can include before you violate the max-min<=k constraint. When it reaches some index ‘end’ you can no longer include, you know the maximum subarray starting at index 0 is arr[0…end-1], and you can count ‘end’ different subarrays there. You then already know arr[1…end-1] is valid, and you try to advance the right boundary again (try arr[1…end], then arr[1…end+1]) and so on until again you reach a point ‘front’ past which you can’t advance. Then you’ll try subarrays starting with index 2, and so on.
In order to simplify the output, I just output the range of subarrays. The final result are the permutation of them. If we consider about result output, it may take more than O(n) time.
Let’s take following example:



My code:

  1. import java.util.ArrayList;
  2. public class CountBoundedSlices2 {
  3.     public static void main(String[] args) {
  4.         int[] arr = {1, 3, 2, 4, 5, 1, 6, 7, 9};
  5.         countBoundedSlices(arr, 4);
  6.     }
  8.     public static void countBoundedSlices(int[] arr, int k){
  9.         //initial maxQueue and minQueue.
  10.         int front=0, end=1;
  11.         BoundedSlicesSData frontElem = new BoundedSlicesSData(arr[front],front);
  12.         BoundedSlicesSData endElem = new BoundedSlicesSData(arr[end],end);
  13.         ArrayList < BoundedSlicesSData> maxQueue = new ArrayList< BoundedSlicesSData>();
  14.         ArrayList < BoundedSlicesSData> minQueue = new ArrayList< BoundedSlicesSData>();
  15.         addToMaxQueue(maxQueue, frontElem);
  16.         addToMaxQueue(maxQueue, endElem);
  17.         addToMinQueue(minQueue, frontElem);
  18.         addToMinQueue(minQueue, endElem);
  19.         //The following elements are recorded to check max-min < k
  20.         BoundedSlicesSData maxElem = maxQueue.get(0);    //indicate the max element.
  21.         BoundedSlicesSData minElem = minQueue.get(0);    //indicate the min element.
  22.         for(;front < arr.length&&end+1 < arr.length;front++){
  23.             //delete elements from front which has position less than front.
  24.             while(maxElem.position < front){
  25.                 maxQueue.remove(0);
  26.                 maxElem = maxQueue.get(0);
  27.             }
  28.             while(minElem.position < front){
  29.                 minQueue.remove(0);
  30.                 minElem = minQueue.get(0);
  31.             }
  32.             //move end forward until max-min < k
  33.             while(front < arr.length&&end+1 < arr.length&&((maxElem.value-minElem.value < k)||front==end)){
  34.                 end++;
  35.                 endElem = new BoundedSlicesSData(arr[end], end);
  36.                 addToMaxQueue(maxQueue, endElem);
  37.                 addToMinQueue(minQueue, endElem);
  38.                 maxElem = maxQueue.get(0);
  39.                 minElem = minQueue.get(0);
  40.             }
  41.             if(front!=end-1){
  42.                 System.out.println(“(“+front+”,”+(end-1)+”)”);
  43.             }
  44.             if(end==arr.length-1){    //to get the last result
  45.                 System.out.println(“(“+front+”,”+end+”)”);
  46.             }
  47.         }
  48.     }
  50.     /*
  51.      * Add a new element to min queue. Keep the min quene with ascend sequence.
  52.      */
  53.     public static void addToMinQueue(ArrayList < BoundedSlicesSData> queue, BoundedSlicesSData newElement){
  54.         if(queue.size()==0){
  55.             queue.add(newElement);
  56.             return;
  57.         }
  58.         BoundedSlicesSData front = queue.get(0);
  59.         if(newElement.value < front.value){    //new element is smaller than the front. Clear queue and add it.
  60.             queue.clear();
  61.             queue.add(newElement);
  62.             return;
  63.         }
  64.         BoundedSlicesSData end = queue.get(queue.size()-1);
  65.          /* Or delete those elements which are larger than new element from end of queue.
  66.          * And add new element to the queue. */
  67.         while(end.value>=newElement.value){
  68.             queue.remove(queue.size()-1);
  69.             end = queue.get(queue.size()-1);
  70.         }
  71.         queue.add(newElement);
  72.     }
  74.     /*
  75.      * Add a new element to max queue. Keep the min quene with descend sequence.
  76.      */
  77.     public static void addToMaxQueue(ArrayList < BoundedSlicesSData> queue, BoundedSlicesSData newElement){
  78.         if(queue.size()==0){
  79.             queue.add(newElement);
  80.             return;
  81.         }
  82.         BoundedSlicesSData front = queue.get(0);
  83.         if(newElement.value>front.value){    //new element is larger than the front. Clear queue and add it.
  84.             queue.clear();
  85.             queue.add(newElement);
  86.             return;
  87.         }
  88.         BoundedSlicesSData end = queue.get(queue.size()-1);
  89.          /* Or delete those elements which are less than new element from end of queue.
  90.          * And add new element to the queue. */
  91.         while(end.value < =newElement.value){
  92.             queue.remove(queue.size()-1);
  93.             end = queue.get(queue.size()-1);
  94.         }
  95.         queue.add(newElement);
  96.     }
  98. }
  99. /*
  100.  * The queue should store both value and position. So create this class for convinent.
  101.  */
  102. class BoundedSlicesSData{
  103.     int value;
  104.     int position;
  105.     public BoundedSlicesSData(){}
  106.     public BoundedSlicesSData(int value, int position){
  107.         this.value = value;
  108.         this.position = position;
  109.     }
  110. }