Monthly Archives: February 2015

Text justification

I got this problem from Junmin: link.

Problem: given a list of words and a window size of w, how to split them into multiple lines so that the fewest lines are used if possible.
Example: w = 10, input:  “given a list of words and a window size of w”
potential optimal alignment:
given a
list of
words and
a window
size of w

not a good alignment:
given
a list
of words
and a
window
size of
w

This one is a DP problem. One of the critical issue is how to measure the cost of a set of word group. The answer is to calcualte sum of the rest of the space of each line.

First of all, we define a array l[][]. l[i][j] has the cost of the word sequence from WORDi to WORDj. And for each rest space of line, we power it by 3. Taking a string “a given word list”, with line length 10 for example, it has the following cost matrix:

The reason why we power it by 3 is because we want the result to be smoothly aligned. For example, considering a text “a b c d e” with length 7, following A, B group are both ok. But abviously A is more smoothly arranged than B.
A:
a b c     <– rest space is 7-5=2
d e       <– rest space is 7-3=4

B:
a          <–rest space is 7-1=6
b c d e  <–rest space is 7-7=0

In order to solve this, we transfer the cost by adding a power by 3. I don’t understand why in official answer it chooses power by 3 of cost of each line. In my opinion, I think power by 2 works too. But the thing here we don’t use plain add is because we want the text to be smoothly arranged.

Now, let’s enter the DP process. We define the cost[]. Cost[i] indicates the cost of the optimized align from WORD0 to WRODi. And I define another array segment[]. Segment[i] indicates the index of the left-most word from WORDi, which is in the same line with WORDi. Segment[] is to store the result for printing. And we have the following DP formula:

The interesting part of this problem lies in cost measurement. We need to define a new cost measurement in order to do the DP.

My code:

  1. package feb;
  2. public class TextJustification {
  3.     public static void main(String[] args) {
  4.         String str = “Geeks for Geeks presents word wrap problem”;
  5.         // str = “given a list of words and a window size of w”;
  6.         str = “aaa bb cc ddddd”;
  7.         textJustification(str, 6);
  8.     }
  9.     public static void textJustification(String str, int rowLen) {
  10.         if (str == null || str == “”) {
  11.             return;
  12.         }
  13.         String[] strs = str.split(” “);
  14.         /*
  15.          * l[i][j] indicate the cost of word sequence, from wordi to wordj
  16.          */
  17.         int[][] l = new int[strs.length][strs.length];
  18.         for (int i = 0; i < l.length; i++) {
  19.             l[i][i] = (int) Math.pow(rowLen – strs[i].length(), 3);
  20.         }
  21.         for (int wordStart = 0; wordStart < strs.length – 1; wordStart++) {
  22.             int len = strs[wordStart].length();
  23.             for (int i = 0; i < wordStart; i++) {
  24.                 l[wordStart][i] = Integer.MAX_VALUE / 100;
  25.             }
  26.             for (int wordEnd = wordStart + 1; wordEnd < strs.length; wordEnd++) {
  27.                 len += strs[wordEnd].length() + 1;
  28.                 if (len > rowLen) {
  29.                     for (int i = wordEnd; i < strs.length; i++) {
  30.                         l[wordStart][i] = Integer.MAX_VALUE / 100;
  31.                     }
  32.                     break;
  33.                 } else {
  34.                     l[wordStart][wordEnd] = (int) Math.pow(rowLen – len, 3);
  35.                 }
  36.             }
  37.         }
  38.         /*
  39.          * cost[i] stores the least cost of the justification from word0 to
  40.          * wordi
  41.          */
  42.         int[] cost = new int[strs.length];
  43.         /*
  44.          * segment[i] stores index of left-most word which combines with wordi
  45.          * in the same line. e.g. segment[6] = 3, it means word3, word4, word5,
  46.          * word6 are in the same line.
  47.          */
  48.         int[] segment = new int[strs.length];
  49.         cost[0] = l[0][0];
  50.         segment[0] = 0;
  51.         for (int i = 1; i < strs.length; i++) {
  52.             cost[i] = l[0][i];
  53.             segment[i] = 0;
  54.             for (int j = 0; j < i; j++) {
  55.                 int currCost = cost[j] + l[j + 1][i];
  56.                 if (currCost < cost[i]) {
  57.                     cost[i] = currCost;
  58.                     segment[i] = j + 1;
  59.                 }
  60.             }
  61.         }
  62.         /*
  63.          * reverse the print sequence, in order to print
  64.          */
  65.         for (int i = strs.length – 1; i > 0;) {
  66.             int wordStart = segment[i];
  67.             segment[wordStart] = i;
  68.             i = wordStart – 1;
  69.         }
  70.         for (int i = 0; i < strs.length;) {
  71.             int wordEnd = segment[i];
  72.             for (int j = i; j <= wordEnd; j++) {
  73.                 System.out.print(strs[j] + ” “);
  74.             }
  75.             System.out.println();
  76.             i = wordEnd + 1;
  77.         }
  78.     }
  79. }

