Valid words

You are given a string 's' and you are given a dictionary of english words. You goal is to write an algorithm that returns all words from the dictionary the can be formed by characters from that string 's'.
Example:
s = "ogeg"
following words can be formed from 's': go egg ego . . .
Further it is given that string 's' always consists of four lower case characters. Lets say that the dictionary is contained in a file and can be fitted in the memory. It is up to you which data structure you use to represent the dictionary.
How would you design an efficient algorithm? Follow up: What if the dictionary file can not be fitted in the memory?

This is a very interesting question. The problem statement is kind confusing.
Here is a question, why do we need to put the whole dictionary into the memory? The goal is to output all words that can be formed from s. From the example, we know that the order doesn't matter. So we only need to construct a hash map and store all four characters of s in it. And then read the dict from the stream and compare it with the characters in the hash map. I used another hash map. Since there are at most four characters for both strings, we don't need much extra space, do we?

If the question is, how to store the output words in an efficient way, I guess Trie would be a good one.

public static void validWords(String s, String dict) throws FileNotFoundException, IOException{
  BufferedReader br = new BufferedReader(new FileReader(dict));
  String currLine;
  Map sMap = new HashMap();
  for(int i = 0; i < s.length(); i++){
   char c = s.charAt(i);
   if(!sMap.containsKey(c))
    sMap.put(c, 1);
   else
    sMap.put(c, sMap.get(c) + 1);
  }
  Map word = new HashMap();
  while((currLine = br.readLine()) != null){
   if(currLine.length() > 4)
    continue;
   word.clear();
   boolean valid = true;
   for(int i = 0; i < currLine.length(); i++){
    char c = currLine.charAt(i);
    if(!sMap.containsKey(c)){
     valid = false;
     break;
    }
    if(!word.containsKey(c))
     word.put(c, 1);
    else
     word.put(c, word.get(c) + 1);
    if(word.get(c) > sMap.get(c)){
     valid = false;
     break;
    }
   }
   if(valid)
    System.out.println(currLine);
  }
  br.close();
 }

Generate Random ID

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.

The hard part for this question is that no extra space is allowed, which means we cannot store the pairs. The method to generate random number based on weight can be found here. Basically based on each weight, we calculate the accumulated weight, then when we generate a random number from 1 to the accumulated weight, return the number at certain range. Using the above array as an example:

1, 2 -> 2
2, 2 -> 4
3, 4 -> 8
4, 10 -> 18

So if we generate a random number between 1 to 18, and if it is 3 or 4,  then we should return 2. The probability is 2 / 18 = 1 / 9.

Now here comes the problem, we are not allowed to backtrack the already read array, what should we do?

One way is to keep generating random number and update the number we need to output until we reach the end of the stream. So if we are at {3, 4}, we generate a random number at 6, this number is greater than the previous accumulated weight (4), so we update the number we need to output to 3. If the number we generated is 3, then we don't update the number. The probability of getting each number is based on its weight (assuming the uniform probability of generating a random number from 1 to accumulated weight).

public int random(String fileName) throws FileNotFoundException{
  Scanner in = new Scanner(new FileReader(fileName));
  Random r = new Random();
  int cum = 0;
  int sample = 0;
  int last = 0;
  while(in.hasNext()){
   int val = in.nextInt();
   int weight = in.nextInt();
   if(val == 0 && weight == 0)
    break;
   cum += weight;
   int p = r.nextInt(cum) + 1;
   if(p >= last && p <= cum)
    sample = val;
   last = cum;
  }
  return sample;
 }

Minimum bits required to send a sequence of a deck of cards

Consider the 52 cards of a deck. You generated a random sequence for these cards and want to send that sequence to a receiver. You want to minimize the communication between you and the receiver, i.e., minimize the number of bits required to send the sequence.
What is the minimum number of bits required to send the sequence?
Hint: It is not 6 x 52

So first, how to come up with 6 * 52? Each card is in the range 1 - 52, so if we use 6 bits, there are 2^6 = 64 possibilities, which can cover all possible sequences.

Now we know that the bits required must include all possible sequences of that 52 cards, so how many possibilities? (52!). This means that we need n bits that 2^n >= (52!), so the theoretical answer is that we need log2(52!) = 226 bits.

So how to get that limit?

The first approach( besides the 6 * 52 one):
We know that the first card has 52 possibilities, the second has 51, ..., the 20th has 33 possibilities, so for the first 20 cards, we need at least 6 bits for each.
Then the 21st has 32 possibilities, ... 36th has 17 possibilities, so the next 16 cards we need at least 5 bits.
Then the next 8 cards we need 4 bits.
Then 4 cards, 3 bits.
Then 2 cards, 2 bits.
Then 1 card, 1 bit.
And after we know 51 cards, we know what the 52th is, so we don't need any bits. Thus in total:

20 * 6 + 16 * 5 + 8 * 4 + 4 * 3 + 2 * 2 + 1 = 249 bits. This solution is still larger.

The second one:
Consider we first send out k cards, which needs at most log2(Permu(k, 52)) bits, and now we have 52 - k cards. So we compute from 1 to 52 the k that can give us the minimum total bits required. We use recursion. Moreover, at each calling, the smaller number is already calculated, so we use an array to store at each n, the minimum bits required, thus can reduce some recursions.

However, Java has some problems with rounding (e.g., permu(1, 6) should return 3, but I get 4), so I cannot reach the optimized solution. See here for the C++ solution that can get to 227 bits.

public class SendingCards {
 static int N = 52;
 //Given n cards, best number of cards sent
 //static int[] cardsSent = new int[N + 1];
 static int[] minBits = new int[N + 1];
 static{
  minBits[1] = 0;
  minBits[2] = 1;
  minBits[3] = 3;
  //given 2 cards, sent 1 card first
  //cardsSent[1] = 1;
  //cardsSent[2] = 1;
  //cardsSent[3] = 3;
  
 }
 public static double logFact(int n){
  if(n == 0)
   return 0;
  double rst = 0;
  for(int i = 1; i <= n; i++)
   rst += Math.log((double)n) / Math.log(2.0);
  return rst;
 }
 public static double logPerm(int k, int n){
  //System.out.format("%d, %d: %.4f\n", k, n, logFact(n) - logFact(n - k));
  return logFact(n) - logFact(n - k);
 }
 //maxSent can be changed, after certain recursions, the number should converge
 //so we don't need to calculate from 1 to 52
 public static int send(int n, int maxSent){
  if(n <= 1)
   return 0;
  if(n == 2)
   return 1;
  if(n == 3)
   return 3;
  //if minBits have been calculated before, return the previous solution
  if(minBits[n] > 0)
   return minBits[n];
  int min = Integer.MAX_VALUE;
  int bits = 0;
  int kmin = 0;
  
  for(int k = 1; k <= Math.min(maxSent, n); k++){
   bits = (int)Math.ceil(logPerm(k, n)) + send(n - k, maxSent);
   if(min > bits){
    min = bits;
    kmin = k;
   }
  }
  System.out.println("n: " + n + ", min: " + min);
  //cardsSent[n] = kmin;
  minBits[n] = min;
  return min;
  
 }
 public static void main(String[] args) {
  System.out.println(send(N, 16));

 }

}

