Monthly Archives: November 2013

Java.io in nutshell: 22 case studies

This post attempts to cover a comprehensive set of operations in java.io. Compared with other books and blogs related to this topic, my motivation is to show “how-to” through case studies. As once a Java student, I realize the most effective way of learning a new program language is through examples: copy and paste a piece of codes, run it to see results, then try to modify and re-run it step-by-step. Therefore, I assume this post will be helpful.

It is worth noting that this post will not touch anything related to java.nio because I think it is quite a different topic.

read more

Recommend – LaTeX symbol classifier

When I am working with LaTeX, one difficulty is to memorize a symbol. Finding it via Internet is not easy either. Detexify is quite useful. You can simply draw the symbol and it will do OCR and search the matched one.

MathJax with blogger.com

MathJax in blogger.com is useful when I need to input equation in my blog. This is a instruction and test of using MathJax in blogger.com.

  1. set blogger.com template to “Simple”. “Dynamic Views” seems not working.
  2. edit HTML by adding the following code between <head> and </head>: <script src='http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML' type='text/javascript'/>
  3. type math equation in the blog.

Given a binary tree, create a list of all the nodes at each depth — Recursive version

Another FAQ on the programming interview.

Question

Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (eg, if you have a tree with depth D, you’ll have D linked lists).

Solution

Cracking the Coding Interview (4ed) (see page 126) provided a non-recursive algorithm. For me, a recursive version is neater and much easier to understand.

Sort a stack in ascending order in O(n log n)

Another FAQ on the programming interview.

Question

Write a program to sort a stack in ascending order. You should not make any assumptions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.

Solution

Cracking the Coding Interview (4ed) (see page 121) provided an O(N^2) algorithm by using one more stack. The idea is to pull an item from the original stack and push it on the other stack. If pushing this item would violate the sort order of the new stack, the algorithm removes enough items from it so that it’s possible to push the new item. Because of the copyright, I won’t paste her code here, but you can easily find it out online (:P).

Can we do better? I think we can mimic the way of quicksort by picking a pivot from the stack (using pop) first. Then we conduct the partition operation by pushing all elements in the stack with values less than the pivot into one stack, while all elements with values greater than the pivot into the other. After that, we recursively sort two sub-stacks and merge two at last with the pivot in the middle.

Because we can only use the stack structure, I pick the pivot using pop. The merge operation is tricky and I am not sure if we can have a better way to combine two stacks. So if you have any idea, please let me know.

On average, this algorithm makes O(n log n) comparisons to sort items. In the worst case, it makes O(n2) comparisons, though this behavior is rare.

public static Stack<Integer> sort(Stack<Integer> s) {
  if (s.isEmpty()) {
    return s;
  }
  int pivot = s.pop();
  
  // partition
  Stack<Integer> left  = new Stack<Integer>();
  Stack<Integer> right = new Stack<Integer>();
  while(!s.isEmpty()) {
    int y = s.pop();
    if (y < pivot) {
      left.push(y);
    } else {
      right.push(y);
    }
  }
  sort(left);
  sort(right);
   
  // merge
  Stack<Integer> tmp = new Stack<Integer>();
  while(!right.isEmpty()) {
    tmp.push(right.pop());
  }
  tmp.push(pivot);
  while(!left.isEmpty()) {
    tmp.push(left.pop());
  }
  while(!tmp.isEmpty()) {
    s.push(tmp.pop());
  }
  return s;
}

read more

Two algorithms to find the nth to last element of a singly linked list

This is one of frequently asked questions on the programming interview. There are two kinds of solution: iteration-based and recursion-based.

Data structure

We first define a toy class for the single linked list.

class LinkedListNode {

  int            data;
  LinkedListNode next;
  
  LinkedListNode(int data, LinkedListNode next) {
    this.data = data;
    this.next = next;
  }
}

Iteration-based algorithm

The iteration-based solution is quite tricky but I really like it. In Cracking the Coding Interview (4ed), the solution uses two pointers p1 and p2. Her algorithm first increaments p2 by (n-1) times, and then moves both p1 and p2 until p2.next reaches the tail of the list. As the result, p1 points to the th to last element. Because of the copyright, I won’t reproduce her code in this post. If you are interested, please see page 106 for the solution.

Recursion-based algorithm

The recursion version is straightforward too. We first recursively call a function until we reach the tail of the list. Then we start to count from 0 and increment the counter when a called function is returned. Essentially, it counts the number of popped function calls on the call stack. When the counter equals to , we record the element, which is the th to the last.

An easier way to count the number of times we have returned to a recursive call is using a global variable. My solution attempted to avoid it by creating a class Record which stores the returned element (null if not) and the counter.

class Record {

  LinkedListNode node;
  Integer        i;

  Record(LinkedListNode node, int i) {
    this.node = node;
    this.i = i;
  }
}

Then I used a helper function for the recursive purpose.

private static Record nthToLastRurHelper(
    LinkedListNode head, 
    int n) {
  if (head == null) {
    // tail
    return new Record(null, 0);
  }
  Record record = nthToLastRurHelper(head.next, n);
  record.i++;
  if (record.i == n) {
    record.node = head;
    return record;
  } else {
    return record;
  }
}

read more

函数式编程的另类指南(10)

The following part is not maintained anymore. Please go to 函数式程序设计的另类指南 for the whole translation.

以下内容不再更新,浏览全部翻译,请访问 函数式程序设计的另类指南

原文链接:Functional Programming For The Rest of Us
原文作者:Vyacheslav Akhmechet

模式匹配

模式匹配不是什么新特性。事实上,它和函数式编程的关系不大。为什么总是把它当做函数式编程的一个特性呢?这是因为函数式语言已经支持模式匹配一段时间了,而现代命令式语言还不行。

read more

函数式编程的另类指南(8)

The following part is not maintained anymore. Please go to 函数式程序设计的另类指南 for the whole translation.

以下内容不再更新,浏览全部翻译,请访问 函数式程序设计的另类指南

原文链接:Functional Programming For The Rest of Us
原文作者:Vyacheslav Akhmechet

惰性求值

当我们采用函数式哲学以后,就可以使用惰性(或延迟)求值这一技术。在并发一节,我们已经看过如下代码:

read more