Saturday, November 2, 2013

SRM596


Level 1 Level 2 Level 3
Div 1 Level 1 Level 2 Level 3
Div 2 Level 1 Level 2 Level 3


Tutorials:


Division One - Level Three:

Solution

Source Code:


Division One - Level Two:

Solution

Source Code:


Division One - Level One:

Solution

Source Code:


Division Two - Level Three:

Solution

Source Code:


Division Two - Level Two:

Solution

Using recursive function to try all of the possible way.

Source Code:

import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class ColorfulRoad
{
	private static final char[] nextC = {'R', 'G', 'B'};
	public int getMin(String road)
	{
		int min = minCost(road.substring(1), 1);
		return min == Integer.MAX_VALUE ? -1 : min;
	}

	private int minCost(String road, int next){
		if(road.length() ==0) return 0;
		long min = Integer.MAX_VALUE;
		for(int i=0; i<road.length(); i++){
			if(road.charAt(i) == nextC[next]){
				//System.out.println(road);
				int tmp = minCost(road.substring(i+1), (next+1)%3);
				if (tmp == Integer.MAX_VALUE) continue;
				min = Math.min(min, (i+1)*(i+1)+ tmp);
			}
		}
		return (int)min;
	}
}
//Powered by [KawigiEdit] 2.0!



Division Two - Level One:

Solution

Source Code:

import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class FoxAndSightseeing
{
	public int getMin(int[] position)
	{
		int min = Integer.MAX_VALUE;
		for(int i=1; i<position.length-1; i++){
			int last = 0;
			int sum = 0;
			for(int j=0; j<position.length; j++){
				if(i!=j){
					sum += Math.abs(position[j] - position[last]);
					last = j;
				}
			}
			min = Math.min(min, sum);
		}
		return min;
	}
	
	
}

Wednesday, October 30, 2013

How to Get The Kth Smallest Element in an Array

Problem:

As the title said, "How to get the kth smallest element in an array?"
This array could be totally unordered.

Solution:

Most intuitive method for this problem would be sort the array, then return the kth value of the array, which cost O(NlogN) + O(1), which is O(NlogN). But there is O(N) algorithms for average case called Selective Algorithms.

It's very like Quick-Sort Algorithm, but this one always cuts the array in two, and choose the one we need. So it would be like:
T(n) = T(P) + O(n) , P is one of (1 , n)
 For average, P would be n/2, since we choose it randomly, then we could have T(n) = O(n).

If K is n/2, then this problem turns to be finding the medium element of array.

This is a very popular interview question, so have fun.


Source Code:

private int getKthSmallestElement(int[] uA, int start, int end, int kth) {
  print(uA, start, end);
  Random r = new Random();
  int pivot = start + r.nextInt(end - start + 1);
  System.out.println(String.format("Pivot Element %d", uA[pivot]));
  int tmp = uA[start];
  uA[start] = uA[pivot];
  uA[pivot] = tmp;
  pivot = start;
  int i, j;
  for (i = start + 1, j = end; i < j;) {
   while (uA[i] <= uA[pivot] && i < j)
    i++;
   while (uA[j] > uA[pivot] && i < j)
    j--;
   if (i < j) {
    tmp = uA[i];
    uA[i] = uA[j];
    uA[j] = tmp;
    i++;
    j--;
   }
  }

  if (i > j || uA[i] > uA[pivot]) {
   i--;
  }
  tmp = uA[i];
  uA[i] = uA[pivot];
  uA[pivot] = tmp;
  pivot = i;

  System.out.println(String.format("(Start, End) : (%d %d)", start, end));
  print(uA, start, end);
  System.out.println(String.format("(i, j) : (%d %d)", i, j));
  System.out.println(String.format("Pivot: %d\n", pivot));
  if (pivot + 1 == kth)
   return uA[pivot];
  else if (pivot + 1 > kth) {
   return getKthSmallestElement(uA, start, pivot - 1, kth);
  } else
   return getKthSmallestElement(uA, pivot + 1, end, kth);
 }

 private void print(int[] array, int start, int end) {
  for (int i = start; i <= end; i++)
   System.out.print(" " + array[i]);
  System.out.println();
 }

Monday, October 28, 2013

Insert into a Cyclic Sorted List

Problem:

 * Given a node from a cyclic linked list which has been sorted, 
 * write a function to insert a value into the list such that it remains a cyclic sorted list. 
 * The given node can be any single node in the list.