Find popular items

Find popular item in sorted array of natural numbers.
An item is popular is if its repeated n/4 times or more.
For Ex:
Input: 123444445678
Popular item is 4.
Liner scan is O(n), but solution needs to be in O(logN) complexity and O(1) space complexity.

This is actually a very interesting problem. Since the popular item is defined as the element is repeated more than 1 / 4 times, and since it is a sorted array, so it can only occurs on 0, n / 4, n /2 and 3n/4 index. And the rest is just do binary search and get the range.

public class PopularNumber {
 public static void popular(int[] n){
  if(n == null || n.length == 0)
   return;
  int len = n.length;
  int[] check = {0, len / 4, len / 2, 3 * len / 4};
  for(int i = 0; i < 4; i++){
   if(i > 0 && n[check[i]] == n[check[i - 1]])
    continue;
   int l = check[i];
   int start = binarySearchStart(n, n[l]);
   int end = binarySearchEnd(n, n[l]);
   //need to be larger than the ceil in case len / 4.0 is not an integer
   if(end - start + 1 >= Math.ceil(len / 4.0))
    System.out.println(n[l]);
  }
 }
 private static int binarySearchEnd(int[] n, int target){
  int len = n.length;
  int start = 0;
  int end = len - 1;
  while(start + 1 < end){
   int mid = (start + end) / 2;
   if(n[mid] <= target)
    start = mid;
   else
    end = mid;
  }
  if(n[end] == target)
   return end;
  else return start;
 }
 private static int binarySearchStart(int[] n, int target){
  int len = n.length;
  int start = 0;
  int end = len - 1;
  while(start + 1 < end){
   int mid = (start + end) / 2;
   if(n[mid] >= target)
    end = mid;
   else
    start = mid;
  }
  if(n[start] == target)
   return start;
  else
   return end;
 }

 public static void main(String[] args) {
  //int[] n = {1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8};
  int[] n = {1, 1, 2, 3, 4};
  popular(n);
 }
}

Integer to String

Write a function that takes an integer as input and produces an output string.
Some sample Input/outputs are as follows
i/p o/p
1 - A
2 - B
3 - AA
4 - AB
5 - BA
6 - BB
7 - AAA
8 - AAB
9 - ABA
10 - ABB
11 - BAA
12 - BAB
13 - BBA
14 - BBB
15 - AAAA

This looks like an integer to binary conversion, however, instead of using 0, 1 representation, it would be easier to understand if we convert in this way:

A       1
B       2
AA    11
AB    12
BA    21


If we use binary representations, we will have:

A       1
B       10
AA    11
AB    110
BA    101

It is reasonable that when n % 2 = 1, we append "A". However, if n % 2 = 0, we will have one extra digit, so we need to subtract 1 before we divide by 2.

public class IntegerToString {
 public static String convert(int n){
  if(n <= 0)
   return null;
  String rst = "";
  while(n > 0){
   if((n & 1) != 0)
    rst = "A" + rst;
   else {
    rst = "B" + rst;
    n -= 1;
   }
   n = (n >> 1);
  }
  return rst;
 }
 public static void main(String[] args) {
  for(int i = 1; i <= 15; i++)
   System.out.println(convert(i));
 }
}

Maximum days to light candles

You are given heights of n candles .
First day you lit one candle
second day you need to lit two candles
Third day you need to lit three candles
..........
........
till possible.
After lighting candles the height of candles deduced by 1 each day.You can also extinguish any candle you want but only at the end of day.
So you need to tell the maximum number number of days , you can carry on lighting the candles.
Example : there are three candles of heights {2 , 2 ,2 }
Answer : 3
1.You light first candle on day one. heights -> {1,2,2}
2.You light second and third and extinguish first one . heights ->{1, 1,1}
3.You light all the candles. heights -{0,0,0}

This is actually a tricky question. The tricky part is not on the actual implementation, in fact, there is no fancy algorithm here, but on how you think of the question.

In fact, the last paragraph was written 90 minutes ago, then when I tried to use an example to explain my first approach, I realized that is was wrong.

Then comes the second and third approach...

Then I realize the problem is as easy as the interview type suggests: A written test.

This is a simple Greedy approach.

Sort the array. Start from the maximum, each day we add an element and subtract the number of candles needed. So given

2 2 2

Day 1: 2 - 1 = 1
Day 2: 1 + 2 - 2 = 1
Day 3: 1 + 2 - 3 = 0

That's it. Simple. Yeah, simple....

public static int maxDays(int[] candles){
  if(candles == null || candles.length == 0)
   return 0;
  Arrays.sort(candles);
  int lit = candles[candles.length - 1] - 1;
  int count = 1;
  
  for(int i = candles.length - 2; i >= 0; i--){
   if(lit + (candles[i] - (count + 1)) < 0)
    break;
   lit += candles[i] - (++count);
  }
  return count;
 }

Task Scheduler

Given the interface below, implement a task scheduler.

interface Task {
    void Run();
    Set<Task> GetDependencies();
}

Additionally, the task scheduler should follow two rules.
1. Each task may only be executed once.
2. The dependencies of a task should be executed before the task itself.

This one is quite straightforward. Given a set of task, using a DFS approach.

public class TaskScheduler {
 Set executed;
 Set allTasks;
 Set inProcess;
 public TaskScheduler(Set tasks){
  allTasks = tasks;
  executed = new HashSet();
  inProcess = new HashSet();
 }
 public void schedule(Set allTasks){
  for(Task t : allTasks){
   if(executed.contains(t))
    continue;
   if(!inProcess.isEmpty() && inProcess.contains(t)){
    t.Run();
    inProcess.remove(t);
    executed.add(t);
    continue;
   }
   inProcess.add(t);
   schedule(t.GetDependencies());
   t.Run();
   inProcess.remove(t);
   executed.add(t);
  }
 }
}

