Saturday, February 28, 2015

Swap numbers without temporary variables


Write a function to swap a number in place without temporary variables.
using XOR.  a = 3 (11), b = 5 (101). a = a ^ b = 110 b = a ^ b  =  3(11), because we flip the bits back. a = a ^ b = 5 (101)


public static void swap(int a, int b){
  a = a ^ b;
  b = a ^ b;
  a = a ^ b;
  System.out.println("a: " + a);
  System.out.println("b: " + b);
 }

Operations


Write a method to implement *, - , / operations.You should use only the + operator.
It is straight forward to convert plus to minus: a - b = a + (-b). But we need to first write a negative. To get the negative counterpart of a number, we simply add -1 (if the number is positive) or 1 (if the number is negative) to both a and 0, then when a reaches 0, the other number becomes the negative (positive) counterpart of a.

Multiplication, think about when we were in elementary school, how do we learn multiplication. We add number by number, 2 * 3 is 2 + 2 + 2 or 3 + 3 since the later requires less operation. The same here, use a loop.

Division is similar, 21 / 7 is number of 7s that can be subtracted from 21 until it is 0. Note that in order to make it compatible with Java's division for int, i.e., return floor of the number if the quotient is not an integer.

For both multiplication and division, negative sign needs to be taken into account.


public class operations {
 public static int negative(int a) {
  if (a == 0)
   return a;
  int neg = 0;
  int d = a < 0 ? 1 : -1;
  while (a != 0) {
   neg += d;
   a += d;
  }
  return neg;
 }
 public static int subtract(int a, int b) {
  return a + negative(b);
 }
 public static int abs(int a) {
  return a < 0 ? negative(a) : a;
 }
 public static int mutiply(int a, int b) {
  if (a < b) {
   int tmp = a;
   a = b;
   b = tmp;
  }
  boolean isNegative = false;
  if ((a < 0 && b > 0) || (a > 0 && b < 0))
   isNegative = true;
  a = abs(a);
  b = abs(b);
  for (int i = 1; i < b; i++)
   a += a;
  return isNegative ? negative(a) : a;
 }
 
 public static int divide(int a, int b) {
  if (b == 0)
   throw new ArithmeticException("Divide by zero!");
  boolean isNegative = false;
  if ((a < 0 && b > 0) || (a > 0 && b < 0))
   isNegative = true;
  a = abs(a);
  b = abs(b);
  int rst = 0;
  while (a > 0) {
   a -= b;
   rst++;
  }
  if (a < 0)
   rst--;
  return isNegative ? negative(rst) : rst;
 }
 public static void main(String[] args) {
  System.out.println(divide(-24, 3));

 }

}

Largest number of people

A circus is designing a tower routine consisting of people standing atop one another’s shoulders.For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her.Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower.
EXAMPLE:
Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output: The longest tower is length 6 and includes from top to bottom: (56, 90) (60,95) (65,100) (68,110) (70,150) (75,190) 

The book (Cracking the coding interview) provides a solution that requires extra O(2n) space. I don't think they are necessary. Basically, sort the list first by height then by weight (or vice versa, doesn't matter), this operation takes O(n log n). Then go through the list, track the current min (min), if min is less both in height and weight than the current element in the list, add the maxLength by 1, set min to current element. Because if either height or weight equals to min, this element is not considered, since the list is sorted, the element with the smallest height and weight is always prior to current element. This operation takes another O(n) time, so totally O(nlogn) time, with no extra space.


public class LongestSequence {
 private static class HeightNWeight {
  int h;
  int w;
  public HeightNWeight(int h, int w){
   this.h = h;
   this.w = w;
  }
  public String toString() {
   String s = "height: ";
   s += String.valueOf(h) + "; weight: " + String.valueOf(w);
   return s;
  }
 }
 public static int largestNumber(List people) {
  if (people == null || people.size() == 0)
   return 0;
  Collections.sort(people, new HNWComparator());
  HeightNWeight min = people.get(0);
  int maxLength = 1;
  for (int i = 1; i < people.size(); i++){
   if (min.h < people.get(i).h && min.w < people.get(i).w) {
    maxLength++;
    min = people.get(i);
   }
  }
  return maxLength;
 }
 private static class HNWComparator implements Comparator {
  public int compare(HeightNWeight hw1, HeightNWeight hw2) {
   if (hw1.h < hw2.h)
    return -1;
   else if (hw1.h > hw2.h)
    return 1;
   else if (hw1.w < hw2.w)
    return -1;
   else if (hw1.w < hw2.w)
    return 1;
   return 0;
  }
 }
 public static void main(String[] args) {
  List people = new ArrayList ();
  people.add(new HeightNWeight(56, 90));
  people.add(new HeightNWeight(60, 90));
  people.add(new HeightNWeight(60, 95));
  people.add(new HeightNWeight(65, 100));
  people.add(new HeightNWeight(68, 150));
  people.add(new HeightNWeight(70, 100));
  people.add(new HeightNWeight(70, 160));
  people.add(new HeightNWeight(75, 180));
  people.add(new HeightNWeight(80, 180));
  people.add(new HeightNWeight(85, 190));
  System.out.println(largestNumber(people));
 }

}

Search string in sparse array

Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.
Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4
Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1 



This follows the ordinary binary search. However, notice that when the mid is an empty string, you should either proceed right or left to find the first nonempty string. 

Besides, use start <= last and start = mid + 1


public static int search(String[] strings, String target) {
  if (strings == null || strings.length == 0 || target == null)
   return -1;
  int start = 0;
  int end = strings.length - 1;
  while (start <= end) {
   while (start < end && strings[start].equals(""))
    start++;
   while (start < end && strings[end].equals(""))
    end--;
   int mid = (start + end) / 2;
   while (mid <= end && strings[mid].equals(""))
    mid++;
   if (strings[mid].equals(target))
    return mid;
   else if (strings[mid].compareTo(target) < 0) {
    start = mid + 1;
   }
   else {
    end = mid - 1;
   }
  }
  if (strings[start].equals(target))
   return start;
  return -1;
 }

External sort


If you have a 2 GB file with one string per line, which sorting algorithm would you use to sort the file and why? 

For large files that cannot be fit into the memory, we need to do external sort. Assume  the memory is 1 GB. 

  1. Divide the file into K chunks, where X * K = 2GB. Bring each chunk into memory and sort the lines as usual using any O(n log n) algorithm, e.g., quick sort. 
  2. Write the sorted data to disk. 
  3. Repeat the above steps until all K chunks are sorted. 
  4. Read the first N portion of each chunk (so that X * N < 1GB) into input buffers in main memory and allocate the remaining memory for an output buffer. 
  5. Perform a k-way merge and store the result in the output buffer. Whenever the output buffer fills, write it to the final sorted file and empty it. Whenever any of the X input buffers empties, fill it with the next N portion of the chunk until no more data from the chunk is available. 
Additional passes, e.g., if we have 500 chunks, after sorting each chunk, we can run a first merge pass combining 25 chunks at a time, resulting in 20 large sorted chunks. Run a second merge pass to merge the 20 larger sorted chunks. 

Efficient external sorts require O(n log n) where n is the total elements to be sorted. Using parallelism may improve performance. 

Sort anagram lists


Write a method to sort an array of strings so that all the anagrams are next to each other.

The basic idea is to write a function and rearrange the string to its lexicographic order, and use String comparator to compare two strings. Some concepts about String comparator from Java doc: 

Compares two strings lexicographically. The comparison is based on the Unicode value of each character in the strings. The character sequence represented by this String object is compared lexicographically to the character sequence represented by the argument string. 
The result is a negative integer if this String object lexicographically precedes the argument string. The result is a positive integer if this String object lexicographically follows the argument string. The result is zero if the strings are equal;compareTo returns 0 exactly when the equals(Object) method would return true.
If two strings are different, then either they have different characters at some index that is a valid index for both strings, or their lengths are different, or both. If they have different characters at one or more index positions, let k be the smallest such index; then the string whose character at position has the smaller value, as determined by using the < operator, lexicographically precedes the other string.  
private static class AnagramComparator implements Comparator {
  public static String sortChars(String s) {
   char[] content = s.toCharArray();
   Arrays.sort(content);
   return new String(content);
  }
  public int compare(String s1, String s2) {
   return sortChars(s1).compareTo(sortChars(s2));
  }
 }
 public static void sortStrings(List list) {
  Collections.sort(list, new AnagramComparator());
 }

Friday, February 27, 2015

