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.

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());
  }

 }
}

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;
 }

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));
 }