Now comes the second one:

implement the same task scheduler with parallel task execution.

So I am thinking, maybe it needs a concurrency approach. So I go back to my old posts and tried to come up an approach. Since all dependencies should be executed first, I use a stack to schedule all tasks. The scheduler will first add all its dependencies to the stack. Then I use a releaseCount to track the available resources. If releaseCount == 0 or if the current Task is not on top of the stack, it should wait for its turn. Pop the task out and execute it, while executing, the task has acquired the resource, so releaseCount should decrement by one, after executing, the task should release the resource, so releaseCount increment by one.

However, I am not sure if my approach is correct, so I have an open question on Stackoverflow.

public class TaskSchedulerParallel {
 Set executed;
 Stack scheduler;
 int releaseCount;
 //number of parallel nodes
 public TaskSchedulerParallel(int N){
  executed = new HashSet();
  scheduler = new Stack();
  releaseCount = N;
 }
 public synchronized void schedule(Task t) throws InterruptedException {
  scheduler.push(t);
  for(Task dep : t.GetDependencies()){
   if(!executed.contains(dep) && !scheduler.contains(dep))
    schedule(dep);
  }
  if(releaseCount == 0 || (!scheduler.isEmpty() && scheduler.peek() != t))
   t.wait();
  releaseCount--;
  scheduler.pop();
  t.Run();
  executed.add(t);
  releaseCount++;
 }
 

}

Diameter of a tree

My last post pumped me to calculate the diameter of a tree. And there is actually the question: 

The diameter of a tree is the number of nodes on the longest path between two leaves in the tree. The diagram below shows a tree with diameter nine, the leaves that form the ends of a longest path are shaded (note that there is more than one path in each tree of length nine, but no path longer than nine nodes).
In particular, note that the diameter of a tree T is the largest of the following quantities:
the diameter of T's left subtree
the diameter of T's right subtree
the longest path between leaves that goes through the root of T
Given the root node of the tree, return the diameter of the tree

public static int maxDepth(TreeNode root){
  if(root == null)
   return 0;
  if(root.left == null && root.right == null)
   return 1;
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
 }
 public static int Diameter(TreeNode root){
  if(root == null)
   return 0;
  if(root.left == null && root.right == null)
   return 1;
  return Math.max(Math.max(Diameter(root.left), Diameter(root.right)), maxDepth(root.left) + maxDepth(root.right));
 }

Construct tree with minimum weight from an acyclic undirected unweighted graph

Given an acyclic undirected unweighted connected graph, find its representation as a tree with the least height. Brute force is O(n^2). Come up with an O(n) solution

Well, the problem is the same as saying given a tree, find it's root. An acyclic graph, unfortunately, is a tree. The problem is, we don't know where is the root. So the way we do it is to find the diameter of the graph. The diameter of the graph is defined as:

The diameter  of a graph is the maximum eccentricity of any vertex in the graph. That is,  it is the greatest distance between any pair of vertices or, alternatively, . To find the diameter of a graph, first find the shortest path between each pair of vertices. The greatest length of any of these paths is the diameter of the graph.

To do it in O(n), we first randomly select a node from the graph. find the farthest node it can reach, call it farthest1. Then find the farthest node farthest1 can reach, call it farthest2. The diameter of the graph is the distance between farthest1 and farthest2. The reason it works is that the given graph is a tree, so the two farthest nodes will only have one neighbor. If not, the we can go farther down find the next farthest node.

So how to find the root? Given the two farthest nodes, the root must be in between. so from one node to the other, find the middle one. The way I do it is a brutal force one, traverse both nodes to the equal distance, then find the common node. So the question is, is it possible that there exists a second common node on the path? The answer is definitely no, since the given graph is a tree.

public class ConstructTree {
 UndirectedGraph forest;
 int diameter;
 public ConstructTree(UndirectedGraph g){
  forest = g;
  //System.out.println("Tree built");
 }
 private UndirectedGraphNode getFarthest(UndirectedGraphNode n){
  Queue q = new LinkedList();
  q.add(n);
  Map distance = new HashMap ();
  distance.put(n, 0);
  //Set visited = new HashSet ();
  int maxDist = 0;
  //int currDist = 0;
  UndirectedGraphNode farthest = null;
  while(!q.isEmpty()){
   UndirectedGraphNode curr = q.poll();
   int d = distance.get(curr);
   for(UndirectedGraphNode neighbor : curr.neighbors){
    if(!distance.containsKey(neighbor)){
     distance.put(neighbor, d + 1);
     q.offer(neighbor);
    }
   }
  }
  for(Entry e : distance.entrySet()){
   if(e.getValue() > maxDist){
    maxDist = e.getValue();
    farthest = e.getKey();
   }
  }
  diameter = maxDist;
  return farthest;
 }
 private UndirectedGraphNode getRoot(UndirectedGraphNode n1, UndirectedGraphNode n2){
  int d1, d2;
  if(diameter % 2 == 0)
   d1 = d2 = diameter / 2;
  else{
   d1 = diameter / 2;
   d2 = diameter - d1;
  }
  Queue q1 = new LinkedList();
  q1.add(n1);
  Queue q2 = new LinkedList();
  q2.add(n2);
  UndirectedGraphNode toReturn = null;
  while(!q1.isEmpty() && d1 > 0){
   UndirectedGraphNode curr = q1.poll();
   for(UndirectedGraphNode nei : curr.neighbors)
    q1.offer(nei);
   d1--;
  }
  while(!q2.isEmpty() && d2 > 0){
   UndirectedGraphNode  curr = q2.poll();
   for(UndirectedGraphNode nei : curr.neighbors)
    q2.offer(nei);
   d2--;
  }
  for(UndirectedGraphNode node1 : q1){
   for(UndirectedGraphNode node2 : q2){
    if (node1 == node2){
     toReturn = node1;
     break;
    }
   }
  }
  return toReturn;
 }
 
 public UndirectedGraphNode construct(){
  UndirectedGraphNode random = forest.vertices.entrySet().iterator().next().getValue();
  UndirectedGraphNode farthest = getFarthest(random);
  UndirectedGraphNode farthest2 = getFarthest(farthest);
  return getRoot(farthest, farthest2);
 }
}

Swap sequence

You are given two arrays - A & B. The length of the arrays is the same - N. The values in the arrays are integers from 0 to N - 1 in random order and no number is repeated. You need to list a sequence of two-element swaps required to reorder the array A into the order of the array B. Additionally, at each step of the sequence you are allowed to swap two elements only if one of them is 0.