Solution:




Source Code:


/**
 * Given a node from a cyclic linked list which has been sorted, 
 * write a function to insert a value into the list such that it remains a cyclic sorted list. 
 * The given node can be any single node in the list.
 */

/**
 * @author Antonio081014
 * @since Oct 28, 2013, 10:43:52 AM
 */
public class Test {

 public static void main(String[] args) {
  CycledList list = new CycledList();
  list.print();
  list.insert(3);
  list.print();
  list.insert(1);
  list.insert(1);
  list.print();
 }
}

class CycledList {
 public Node head;

 /**
  * Several Cases:

  * 1st, when linked list is empty; 

  * 2nd, when new element is either minimum or maximum; 

  * 3rd, when new element is in between two sorted elements. 

  * 
  * 
  * Since this list is like a circle, we don't necessary to have the smallest
  * element as the head, but it's definitely sorted.
  * */
 public void insert(int x) {
  // 1st Case;
  if (head == null) {
   head = new Node(x);
   head.next = head;
   return;
  }
  Node p = head;
  Node prev = null;
  do {
   prev = p;
   p = p.next;
   // 2nd Case;
   if (prev.data >= p.data && (x <= p.data || x >= prev.data))
    break;
   // 3rd Case;
   if (prev.data <= x && p.data >= x)
    break;
  } while (p != head);
  Node tmp = new Node(x);
  prev.next = tmp;
  tmp.next = p;
 }

 public void print() {
  if (head == null) {
   System.out.println("Empty Cycled List");
   return;
  }
  Node p = head;
  do {
   System.out.print(p.data + " ");
   p = p.next;
  } while (head != p);
  System.out.println();
 }
}

class Node {
 public int data;
 public Node next;

 public Node(int x) {
  this.data = x;
  next = null;
 }

 public Node(int x, Node n) {
  this.data = x;
  this.next = n;
 }
}


Tuesday, August 27, 2013

SRM589


Level 1 Level 2 Level 3
Div 1 Level 1 Level 2 Level 3
Div 2 Level 1 Level 2 Level 3


Tutorials:


Division One - Level Three:

Solution

Source Code:


Division One - Level Two:

Solution

Source Code:


Division One - Level One:

Solution

Generally, this problem asks to connect character in the palindrome place. For instance, string "abcde", then, 'a' will group with 'e', 'b' will group with 'd', 'c' will group with 'c'. By default, any English character will group with itself. For another example, string "abcbde", 'a' will group with 'e', 'b' will group with 'd', 'c' will group with 'b', while 'b' and 'd' are in the same group, then 'b', 'c', 'd' are in the same group, so we have two groups, [a,e] and [b,c,d].

So, for this problem, we will count the number of changes from non-maximum characters to the maximum count character for each group.

So, for the first step, grouping each English character is implemented by three different methods.
getmin2 uses Flood Fill (DFS). O(N), N is the length of String S.
getmin3 uses Floyd–Warshall algorithm. O(26^3)
getmin uses Union-Find data structure with Path Compression.  Time Complexity: < O(N)

So, for N <= 50, it looks like the getmin function is the fastest one.

Source Code:

public class GooseTattarrattatDiv1 {

 private int[] count;
 private boolean[] notVisited;

 public int getmin2(String S) {
  count = new int[26];
  int min = S.length();
  int N = S.length();
  notVisited = new boolean[26];
  for (int i = 0; i < N; i++) {
   int a = S.charAt(i) - 'a';
   count[a]++;
   notVisited[a] = true;
  }
  for (int i = 0; i < N; i++) {
   min -= dfs(S.charAt(i), S);
  }
  return min;
 }

 /**
  * Find the maximum number of characters connect to c in s; It's like a
  * chain. We need to find the node in the chain with maximum cost; The
  * algorithm here is like Flood Fill;
  * */
 private int dfs(char c, String s) {
  if (notVisited[c - 'a'] == false)
   return 0;
  int max = count[c - 'a'];
  notVisited[c - 'a'] = false;
  for (int i = 0; i < s.length(); i++) {
   if (c == s.charAt(i))
    max = Math.max(max, dfs(s.charAt(s.length() - 1 - i), s));
  }
  return max;
 }