Number of ways to make changes


Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.
Assume we need 25 cents, and we want to  make changes, how can we do it?

Naturally, we will think of first, get 1 quarter
1. 25cents
Since we only need 25 cents, so at most 1 1 quarter will be used. Then we will think of the next largest domination, dime
2. 10 + 10 + 5
Because we want to add up all coins to 25
Then we further split 1 10 cent to to 5
3. 10 + 5 + 5 + 5
Then we use all 5 cents
4. 5 + 5 + 5 + 5 +5

So each time we use one domination, and find next needed coins based on the cents left, and we can do it recursively.



public class RepresentCents {
 public static int makeChange(int n) {
  return ways(n, 25);
 }
 public static int ways(int n, int denom){
  int next_denom = 0;
  //find the next largest denomination
  switch(denom) {
  case 25:
   next_denom = 10;
   break;
  case 10:
   next_denom = 5;
   break;
  case 5:
   next_denom = 1;
   break;
  //after we use the smallest denomination,
  //we need to check if all coins have added up to 
  //the desired cents, if they have, return 1 way
  //otherwise return 0 ways
  case 1:
   if (n == 0)
    return 1;
   else
    return 0;
  }
  int ways = 0;
  //check all number of coins can be used in current denomination
  for (int i = 0; i * denom <= n; i++){
   ways += ways(n - i * denom, next_denom);
  }
  return ways;
 }

 public static void main(String[] args) {
  System.out.println(makeChange(30));

 }

}

Wednesday, February 25, 2015

Sort a stack

Use another stack r. pop the head (tmp) of the input stack s, compare it with the head in r, if the head is larger, push the head of r to s until the next value is no larger than tmp, push tmp to r.

For example:
stack s:
head 3, 9, 6, 2 tail
tmp = 3
stack r:
empty
push 3 to r
stack r:
3

tmp = 9
3 < 9
push 9 to r
stack r:
3, 9

tmp = 6
9 > 6
push 9 to s
stack s:
9, 2
3 < 6
push 6 to r
stack r
3, 6

tmp = 9
6 < 9
push 9 to r
stack r:
3, 6, 9

tmp = 2
9, 6, 3, > 2
push 9, 6, 3, to s
stack s:
3, 6, 9
push 2 to r
stack r:
2
push 3, 6, 9, to r
stack r:
2, 3, 6, 9

If the head of r is smaller than tmp, we need to push all elements in r that is larger than tmp back to s, at worst case, we will have to push all elements in r back to s, (like when tmp = 2 in the example), so this operation will take O(n). The outer loop will take another O(n) time, so in total O(n^2).


public class SortAStack {
 public static Stack sort(Stack s) {
  Stack r = new Stack ();
  while (!s.isEmpty()) {
   int tmp = s.pop();
   while(!r.isEmpty() && r.peek() > tmp) {
    s.push(r.pop());
   }
   r.push(tmp);
  }
  return r;
 }

 public static void main(String[] args) {
  Stack s = new Stack ();
  s.push(1);
  s.push(5);
  s.push(4);
  s.push(2);
  s.push(6);
  s.push(9);
  s.push(3);
  for (int i : sort(s)) {
   System.out.println(i);
  }
 }
}

Hanoi Game

In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of different sizes which can slide onto any tower.The puzzle starts with disks sorted in ascending order of size from top to bottom (e.g., each disk sits on top of an even larger one).You have the following constraints:
(A) Only one disk can be moved at a time.
(B) A disk is slid off the top of one rod onto the next rod.
(C) A disk can only be placed on top of a larger disk.
Write a program to move the disks from the first rod to the last using Stacks.


Consider the easiest problem, if we have 2 disks, how should we move from Tower 0 to Tower 2? See the following illustration:


Now what if we have 3 disks? So in the end we want to move all 3 disks to Tower 2, we would have to move disk0 and disk1 to Tower 1 first, because disk2 will be at the bottom of Tower 2, so we need to leave the space for it. 


Yes, we will use recursion to solve the problem. 


import java.util.Stack;
public class HanoiGame {
 private Stack disks;
 private int index;
 public HanoiGame(int i) {
  disks = new Stack();
  index = i;
 }
 /**
  * tower id
  * @return
  */
 public int index() {
  return index;
 }
 /**
  * add disk with length d to the tower
  * if the last disk on the top of the tower is smaller
  * than d, then d cannot be added to the tower
  * @param d
  * @return
  */
 public boolean add(int d) {
  if (!disks.isEmpty() && disks.peek() <= d) {
   System.out.println("Error placing disk: " + d);
   return false;
  }
  else
   disks.push(d);
  return true;
 }
 /**
  * move the top disk to the desired tower
  * @param hg
  */
 public void moveTopTo(HanoiGame tower) {
  int top = disks.pop();
  if (!tower.add(top))
   disks.push(top);
  //System.out.println("Move disk " + top + " from " + index() 
   // + " to " + tower.index());
 }
 public void print() {
  System.out.println("Contents of Tower: " + index());
  for (int i = disks.size() - 1; i >= 0; i--) {
   System.out.println(disks.get(i) + " ");
  }
 }
 /**
  * move the disks to the destination
  * use recursion to solve the problem
  * @param n
  * @param destination
  * @param intermediate
  */
 public void moveDisks(int n, HanoiGame destination, HanoiGame intermediate) {
  if (n > 0) {
   //since the last disk must be placed at the destination
   //we need to move n - 1 disks above it to the intermediate first
   moveDisks(n - 1, intermediate, destination);
   //move the last disk to the destination
   moveTopTo(destination);
   //from intermediate move the n - 1 disks to the destination, 
   //using current tower as the new intermediate
   intermediate.moveDisks(n - 1, destination, this);
  }
 }
 public static void main(String[] args) {
  int n = 5;
  HanoiGame[] towers = new HanoiGame[3];
  for (int i = 0; i < 3; i++)
   towers[i] = new HanoiGame(i);
  for (int i = n - 1; i >= 0; i--)
   towers[0].add(i);
  towers[0].print();
  towers[0].moveDisks(n, towers[2], towers[1]);
  towers[2].print();
 }

}

Min Stack

The stack can be implemented using LinkedList implementation. So the problem is how to track the minimum efficiently. One way to do it is to design a structure and store the minimum of all elements prior to head into the stack. Thus each node will also contain the information of the local minimum. The problem with this method is that there will be lots of duplicate data. For example, if I have a stack (0, 1, 2, 3, 4), the head is 4, with the minimum 0, every node stores 0, which is unnecessary and infeasible for very large stack.

So the question is, how can we do better?

One approach may be to use another List, or another stack to only track the local minimum. If the pushed node is smaller than the minimum of all existing nodes in the stack, push the node to the second stack. So for (0, 1, 2, 3, 4), we will have another list/stack only contains (0).
class MinStack {
    ListNode head;
    ListNode currMin;
    public MinStack() {
        head = null;
        currMin = null;
    }
    public MinStack(int val) {
        head = new ListNode(val);
        currMin = new ListNode(val);
    }
    
    public void push(int x) {
        if (head == null) {
            head = new ListNode(x);
            currMin = new ListNode(x);
        }
        else {
            ListNode node = new ListNode(x);
            node.next = head;
            head = node;
            //if there are two nodes with the same minimum value in the stack, 
            //if we delete the first one, or the one pushed in later, the minimum
            //of the stack is still the same value, thus we need to push the node
            //to the min stack as long as it equals the minimum
            if (x <= currMin.val) {
                //need to create a new node and push it
                //to the second list, 
                //otherwise the current node's next will points to next min
                //because we override it with the previous min
                ListNode tmp = node;
                tmp.next = currMin;
                currMin = tmp;
            }
        }
    }

    public void pop() {
        if (head == null)
            return;
        if (currMin.val == head.val) {
            currMin = currMin.next;
        }
        head = head.next;
    }

    public int top() {
        if (head == null)
            return -1;
        return head.val;
    }

    public int getMin() {
        if (head == null)
            return -1;
        return currMin.val;
    }
    private class ListNode{
        int val;
        ListNode next;
        public ListNode(int val) {
            this.val = val;
            next = null;
        }
    }
}

Tuesday, February 24, 2015

Rotate array

So how to do it in place? The answer is easy but tricky. Reverse the array 3 times. First reverse the whole array, second reverse (0, k - 1) and third reverse(k, n -1).
Take a look of the example.




public void rotate(int[] nums, int k) {
        if (nums == null || nums.length <= 1 || k <= 0 || k == nums.length)
            return;
        int l = nums.length;
        k = k % l;
        reverse(nums, 0, l - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, l - 1);
        
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }

Monday, February 23, 2015

Number of pages in a book

A book contains with pages numbered from 1 - N. Imagine now that you concatenate all page numbers in the book such that you obtain a sequence of numbers which can be represented as a string.
You can compute number of occurrences 'k' of certain digit 'd' in this string.
For example, let N=12, d=1, hence
s = '123456789101112' => k=5
since digit '1' occur five times in that string.

Problem: Write a method that, given a digit 'd' and number of its occurrences 'k', returns a number of pages N. More precisely, return a lower and upper bound of this number N.
Example:
input: d=4, k=1;
output {4, 13} - the book has 4-14 pages
input d=4 k=0;
output {1, 3} - the book has 1-3 pages
 I don't consider my solution is the most efficient one, but it is reasonable, and at least, correct.

For every 100 pages, or more precisely, 0 - 99 (100 - 199, ...) pages, there exists 20 occurrences of any digit d, except for 0 for (0 - 99 pages), there are only 9,  because there is no 0 from 0 - 9 pages. So the first step is to calculate how many hundreds of pages in the book.

hundreds = k / 20;

Next, we want to know how many d's left in tens. This is done by mod k by 20;

tens = k % 20;

If tens = 6, then there are 6 ds in (0 - 99) pages, or (hundreds * 100, hundreds * 100 + 99) pages.

Now we have the tricky part. Let's take d = 7as an example.

If tens = 0, then it is easy, the range of the pages will include all d's in one hundred pages.

(hundreds - 1) * 100 + 90 + d, range[0] + 10 - 1)

Take 7 as an example, if k = 20, then the range is
(97, 106).
Note we need to decrement hundreds by 1 when tens = 0.

If tens != 0, we will have different cases. Note that we will have d of ds if  tens (the second digit in the page number) is less than d. Then we will have 11 ds from d * 10 to d * 10 + 9. Then we will have another 9 - d ds after that.
If d = 7, we will have 7 7s from 0 - 69, 11 7s from 70 - 79 and another 2 ds from 80 - 99. Thus we need to calculate ranges based on different situations.

If tens < d,


range[0] = hundreds * 100 + (tens - 1) * 10 + d;
range[1] = range[0] + 10 - 1;

d = 7, k = 25 -> hundreds = 1, tens = 5
(147, 156)

If tens = d
we have to exclude d * 10 to d * 10 + d - 1
so 

range[0] = hundreds * 100 + (tens - 1) * 10 + d;
range[1] = hundreds * 100 + (tens - 1) * 10 + 9;

d = 7, k = 27 ->  hundreds = 1, tens = 7
(167, 169)

Now if tens > d, let dInTens, which is the number of ds from ( d * 10,  d * 10 + 9) = tens - d

start from the easier one, if dInTens > 11, then the range must be from (d + 1) * 10 - 99, for d = 7, it is 80 - 99

range[0] = hundreds * 100 + (tens - 11) * 10 + d;
range[1] = range[0] + 10 - 1;

d = 7, k = 39 -> hundreds = 1, tens = 19
range (187, 196)

if dInTens < 11, then we are in the range d * 10 to d * 10 + 8. In this situation, increment any page will increase k, thus the range is an exact number. Moreover, when the single digit equals to d, we will have 2 ds. 


If dInTens <= d, then the range is from d * 10 to d * 10 + d - 1. 
For d = 7, k = 13 -> tens = 13, dInTens = 6, the range is (70, 76), more precisely, 

range[0] = range[1] = hundreds * 100 + d * 10 + dInTens - 1;

so (75, 75)

If dInTens > d, then 

range[0] = range[1] = hundreds * 100 + d * 10 + dInTens - 2;

Because d* 10 + d takes 2 ds. 
For d = 7, k = 17 -> tens = 17, dInTens = 10, range (77, 77)

Now we have one more situation, where dInTens = 11, we are in the range ( d * 10 + 9, d * 10 + 9 + d). Because the next d will occur when the next single digit = d. 

range[0] = hundreds * 100 + d * 10 + 9;
range[1] = range[0] + d;

for d = 7, k = 18 -> tens = 18, dInTens = 11, range (79, 96)


I know the explanation looks tedious. Honestly I am also looking for a more concrete code. 




public class NumberOfPages {
 public static int[] pages(int d, int k) {
  if (d < 0 || k < 0)
   throw new IllegalArgumentException("pages must be non negative!");
  int[] range = new int[2];
  if (k == 0) {
   if (d == 1)
    range[0] = range[1] = 0;
   else {
    range[0] = 1;
    range[1] = d - 1;
   }
   return range;
  }
  //the number of hundreds of pages
  int hundreds = k / 20;
  if (d == 0) {
   hundreds = k > 9 ? ((k - 9) / 20) + 1 : 0;
  }
  //the number of d's from 0 - 99 pages
  int tens = k % 20;
  if (tens == 0) {
   range[0] = (hundreds - 1) * 100 + 90 + d;
   range[1] = range[0] + 10 - 1;
  }
  else if (tens - d  <= 0) {
   range[0] = hundreds * 100 + (tens - 1) * 10 + d;
   //System.out.println("range[0]: " + range[0]);
   if (tens - d  == 0) 
    range[1] = hundreds * 100 + (tens - 1) * 10 + 9;
   else
    range[1] = range[0] + 10 - 1;
   //System.out.println("range[1]: " + range[1]);
  }
  else {
   int dInTens = tens - d;
   if (dInTens > 11) {
    range[0] = hundreds * 100 + (tens - 11) * 10 + d;
    range[1] = range[0] + 10 - 1;
   }
   else {
    if (dInTens <= d)
     range[0] = range[1] = hundreds * 100 + d * 10 + dInTens - 1;
    else if (dInTens == 11) {
     range[0] = hundreds * 100 + d * 10 + 9;
     range[1] = range[0] + d;
    }
    else 
     range[0] = range[1] = hundreds * 100 + d * 10 + dInTens - 2;
   }
  }
  return range;
 }

 public static void main(String[] args) {
  for (int k = 0; k <= 20; k++) {
   for (int i : pages(7, k))
    System.out.print(i + " ");
   System.out.println();
  }
  for (int i : pages(7, 18))
   System.out.print(i + " ");
 }

}


Sunday, February 22, 2015

Find minimum number K such that given integer N can be represented by K number of squares


You are given a positive integer number N. Return the minimum number K, such that N can be represented as K integer squares.
Examples:
9 --> 1 (9 = 3^2)
8 --> 2 (8 = 2^2 + 2^2)
15 --> 4 (15 = 3^2 + 2^2 + 1^2 + 1^2)

See the comment on the top of the code... Sorry just don't bother to type them again...

/**
 * You are given a positive integer number N. 
 * Return the minimum number K, such that N can be 
 * represented as K integer squares. 
 * Examples: 
 * 9 --> 1 (9 = 3^2) 
 * 8 --> 2 (8 = 2^2 + 2^2) 
 * 15 --> 4 (15 = 3^2 + 2^2 + 1^2 + 1^2) 
 * First reach a solution without any assumptions, 
 * then you can improve it using this mathematical lemma (Lagrange's four-square theorem): 
 * For any positive integer N, there is at least one representation 
 * of N as 4 or less squares.
 * N = a^2 + b^2 + c^2 + d^2 such that
 * a >= b >= c >= d
 * a : {floor(sqrt(N)), ceil(sqrt(N / 4))}
 * b : {floor(sqrt(N - a * a)), ceil(sqrt((N - a * a)/3)}
 * c : {floor(sqrt(N - a * a - b * b)), ceil(sqrt((N - a * a - b* b)/2))}
 * d : N - a * a - b * b - c * c
 * if we can find a and b, then if sqrt(N - a * a - b * b) is an integer
 * we have our 3rd integer, thus we don't have to loop to find c
 * if we cannot find a, b, c such that a * a + b * b + c * c = N
 * then we need the 4th integer
 * So the complexity is O(sqrt(N) * sqrt(N)), which is O(N)
 * @author shirleyyoung
 *
 */