The idea is very simple.
1. Find the index of element 0 in A, then in B we get an corresponding element.
2. If it is not zero, find the index of that element in A, swap them.
3. If it is zero, then find the index of first element in A that is not equal to the corresponding element in B, swap it with 0 in A. Repeat 2.

public class SwapSequence {
 public static void printSequence(int[] A, int[]B){
  int indexZ  = findIndex(A, 0);
  if(B[indexZ] == 0){
   indexZ = getIndex(A, B, indexZ);
   if(indexZ == -1)
    return;
  }
  while(B[indexZ] != 0){
   int index = findIndex(A, B[indexZ]);
   System.out.println(A[indexZ] + " " + A[index]);
   swap(A, indexZ, index);
   indexZ = B[index] == 0 ? getIndex(A, B, index) : index;
   if(indexZ == -1)
    return;
  }
  
 }
 private static int getIndex(int[] A, int[] B, int indexZ){
  for(int i = 0; i < A.length; i++){
   System.out.println(A[i] + " " + B[i]);
   if(A[i] != B[i]){
    swap(A, i, indexZ);
    return i;
   }
  }
  return -1;
 }
 private static void swap(int[] array, int i, int j){
  int tmp = array[i];
  array[i] = array[j];
  array[j] = tmp;
 }
 private static int findIndex(int[] array, int element){
  for(int i = 0; i < array.length; i++){
   if(array[i] == element)
    return i;
  }
  return -1;
 }

 public static void main(String[] args) {
  int[] A = {0, 4, 8, 7, 1, 2, 5, 3, 6};
  int[] B = {1, 7, 6, 5, 8, 4 ,2, 3 ,0};
  printSequence(A, B);
  System.out.println(Arrays.toString(A));

 }

}

Read bytes

Given an API ReadFromDisk() which returns a block of 256 bytes from disk. Implement the API Read(SizeInBytes) which reads SizeInBytes bytes from the disk by calling only ReadFromDisk. Notice that every call to ReadFromDisk() will read the next 256 bytes from disk.

Update 2015 - 03 - 30
I realize that I understood the ReadN problem wrong, the char[] buff is the output array. Here is the updated version. I updated the ReadN too.

public int read2(byte[] buff, int sizeInBytes){
  int index = 0, next = 0;
  //assume return -1 if reach the end of the file
  byte[] tmp = new byte[256];
  while(index < sizeInBytes && (next = readFromDisk(tmp))!= -1)
   for(int i = 0; i< next && index < sizeInBytes; buff[index++] = tmp[i++]);
  return index;
 }
 public int readFromDisk(byte[] buff){
  return 256;
 }

This is similar to the LeetCode's ReadN question. I hijacked the code from java src (see here if you want the original).

public void read(int sizeInBytes) throws IOException{
  //readFromDisk() will read 256 bytes and put into 
  //the byte array, so we only need the size / 256
  int size = sizeInBytes / 256;
  byte[] b = new byte[size];
  int c = readFromDisk();
  //assume readFromDisk() will return -1 if the 
  //length is less than 256
  if(c == -1)
   return;
  b[0] = (byte)c;
  int i = 1;
  for(; i < size; i++){
   c = readFromDisk();
   //reach the end of the file
   if(c == -1)
    break;
   b[i] = (byte)c;
  }
 }
 public int readFromDisk(){
  return 255;
 }

Snakes and Ladders

Design an optimized algorithm to solve snakes and ladders with the least amount of roles possible under the assumption that you get whatever role you want when you role the dice.

I didn't even know about the game at first. As usual, if the question asks about "minimum" something, there is highly chance that it is a DP.

Just to describe the game for short:

It is a common board game, where you roll the dice and proceed the amount you get;
If you hit the lower side of the ladder, you are lucky, you move up to the upper side of the ladder;
If you face a snake (upper side of the snake), congratulations, go back to the tail (lower side) of the snake;
If you are the first one to proceed to the destination, you win.

If you are so interested in playing the game, consult Wikipedia.

Ok, back to the problem. Create a 1D array of length n * n, which is the minimum roles needed to proceed to that spot. If index < 6, then as long as it's not the upper side of the snake, it takes minimum 1 step. If index > 6, then it takes minimum from index - 6 to index - 1 plus 1 step, assuming normal condition. If it is the upper side of the ladder, it equals the step needed to go to the lower side of the ladder. If it is the upper side of a snake, since every time you hit this square, you always have to return, it takes infinity to go to the destination.

I use a struct to store the information on the board. The board of the test case can be viewed as this:

import java.util.*;
public class SnakesNLadders {
 public static int roles(Struct[][] board){
  if(board == null || board.length == 0 || board[0].length == 0 || board.length != board[0].length)
   return 0;
  int n = board.length;
  int[] roles = new int[n * n];
  for(int i = 0; i < n * n; i++){
   int x = i / n;
   int y = (x % 2 != 0) ? (n - 1 - i % n) : i % n;
   if(i < 6){
    roles[i] = board[x][y].s.equals("SU") ? Integer.MAX_VALUE / 2 : 1;
   }
   else{
    roles[i] = Integer.MAX_VALUE;
    for(int j = i - 6; j < i; j++)
     roles[i] = Math.min(roles[i], roles[j] + 1);
    if(board[x][y].s.equals("LU"))
     //in case the lower end of the ladder is the upper end of the
     //snake
     roles[i] = Math.min(ladder(board, x, y, roles),  roles[i]);
    else if(board[x][y].s.equals("SU"))
     roles[i] = Integer.MAX_VALUE / 2;
   }
  }
  
  return roles[n * n - 1];
 }
 private static int ladder(Struct[][] board, int x, int y, int[] roles){
  int n = board.length;
  int xc = board[x][y].x;
  return xc % 2 != 0 ? roles[xc * n + (n - 1 - board[x][y].y)]
     : roles[xc * n + board[x][y].y];
 }
 /**
  * consists the string which represents the status of the square:
  * "SU": snake upper side
  * "SL": snake lower side
  * "LU": ladder upper side
  * "LL": ladder lower side
  * as well as the coordinates of its corresponding end
  * e.g., "SU", 1, 1 indicates the lower side of the snake is at x = 1, y = 1 
  * @author shirleyyoung
  *
  */
 private static class Struct{
  String s;
  //the coordinate of the corresponding square
  int x;
  int y;
  public Struct(String s, int x, int y){
   this.s = s;
   this.x = x;
   this.y = y;
  }
 }
 public static void main(String[] args) {
  Struct[][] board = new Struct[4][4];
  for(int i = 0; i < 4; i++)
   //indicate nothing in the square
   Arrays.fill(board[i], new Struct("", -1, -1));
  board[0][1] = new Struct("SL", 1, 2);
  board[1][2] = new Struct("SU", 0, 1);
  board[0][3] = new Struct("LL", 2, 3);
  board[2][3] = new Struct("LU", 0, 3);
  board[1][1] = new Struct("SL", 3, 2);
  board[3][2] = new Struct("SU", 1, 1);
  board[1][0] = new Struct("LL", 2, 0);
  board[2][0] = new Struct("LU", 1, 0);
  System.out.println(roles(board));
 }
}