Rearrange array

This is from G4G. link
Problem description:

Given an array of size n where all elements are in range from 0 to n-1, change contents of arr[] so that arr[i] = j is changed to arr[j] = i.

Examples:

Example 1:
Input: arr[]  = {1, 3, 0, 2};
Output: arr[] = {2, 0, 3, 1};
Explanation for the above output.
Since arr[0] is 1, arr[1] is changed to 0
Since arr[1] is 3, arr[3] is changed to 1
Since arr[2] is 0, arr[0] is changed to 2
Since arr[3] is 2, arr[2] is changed to 3

Example 2:
Input: arr[]  = {2, 0, 1, 4, 5, 3};
Output: arr[] = {1, 2, 0, 5, 3, 4};

Example 3:
Input: arr[]  = {0, 1, 2, 3};
Output: arr[] = {0, 1, 2, 3};

Example 4:
Input: arr[]  = {3, 2, 1, 0};
Output: arr[] = {3, 2, 1, 0};

Analysis:
This is similar to the circle sort. The current position will determine the next position in array. Finally, it will finish by circulate back to the beginning position. In order to reach O(1) space, I changed the value to negative to mark that a position is finished. In the end, restore the initial values in the array.

Code:

  1.     public static void rearrangeArray(int[] a) {
  2.         if (a == null || a.length == 1) {
  3.             return;
  4.         }
  5.         for (int start_pos = 0; start_pos < a.length; start_pos++) {
  6.             if (a[start_pos] < 0) {
  7.                 continue;
  8.             }
  9.             int next_pos = a[start_pos];
  10.             int pre_pos = start_pos;
  11.             while (next_pos != start_pos) {
  12.                 int tmpNextPos = a[next_pos];
  13.                 a[next_pos] = -pre_pos – 1;
  14.                 pre_pos = next_pos;
  15.                 next_pos = tmpNextPos;
  16.             }
  17.             a[start_pos] = -pre_pos – 1;
  18.         }
  19.         for (int i = 0; i < a.length; i++) {
  20.             a[i] = -(a[i] + 1);
  21.         }
  22.     }

Circle Sort

The characteristic of circle sort is that it takes least swap operation than any other sorting algorithm.
Given an integer array a[], it loops the element start_pos from a[0] to a[length-2]. Each time, find the right position(next_pos) for a[start_pos]. And we should still find the position for a[next_pos], and update the next_pos on and on, until next_pos goes to start_pos. The above operation happens in certain elements, which one replace another one like a circle.

  1. public static void circleSort(int[] a) {
  2.         if (a == null || a.length == 1) {
  3.             return;
  4.         }
  5.         for (int start_pos = 0; start_pos < a.length – 1; start_pos++) {
  6.             int next_pos = start_pos;
  7.             for (int i = start_pos + 1; i < a.length; i++) {
  8.                 if (a[start_pos] > a[i]) {
  9.                     next_pos++;
  10.                 }
  11.             }
  12.             if (next_pos == start_pos) {
  13.                 continue;
  14.             }
  15.             while (a[next_pos] == a[start_pos]) {
  16.                 next_pos++;
  17.             }
  18.             while (true) {
  19.                 int tmp_ele = a[next_pos];
  20.                 a[next_pos] = a[start_pos];
  21.                 next_pos = start_pos;
  22.                 for (int i = start_pos + 1; i < a.length; i++) {
  23.                     if (tmp_ele > a[i]) {
  24.                         next_pos++;
  25.                     }
  26.                 }
  27.                 if (next_pos == start_pos) {
  28.                     a[start_pos] = tmp_ele;
  29.                     break;
  30.                 }
  31.                 while (a[next_pos] == a[start_pos]) {
  32.                     next_pos++;
  33.                 }
  34.             }
  35.         }
  36.     }