public class KIntegerSquares {
 public static int kSquares(int N) {
  if (N < 0)
   throw new IllegalArgumentException("Input must be positive!");
  int sqrt = (int)Math.sqrt(N);
  if (sqrt * sqrt == N)
   return 1;
  int aUpper = (int)Math.sqrt(N);
  int aLower = (int)Math.ceil(Math.sqrt(N / 4.0));
  for (int a = aUpper; a >= aLower; a--) {
   int bUpper = (int)Math.sqrt(N - a * a);
   int bLower = (int)Math.ceil(Math.sqrt((N - a * a) / 3.0));
   for (int b = bUpper; b >= bLower; b--) {
    int currSum = a * a + b * b;
    if (currSum == N)
     return 2;
    double c = Math.sqrt(N - currSum);
    if (c == Math.floor(c))
     return 3;
   }
  }
  return 4;
 }

 public static void main(String[] args) {
  System.out.println(kSquares(31));
 }
}


Update 2015 - 03 - 16
A DP solution that is much easier to understand. Note recursion will not work since it follows a greedy approach which may not give the best answer.


public static int kSquares3(int N){
  if(N < 0)
   throw new IllegalArgumentException("Input must be greater than 0!");
  if(N == 0)
   return 0;
  int[] minSquare = new int[N + 1];
  int max = (int)Math.sqrt(N);
  for (int i = 0; i <= N; i++)
   minSquare[i] = i;
  for(int i = 1; i <= N; i++){
   for(int j = 1; j <= max; j++){
    if(i - j * j < 0)
     continue;
    minSquare[i] = Math.min(minSquare[i], minSquare[i - j * j] + 1);
   }
  }
  return minSquare[N];
 }

Auto Complete method


Write a class that receives in the constructor a vector of strings representing a browser history (URLs), and a method for "auto-complete":
The method that receives a string representing a partial URL typed by the user and returns a vector of all possible completions of this partial URL (prefix).

Starts from some concepts:

Trie 
a trie/digital tree/radix tree/prefix tree, is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings.  No node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest.
A radix tree/radix trie/compact prefix tree is a space-optimized trie data structure where each node with only one child is merged with its parent. The result is that every internal node has up to the number of children of the radix r of the radix trie, where r is a positive integer and a power x of 2, having x >= 1. Unlike in regular tries, edges can be labeled with sequences of elements as well as single elements. This makes them much more efficient for small sets (especially if the strings are long) and for sets of strings that share long prefixes. 

Just to go through how this thing works. When we initialize a new trie object, we create an empty trie node. Every trie has an empty root, i.e., the root doesn't hold any string values. The trie uses a map to store all its children, i.e., the suffixes generated from this node.

When we insert a string, the trie first tries to find if any of its children contains the first character of the string (the prefix), if it can find one, it will recursively try to find the next character until it cannot find one, that's when it will add a new node and put it into the children map.

In order to find if a string is in the trie, similarly, it will recursively try to find if every character in the string is in the children map, if any of the character doesn't in a children map, return false, when it reaches to the end of the string, check if the current node's value equals the string.

The autocomplete method, this method is in fact ask us to return all suffixes given a prefix. Follow the same approach as the previous to methods, the trie first finds the path of the prefix, say, s-h-, then it will add all children of the node "sh" and all children's children into the list, and return the list. For example, if "sh"  has children "she", "shirt", "shirley", it will return all 3. Note that "shir" is a path that has two branches: "shirt" and "shirley". However, since "shir" itself is not a string that has been inserted to the trie, it will not be returned.


import java.util.*;
import java.util.Map.Entry;
public class AutoCompleteTrie {
 protected final Map children;
 protected String value;
 protected boolean isWord = false;
 /**
  * constructor, initialize a new ACT with empty string as the root
  * @param value
  */
 private AutoCompleteTrie(String value) {
  this.value = value;
  children = new HashMap ();
 }
 public AutoCompleteTrie() {
  this("");
 }
 /**
  * insert a word, this will construct a root to leave path
  * with the key of each node a character in the word, 
  * value the prefix of the word till the key character
  * @param word
  */
 public void insert (String word) {
  if (word == null)
   throw new IllegalArgumentException("Null string!");
  //this is a reference to the current object: 
  //the object whose method or constructor is being called
  AutoCompleteTrie node = this;
  for (char c : word.toCharArray()) {
   //System.out.println(c + ": " + node.value);
   if (!node.children.containsKey(c))
    node.add(c);
   node = node.children.get(c);
   
  }
  //System.out.println();
  node.isWord = true;
 }
 /**
  * add a child of the node
  * the child will have the key the input character
  * and the value the value of the node + key character
  * @param c
  */
 private void add(char c) {
  String val; 
  val = this.value + c;
  children.put(c, new AutoCompleteTrie(val));
 }
 
 /**
  * search if a word exists in the trie
  * @param word
  * @return
  */
 public boolean find(String word) {
  AutoCompleteTrie node = this;
  for (char c : word.toCharArray()) {
   if (!node.children.containsKey(c)) 
    return false;
   node = node.children.get(c);
  }
  return node.value.equals(word);
 }
 
 /**
  * input prefix return all possible strings 
  * with the same prefix in the trie
  * find the node of the prefix in the trie
  * call allChildren method and return the list
  * @param prefix
  * @return
  */
 public Collection autoComplete(String prefix) {
  AutoCompleteTrie node = this;
  for (char c : prefix.toCharArray()) {
   if (!node.children.containsKey(c))
    return Collections.emptyList();
   node = node.children.get(c);
  }
  return node.allChildren();
 }
 /**
  * generate the list of all children of the current node/object
  * @return
  */
 private Collection allChildren() {
  List rst = new ArrayList ();
  //if the prefix is also a previous input word, add it to the list
  if (this.isWord) {
   rst.add(this.value);
  }
  //add all children
  for (Entry entry : children.entrySet()) {
   AutoCompleteTrie child = entry.getValue();
   Collection childPrefixes = child.allChildren();
   rst.addAll(childPrefixes);
  }
  return rst;
 }
}

Object-Oriented Programming 101

Object:
An object stores its state in fields/variable and exposes its behavior through methods/functions.
Objects define their interaction with the outside world through the methods they expose.
encapsulation: Hiding internal variables and requiring all interaction to be performed through an object's method.

public class demo {
    private int x;
    private int y;
    
    public demo() {
        x = 0;
        y = 0;
    }
    public void setX(int x) {
        this.x = x;
    }
    public void setY(int y) {
        this.y = y;
    }
    public int getX() {
        return x;
    }
    public int getY() {
        return y;
    }
}

Memory of object: 
Any Java object occupies at least 16 bytes, 12 out of which are occupied by a Java object header. Besides, all Java objects are aligned by 8 bytes boundary. It means that, for example, an object containing 2 fields: int and byte will occupy not (12 + 4 + 1) = 17, but 24 bytes (17 aligned by 8 bytes).
Each Object reference occupies 4 bytes if the Java heap is under 32G and is turned on (it is turned on by default in the recent Oracle JVM versions). Otherwise, Object references occupy 8 bytes.

Arrays:
Consume 12 bytes plus their length multiplied by element size (rounded by 8 bytes alignment).

String:
contains 3 fields:

  • a char[] with the string data
  • 2 int fields with 2 hash codes calculated by different algorithms.
Thus, a String itself needs 12(header) + 4(char[] reference)
Class:
A class is the blueprint from which individual objects are created. Object a is an instance of  the class of objects known as A.
A class CLASS may not have a main() method. That's because the class may not be a complete application, it's just the blueprint for CLASS that might be used in an application. The responsibility of creating and using CLASS objects belongs to some other class in the application.


Difference between object and class:

  • An object is an instance of a class, an object must belong to a class. 
  • An object has a lifespan but a class does not. Objects are created and eventually destroyed, so they only live in the program for a limited time. While objects are 'living', their properties may also be changed significantly. 
  • A constructor allows actual properties (fields/variables) to be passed to the object. A constructor constructs a specific instance of a class. 

Inheritance:
Object-oriented programming allows classes to inherit commonly used state (fields/variables) and behaviors (methods/functions) from other classes. Class SUPER may become superclass of Class SUB1, SUB2, ... . In Java, each class is allowed to have only one direct superclass, and each superclass has the potential for an unlimited number of subclasses.


public class SUPER {
    int variable1;
    int variable2;
    public int method1() {
        Some awesome code...
    }
}
public class SUB1 extends SUPER {
    int variable1;
    int variable2;
    int variable_sub1;
    public int method1() {
        Some awesome code...
    }
    public int method_sub1() {
        Other awesome code...
    }
}