Markov String Generator

Update 2015 - 03 - 31:

Ok, I optimized to code and removed those cumbersome extra space. Now my code reads the strings from the file and generate the table directly.

public class StringGenerator2 {
 private class Frequency{
  String s;//hashcode of the string
  int count;//occurrence
  public Frequency(String s, int c){
   this.s = s;
   this.count = c;
  }
 }
 Map> table;
 Random r;
 public StringGenerator2(String fileName) throws FileNotFoundException, IOException{
  table = new HashMap> ();
  r = new Random();
  generateTable(fileName);
  assert(isUniqueList());
 }
 public void generateTable(String fileName) throws FileNotFoundException, IOException{
  BufferedReader reader = new BufferedReader(new FileReader(fileName));
  String line;
  String last = null;
  while((line = reader.readLine()) != null){
   String[] row = line.split(" ");
   for(String s : row){
    String puntua = null;
    if(!Character.isLetter(s.charAt(s.length() - 1))){
     puntua = s.substring(s.length() - 1);
     s = s.substring(0, s.length() - 1);
    }
    if(!table.containsKey(s))
     table.put(s, new ArrayList ());
    if(last != null)
     add(table.get(last), s);
    if(puntua != null)
     add(table.get(s), puntua);
    last = s;
   }
  }
  reader.close();
  mapFrequency();
 }
 private void add(List next, String s){
  int index = -1;
  for(int i = 0; i < next.size(); i++){
   if(next.get(i).s.equals(s)){
    index = i;
    break;
   }
  }
  if(index != -1)
   next.get(index).count++;
  else
   next.add(new Frequency(s, 1));
 }
 private void mapFrequency(){
  for(Entry> e : table.entrySet()){
   List next = e.getValue();
   for(int i = 1; i < next.size(); i++){
    next.get(i).count += next.get(i - 1).count;
   }
  }
 }
 private boolean isUniqueList(){
  Set words = new HashSet ();
  for(List next : table.values()){
   words.clear();
   for(Frequency f : next){
    if(!words.add(f.s))
     return false;
   }
  }
  return true;
 }
 public void generator(String outputName, int length) throws IOException{
  if(table.size() == 0){
   System.out.println("No training set found!");
   return;
  }
  FileWriter writer = new FileWriter(outputName);
  int index = 0;
  String last = null;
  int countWord = 0;//number of words in one line
  while(index < length){
   String s = null;
   if(last == null || !table.containsKey(last)){
    //generate a random string from the key set
    Object[] keys = table.keySet().toArray();
    s = (String) keys[r.nextInt(keys.length)];
   } else
    s = getNext(table.get(last));
   writer.append(s).append(" ");
   countWord++;
   if(countWord == 15){
    writer.append("\n");
    countWord = 0;
   }
   last = s;
   index++;
  }
  writer.append(".\n");
  writer.flush();
  writer.close();
 }
 private String getNext(List next){
  int size = next.size();
  int nextIndex = r.nextInt(next.get(size - 1).count) + 1;
  for(Frequency f : next){
   if(nextIndex <= f.count)
    return f.s;
  }
  return next.get(r.nextInt(size)).s;
 }
  
}

Too much fun for this morning. I saw this problem posted on Career Cup yesterday. I couldn't understand what the problem really meant (see here), especially after I took a look at Wikipedia's couldn't-be-more-confusing explanation on Markov chain. But Google never let me down. I found this blog, which explained it in a clearer way. In short, using Markov chain to generate a new String is like using Bayesian  to predict when the first snow in next year will happen: based on the probability of when the first snow in last couple years happened.

In short, given a training set of strings, we create a table of the probability of all the next strings after a given string. Then when we need to generate a new string, we randomly select the first string from our training set, then pick the next string based on the probability of each "next" string in the table given the last generated string.

To get the next string based on the pre-calculated probability, I used this method. Basically when you get the probability distribution. You generate a random number, and based on the corresponding range in the PDF, you select the string.

I have to say that my implementation is not a good one. First, I used a list to store all strings into the memory, it definitely will cause a problem if there are too many strings. However, I don't know how to check if the current string is already in the table if I don't put everything into the memory.

Next, I calculate the frequency, to do that, I used another map, which is used to count the occurrence of each "next" string, then use two arrays to sum up, and finally use a list of structure (string, accumulated frequency) to store all "next" strings, given one string key in the table. See how much extra space I have used, this is definitely not good.

Moreover, when we hit a punctuation, I added the punctuation into the "next" list but didn't include it as a key.

To actually generate the string is easy, as I mentioned before, just keep randomly generate the next string in the "next" string list based on the frequency.

There are lots of ways to optimize this implementation. But I think this is enough for interview/learning purpose.

