# 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 = 3, it means word3, word4, word5,
46.          * word6 are in the same line.
47.          */
48.         int[] segment = new int[strs.length];
49.         cost = l;
50.         segment = 0;
51.         for (int i = 1; i < strs.length; i++) {
52.             cost[i] = l[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

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 is 1, arr is changed to 0
Since arr is 3, arr is changed to 1
Since arr is 0, arr is changed to 2
Since arr is 2, arr 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 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’);
3. console.log(token);
4. var decoded = jwt.verify(token, ‘this is the kez’, inValidProcess);
5. function inValidProcess(err, decoded){
6.     if(err){
7.         console.log(“token invalid: ” + err);
8.     }
9.     else{
10.         console.log(decoded);
11.     }
12. }

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
*/
JWTSigner signer = new JWTSigner("local key");
System.out.println("token:" + token);
/**
* Verify a token and get the payload
*/
JWTVerifier verifier = new JWTVerifier("local key");
}catch (SignatureException e){
e.printStackTrace();
}catch (Exception e){
e.printStackTrace();
}
}
}```

After the Amazon interview, I spent a great effort to prepare for google interview. I did so many exercises and preparation. But unfortunately, I got rejected again. It is big setback to me. Sign!! Anyway, I went through the whole google interview process. Let me write it down my experience. It may help others!

Whole process. 4 months. (Yes, it is 4 months. My whole google interview took 4 months. It was such a long and painful time).
Nov, 10th. I was noticed to have an interview. But date hasn’t been scheduled.
Dec, 7th. I haven’t got any respone for a month. So I emailed to the recruitor. She told me she was waiting for my availabilities confirmation. I was kind of mad, because a month has passed. But on the hand, I also suspected if it was my fault because I didn’t communicate well with her in the phone.
Dec, 12th. I was emailed that the phone interview date is scheduled.
Jan, 9th. Phone call interview.
Jan, 30th. I was emailed to have on-site interview in Mountain View, San Jose.
Feb, 5th. On-site interview.
Feb, 10th. Google recruitor said NO and THANK YOU.

Let me focus on the 2 interviews.
Jan, 9th. Phone call interview.
I did the coding in google doc. It was similar to amazon interview. It was just 1 question. I was asked to code within 45 minutes. I was a bit nervous. At the beginning, I didn’t fully get the question and rushly coded. Interviewer told me it was not right. So I checked the question again, and made 2nd version. It was quite rush to me. Fortunately, I came up with the solution.

Feb, 5th. On-site interview.
Google doesn’t has any open questions. All you do is to code, and discuss with technical questions. I have 5 interviews on that day. 3 of them are normal coding question. 1 is Big O discussion. Last one is about coding correction and coding test. I perfectly solved 2 out of 5. With other 3, I couldn’t think up the solution at first glance, but still gave out my acceptable solution. Interviewer are very nice.
At noon, I had great opportunity to lunch with a Googler. He was very nice, and told me his experience in google. I had a great talk with him! I was told Google is such a cool company that many problem could exist only in Google. There are so many talents people out there.

Summary & Tips
Compared to Amazon, google problem is bit difficult. I did exercise on careercup. In my opinion, that doesn’t really help. Actually, google questions are more flexible and hard. You should always try to find out the O(logn), even O(1) solution. My only suggestion is that you should do more and more exercises, and have extensive algorithm exercises.

To those computer guys, Google is always the greatest place to go. It is the dream land for so many people! Indeed, I feel sad. But I would say I still experienced and learned from it. Following are some screen shots to remember my hard work preparing for the top company interviews:   ## 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(){
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;
int result = 0;
for (int i = 1; i < input.length; i++) {
if (input[i] == 0 && input[i] == 0) {
break;
}
double newTotalWeight = totalWeight + input[i];
double newChance = ((double) input[i]) / 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; 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.length == 0) {
19.             return null;
20.         }
21.         int leftCol = 0, rightCol = matrix.length, totalRow = matrix.length, totalCol = matrix.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 