Thursday, September 1, 2016

Recursion is all about trust.

Image credit: http://www.cr31.co.uk/logoarts/
The secret of recursion is only one thing. Trust. Here's a neat example to show you what it exactly means. Quoting Stephan van Hulst from Code Ranch here.

Say there's a long queue of people, and you want to know how many are in the queue. You can simply ask the guy in front of you how many people there are in the queue, and then add 1 for yourself. You don't care how the guy in front of you got the answer, you just trust that it's correct. The guy in front uses the same technique. This goes on all the way until the guy at the front of the queue is asked how many people there are in the queue. The guy at the front sees no people in front of him, so he just reports 1. He is the base case.

final class PersonInQueue {
 
  private final PersonInQueue next;
 
  int askForLengthOfQueue() {
    if (next == null)
      return 1;
 
    return next.askForLengthOfQueue() +1;
  }
}
Here's the post: Algorithm explanation if you want to have a look. The question was on Tower of Hanoi.

Sunday, April 10, 2016

IP v4 address matcher (regex)

IP address is a string in the form "A.B.C.D", where the value of A, B, C, and D may range from 0 to 255. Leading zeros are allowed. The length of A, B, C, or D can't be greater than 3.

image
The pattern is: ^(?:(?:25[0-5]?|2[0-4]?[0-9]?|[01]?[0-9][0-9]?)\.){3}(?:25[0-5]?|2[0-4]?[0-9]?|[01]?[0-9][0-9]?)$

Java:
public class IPv4Regex {
	static final String ipV4Pattern = "^(?:(?:25[0-5]?|2[0-4]?[0-9]?|[01]?[0-9][0-9]?)\\.){3}"
			+ "(?:25[0-5]?|2[0-4]?[0-9]?|[01]?[0-9][0-9]?)$";
	
	public static void main(String[] args) {
		System.out.println("000.123.234.245".matches(ipV4Pattern));
	}
}

Tuesday, March 8, 2016

Tree traversal notes

1. Inorder:

- travel left subtree in inorder
- visit root
- travel right subtree in inorder

Recursive approach:

void inOrder() {
 if(root != null) {
  inOrder(root.left);
  System.out.println(root.data);
  inOrder(root.right);
 }
}

Iterative approach using stacks:

void inOrder() {

    Stack stack = new Stack();

    Node current = root;

    while(current!=null || !stack.isEmpty()) {
        //push to stack and move to left sub-tree
        if(current!=null){
            stack.push(current);
            current = current.left;
        }
        else { //we need to pop out nodes from stack and shift to its right sub-tree
            current = stack.pop(); //visited node
            System.out.println(current.data);
            current = current.right;
        }
    }
}

2. Pre-order:

- visit root
- travel left subtree in preorder
- travel right subtree in preorder

Recursive approach:

void preOrder() {
    if(root != null) {
        System.out.println(root.data);
        preOrder(root.left);
        preOrder(root.right);
    }
}

Iterative approach using stacks:

void inOrder() {

    Stack stack = new Stack();

    Node current = root;

    while(current!=null || !stack.isEmpty()) {
        //print each value, then push its right subtree to stack and move to left subtree
        if(current!=null){
            System.out.println(current.data); //visited node
            stack.push(current.right); //push right subtree
            current = current.left; //shift to left subtree
        }
        else {
            current = stack.pop();
        }
    }
}

Friday, February 12, 2016

Designing your own iterable stuff

Or, simply, implementing iterator logic in your own class, on which you can iterate or even use for-each loop. Because, for-each works only on Iterator based collections.
Following is a generic Java 7 code that takes into account a simple custom linked list implementation that is generic and can be iterated over, using following steps.
1. The stuff we want to iterate upon has to be Iterable and expose
iterator()
2. Design a java.util.Iterator by overriding hasNext(), next() and remove().

Sunday, June 28, 2015

Sorting Key-Value pairs in Java

Saw making your own sorting logic by implementing Comparable or Comparator? If not, click here. Now, how about sorting key-value pairs! Well, we need just a little code modification. See following code sample that sorts key-value pairs, first by key, then values. Look at the compareTo method implementation.