package markovChain;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.*;
import java.util.Map.Entry;
public class StringGenerator {
 List trainingSet;
 String file;
 public StringGenerator(String file) throws FileNotFoundException, IOException{
  this.file = file;
  trainingSet = new ArrayList ();
  read();
 }
 /**
  * read training set and buffered it into a list
  * @throws FileNotFoundException
  * @throws IOException
  */
 public void read() throws FileNotFoundException, IOException{
  BufferedReader reader = new BufferedReader(new FileReader(file));
  String line;
  while((line = reader.readLine()) != null){
   String[] row = line.split(" ");
   for(String s : row)
    trainingSet.add(s);
  }
  reader.close();  
 }
 /**
  * Generate frequency table
  * @param output
  * @param length
  * @throws IOException
  */
 private Map> generateTable(){
  Map> frequencyTable = new HashMap> ();
  frequencyTable.put(trainingSet.get(0), new ArrayList ());
  for(int i = 1; i < trainingSet.size(); i++){
   String s = trainingSet.get(i);
   String p = null;
   if(!Character.isLetter(s.charAt(s.length() - 1))){
    p = s.substring(s.length() - 1, s.length());
    s = s.substring(0, s.length() - 1);
   }
   if(!frequencyTable.containsKey(s)){
    frequencyTable.put(s, new ArrayList ());
    if(p != null)
     frequencyTable.get(s).add(p);
   }
   String last = trainingSet.get(i - 1);
   if(!Character.isLetter(last.charAt(last.length() - 1)))
    last = last.substring(0, last.length() - 1);
   frequencyTable.get(last).add(s); 
  }
  Map> nextFrequency = getFrequency(frequencyTable);
  return nextFrequency;
 }
 private Map> getFrequency(Map> frequencyTable){
  Map> countFre = new HashMap>();
  for(Entry> e : frequencyTable.entrySet()){
   String key = e.getKey();
   List next = e.getValue();
   Map f = new HashMap();
   for(String s : next){
    if(!f.containsKey(s))
     f.put(s, 1);
    else
     f.put(s, f.get(s) + 1);
   }
   List nextFrequency = mapFrequency(f);
   countFre.put(key, nextFrequency); 
  }
  return countFre;
 }
 private List mapFrequency(Map f){
  String[] array = new String[f.size()];
  int[] c = new int[f.size()];
  int index = 0;
  for(Entry ec : f.entrySet()){
   array[index] = ec.getKey();
   c[index] = ec.getValue();
   index++;
  }
  for(int i = 1; i < c.length; i++){
   c[i] += c[i - 1];
  }
  List rst = new ArrayList ();
  for(int i = 0; i < c.length; i++)
   rst.add(new Frequency(array[i], c[i]));
  return rst;
 }
 
 
 /**
  * generate the string
  * @param output
  * @param length
  * @throws IOException
  */
 public void Generator(String output, int length) throws IOException{
  if(trainingSet.size() == 0){
   System.out.println("No training set found!");
   return;
  }
  Map> nextFrequency = generateTable();
  Random r = new Random();
  FileWriter writer = new FileWriter(output);
  int i = 0;
  String last = null;
  int countWord = 0;
  while(i < length){
   String s = null;
   if(last == null || !nextFrequency.containsKey(last))
    s = trainingSet.get(r.nextInt(trainingSet.size()));
   else
    s = getNext(nextFrequency.get(last));
   writer.append(s).append(" ");
   countWord++;
   if(countWord == 15){
    writer.append("\n");
    countWord = 0;
   }
   last = s;
   i++;
  }
  writer.append(".\n");
  writer.flush();
  writer.close();
 }
 private String getNext(List nextFre){
  int size = nextFre.size();
  Random r = new Random();
  int next = r.nextInt(nextFre.get(size - 1).count) + 1;
  for(Frequency f : nextFre){
   if(next <= f.count)
    return f.s;
  }
  return nextFre.get(r.nextInt(size)).s;
 }
 /**
  * the structure that contains the string and its count
  * @author shirleyyoung
  *
  */
 private class Frequency{
  String s;
  int count;
  public Frequency(String s, int c){
   this.s = s;
   count = c;
  }
 } 
}

Test
In order to show my averseness to the research that I am working on. I decide to use some paragraphs from the papers I am reading as the test case.

"The dynamics of flexible polymers in shear is of great practical interest because this type of flow occurs whenever a fluid flows past a surface. 

Macroscopic, non-Newtonian rheological properties of polymer solutions, such

as flow-dependent viscosities and normal

stresses, result from microscopic stresses that

arise when polymeric molecules are stretched

and affect the solvent motion. Thus, much

effort has been directed at predicting the molecular

dynamics of polymers in shear flows. However, it has been difficult to rigorously

test these predictions because the dynamics

of a polymer molecule in shear have

not been observed directly. Experimental efforts

have mainly focused on measuring bulk

rheological properties or on measuring the

scattering of light or neutrons by polymer

solutions. Here we describe how single-molecule imaging techniques can be

used to study the configurations of polymers

in shear flow so that the detailed molecular predictions of theories can be tested.

In short, Shirley doesn't care about how polymer tumbles in shear flow!

Polymer dynamics are of central importance in materials science,

mechanical engineering, biology and medicine. The dynamics of

macromolecular solutions and melts in shear flow are typically

studied using bulk experimental methods such as light and

neutron scattering and birefringence. But the effect of shear

on the conformation and dynamics of individual polymers is

still not well understood. Here we describe observations of the

real-time dynamics of individual, flexible polymers fluorescently

labelled DNA molecules under a shear flow. The sheared

polymers exhibit many types of extended conformation with an

overall orientation ranging from parallel to perpendicular with

respect to the flow direction. For shear rates much smaller than

the inverse of the relaxation time of the molecule, the relative

populations of these two main types of conformation are

controlled by the rate of the shear flow. These results question

the adequacy of assumptions made in standard models of polymer

dynamics."

Here is the 300 strings generated from the input.

"mainly focused on measuring bulk rheological properties or on measuring the rate of extended conformation 

and dynamics of individual flexible polymers in shear is still not been difficult to rigorously 

test these predictions of shear on measuring bulk rheological properties or on measuring bulk rheological 

properties of assumptions made in shear is still not been difficult to rigorously test these 

two main types of polymer solutions Here we describe how polymer solutions , the detailed 

molecular dynamics of the molecular predictions of light and normal stresses result from microscopic stresses 

that the shear on measuring the molecular predictions of polymers exhibit many types of individual 

flexible polymers fluorescently labelled DNA molecules are controlled by the shear is of extended conformation 

with an overall orientation ranging from microscopic stresses result from microscopic stresses that arise when 

polymeric molecules are of polymers in shear flow Polymer dynamics of flow occurs whenever a 

shear flows However , by the molecule in shear rates much effort has been observed 

directly Experimental efforts have mainly focused on the effect of conformation with an overall orientation 

ranging from microscopic stresses that arise when polymeric molecules under a surface . flexible polymers 

exhibit many types of light and normal stresses , rheological properties of the adequacy of 

a shear flow so that the detailed molecular dynamics of conformation are of polymers in 

shear flow occurs whenever a surface . under a shear flow Polymer dynamics of assumptions 

made in shear flow are controlled by the dynamics of extended conformation and neutron scattering 

and affect the molecule the effect of great practical interest because the scattering and affect 

the scattering of polymers is still not been difficult to study the solvent motion Thus 

, much smaller than the inverse of shear flow Polymer dynamics of conformation and medicine."

Well, not that bad. 

Print frequency