JWT sample, and implementation in node.js and java

This is quoted from here link.

The following example JOSE Header declares that the encoded object is a JSON Web Token (JWT) and the JWT is a JWS that is MACed using the HMAC SHA-256 algorithm:

  {"typ":"JWT",
   "alg":"HS256"}

To remove potential ambiguities in the representation of the JSON object above, the octet sequence for the actual UTF-8 representation used in this example for the JOSE Header above is also included below. (Note that ambiguities can arise due to differing platform representations of line breaks (CRLF versus LF), differing spacing at the beginning and ends of lines, whether the last line has a terminating line break or not, and other causes. In the representation used in this example, the first line has no leading or trailing spaces, a CRLF line break (13, 10) occurs between the first and second lines, the second line has one leading space (32) and no trailing spaces, and the last line does not have a terminating line break.) The octets representing the UTF-8 representation of the JOSE Header in this example (using JSON array notation) are:

[123, 34, 116, 121, 112, 34, 58, 34, 74, 87, 84, 34, 44, 13, 10, 32, 34, 97, 108, 103, 34, 58, 34, 72, 83, 50, 53, 54, 34, 125]

Base64url encoding the octets of the UTF-8 representation of the JOSE Header yields this Encoded JOSE Header value:

  eyJ0eXAiOiJKV1QiLA0KICJhbGciOiJIUzI1NiJ9

The following is an example of a JWT Claims Set:

  {"iss":"joe",
   "exp":1300819380,
   "http://example.com/is_root":true}

The following octet sequence, which is the UTF-8 representation used in this example for the JWT Claims Set above, is the JWS Payload:

[123, 34, 105, 115, 115, 34, 58, 34, 106, 111, 101, 34, 44, 13, 10, 32, 34, 101, 120, 112, 34, 58, 49, 51, 48, 48, 56, 49, 57, 51, 56, 48, 44, 13, 10, 32, 34, 104, 116, 116, 112, 58, 47, 47, 101, 120, 97, 109, 112, 108, 101, 46, 99, 111, 109, 47, 105, 115, 95, 114, 111, 111, 116, 34, 58, 116, 114, 117, 101, 125]

Base64url encoding the JWS Payload yields this encoded JWS Payload (with line breaks for display purposes only):

  eyJpc3MiOiJqb2UiLA0KICJleHAiOjEzMDA4MTkzODAsDQogImh0dHA6Ly
  9leGFtcGxlLmNvbS9pc19yb290Ijp0cnVlfQ

Computing the MAC of the encoded JOSE Header and encoded JWS Payload with the HMAC SHA-256 algorithm and base64url encoding the HMAC value in the manner specified in [JWS], yields this encoded JWS Signature:

  dBjftJeZ4CVP-mB92K27uhbUJU1p1r_wW1gFWFOEjXk

Concatenating these encoded parts in this order with period (‘.’) characters between the parts yields this complete JWT (with line breaks for display purposes only):

  eyJ0eXAiOiJKV1QiLA0KICJhbGciOiJIUzI1NiJ9
  .
  eyJpc3MiOiJqb2UiLA0KICJleHAiOjEzMDA4MTkzODAsDQogImh0dHA6Ly9leGFt
  cGxlLmNvbS9pc19yb290Ijp0cnVlfQ
  .
  dBjftJeZ4CVP-mB92K27uhbUJU1p1r_wW1gFWFOEjXk

This computation is illustrated in more detail in Appendix A.1 of [JWS]. See Appendix A.1 for an example of an encrypted JWT.

Implementation
Following code uses jsonwebtoken.js to generate the JWT token in node.js

  1. var jwt = require(‘jsonwebtoken’);
  2. var token = jwt.sign({ foo: ‘bar’ }, ‘this is the kez’);
  4. console.log(token);
  6. var decoded = jwt.verify(token, ‘this is the kez’, inValidProcess);
  8. function inValidProcess(err, decoded){
  9.     if(err){
  10.         console.log(“token invalid: ” + err);
  11.     }
  12.     else{
  13.         console.log(decoded);
  14.     }
  15. }