Interface:
An interface is a reference type, that can contain only constants. method signatures, default methods, static methods, and nested types. Method bodies exist only for default methods and static methods. Interfaces can only be implemented by classes or extended by other interfaces. Implementing an interface allows a class to become more formal about the behavior it promises to provide. Interfaces form a contract between the class and the outside world (through method), and this contract is enforced at build time by the compiler. If a class claims to implement an interface, all methods defined by that interface must appear in its source code before the class will successfully compile.

Default methods enable you to add new functionality to the interfaces of your libraries and ensure binary compatibility with code written for older versions of those interfaces. The classes that implements the old version of the interface will automatically have the new default method defined.
When you extend interfaces that contain default methods, you can:

  • Not mention the default method at all, which lets your extended interface inherit the default method;
  • Redeclare the default method, which makes it abstract
  • Redefine the default method, which overrides it. 


public interface INTERFACE {
    //automatically public, static, and final
    int variable1;
    int variable2;
    public void iMustAppearInClass1() {
    }
    public void iMustAppearInClass2() {
    }
}
public class CLASS implements INTERFACE {
    public void iMustAppearInClass1() {
        Some awesome code...
    }
    public void iMustAppearInClass2() {
        Other awesome code...
    }
    public void iBelongToThisClass() {
        More awesome code...
    }
}



Abstract classes and methods:
An abstract class is a class that is declared abstract, it may or may not include abstract methods. Abstract classes cannot be instantiated, but they can be subclassed.

An abstract method is a method that is declared without an implementation (without braces, and followed by a semicolon). If a class include abstract methods, then the class itself must be declared abstract.

public abstract class ABSTRACT {
    int variable1;
    int variable2;
    abstract void iAmAbstract();
}

When an abstract class is subclassed, the subclass usually provides implementations for all of the abstract methods in its parent class. If it does not, the subclass must also be declared abstract. 

Abstract classes and interfaces:

  • Both abstract classes and interfaces cannot be instantiated
  • Both abstract classes and interfaces may contain a mix of methods declared with or without an implementation (default method for implementation). 
  • With interfaces, all fields are automatically public, static, and final, and all methods that you declare or define (as default methods) are public. With abstract classes, you can declare fields that are not static and final, and defined public protected and private concrete methods
  • Only one class can be extended, whether or not it is abstract, but any number of interfaces can be implemented


Using abstract classes when:

  • Share code among several closely related classes;
  • Expect that classes that extend the abstract class have many common methods or fields, or require access modifiers other than public (such as protected and private);
  • Declare non-static or non-final fields. 


Using interfaces when:

  • Expect unrelated classes would implement the interface. E.g., Comparable and Cloneable;
  • Specify the behavior of a particular data type, but not concerned about who implements its behavior;
  • Take advantage of multiple inheritance of type. 

Package:
A package is a namespace that organizes a set of related classes and interfaces. The Java platform provides an enormous class library (a set of packages) suitable for use. This library is known as the "Application Programming Interface (API)".


Instantiation:
The new operator instantiates (aka, creating an object, creating an instance of a class) a class by allocating memory for a new object and returning a reference to that memory. The new operator also invokes the object constructor.
The new operator requires a single, postfix argument: a call to a constructor. It returns a reference to the object it created.


Initialization:
The constructor lets you to provide initial values for the fields of the object of a class.

Method and function: 
A function is a piece of code that is called by name. It can be passed data to operate on (i.e., parameters) and can optionally return data (the return value). All data that is passed to a function is explicitly passed. Functions have independent existence, meaning they can be defined outside of the class. (E.g., main() in C, C++).
A method is a piece of code that is called by name that is associated with an object. It does not have independent existence, it is always defined within the class. Methods are called using objects/instances.


Inheritance:
In Java, classes can be derived from other classes, thereby inheriting fields and methods from those classes.
Subclass/derived class/extended class/child class: a class that is derived from another class.
Superclass/base class/parent class: the class from which the subclass is derived.
Object class in Java has no superclass. In the absence of any other explicit superclass, every class in Java is implicitly a subclass of Object. Every class has at most one parent.
A subclass inherits all of the public and protected members of its parent, regardless what package the subclass is in. If the subclass is in the same package as its parent, it also inherits the package-private members of the parent. A subclass does NOT inherit the private members of its parent. However, if the superclass has public or protected methods for accessing its private fields, these can also be used by the subclass. A nested class has access to all the private members of its enclosing class -- both fields and methods. Therefore, a public or protected nested class inherited by a subclass has indirect access to all of the private members of the superclass.
Declare a field in the subclass with the same name as the one in the superclass will hide that in the superclass (not recommended).
Write a new instance method in the subclass with the same signature as the one in the superclass will override that in the superclass.
Write a new static method in the subclass that has the same signature as the one in the superclass will hide that in the superclass.
You can write a subclass constructor that invokes the constructor of the superclass, either implicitly or by using the keyword super.

Multiple inheritance: 
An object or class can inherit characteristics and features from more than one parent object or parent class. It may be ambiguous as to which parent class a particular feature is inherited from if more than one parent class implements said feature. C++ allows multiple inheritance.

Diamond problem:

An ambiguity that arises when two classes B and C inherit from A, and class D inherits from both B and C. If there is a method in A that B and/or C has overridden, and D does not override it, then which version of the method does D inherit?

Example, in the context of GUI software development, a class Button may inherit from both classes Rectangle and Clickable, and both Rectangle and Clickable inherit from Object class. Now if the equals method is called for a Button object and there is no such method in the Button class but there is an overridden equals method in Rectangle or Clickable (or both), which method should be eventually called? 

Virtual inheritance
A base class in an inheritance hierarchy is declared to share its member data instances with any other inclusions of that same base in further derived classes. This technique makes the virtual base a common subobject for the deriving class and all classes that are derived from it. It clarifies ambiguity over which ancestor class to use, as from the perspective of the deriving class, the virtual base acts as though it were direct base of the deriving class.



class Animal {
    public:
        virtual void eat();
};
class Mammal : public virtual Animal {
    public:
        virtual void breathe();
};
class WingedAnimal : public virtual Animal {
    public:
        virtual void flap();
};
// A bat is a winged mammal
class Bat : public Mammal, public WingedAnimal {
}

In the above example, the Animal portion of Bat :: WingedAnimal is now the same Animal instance as the one used by Bat::Mammal, so Bat has only one, shared, Animal instance in its representation, and so a call to Bat::eat() is unambiguous. The Bat becomes (vpointer, Mammal, vpointer, WingedAnimal, Bat, Animal)

Java 8 introduces default methods on interfaces. If A, B, C are interfaces, B, C can each provide a different implementation to an abstract method of A, causing the diamond problem. Either class D must reimplement the method, or the ambiguity will be rejected as a compile error. The default interface method capability added with Java 8 introduced a type of multiple inheritance since classes can implement more than one interface, which can contain default methods that have the same name. However, the Java compiler provides rules to determine which default method a particular class uses, which prevents the Diamond problem.

Multiple inheritance of state: the ability to inherit fields from multiple classes;
Multiple inheritance of implementation: the ability to inherit method definitions from multiple classes;
Multiple inheritance of type: the ability of a class to implement more than one interface.

Instance method: an instance method in a subclass with the same signature and return type as an instance method in the superclass overrides the superclass's method. An overriding method can also return a subtype of the type returned by the overridden method. This subtype is called a covariant return type.



Polymorphism:
Subclasses of a class can define their own unique behaviors and yet share some of the same functionality of the parent class. Subclasses overrides the corresponding instance method in the parent class. The Java virtual machine (JVM) calls the appropriate method for the object that is referred to in each variable. It does not call the method that is defined by the variable's type. This behavior is referred to as virtual method invocation.


Virtual method and pure virtual method: 
A virtual function/method is a function or method whose behavior can be overridden within an inheriting class/subclass by a function with the same signature. The overridden method called by such a reference or pointer can be bound either 'early' (by the compiler), according to the declared type of the pointer or reference, or 'late' (i.e., by the runtime system of the language), according to the actual type of the object referred to. Virtual functions are resolved 'late'. If the function is 'virtual' in the base class, the most-derived class's implementation of the function is called according to the actual type of the object referred to, regardless of the declared type of the pointer or reference. If it is not 'virtual', the method is resolved 'early' and the function called is selected according to the declared type of the pointer or reference. Virtual functions allow a program to call methods that don't necessarily even exist at the moment the code is compiled. Non-virtual members can not be accessed through a reference of the base class: i.e., if virtual is removed from the declaration of the method in the base class, call the method will call the method in the base class.