 /**
  * Floyd–Warshall algorithm

  * Finding all the connectivity for all the characters from 'a' to 'z'.

  * Then, find the maximum and total characters for each group (subgraph),
  * make all the rest of characters change to the character holds the
  * maximum, Thus, it costs (total - maximum);
  * */
 public int getmin3(String s) {
  int N = s.length();
  int[] counter = new int[26];
  boolean[][] connected = new boolean[26][26];
  for (int i = 0; i < N; i++) {
   counter[s.charAt(i) - 'a']++;
  }
  for (int i = 0; i < N - i; i++) {
   int a = s.charAt(i) - 'a';
   int b = s.charAt(N - i - 1) - 'a';
   connected[a][b] = true;
   connected[b][a] = true;
  }

  for (int i = 0; i < 26; i++)
   connected[i][i] = true;
  for (int k = 0; k < 26; k++) {
   for (int i = 0; i < 26; i++) {
    for (int j = 0; j < 26; j++) {
     connected[i][j] |= connected[i][k] && connected[k][j];
    }
   }
  }
  int ret = 0;
  for (int i = 0; i < N; i++) {
   if (counter[s.charAt(i) - 'a'] <= 0)
    continue;
   int total = 0;
   int max = 0;
   for (int j = 0; j < 26; j++) {
    if (connected[s.charAt(i) - 'a'][j]) {
     total += counter[j];
     max = Math.max(max, counter[j]);
     counter[j] = 0;
    }
   }
   ret += total - max;
  }
  return ret;
 }

 /**
  * This problem actually asks to group 'a' - 'z'. Here I use the Union-Find
  * data structure to speed this process up;
  * */
 public int getmin(String S) {
  int[] count = new int[26];
  for (int i = 0; i < S.length(); i++) {
   count[S.charAt(i) - 'a']++;
  }
  int min = 0;
  Union_Find set = new Union_Find(26);
  for (int i = 0; i < S.length() - 1 - i; i++) {
   set.union(S.charAt(i) - 'a', S.charAt(S.length() - 1 - i) - 'a');
  }
  for (int i = 0; i < 26; i++) {
   int total = 0;
   int max = 0;
   for (int j = 0; j < 26; j++) {
    if (set.find(j) == set.find(i)) {
     total += count[j];
     max = Math.max(max, count[j]);
     count[j] = 0;
    }
   }
   min += total - max;
  }
  return min;
 }

 class Union_Find {
  public int[] parents;

  public Union_Find(int N) {
   parents = new int[N];
   for (int i = 0; i < N; i++) {
    parents[i] = i;
   }
  }

  public int find(int x) {
   if (x == parents[x])
    return x;
   return parents[x] = find(parents[x]);
  }

  public void union(int x, int y) {
   int xx = find(x);
   int yy = find(y);
   if (xx != yy) {
    this.parents[xx] = yy;
   }
  }
 }
}


Sivision Two - Level Three:

Solution

Source Code:


Division Two - Level Two:

Solution

This is a Dynamic Programming problem, people could easily find out the dp state formula for this problem. For every gear, people could choose use it or remove it. So we could either use the current gear or not use current one, which depends on the previous state.

For this problem, I tried to find the number of most gears we could use to work, which equals to the problem finds the fewest removal of gears to make it work.

But this problem has one thing requires your attention, which asks you to make this gear string in circular, that means the first and very last one is connected. This brings the challenge, while bringing the convenience for us. We could start at any point in this circular, so we ideally choose the 0th one to start, but we have to remember for every state that if any current state result depends on using the 0th gear or not. Then at last, we need to check if we use the 0th gear for my last state result, when first and last gear direction is the same. If the result depends on it, then we should not use the last gear, otherwise just use it, since it will bring you one more gear to use.

Source Code:

import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class GearsDiv2 {

 public int getmin(String dir) {
  int[][] dp = new int[dir.length()][2];
  boolean[][] hasFirst = new boolean[dir.length()][2];
  dp[0][0] = 0;
  dp[0][1] = 1;
  hasFirst[0][0] = false;
  hasFirst[0][1] = true;
  for (int i = 1; i < dir.length(); i++) {
   if (dp[i - 1][0] == dp[i - 1][1]) {
    hasFirst[i][0] = hasFirst[i - 1][0] && hasFirst[i - 1][1];
    dp[i][0] = dp[i - 1][1];
   } else if (dp[i - 1][0] > dp[i - 1][1]) {
    hasFirst[i][0] = hasFirst[i - 1][0];
    dp[i][0] = dp[i - 1][0];
   } else {
    hasFirst[i][0] = hasFirst[i - 1][1];
    dp[i][0] = dp[i - 1][1];
   }
   // dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
   if (dir.charAt(i) != dir.charAt(i - 1)) {
    dp[i][1] = 1 + dp[i][0];
    hasFirst[i][1] = hasFirst[i][0];
   } else {
    dp[i][1] = dp[i - 1][0] + 1;
    hasFirst[i][1] = hasFirst[i - 1][0];
   }
  }
  // return dir.length() - Math.max(dp[dir.length()-1][0],
  // dp[dir.length()-1][1]);
  if (dir.charAt(dir.length() - 1) != dir.charAt(0)) {
   return dir.length()
     - Math.max(dp[dir.length() - 1][0], dp[dir.length() - 1][1]);
  } else {
   if (hasFirst[dir.length() - 1][1]) {
    return dir.length() - dp[dir.length() - 1][0];
   } else {
    return dir.length() - dp[dir.length() - 1][1];
   }

  }
 }
 // <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!

The second solution comes from TC tutorial. The two key ideas of this recursion solution are:
1, Don't be trapped by this circular requirement, for the first and last gears, we only have four possibilities, we keep them both, keep first, keep last and remove them both. Since we are using a recursion to solve this problem, the 4th possibility will come through one of 2nd and 3rd case, since remove one, we could possibly remove the other later. This way, we could get rid of circular trap and treat the new string as a linear problem.
2, In the linear problem, when two adjacent gears are the same, we have to remove one of them, here we absolutely remove the second one. Further detail reason, check out the link.

public class GearsDiv2 {
 public int getmin(String dir) {
  int N = dir.length();
  int ret = N - 1;
  if (dir.charAt(0) != dir.charAt(N - 1))
   ret = Math.min(ret, getminLinear(dir));
  ret = Math.min(ret, 1 + getminLinear(dir.substring(1)));
  ret = Math.min(ret, 1 + getminLinear(dir.substring(0, N - 1)));
  return ret;
 }

 private int getminLinear(String dir) {
  if (dir.length() < 2)
   return 0;
  // change the second one to '_'
  if (dir.charAt(0) == dir.charAt(1)) {
   return 1 + getminLinear(dir.substring(2));
  }
  return getminLinear(dir.substring(1));
 }
}

Division Two - Level One:

Solution

Source Code:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class GooseTattarrattatDiv2
{
 public int getmin(String s)
 {
  int[] count = new int[26];
  int max = 0;
  int index = -1;
  for(int i=0; i<s.length(); i++){
   count[s.charAt(i)-'a']++;
   if(max < count[s.charAt(i)-'a'])
   {
    max = count[s.charAt(i)-'a'];
    index = s.charAt(i)-'a';
   }
  }
  
  int ret = 0;
  for(int i=0; i<26; i++){
   if(count[i] > 0 && i != index){
    ret += count[i];
   } 
  }
  return ret;
 }
}
//Powered by [KawigiEdit] 2.0!

Tuesday, August 13, 2013

Binary Tree Level-Order Traversal

Problem:

Yesterday(8/12/2013), I was asked to implement this problem Binary Tree Level-Order Traversal in a short time. For the first thought, it looks like an easy BFS problem, but quickly I realize a problem how can I track the level of the tree? Haha...

At the end, I gave my solution, but the interviewee said my solution is most weird one he has ever seen. LOL... I don't know what will be coming for me, but it's a great experience, and we'll see.

The following are my solutions for this problem with different strategy. Have Fun.

PS: every solution I provided uses Linear time and space. Approvement might be attached.

Source Code:


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
/**
 * This is a demo class in java <br />
 * Implementing Binary Tree Traverse Level By Level with BFS and DFS. <br /> 
 * All of the algorithm I implemented use O(N) time, N here represents the number of nodes in the tree.
 * 
 */
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Antonio081014
 * @since Aug 13, 2013, 9:22:40 AM
 */
public class Solution {

 public static void main(String[] args) {
  Solution main = new Solution();
  Node root = main.new Node("3");
  root.left = main.new Node("9");
  root.right = main.new Node("20");
  root.right.left = main.new Node("15");
  root.right.right = main.new Node("7");
  main.printLevelOrder_Option4(root);
  System.exit(0);
 }

 /**
  * Tree node structure;
  * */
 class Node {
  String value;
  Node left;
  Node right;

  public Node(String v) {
   value = v;
   left = null;
   right = null;
  }
 }

 /**
  * This is the answer I gave when I was in the interview.<br />
  * Basically, track the number of children we counted, if all the children
  * in that level is counted, then we print a newline and increase the tree
  * level; The flaw of this algorithm is it can not take too many levels,
  * since integer in java can't exceed 2^32; which means we maximumly will
  * have 32 levels, even if we use long instead of int, this one is still not
  * a good choice.
  * */
 private void printLevelOrder_Option0(Node root) {
  if (root == null)
   return;
  Queue<Node> queue = new LinkedList<Node>();
  int level = 1;
  int count = 0;
  queue.add(root);
  while (!queue.isEmpty()) {
   Node node = queue.poll();
   if (count == 0)
    System.out.print(node.value);
   else
    System.out.print(" " + node.value);

   if (node.left != null)
    queue.add(node.left);
   if (node.right != null)
    queue.add(node.right);
   count += 2;

   if (count == (int) Math.pow(2, level)) {
    System.out.println();
    level++;
    count = 0;
   }
  }
 }

 /**
  * Generally, this algorithm uses BFS, which involves two queues keep tracks
  * of node in current level and nodes in next leve;<br />
  * Basically,<br />
  * 1, When a node is extracted, we print it, while adding its children to
  * the next level if they are not null;<br />
  * 2, When current level queue is empty, which means all of the current
  * nodes are extracted and printed, also all the children of current level
  * nodes are added to the next level queue. So we could just copy every
  * single node in next level queue and add it to the current queue, and
  * print the newline.
  * */
 private void printLevelOrder_Option1(Node root) {
  if (root == null)
   return;
  Queue<Solution.Node> currentLevel = new LinkedList<Solution.Node>();
  Queue<Solution.Node> nextLevel = new LinkedList<Solution.Node>();
  currentLevel.add(root);
  while (!currentLevel.isEmpty()) {
   Solution.Node node = currentLevel.poll();
   System.out.print(node.value + " ");
   if (node.left != null)
    nextLevel.add(node.left);
   if (node.right != null)
    nextLevel.add(node.right);
   if (currentLevel.size() == 0) {
    System.out.println();
    while (!nextLevel.isEmpty()) {
     currentLevel.add(nextLevel.poll());
    }
   }
  }
 }

 /**
  * For this algorithm, we use two counters to keep track of number of nodes
  * in current level, and the number of nodes in next level; <br />
  * This idea is very similar with printLevelOrder_Option1(Node root),
  * however, it uses less memory and doesn't need to copy each node from one
  * queue to another.
  * */
 private void printLevelOrder_Option2(Node root) {
  if (root == null)
   return;
  Queue<Node> queue = new LinkedList<Node>();
  int nodesInCurrentLevel = 0;
  int nodesInNextLevel = 0;
  queue.add(root);
  nodesInCurrentLevel++;
  while (!queue.isEmpty()) {
   Node node = queue.poll();
   System.out.print(" " + node.value);
   nodesInCurrentLevel--;
   if (node.left != null) {
    queue.add(node.left);
    nodesInNextLevel++;
   }
   if (node.right != null) {
    queue.add(node.right);
    nodesInNextLevel++;
   }
   if (nodesInCurrentLevel == 0) {
    System.out.println();
    nodesInCurrentLevel = nodesInNextLevel;
    nodesInNextLevel = 0;
   }
  }
 }

 /**
  * This algorithm uses a trick of BFS.<br />
  * Since we are using BFS to traverse this binary tree level by level in a
  * very nature way. We just add a newline node at the very beginning, then
  * if this newline node is reached, that means all of nodes of current nodes
  * has been visited, so we are going to move to the next level, then print
  * the newline here.
  * 
  * This trick uses the nature of BFS in binary, very smart. I think the
  * interviewee was trying to ignite me to this solution. Somehow, I didn't
  * get it. For this algorithm, user could replace this newline node with
  * other flag node for other purposes.
  * */
 private void printLevelOrder_Option3(Node root) {
  if (root == null)
   return;
  Queue<Node> queue = new LinkedList<Node>();
  queue.add(root);
  queue.add(new Node("\n"));
queue.add(new Node("\n"));
  while (queue.size() > 1) {
   Node node = queue.poll();
   System.out.print(node.value + " ");
   if (node.value.compareTo("\n") == 0) {
    queue.add(node);
    continue;
   }
   if (node.left != null)
    queue.add(node.left);
   if (node.right != null)
    queue.add(node.right);
  }
 }

 /**
  * This algorithm uses DFS;<br />
  * 1, Get the height from root tree node.<br />
  * 2, For each level, print the nodes on that level with a newline.
  * 
  * Although the DFS solution traverse the same node multiple times, it is
  * not another order slower than the BFS solution. Here is the proof that
  * the DFS solution above runs in O(N) time, where N is the number of nodes
  * in the binary tree and we assume that the binary tree is balanced.
  * 
  * We first compute the complexity of printLevel for the kth level:
  * 
  * T(k) <br />
  * = 2T(k-1) + c <br />
  * = 2k-1 T(1) + c <br />
  * = 2k-1 + c
  * 
  * Assuming it’s a balanced binary tree, then it would have a total of lg N
  * levels. Therefore, the complexity of printing all levels is:
  * 
  * T(1) + T(2) + ... + T(lg N) = 1 + 2 + 22 + ... + 2lg N-1 + c = O(N)
  * Finding the maximum height of the tree also takes O(N) time, therefore
  * the overall complexity is still O(N).
  * */
 private void printLevelOrder_Option4(Node root) {
  int height = treeLevel(root);
  for (int i = 1; i <= height; i++) {
   printLevel(root, i);
   System.out.println();
  }
 }

 /**
  * Print the nodes on Level: level.
  * */
 private void printLevel(Node root, int level) {
  if (root == null)
   return;
  if (level == 1) {
   System.out.print(root.value + " ");
  } else {
   printLevel(root.left, level - 1);
   printLevel(root.right, level - 1);
  }
 }

 private int treeLevel(Node root) {
  if (root == null)
   return 0;
  return 1 + Math.max(treeLevel(root.left), treeLevel(root.right));
 }
}

Saturday, August 3, 2013

USACO: Beef McNuggets

Problem Links:

USACO_nuggets.

Problem:

Beef McNuggets
Hubert Chen
Farmer Brown's cows are up in arms, having heard that McDonalds is considering the introduction of a new product: Beef McNuggets. The cows are trying to find any possible way to put such a product in a negative light.
One strategy the cows are pursuing is that of `inferior packaging'. ``Look,'' say the cows, ``if you have Beef McNuggets in boxes of 3, 6, and 10, you can not satisfy a customer who wants 1, 2, 4, 5, 7, 8, 11, 14, or 17 McNuggets. Bad packaging: bad product.''
Help the cows. Given N (the number of packaging options, 1 <= N <= 10), and a set of N positive integers (1 <= i <= 256) that represent the number of nuggets in the various packages, output the largest number of nuggets that can not be purchased by buying nuggets in the given sizes. Print 0 if all possible purchases can be made or if there is no bound to the largest number.
The largest impossible number (if it exists) will be no larger than 2,000,000,000.

PROGRAM NAME: nuggets

INPUT FORMAT

Line 1:N, the number of packaging options
Line 2..N+1:The number of nuggets in one kind of box

SAMPLE INPUT (file nuggets.in)

3
3
6
10

OUTPUT FORMAT

The output file should contain a single line containing a single integer that represents the largest number of nuggets that can not be represented or 0 if all possible purchases can be made or if there is no bound to the largest number.

SAMPLE OUTPUT (file nuggets.out)

17

Solution:

1st, check if the answer existed and can be represented. If not return 0;
2nd, Using Dynamic Programming to mark all the possible solution, till reach the boundary.

Source Code: [on GitHub]


/*
 ID: 
 LANG: JAVA
 PROG: nuggets 
 */
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;

/**
 * @author antonio081014
 * @time Jul 28, 2013, 3:26:58 PM
 */
public class nuggets {

  private static final int SIZE = 100000;
 private boolean[] mark;

 public static void main(String[] args) {
  nuggets main = new nuggets();
  main.run();
  System.exit(0);
 }

 private void run() {
  try {
   BufferedReader in = new BufferedReader(new FileReader("nuggets.in"));
   PrintWriter out = new PrintWriter(new FileWriter("nuggets.out"));
   int N = Integer.parseInt(in.readLine());
   int[] array = new int[N];
   for (int i = 0; i < N; i++) {
    array[i] = Integer.parseInt(in.readLine());
   }
   in.close();
   out.println(solve(array));
   out.close();
  } catch (Exception e) {
   e.printStackTrace();
  }
 }

 private int solve(int[] array) {
  mark = new boolean[SIZE];
  boolean flag = true;
  for (int i = 0; i < array.length; i++)
   for (int j = i + 1; j < array.length; j++)
    if (gcd(array[i], array[j]) == 1)
     flag = false;
  if (flag)
   return 0;

  int max = 0;
  mark[0] = true;
  for (int i = 0; i < SIZE; i++) {
   if (!mark[i])
    max = i;
   else
    for (int j = 0; j < array.length; j++) {
     if (i + array[j] < SIZE)
      mark[i + array[j]] = true;
    }
  }
  return max;
 }

 public int gcd(int a, int b) {
  if (b == 0)
   return a;
  else
   return gcd(b, a % b);
 }
}

Monday, July 29, 2013

Update

I just upload my code solving USACO Training, Poj, UVa oj to Github to share with other programmers.

PS: The recent code I wrote has more comments in it. Hope I get a chance to add comment for my older code.

Saturday, July 6, 2013

Generic AVL Tree Implementation in Java

UPDATE: Thanks to +Josh Dotson, who figured out the big mistakes I made, which resulted the AVL insert into a O(n) implementation. PS: depth of the tree is important.

Speaking of AVL Tree, I guess most of people with Computer Science(CS) background would not be unfamiliar with it. It's one of most famous self balanced binary search tree exists so far. So for the basic background information, please check on this Wiki Link. One thing very important is every basic action of AVL Tree takes O(logn). That is so wonderful.

I assume people read this blog already knew what Java Generic Programming means, even he/she doesn't know how to implement it. I believe this code is pretty easy to understand.

First of all, What do we store in our tree, so let's define our data type for our data to be stored in our tree. We typically name it as Node.

/**
 * 
 */

/**
 * @author antonio081014
 * @time Jul 5, 2013, 9:31:32 PM
 */
public class Node<T extends Comparable<T>> implements Comparable<Node<T>> {

 private T data;
 private Node<T> left;
 private Node<T> right;
 public int level;
 private int depth;

 public Node(T data) {
  this(data, null, null);
 }

 public Node(T data, Node<T> left, Node<T> right) {
  super();
  this.data = data;
  this.left = left;
  this.right = right;
  if (left == null && right == null)
   setDepth(1);
  else if (left == null)
   setDepth(right.getDepth() + 1);
  else if (right == null)
   setDepth(left.getDepth() + 1);
  else
   setDepth(Math.max(left.getDepth(), right.getDepth()) + 1);
 }

 public T getData() {
  return data;
 }

 public void setData(T data) {
  this.data = data;
 }

 public Node<T> getLeft() {
  return left;
 }

 public void setLeft(Node<T> left) {
  this.left = left;
 }

 public Node<T> getRight() {
  return right;
 }

 public void setRight(Node<T> right) {
  this.right = right;
 }

 /**
  * @return the depth
  */
 public int getDepth() {
  return depth;
 }

 /**
  * @param depth
  *            the depth to set
  */
 public void setDepth(int depth) {
  this.depth = depth;
 }

 @Override
 public int compareTo(Node<T> o) {
  return this.data.compareTo(o.data);
 }

 @Override
 public String toString() {
  return "Level " + level + ": " + data;
 }

}

Basically, this data is comprised of one generic data, one left child and one right child. This is just like the general binary tree, two children with one data to be stored. But we need our generic data can be comparable, so we can search them and have them in order.

Second, let's use this Node structure to build our tree.


import java.util.LinkedList;
import java.util.Queue;

public class AVLTree<T extends Comparable<T>> {
 Node<T> root;

 public AVLTree() {
  root = null;
 }

 public T Maximum() {
  Node<T> local = root;
  if (local == null)
   return null;
  while (local.getRight() != null)
   local = local.getRight();
  return local.getData();
 }

 public T Minimum() {
  Node<T> local = root;
  if (local == null)
   return null;
  while (local.getLeft() != null) {
   local = local.getLeft();
  }
  return local.getData();
 }

 private int depth(Node<T> node) {
  if (node == null)
   return 0;
  return node.getDepth();
  // 1 + Math.max(depth(node.getLeft()), depth(node.getRight()));
 }

 public Node<T> insert(T data) {
  root = insert(root, data);
  switch (balanceNumber(root)) {
  case 1:
   root = rotateLeft(root);
   break;
  case -1:
   root = rotateRight(root);
   break;
  default:
   break;
  }
  return root;
 }

 public Node<T> insert(Node<T> node, T data) {
  if (node == null)
   return new Node<T>(data);
  if (node.getData().compareTo(data) > 0) {
   node = new Node<T>(node.getData(), insert(node.getLeft(), data),
     node.getRight());
   // node.setLeft(insert(node.getLeft(), data));
  } else if (node.getData().compareTo(data) < 0) {
   // node.setRight(insert(node.getRight(), data));
   node = new Node<T>(node.getData(), node.getLeft(), insert(
     node.getRight(), data));
  }
  // After insert the new node, check and rebalance the current node if
  // necessary.
  switch (balanceNumber(node)) {
  case 1:
   node = rotateLeft(node);
   break;
  case -1:
   node = rotateRight(node);
   break;
  default:
   return node;
  }
  return node;
 }

 private int balanceNumber(Node<T> node) {
  int L = depth(node.getLeft());
  int R = depth(node.getRight());
  if (L - R >= 2)
   return -1;
  else if (L - R <= -2)
   return 1;
  return 0;
 }

 private Node<T> rotateLeft(Node<T> node) {
  Node<T> q = node;
  Node<T> p = q.getRight();
  Node<T> c = q.getLeft();
  Node<T> a = p.getLeft();
  Node<T> b = p.getRight();
  q = new Node<T>(q.getData(), c, a);
  p = new Node<T>(p.getData(), q, b);
  return p;
 }

 private Node<T> rotateRight(Node<T> node) {
  Node<T> q = node;
  Node<T> p = q.getLeft();
  Node<T> c = q.getRight();
  Node<T> a = p.getLeft();
  Node<T> b = p.getRight();
  q = new Node<T>(q.getData(), b, c);
  p = new Node<T>(p.getData(), a, q);
  return p;
 }

 public boolean search(T data) {
  Node<T> local = root;
  while (local != null) {
   if (local.getData().compareTo(data) == 0)
    return true;
   else if (local.getData().compareTo(data) > 0)
    local = local.getLeft();
   else
    local = local.getRight();
  }
  return false;
 }

 public String toString() {
  return root.toString();
 }

 public void PrintTree() {
  root.level = 0;
  Queue<Node<T>> queue = new LinkedList<Node<T>>();
  queue.add(root);
  while (!queue.isEmpty()) {
   Node<T> node = queue.poll();
   System.out.println(node);
   int level = node.level;
   Node<T> left = node.getLeft();
   Node<T> right = node.getRight();
   if (left != null) {
    left.level = level + 1;
    queue.add(left);
   }
   if (right != null) {
    right.level = level + 1;
    queue.add(right);
   }
  }
 }
}

For AVLTree class, we need a root node to let user know where this tree starts. Each function works the way as the method name suggested, insert is to insert the new node to our tree, maximum is to get the maximum value of the tree and minimum if to get the minimum value of the tree.

For the insert function, every time we insert a new node, we need to check if every parent of the new node is still balanced. If yes, we'll have no problem with it, otherwise, we have to make some action like rotateLeft, rotateRight to have it rebalanced.

For the search, maximum and minimum function, each use recursive way or non-recursive way to go from root node to leave node to find what they need.

For the PrintTree function, it uses a CS tech called Breadth-First-Search(BFS) to go through our tree level by level. At the same time, it will print each node to system output.

For rotation of AVL Tree, this picture on Wiki explains a lot.

There are four cases you need to take care to make a rotation as the picture above indicates. My code uses a DFS recursive call to insert the new node into our tree, if new node is inserted into 4's subtree, then we check on 4's parent to see if it's balanced, if not, we'll make the rotation. Then check on the 4's parant's parant, rotate it if it's unbalanced, keep checking until your function reach back to "root".

So, for testing our AVL Tree API, I made a simple demo here.


/**
 * @author antonio081014
 * @time Jul 5, 2013, 9:31:10 PM
 */
public class Main {

 public static void main(String[] args) {
  AVLTree<Integer> tree = new AVLTree<Integer>();
  for (int i = 1; i <= 7; i++)
   tree.insert(new Integer(i));
  tree.PrintTree();
 }
}
The output of this:
Level 0: 4
Level 1: 2
Level 1: 6
Level 2: 1
Level 2: 3
Level 2: 5

Level 2: 7
To make this more graphically, it will looks like:
             4
           /   \
         2     6
        /  \   /  \
      1  3  5  7
This is pretty much what we need.

The user could use other Object type, like String, Double, rather than primitive types like int, double.

For a more clear view, visit my gist page.