For java, we can use following maven:

<dependency>
    <groupId>com.auth0groupId>
    <artifactId>java-jwtartifactId>
    <version>2.0.1version>
dependency>

Java code:

import com.auth0.jwt.JWTSigner;
import com.auth0.jwt.JWTVerifier;
import java.security.SignatureException;
import java.util.HashMap;
import java.util.Map;

/**
 * Created by pli on 4/17/2015.
 */
public class App {
    public static void main(String[] args) {
        try {
            /**
             * Generate a token
             */
            Map payload = new HashMap();
            payload.put("name", "pli");
            payload.put("age", "27");
            payload.put("ok", "ok");
            JWTSigner signer = new JWTSigner("local key");
            String token = signer.sign(payload);
            System.out.println("token:" + token);
            /**
             * Verify a token and get the payload
             */
            JWTVerifier verifier = new JWTVerifier("local key");
            payload = verifier.verify(token);
            System.out.println("payload:" + payload);
        }catch (SignatureException e){
            e.printStackTrace();
        }catch (Exception e){
            e.printStackTrace();
        }
    }
}

Amazon interview(Software engineer)

This is my experience with Amazon software engineer interview. Even though I didn’t get the offer, but I went through the whole process: phone interview and on-site interview. I think the experience is valuable to share with.

Interview process. 2 weeks.
Dec, 2nd. Got noticed for the phone call interview
Dec, 5th. Phone call interview
Dec, 8th. Got noticed to have on-site interview in Seattle
Dec, 12th. On-site interview
Dec, 16th. Got rejected.

Dec, 2nd. Got noticed for the phone call interview
I got phone call that I will prepare for the phone call interview. HR told me that 3 departments are interesed in me and asked me which one am I intersted in. I chose 2 of them.

Dec, 5th. Phone call interview
In the afternoon, I got the phone call on time. There are 5 questions. 4 of them are very basic knowledge for data structure, very easy. Last one is a coding question. I got link from Amazon, and should code in codepair.hackerrank.com. I couldn’t think up with the solution. Interviewer showed me the trick of it, and asked me can you write it now? I thought a little bit, and write the solution.

Dec, 8th. Got noticed to have on-site interview in Seattle
I got the email saying I was invited for the on-site interview in Seattle. I contacted the Amazon and booked the ticket and hotel. They are very nice to grant me for staying in Seattle for 3 nights! And I have chance to hang out in Seattle. Thank you Amazon!

Dec, 12th. On-site interview
I arrived the Amazon HQ. Firstly, I talked with HR. She asked me why Amazon, salary expectations etc. 2 HRs are very nice and friendly. It’s more like a casual chat.
There are 5 interviews. I coded on white board for each interview. After the coding, engineers will ask me some open questions. I guess Amazon chose people not only by their coding ability, but also your personal characteristics. The five coding problem are pretty easy to me, I came up with all solutions. And I was very confident to get the offer.

Dec, 16th. Got rejected.
After the weekend, on the next Tuesday, I was emailed that I got rejected. I asked why, the HR wouldn’t let out any details. Very sad…

Interview tips
1. Keywords for the interview includes: HashMap, Linklist, dynamic programming, archeticture design, time/space complexity
2. Do exercise on geeksforgeeks. G4G really helps a lot for the interview!
3. Fully understand the question. It is necessary to fully understand what interviewer ask you. You should ask back if the question is not clear to you.
4. Write code professionally, don’t expect to write pseudo-code.

Summary
Amazon interview alrealdy passed for 2 months. The interview process is pretty fast and efficient. Engineers are very friendly. Seattle is a very modern, beautiful city. The technical questions are not hard to me. I don’t understand the reason for being rejected. I think that I don’t have work experience could be one of the reason. Not sure. On the same day, there was another guy from Microsoft having the interview too. Compared to him, my experience seems more listless.

Next greater element

Given a number n, find the smallest number that has same set of digits as n and is greater than n. If x is the greatest possible number with its set of digits, then print “not possible”.