Early binding/static binding: the compiler is able to directly associate the identifier name (such as a function or variable name) with a machine address.
Late binding/dynamic binding: In some programs, it is not possible to know which function will be called until runtime.

A pure virtual function/method is a virtual function that is required to be implemented by a derived class if that class is not abstract. Classes containing pure virtual methods are termed "abstract" and they cannot be instantiated directly. A subclass of an abstract class can only be instantiated directly if all inherited pure virtual methods have been implemented by that class or a parent class. Pure virtual methods typically have a declaration (signature) and no definition(implementation).

Methods:
Method signature: the method's name and the parameter types.
calculateAnswer(double, int, double, String, char)


Overloading methods: Methods within a class can have the same name if they have different parameter lists.

Final methods: The method CANNOT be overridden by subclasses.
Access control of classes: 
At the top level: public, or package-private (no explicit modifier)
At the member level: public, private, protected, or package-private
public: the class is visible to all classes everywhere;
private: the member can only be accessed in its own class;
protected: the member can only be accessed in its own package and by a subclass of its class in another package. 





Class initializer/Static Initialization Blocks: 
A static initialization block is a normal block of code enclosed in braces, {}, and preceded by static keyword. Without the static modifier, the code block is an instance initializer.  

static {
    write some awesome code...
}


A class can have any number of static initialization blocks, and they can appear anywhere in the class body. The runtime system guarantees that static initialization blocks are called in the order that they appear in the source code.

Instance initializers are executed in the order defined when the class is instantiated, immediately before the constructor code is executed, immediately after the invocation of the super constructor.


public class Test {
    static {
        System.out.println("Static");
    }
    {
        System.out.println("Non-static block");
    }
    public static void main(String[] args) {
        Test t = new Test();
        Test t2 = new Test();
    }
}


The above example will print:

Static
Non-static block
Non-static block


The non static block gets called every time the class is instantiated. The static block only gets called once, no matter how many objects of that type you create.


Constructors:
A class contains constructors that are invoked to create objects from the class blueprint. As with methods, the Java platform differentiates constructors on the basis of the number of arguments in the list and their types. If no explicit constructor is provided, the compiler automatically provides a no-argument, default constructor. This default constructor will call the no-argument constructor of the superclass. In this situation, the compiler will complain if the superclass doesn't have a no-argument constructor so you must verify that it does. If your class has no explicit superclass, then it has an implicit superclass of Object, which DOES have a no-argument constructor.

Destructors/Finalizers: 
A destructor is a method which is automatically invoked when the object is destroyed. It can happen when its lifetime is bound to scope and the execution leaves the scope, when it is embedded into another object whose lifetime ends, or when it was allocated dynamically and is released explicitly.
Its main purpose is to free the resources (memory allocations, open files or sockets, database connections, resource locks, etc.) which were acquired by the object along its life cycle and/or deregister from other entities which may keep references to it.

C++
In C++, the destructor has the same name as the class, but with a tilde (~) in front of it. If the object was created as an automatic variable, its destructor is automatically called when it goes out of scope. If the object was created with a new expression, then its destructor is called when the delete operator is applied to a pointer to the object. In inheritance hierarchies, the declaration of a virtual destructor in the base class ensures that the destructors of derived classes are invoked properly when an object is deleted through a pointer-to-base class. Object that may be deleted in this way need to inherit a virtual destructor.

A finalizer/finalize method is a special method that performs finalization, generally some form of cleanup. A finalizer is executed during object destruction, prior to object being deallocated, and is complementary to an initializer, which is executed during object creation, following allocation.
Finalizer is primarily used in OO languages that use garbage collection, e.g., Java. This is contrasted with a destructor, which is a method called for finalization in languages with deterministic object lifetimes, e.g., C++. These are generally exclusive, but in rare cases a language may have both, such as C++.

Garbage collection: A form of automatic memory management. The garbage collector, or just collector, attempts to reclaim garbage, or memory occupied by objects that are no longer in use by the program.


Primitive types (Java):
byte, short, int, long, float (single-precision 32-bit IEEE 754 floating point), double (double-precision 64-bit IEEE 754 floating point). boolean, char.

Generic Types (Java): 
A generic type is a generic class or interface that is parameterized over types. A type variable can be any non-primitive type you specify: any class type, any interface type, any array type, or even another type variable.

Type parameter:
E - Element;
K -Key;
N - Number;
T - Type;
V - Value;
S, U, V etc. - 2nd, 3rd, 4th types

Memory Layout: Java
When we run a java program, JVM will create a main thread for execution. Different types of data areas are required for execution of the thread. Some of these data areas are created when a java thread is created. These are per thread areas and are destroyed when the thread exits. There are other data areas which are created when the JVM starts and are destroyed when the JVM exits.

The Program counter: Each JVM thread will have its own PC register. A thread may have multiple methods and at a time, only one method's code is executed. If that method is not a native method, then PC register will contain address of the current instruction. If the method is a native one, then the content of PC register is undefined.

JVM Stacks: Each thread has its own stack. The stack is created when the thread is created. It stores local variables and intermediate results and is used for method invocation and return. The memory of JVM stack may not be contiguous (shared).

JVM Heap: The JVM heap is shared among all the threads. It is a run-time data area. Memory for all class instances is allocated from heap. Heap is created when JVM starts. Memory allocated to a class instance from heap is reclaimed back. there is an automatic storage management system also known as garbage collector which does this job. Heap need not be a contiguous memory and can dynamically expand or contract as and when required.

JVM Method Area: The OS processes have an area called as text area. Method area is analogous to that. It is shared among all threads. It is created on virtual machine start-up. The memory may not be contiguous. It stores per class structures such as code for methods, constructors, interface initialization, run-time constant pool, field and method data etc.

JVM Frames: A frame is created every time a method is invoked. The frame is destroyed when the invocation completes. The completion may be normal or abrupt. Frames are created from stack of the JVM for that thread. The frame has its own local variables, run-time constant pool, etc. In a given thread control, at any point of time only the frame of the executing method method is active and is called current frame.

Java Native method: There can be situations when an application cannot be completely developed in java probably because there are some platform specific features which java class library does not support. Java native interface, JNI enables writing native methods to handle such situations.
Java Native Interface (JNI): a programming framework that enables Java code running in a JVM to call and be called by native applications(programs specific to a hardware and OS platform) and libraries written in other languages such as C, C++ and assembly.

Execution Engine: The execution engine has the virtual processor an interpreter and a just-in-time compiler.

Source: http://www.mybodhizone.com/Core_Java/mbz_corejava_memoylayout.php

Enum type
An enum type is a special data type that enables for a variable to be a set of predefined constants. The variable must be equal to one of the values that have been predefined for it. The names of an enum type's fields are in uppercase letters.

You should use enum types any time you need to represent a fixed set of constants. That includes natural enum types such as the planets in our solar system and data sets where you know all possible values at compile time.

The enum declaration defines a class. The enum class body can include methods and other fields. The compiler automatically adds some special methods when it creates an enum. For example, they have  a static values method that returns an array containing all of the values of the enum in the order they are declared.

An enum cannot extend any other classes because it is implicitly extend java.lang.Enum.

Each enum constant is declared with values. These values are passed to the constructor when the constant is created. Java requires that the constants be defined first, prior to any fields or methods, the list of enum constants must end with semicolon.

The constructor for an enum type must be package-private or private access. It automatically creates the constants that are defined at the beginning of the enum body. You cannot invoke an enum constructor yourself.

Serialization
A process of convert an object to a byte stream so that it can be stored (e.g., in a file system or memory buffer) and reconstructed later into a copy of the object. It is a standardized and already available way of converting the object to a stream of bytes.

Find maximum QAZ


qaz is a value for a number where this number is less than the other next values which have indexes larger than the index of this number.
For example: 33 , 25 , 26 , 58 , 41 , 59 -> qaz of (33) = 3 where 33 less than 3 numbers (58 , 41 , 59), qaz of (25) = 4 and not 5 because the index of 33 is less than the index of 25, qaz of (26) = 3 , qaz of (58) = 1 , qaz of (41) = 1 , qaz of (59) = 0.
The question is to find the max qaz.
It can be solved simply using 2 loops which takes time of O(n^2).
That's ok but how can we solve this problem in O(nlogn). 


When we need to solve some problem using O(nlogn), either it is sort (merge sort, quick sort...) or divide and conquer (technically merge sort is also a divide and conquer approach). This problem doesn't require us to "sort" the array, actually we cannot sort it, otherwise how can we preserve the original index?