Given an unsorted array of natural numbers. Where numbers repeat in array. Out put numbers in the order of frequency. Where number of out put is passed as parameter.
For Ex:
Array -> [0, 0, 100, 3, 5, 4, 6, 4, 2, 100, 2, 100]
n -> 2
Out put -> [100, 0] or [100, 2]
Since 100 is repeated 3 times and 0, 2 is repeated 2 times, out put up to 2 most frequent elements, program should out put either 100, 0 or 100, 2

It doesn't look like there are ways (not on top of my mind) that we can avoid extra space. The PriorityQueue I created is fixed to the size of n, and it is a min heap. So each time I poll out the head if it is smaller than the one that is supposed to be put in, and add the new one into the queue. In the end, iterate through the queue and print out all elements in it.

public static void frequencyPrinter(int[] num, int n){
  if(num == null || num.length == 0)
   return;
  Map count = new HashMap ();
  for(int i : num){
   if(!count.containsKey(i))
    count.put(i, 1);
   else
    count.put(i, count.get(i) + 1);
  }
  PriorityQueue> pq = new PriorityQueue> (n, new countComparator());
  for(Entry e : count.entrySet()){
   if(pq.size() < n)
    pq.add(e);
   else{
    if(e.getValue() > pq.peek().getValue()){
     pq.poll();
     pq.offer(e);
    }
   }
  }
  Iterator> it = pq.iterator();
  while(it.hasNext()){
   System.out.println(it.next().toString());
  }
 }
 private static class countComparator implements Comparator>{
  public int compare(Entry a, Entry b){
   return a.getValue() - b.getValue();
  }
 }

Sort String

You are given two strings. String T is a string where characters need to be reordered. String O contains characters (none of them repeated) which defines the order/precendence to be used while reordering the string T. Write an algorithm to do the reordering.
*** SPOILER ALERT ***
The question was pusposefully underspecified - upon questioning it was revealed that the string O might not necessarily include all characters used in string T - the characters not included in string O are supposed to be placed at the beginning of the resulting string (in no particular order).

At first, I thought it is a type of counting sort, so I was trying to use an array. The spoiler reminds me that not all characters in String T is included in String O, so it probably is not. I finalized with a map implementation, which may not be the most optimal one consider the extra space I used.

public class SortString {
 public static String sortString(String T, String O){
  if(T == null || O == null || T.length() == 0 || O.length() == 0)
   return T;
  Map count = new HashMap ();
  for(int i = 0; i < O.length(); i++)
   count.put(O.charAt(i), 0);
  StringBuilder rst = new StringBuilder();
  for(int i = 0; i < T.length(); i++){
   char c = T.charAt(i);
   if(!count.containsKey(c))
    rst.append(c);
   else
    count.put(c, count.get(c) + 1);
  }
  for(int i = 0; i < O.length(); i++){
   char c = O.charAt(i);
   int num = count.get(c);
   while(num-- > 0){
    rst.append(c);
   }
  }
  return rst.toString();
 }

 public static void main(String[] args) {
  String T = "dcdavgtealgbm";
  String O = "abcdefghijkl";
  System.out.println(sortString(T, O));

 }

}

Apply Function to multiple machines

Part 1: You are given a computer #1 with array Foo, a computer #2 with array Bar and a spare computer #3. You need to apply a function F to corresponding/matching elements of the two arrays. How would you do that?
Part 2: Once you scale up, how would you balance the number of machines sorting with the machines applying the function?
Part 3: What if the master (which is distributing the work) dies and never recovers?

I would try to use my limited knowledge to approach this problem. The answer may or may not be correct. For the original problem, see here.


Part1:
From Part2, we know that we need to sort the two arrays. However, the problem is not clear on "matching elements", so I would say, sort them separately in two machines and merge the result in computer #3. We can also assign some elements of both arrays to computer #3 and let it do some of the work, then merge all 3 partially sorted arrays. However, we need to think about the band width problem when we try to distribute some data to the third machine. Any O(nlogn) sorting algorithm would be good.

So the next step is to find all needed elements, distribute them evenly  (to all three) and let them apply the function F.


Part2:
I think the problem may be, while sorting the array, if we find some elements that we need to apply to F, we can just send another job for applying F. The answer provided by the interviewee is quite nice:

Either run a small subset first to get an idea if it is linear distribution and then divide statically according to that or try to adapt during processing depending on the load of the machines.

Part3:
I would say to always keep a copy of the data to the other two machines (assuming we only have 3), and keep communicating with each other for data update. When one fails, use another one as the master.

Least significant digit of Fibonacci

Assume we only take the least significant digit of each value in fibonacci sequence, and form the sequence of digits into pairs. In those pairs, the first value of one pair is the same as second value of its predecessor. 

As we know the fibonacci sequence is 1, 1, 2, 3, 5, 8, 13, 21... 

so the pair sequence is: 

[1, 1], [1, 2], [2, 3], [3, 5], [5, 8], [8, 3], [3, 1] ... 

Write a function to output the first n pairs of this sequence. 

void Outputpairs(int n)

public class FibonacciLeastDigit {
 public static void outPutPairs(int n){
  int prevprev = 1;
  int prev = 1;
  for(int i = 1; i <= n; i++){
   System.out.format("[%d , %d]\n", prevprev, prev);
   int curr = (prevprev + prev) % 10;
   prevprev = prev % 10;
   prev = curr;
  }
 }

 public static void main(String[] args) {
  outPutPairs(13);
 }
}

Interweave array

Given an array Of integers build a new array of integers such that every 2nd element of the array is greater than its left and right element.

eg:
[1,4,5,2,3]

o/p:
[1,4,2,5,3]

Soln proposed:

Step 1:Sort The array -> O(nlogn)
Step 2:Use 2 indices: one starting at leftmost index and other at rightmost index.
and populate the new array alterntely using the left pointer(index) first and then the right pointer and then increment the pointer used. till both the pointers meet/cross each other. -> O(n).

I see this "simple" problems couple times and finally get the solution. If we break down the question, we will see that we actually need to maintain all triplets in the order of a <= b >= c.

I was stuck on the part on how to maintain the order of the triplets, in the end, I should just increment the index by 2 instead of 1.

public static void swapArray(int[] array){
  if(array == null || array.length <= 1)
   return;
  for(int i = 1; i < array.length; i += 2){
   if(array[i - 1] > array[i])
    swap(array, i - 1, i);
   if(i < array.length - 1 && array[i + 1] > array[i])
    swap(array, i, i + 1);
  }
 }
 private static void swap(int[] array, int i, int j){
  int tmp = array[i];
  array[i] = array[j];
  array[j] = tmp;
 }

Ice cream order