examples:
input: 1111
output: not possible

inout: 1234
output: 1243

input: 12345765
output: 12346557

Solution:
Assume the input is a int[] num.
1. Scan from the end, and find the 1st position i, where num[i] < num[i+1]. Let i be smallPos.
2. Scan from the end again, find the 1st position j, where num[smallPos] < num[j]. Let j be largePos.
3. Do exchange between num[smallPos] and num[largePos].
4. Do exchange from num[smallPos+1] and num[num.length – 1], num[smallPos+2] and num[num.length – 2], num[smallPos+3] and num[num.length – 3] and so on.
This time, I used node.js to solve this problem.
The visiting format is http://allenlipeng47.com:3000/nge/{input}
For example: http://allenlipeng47.com:3000/nge/66355331
There are 2 files: app.js and npe.js:
node/app.js
node/mymodule/npe.js

npe.js:

  1. /*
  2. Given a number n, find the smallest number that has same set of digits as n and is greater than n. If x is the greatest possible number with its set of digits, then print “not possible”.
  3. The input num is a char array type.
  4. */
  5. function npe(num){
  6.     num = num.split(”);
  7.     if(num.length==1){
  8.         return ‘not possible’;
  9.     }
  10.     var smallPos = num.length – 2;
  11.     while(smallPos >=0 && num[smallPos] >= num[smallPos+1]){
  12.         smallPos–;
  13.     }
  14.     if(smallPos < 0){
  15.         return ‘not possible’;
  16.     }
  17.     var largePos = num.length – 1;
  18.     while(num[largePos] <= num[smallPos]){
  19.         largePos–;
  20.     }
  21.     var tmp = num[smallPos];
  22.     num[smallPos] = num[largePos];
  23.     num[largePos] = tmp;
  24.     for(largePos = num.length – 1, ++smallPos; smallPos < largePos; smallPos++, largePos–){
  25.         var tmp = num[smallPos];
  26.         num[smallPos] = num[largePos];
  27.         num[largePos] = tmp;
  28.     }
  29.     num = num.join(”);
  30.     return num;
  31. }
  32. module.exports = npe;

app.js

  1. var express = require(‘express’)
  2. var app = express();
  3. app.get(‘/nge/:id’, function (req, res){
  4.     var npe = require(‘./mymodule/npe.js’);
  5.     var result = npe(req.params.id);
  6.     res.send(result);
  7. })
  8. app.get(‘*’, function (req, res){
  9.     res.send(‘Welcome to Li Peng\’s node.js!’);
  10. })
  11. var server = app.listen(3000, function(){
  12.     var host = server.address().address
  13.     var port = server.address().port
  14. });

Return index with probability proportional to its weight

This question is from careercup. link
Problem description:
Write a function that receives a stream of pairs: id (some unique integer) + weight (positive real number).
The stream ends with the special pair {0,0}.
The function should return one the unique ids at random, with probability proportional to its weight (compared to the total weights sum when stream has ended).
Stream size and weights sum are unknown in advance, and you are allowed O(1) memory consumption.
Example: If this was the stream: {1,2},{2,2},{3,4},{4,10}, then id 2 would be returned with probability 1/9.

Analysis:
Assume the input from [0,W0], [1,W1],…[n,Wn], the selected index is i. Let totalWeight=sum(W0,…,Wn).
Now consider a new input [n+1,Wn+1], the probability to keep index I is totalWeight / (totalWeight + Wn+1), and probbability to have a new index n+1 is Wn+1 / (totalWeight + Wn+1).

Instead of a input stream, I used int[][] array for short.

public static int getRandom(int[][] input) {
    double totalWeight = input[0][1];
    int result = 0;
    for (int i = 1; i < input.length; i++) {
        if (input[i][0] == 0 && input[i][1] == 0) {
            break;
        }
        double newTotalWeight = totalWeight + input[i][1];
        double newChance = ((double) input[i][1]) / newTotalWeight;
        if (Math.random() <= newChance) {
            result = i;
        }
        totalWeight = newTotalWeight;
    }
    return result;
}