Recursively halve the array (divide from the middle). Before merge (conquer), store the minimum and maximum QAZ of both the left and the right part. When merge, note only the QAZ at the left part can change (the right part always has the larger index compare to the left part). The element with the max QAZ will always be a local minimum, i.e., it will be minimum value among all elements that have index larger than it. So we only need to consider the QAZ for the left min each time we merge two parts. If the left min is smaller than the right min, that means all elements in the right part are larger than left min, thus we increment left.qaz by the number of elements in the right part. Otherwise, do a linear scan in the right part to find all elements that are larger than left min. Return the struct (between left and right) that has the larger QAZ.



public class QAZ {
 private static class QAZstruct {
  int min;
  int qaz;
  public QAZstruct(int min, int qaz) {
   this.min = min;
   this.qaz = qaz;
  }
 }
 public static int maxQAZ(int[] array) {
  if (array == null || array.length <= 1)
   return 0;
  return getMaxQAZ(array, 0, array.length - 1).qaz;
 }
 
 private static QAZstruct getMaxQAZ(int[] array, int start, int end) {
  if (end <= start)
   return new QAZstruct(array[end], 0);
  
  if (end == start + 1)
   return array[start] < array[end] ? new QAZstruct(array[start], 1) : new QAZstruct(array[end], 0);
  int mid = (start + end) / 2;
  QAZstruct left = getMaxQAZ(array, start, mid);
  QAZstruct right = getMaxQAZ(array, mid + 1, end);
  //if the left min is smaller than right min, then every element in the right part is greater than the left minimum, thus
  //qaz of the left part will increment by the number of elements in the right part
  if (left.min < right.min)
   return new QAZstruct(left.min, left.qaz + end - mid);
  for (int i = mid + 1; i <= end; i++) {
   if (array[i] > left.min)
    left.qaz++;
  }
  return left.qaz > right.qaz ? left : right;
   
 }
 public static void main(String[] args) {
  //int[] array = {28};
  //int[] array = {19, 37};
  int[] array = {37, 19};
  //int[] array = {97, 65, 23, 78, 46, 31};
  System.out.println(maxQAZ(array));
 }
}

Print ASCII


Warm-up question: Write a function that prints all ASCII characters. You are not allowed to use for/while loop

Always starts from basic contents from Programming 101 that hibernates deep inside my memory.-_-

ASCII, abbreviated from American Standard Code for Information Interchange, is a character-encoding scheme, which encodes 128 specified characters into 7-bit binary integers.

In Java, we can convert the integer (0 - 127) to the corresponding ASCII character.