Write algorithm to determine the total time to make ice cream and when it leaves the store.
Consist of an order time, order number, and ice cream type.
“ice cream Type” is an integer: 0 for combo, 1 for vanilla. Order numbers are increasing.
We have three machines for making ice creams.
It takes 45 seconds to make a combo ice cream and 15 for vanilla. Can only make one ice cream at a time.
Need to determine total time to make ice cream and time the ice cream leaves the store (delivered).
In: order_time,order_num,ice_cream_type
Out: order_num,depart_time,total_time

This is a very interesting problem, I don't think I am at a very good approach, but it sort of works. Assuming we should process the problem in this way, each order comes continuously, so every time there is an available machine, we should use it for the new order.

Two thoughts:

First, use threads. Use takeOrder and finishOrder methods. Use a boolean variable available and ask the thread to wait before taking the order if the machine is working and wait before working if the machine hasn't taken any order. I can write a code if there is only one machine. However, the problem states that there are three machines, I stuck in how to create three threads and share the variable of number of ice cream in each order.

Second, write a machine class and create three objects. This approach is based on the assumption that, first, the start time of the next order is the later between the order time and the end time of the previous order, and second, the total time of finishing an order only depends on the number of orders, or the longest worked time among all three machines, and depart time is start time plus total time.

I think I missed something. But I don't know what. Moreover, I cannot generalize this approach, i.e., what if there are N machines?

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class RunMachine {

 public static void main(String[] args) {
  BufferedReader br = null;
  String currLine;
  Machine machine1 = new Machine();
  Machine machine2 = new Machine();
  Machine machine3 = new Machine();
  int iceCreamType;
  int orderNumber;
  int startTime;
  int totalTime;
  int nextStartTime = 0;
  try{
   br = new BufferedReader(new FileReader("iceCreamOrder.txt"));
   while((currLine = br.readLine()) != null){
    String[] order = currLine.split(" ");
    //start time is the later between the order time and the time when last order is finished
    startTime = (Integer.parseInt(order[0]) > nextStartTime) ? Integer.parseInt(order[0]) : nextStartTime;
    orderNumber = Integer.parseInt(order[1]);
    iceCreamType = Integer.parseInt(order[2]);
    int totalNumber = orderNumber;
    while(orderNumber > 0){
     machine1.getOrder(orderNumber--, iceCreamType);
     machine2.getOrder(orderNumber--, iceCreamType);
     machine3.getOrder(orderNumber--, iceCreamType);
     if(machine1.isFinished() || machine2.isFinished() || machine3.isFinished())
      break;
    } 
    totalTime = Math.max(machine1.getTime(), Math.max(machine2.getTime(), machine3.getTime()));
    int departTime = startTime + totalTime;
    System.out.format("%d, %d, %d\n", totalNumber, departTime, totalTime);
    machine1.set();
    machine2.set();
    machine3.set();
    nextStartTime = departTime;
    
   }
  } catch (Exception e){
   System.out.println(e);
  }
  finally {
   if(br != null){
    try{
     br.close();
    } catch (IOException er){
     er.printStackTrace();
    }
   } 
  }

 }

}
public class Machine {
 private boolean finished = false;
 private int timeWorked = 0;
 
 public void getOrder(int orderNumber, int orderType){
  if(orderNumber == 0){
   finished = true;
   return;
  }
  timeWorked += orderType == 0 ? 45 : 15;
 }
 public int getTime(){
  return timeWorked;
 }
 public void set(){
  timeWorked = 0;
  finished = false;
 }

 public boolean isFinished(){ 
  return finished;
 }
}

Diameter of a graph

Problem Statement
Diameter
The diameter of a graph is the maximum shortest path between any two nodes.
At the beginning, there is a simple grpah contains exactly 1 node. Then we add new nodes one by one to the graph. Each time when we add a new node to the graph, we also add exactly one edge to connect this node to another node which already exists.
We want to find the diameter of the graph each time we add a new node. Note that each edge cost 1.
Input Format:
First line of the input contains one integer N, indicating how many new nodes we will add.
Then following N lines. The ith line contains an integer X, which means we add the ith node and an edge connecting the Xth node and ith node.
The original node is the 0th node.
Output Format:
Output N lines. The ith line is an integer indicating the diameter of the graph after adding the ith node.
Constraints:
0 < N <= 100000
0 <= Xi < i
i is counting from 1
Sample Input:
5
0
0
1
1
1
Sample Output:
1
2
3
3
3
Explanation:
Firstly the graph contains only node 0. The first line of output is 1 because the diameter becomes 1 when node 1 is added and connected to node 0. Diameter becomes 2 after adding node 2 to node 0. Then adding node 3, 4, 5, all of them are connecting to node 1, caculate the shortest path of all pairs of nodes, the maximum shortest path is 3, so the last 3 lines of output are all 3.

My approach is based on the assumption that

1. The constructed graph is a tree
2. The shortest distance between any node pair will not change when the new node is added. 

Somehow I think my approach is correct, but I don't know how to prove it.

public class Diameter {
 static int N;
 static int[][] shortestPath;
 static int newNode = 0;
 public static void maxShortestDistance(String input){
  Stdin inStream = new Stdin(input);
  N = Integer.parseInt(inStream.readLine());
  shortestPath = new int[N + 1][N + 1];
  for(int i = 0; i <= N; i++)
   //Integer.MAX_VALUE will overflow
   Arrays.fill(shortestPath[i], Integer.MAX_VALUE / 2);
  for(int i = 0; i <= N; i++)
   shortestPath[i][i] = 0;
  int max = 0;
  try{
   while(!inStream.isEmpty()){
    newNode++;
    int connected = Integer.parseInt(inStream.readLine());
    shortestPath[connected][newNode] = 1;
    shortestPath[newNode][connected] = 1;
    for(int i = 0; i < newNode; i++){
     for(int j = 0; j < newNode; j++){
      shortestPath[i][newNode] = Math.min(shortestPath[i][newNode], 
        shortestPath[i][j] + shortestPath[j][newNode]);
     }
     shortestPath[newNode][i] = shortestPath[i][newNode];
     max = Math.max(max, shortestPath[i][newNode]);
     //System.out.println(i + " to " + newNode + ": " + shortestPath[newNode][i]);
    }
    System.out.println(max);
   }
  } catch (Exception e){
   System.out.println(e);
  }
  
  inStream.close();
 }

 public static void main(String[] args) {
  maxShortestDistance("/Users/shirleyyoung/Documents/workspace/Google/src/maxShortestDistance.txt");
 }
}