public static void main(String[] args) {
    int[][] input = { { 1, 4 }, { 2, 2 }, { 3, 2 }, { 0, 0 } };
    int result = getRandom(input);
    System.out.println(result);
    /*
     * Following runs for 1000 times to check the answer correctness.
     *
     * int[] test = new int[3]; for (int i = 0; i < 1000; i++) {
     * test[getRandom(input)]++; } for (int i = 0; i < test.length; i++) {
     * System.out.print(test[i] + “\t”); }
     */
}

Find peak in matrix

This is eveolved from 1D problem – find local min.
I would say this is a interesting problem and hvae great solution. The definition of “local” is near elements, ans in same row or column.
There is junmin’s implementation, link , which is similar to mine. And another very clear material from mit, link.

  1. package weeklychallenge3;
  2. import java.util.Arrays;
  3. public class PeakInMatrix {
  4.     public static void main(String[] args) {
  5.         int[][] matrix = {
  6.                 { 9, 3, 5, 2, 4, 9, 8 },
  7.                 { 7, 2, 5, 1, 4, 0, 3 },
  8.                 { 9, 8, 2, 3, 4, 4, 8 },
  9.                 { 7, 6, 3, 1, 3, 2, 3 },
  10.                 { 9, 0, 6, 0, 4, 6, 4 },
  11.                 { 9, 7, 8, 0, 5, 3, 0 },
  12.                 { 2, 1, 2, 1, 1, 1, 1 }
  13.             };
  14.         int[] result = findPeakInMatrix(matrix);
  15.         System.out.println(Arrays.toString(result));
  16.     }
  17.     public static int[] findPeakInMatrix(int[][] matrix) {
  18.         if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
  19.             return null;
  20.         }
  21.         int leftCol = 0, rightCol = matrix[0].length, totalRow = matrix.length, totalCol = matrix[0].length;
  22.         int midCol = 0, maxIndex = 0;
  23.         while (leftCol <= rightCol) {
  24.             midCol = (leftCol + rightCol) >> 1;
  25.             maxIndex = 0;
  26.             for (int i = 1; i < totalRow; i++) {
  27.                 maxIndex = (matrix[i][midCol] > matrix[maxIndex][midCol]) ? i : maxIndex;
  28.             }
  29.             if (midCol – 1 >= 0    && matrix[maxIndex][midCol – 1] > matrix[maxIndex][midCol]) {
  30.                 rightCol = midCol;
  31.             } else if (midCol + 1 < totalCol && matrix[maxIndex][midCol + 1] > matrix[maxIndex][midCol]) {
  32.                 leftCol = midCol;
  33.             } else {
  34.                 break;
  35.             }
  36.         }
  37.         return new int[] { maxIndex, midCol };
  38.     }
  39. }

Find all intervals covering an integer

For example, we have intervals
[1,3]
[2,7]
[3,6]
[5,5]
[8,9]

If we give a number 3, it should return:
[1,3]
[2,7]
[3,6]

Solution 1, Linear solution
An obvious solution is to iterate all intervals. This takes O(n) time.

Solution 2, Range tree.
Maintain 2 BST for left and right bound.
 
Find the range for left bound and right bound, and do intersection

Qaz

This problem is from careercup, link
Problem description:
1. qaz is a value for a number where this number is less than the other next values which have indexes larger than the index of this number.
for example: 33 , 25 , 26 , 58 , 41 , 59 -> qaz of (33) = 3 where 33 less than 3 numbers (58 , 41 , 59), qaz of (25) = 4 and not 5 because the index of 33 is less than the index of 25, qaz of (26) = 3 , qaz of (58) = 1 , qaz of (41) = 1 , qaz of (59) = 0.
the question is to find the max qaz.

A brute force solution is to iterate each element, and find how many elements after and larger than it.
A O(nlogn) solution can be achieved by mergesort:
For each array, it has a maxQaz. Let’s consider to merge {33, 48, 26} and {58, 41, 59}.
Final result of 2 arrays are:
{26(0), 33(1), 48(0)}, leftQaz = 1.
{41(1), 58(1), 59(0)}, rightQaz = 1.
-initial added_qaz = 0,
-traverse both arrays from end to the beginning,
-move the pointer which is pointing to the bigger number,
—when moving the pointer of the right sub array, increase added_qaz
—when moving the pointer of the left sub array, apply added_qaz to qaz of pointed element before moving 
Because only left sub array is updated.
Now, left sub array should be {26(3), 33(4), 48(2)}. And we know leftQaz is 4.
Before return, we use merge sort to merge 2 subarrays, and got:
{26(3), 33(4), 41(1), 48(2), 58(1), 59(0)}.
Now, we should return max(leftQaz, rightQaz). The result would be 4.