public class PrintASCII {
 public static void printASCII() {
  printASCII(0);
 }
 private static void printASCII(int x) {
  char y = (char) x;
  System.out.println(x++ + ": " + y);
  if (x < 128)
   printASCII(x);
 }

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

DBNZ -> CLEAR & NEGATE


You given and instruction called DBNZ ( Decrement and Branch if Not Zero)
which can be used as "DBNZ X L10".
This instruction decrement X by one and checks X, if X is not zero than branches line 10,
if it is zero than continue to next instructions.
By using DBNZ instruction implement CLEAR instruction.
CLEAR can be used as "CLEAR X" which means set X to zero.

By using DBNZ and CLEAR instructions implement NEGATE instruction
NEGATE can be used as "NEGATE X Y" which means set Y to negative of X ( Y = -X)
Well, to understand this question, I have to start with what does "branch" mean.

A branch is an instruction in a computer program that may, when executed by a computer, cause the computer to begin execution of a different instruction sequence. A branch instruction can be either an unconditional branch, which always results in branching, or a conditional branch, which may or may not cause branching depending on some condition. 
For example, GOTO.

Now the actual problem. The CLEAR instruction will set the given parameter to 0. Assuming X is positive at first, then

L1 : DBNZ L1

will decrement L1 until it is zero, and then continues to the next instruction.

Let Y be any number, then

CLEAR Y -> set Y to zero
L1: DBNZ Y L2 -> decrement Y, it will not be zero, then branches to L2
L2: DBNZ X L1 -> decrement X, if it is not zero, then branches to L1

This instruction will decrement X times of Y from zero, thus will give us -X.

These instructions are initially instructions from One instruction set computer (OISC), which is an abstract machine that uses only one instruction. With a judicious choice for the single instruction and given infinite resources, an OISC is capable of being a universal computer in the same manner as traditional computers that have multiple instructions.








Saturday, February 21, 2015

Assign numbers

There are numbers in between 0-9999999999 (10-digits) which are assigned to someone.
Write two methods called "getNumber" and "requestNumber" as follows: 
Number getNumber();
boolean requestNumber(Number number);
getNumber method should find out a number that did not assigned than marks it as assigned and return that number.
requestNumber method checks the number is assigened or not. If it is assigened returns false, else marks it as assigned and return true.
Design a data structure to keep those numbers and implement those methods

I like this problem a lot because it tests you two things: how to handle large data that may not fit into memory and how to use bits. I am good at neither. :(

Well, first, memory. So we have 10^10 numbers, each number takes 4 byte, so in total we will have ...eh... 40 GB data (thank you, Google!). It definitely cannot fit into the memory, so how should we deal with it? Remember 4 byte = 32 bits, so 1 integer takes 32 bits, can we only use 1 bit? That can reduce the memory to 40 / 32 ~ 1.25 GB, if we have a machine with 2 GB memory, we can handle it!

Yup, here comes the second, the BitSet. I wasn't quite familiar with the concept. A bit set is a vector of bits that grows as needed.  Each component of the bit set has a boolean value. So consider if I initialize a BitSet with initial size of 32, by flipping each component in the set (true -> false or false -> true), we can get 2^32 numbers, and that fits our problem set.

For the requestNumber() part, I use a hashSet to store all added numbers, this will allow retrieval of the number takes only O(1) time.


/**
 * 
 *There are numbers in between 0-9999999999 (10-digits) which are 
 *assigned to someone (does not matter which number assigned to whom) 
 *Write two methods called "getNumber" and "requestNumber" as follows 
 *
 *Number getNumber(); 
 *boolean requestNumber(Number number); 
 *
 *getNumber method should find out a number that 
 *did not assigned than marks it as assigned and return that number. 
 *requestNumber method checks the number is assigned or not. 
 *If it is assigned returns false, else marks it 
 *as assigned and return true. 
 *design a data structure to keep those numbers and implement those methods
 * @author shirleyyoung
 *
 */
import java.util.*;
public class AssignNumbers {
 private static BitSet bits = new BitSet(32);
 private static Set numbers = new HashSet ();
 private static void toBitSet(int number) {
  int index = 0;
  while (number != 0) {
   if (number % 2 != 0)
    bits.set(index);
   index++;
   // >> signed
   // >>> unsigned
   number = number >> 1;
  }
 }
 
 private static int toInteger() {
  int value = 0;
  for (int i = 0; i < bits.length();i++) {
   value += bits.get(i) ? (1 << i) : 0;
  }
  return value;
 }
 
 public static int getNumber() {
  if (!numbers.contains(toInteger())) {
   numbers.add(toInteger());
   return toInteger();
  }
  else {
   for (int i = 0; i < 32; i++) {
    bits.flip(i);
    if (!numbers.contains(toInteger())) {
     numbers.add(toInteger());
     return toInteger();
    }
   }
  }
  return -1;
 }
 public static boolean requestNumber(int number) {
  if (numbers.contains(number))
   return false;
  else {
   numbers.add(number);
   toBitSet(number);
   return true;
  }
 }

 public static void main(String[] args) {
  System.out.println(getNumber());
  //System.out.println(requestNumber(123));
  //System.out.println(requestNumber(123));
  //System.out.println(getNumber());
  for (int i = 0; i < 1000; i++) {
   System.out.println(getNumber());
  }

 }
}

Thursday, February 19, 2015

Read N Characters Given Read4 I & II

The API: int read4(char *buf) reads 4 characters at a time from a file.
The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.
By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.
Note: (for II)
The read function may be called multiple times.



Update: 2015 - 03 - 30
I realized that I understood the question wrong. The char* buf is the output array. The explanation below is correct, here is the updated code.


public int read4(char[] buff){
  return 4;
 }
 public int readN(char[] buff, int N){
  char[] tmp = new char[4];
  int index = 0, next = 0;
  while(index < N  && (next = read4(tmp)) != 0)
   for(int i = 0; i < next && index < N; buff[index++] = tmp[i++]);
  return index;
 }
 int curr = 0;
 public int readN2(char[] buff, int N){
  char[] tmp = new char[4];
  int next = 0;
  int length = 0;
  while(length < N && (next = read4(tmp)) != 0){
   for(int i = 0; i < next && length++ < N; buff[curr++] = tmp[i++]);
  }
  return length;
 }


It took me a while to understand how the read() method works. I implemented the read4() method, which makes the whole class easier to test.

Basically, if n >= length of the buf, we read the whole array and return its length. Otherwise, we track the position of the next character (nextChar) we will read next time we call readN() method, so we simply start from nextChar every time we call readN(). Since we initialize the out array (the one we stored the characters) with size n, each time we call readN(), we need to increment the length of the out array if the length of  buf is larger than n. I wrote another method read() to handle cases such as length of buff is smaller than n or the remaining unread length of array is smaller than n, reset index and nextChar to zero since we have reached the end of the array.

It is much easier to understand if you happen to know how Java implements read().


public class ReadN {
 static char[] out = new char[4];
 static int index = 0;
 static int nextChar = 0;
 
 private static int read4(char[] buf, int start, int length) {
  int len = length - start;
  if (len < 4) {
   int i = len;
   while (i > 0) {
    out[index++] = buf[start++];
    i--;
   } 
   return len;
  }
  for (int i = 0; i < 4; i++) {
   out[index++] = buf[start++];
  }
  return 4;
 }
 private static int read(char[] buf) {
  int total = 0;
  int length = buf.length;
  int start = nextChar;
  while (start < length) {
   total += read4(buf, start, length);
   start += 4;
  }
  index = 0;
  nextChar = 0;
  return total;
 }
 /**
  * I
  * @param buf
  * @param n
  * @return
  */
 public static int readN(char[] buf, int n) {
  if (buf == null)
   throw new NullPointerException("Null array!");
  int length = buf.length;
  out = new char[n];
  if (length <= n) {
   return read(buf);
  }
  int start = 0;
  int total = 0;
  while (start < n) {
   total += read4(buf, start, n);
   start += 4;
  }
  return total;
 }
 /**
  * II
  * call multiple times
  * @param buf
  * @param n
  * @return
  */
 public static int readNII(char[] buf, int n) {
  if (buf == null)
   throw new NullPointerException("Null array!");
  int length = buf.length;
  if (index == 0)
   out = new char[n];
  else {
   int incrementLen = length - nextChar >= n ? n : length - nextChar;
   char[] copy = new char[out.length + incrementLen];
   System.arraycopy(out, 0, copy, 0, out.length);
   out = copy;
   if (incrementLen < n)
    length = incrementLen;
  }
  if (length <= n) {
   return read(buf);
  }
  int start = nextChar;
  int total = 0;
  while (start < n) {
   total += read4(buf, start, n);
   if (start + 4 > n) {
    start = n;
    break;
   }
   start += 4;
  }
  nextChar = start;
  return total;
 }
 public static void main(String[] args) {
  //char[] input = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'};
  //char[] input = {};
  //char[] input = {'a', 'b', 'c'};
  char[] input = {'a', 'b', 'c', 'd'};
  int total = 0;
  while (total < input.length) {
   total += readNII(input, 6);
  }
  System.out.println(total);

 }
}

Find second largest element in an unsorted array

Construct a tree and find the largest element by pairwise comparison ( I use a 2D array).
Back track all the elements that have been compared with the maximum.
Total comparison:
find the maximum: n /2 + n / 4 + ... n / k = n - 1, where k is the depth of the tree
find the second maximum log2n - 1 (1 comparison each layer)


public static int secondLargest(int[] array) {
  if (array == null || array.length == 0)
   throw new IllegalArgumentException("Null or empty array!");
  int[][] arrayTree = getTree(array);
  int maxEle = arrayTree[arrayTree.length - 1][0];
  int maxPos = 0;
  int secondMax = Integer.MIN_VALUE;
  for (int i = arrayTree.length - 2; i >= 0; i--) {
   maxPos = arrayTree[i][maxPos * 2] == maxEle ? maxPos * 2 : maxPos * 2 + 1;
   if (arrayTree[i].length % 2 != 0 && maxPos == arrayTree[i].length - 1) {
    //System.out.println(i);
    continue;
   }
   //the position of the potential second max
   //if max position is at odd index, second max = maxPos - 1;
   //else maxPos + 1
   int secondPos = maxPos % 2 == 0 ? maxPos + 1 : maxPos - 1;
   secondMax = Math.max(secondMax, arrayTree[i][secondPos]);
  }
  return secondMax;
 }
 private static int[][] getTree(int[] array) {
  int depth = (int)Math.ceil((Math.log((double)array.length) / Math.log(2.0))) + 1;
  int[][] tree = new int[depth][];
  tree[0] = array;
  for (int i = 1; i < depth; i++) {
   int length = tree[i - 1].length % 2 == 0 ? tree[i - 1].length / 2 : tree[i - 1].length / 2 + 1;
   tree[i] = new int[length];
   int index = 0;
   for (int j = 0; j < tree[i - 1].length - 1; j += 2) {
    tree[i][index] = Math.max(tree[i - 1][j], tree[i - 1][j + 1]);
    index++;
   }
   if (index < length)
    tree[i][index] = tree[i - 1][tree[i - 1].length - 1];
  }
  return tree;
 }

Wednesday, February 18, 2015

Summarize String.format()

I was preparing my interview, and I realized that I actually don't know how all the formatting works. So here it is:


public static void main(String[] args) {
  System.out.println("******integer format******");
  //if the number of digits is less than 4, the output will 
  //have leading spaces
  System.out.println("**" + String.format("%4d", 123) + "**");
  //if the number of digits is less than 4, the output will 
  //have trailing spaces
  System.out.println("**" + String.format("%-4d", 123) + "**");
  //if the number of digits is less than 4, the output will 
  //have leading zeros
  System.out.println("**" + String.format("%04d", 123) + "**");
  //will print maximum 2 characters of the string
  System.out.println("**" + String.format("%.2s", 123) + "**");
  //String will have at least length of 7, if the total length is 
  //less than 7, trailing space, group by ","
  //"+": including sign 
  System.out.println("**" + String.format("%+,7d",-1234) + "**");
  
  System.out.println("\n******String format******");
  //if the length of string is less than 15, the output will 
  //have trailing spaces
  System.out.println("**" + String.format("%15s", "abcdefghijk") + "**");
  //if the length of string is less than 15, the output will 
  //have leading spaces
  System.out.println("**" + String.format("%-15s", "abcdefghijk") + "**");
  //print at most 8 characters
  System.out.println("**" + String.format("%.8s", "abcdefghijk") + "**");
  
  
  System.out.println("\n******Floating point******");
  //actual number
  System.out.println("**" + String.format("%f", 3.14159) + "**");
  //padded left with zeros
  System.out.println("**" + String.format("%8f", 3.14159) + "**");
  //maximum 8 digits, if total digits is less than 8
  //padded left with zeros
  System.out.println("**" + String.format("%.8f", 3.14159) + "**");
  //total 10 digits, will have trailing blank spaces if total digits
  //is less than 10, at most 3 digits after the decimal point
  System.out.println("**" + String.format("%-10.3f", 3.14159) + "**");
  //total 10 digits, will have leading blank spaces if total digits
  //is less than 10, at most 3 digits after the decimal point
  System.out.println("**" + String.format("%10.3f", 3.14159) + "**");
  
  System.out.println("\n******time date******");
  //Calendar c = Calendar.getInstance();
  //year, the month with index 2 starting from 0 (0: January), date
  Calendar c = new GregorianCalendar(2015, 2, 1, 3, 24, 39);
  //full name of month, date(leading zeros if needed, only for date), 
  //4-digit year
  System.out.println(String.format("%tB %td, %tY", c, c, c));
  //full name of month, date(no leading zero, only for date), 
  //4-digit year
  System.out.println(String.format("%tB %te, %tY", c, c, c));
  //full name of month, date(no leading zero, only for date), 
  //2-digit year
  System.out.println(String.format("%tB %te, %ty", c, c, c));
  //month in two digits, with leading zero if necessary
  System.out.println(String.format("%tm %te, %tY", c, c, c));
  //can only be used on time, no date year can be included
  //12-hour clock : minute
  System.out.println(String.format("%tl:%tM%tp", c, c, c));
  //== %tm/%td/%ty
  System.out.println(String.format("%tD",c));
  System.out.println(String.format("%tm/%td/%ty", c, c, c));
 }