The code is kinda long. Because we use mergesort, so 2 helper arrays for auxiliary space are used.

  1. package feb;
  2. public class QAZ {
  3.     public static void main(String[] args) {
  4.         int[] arr = { 7, 8, 2, 3, 4, 5 };
  5.         int qaz = qaz(arr);
  6.         System.out.println(qaz);
  7.     }
  8.     public static int qaz(int[] arr) {
  9.         int[] eleTimes = new int[arr.length];
  10.         int[] helperQaz = new int[arr.length];
  11.         int[] helperTimes = new int[arr.length];
  12.         return qazUtil(arr, eleTimes, 0, arr.length – 1, helperQaz, helperTimes);
  13.     }
  14.     /*
  15.      * Return qaz of arr[]
  16.      * @param qazArr[], qazArr[i] stores the qaz of element arr[i] from arr[start,…,end].
  17.      * @param start, the start position of arr[]
  18.      * @param end, the end position of arr[]
  19.      * @param helperQaz, this is a helper array for mergesort. It helps for arr[]
  20.      * @param helperTimes, a helper array for merge sort. It is temporary place for eleTimes
  21.      */
  22.     private static int qazUtil(int[] arr, int[] qazArr, int start, int end,
  23.             int[] helperQaz, int[] helperTimes) {
  24.         if (start > end) {
  25.             return 0;
  26.         }
  27.         if (start == end) {
  28.             return 0;
  29.         }
  30.         int mid = start + (end – start) / 2;
  31.         int qazLeft = qazUtil(arr, qazArr, start, mid, helperQaz, helperTimes);
  32.         int qazRight = qazUtil(arr, qazArr, mid + 1, end, helperQaz, helperTimes);
  33.         // 1. Update eleTimes in left part.
  34.         int pointerL = mid, pointerR = end;
  35.         int added = 0;
  36.         while (pointerL >= start) {
  37.             while (arr[pointerL] < arr[pointerR] && pointerR >= mid + 1) {
  38.                 pointerR–;
  39.                 added++;
  40.             }
  41.             qazArr[pointerL] += added;
  42.             qazLeft = (qazArr[pointerL] > qazLeft) ? qazArr[pointerL]: qazLeft;
  43.             pointerL–;
  44.         }
  45.         // 2. Mergesort left and right part into helperQaz, helperTimes
  46.         pointerL = start;
  47.         pointerR = mid + 1;
  48.         int helpIndex = start;
  49.         while (pointerL <= mid && pointerR <= end) {
  50.             if (arr[pointerL] < arr[pointerR]) {
  51.                 helperQaz[helpIndex] = arr[pointerL];
  52.                 helperTimes[helpIndex] = qazArr[pointerL];
  53.                 pointerL++;
  54.             } else {
  55.                 helperQaz[helpIndex] = arr[pointerR];
  56.                 helperTimes[helpIndex] = qazArr[pointerR];
  57.                 pointerR++;
  58.             }
  59.             helpIndex++;
  60.         }
  61.         while (pointerL <= mid) {
  62.             helperQaz[helpIndex] = arr[pointerL];
  63.             helperTimes[helpIndex] = qazArr[pointerL];
  64.             pointerL++;
  65.             helpIndex++;
  66.         }
  67.         while (pointerR <= end) {
  68.             helperQaz[helpIndex] = arr[pointerR];
  69.             helperTimes[helpIndex] = qazArr[pointerR];
  70.             pointerR++;
  71.             helpIndex++;
  72.         }
  73.         // 2.2 Copy result from helperQaz, helperTimes back to arr, eleTimes
  74.         for (int i = start; i <= end; i++) {
  75.             arr[i] = helperQaz[i];
  76.             qazArr[i] = helperTimes[i];
  77.         }
  78.         return Math.max(qazLeft, qazRight);
  79.     }
  80. }