Friday, August 29, 2014

Algorithm Excercise

1. Linked List

1.1 single-linked list. it's a node and a list

package linkedList;

public class LList {

public LList next;

String data;

public LList(String data) {
this.data = data;
}

public void insertFront(String data) {

LList newNode = new LList(this.data);
newNode.next = this.next;
this.data = data;
this.next = newNode;
}

public LList find(String data) {
LList nextNode;
nextNode = this;
while (nextNode != null) {
if (nextNode.data != null && nextNode.data.equals(data))
return nextNode;
nextNode = nextNode.next;
}
return null;
}

public void delete(String data) {
if (data == null)
return;
LList cursor = this;
LList previous = null;
// first element need to be removed. this can not be removed so ship all
// element and remove last one
if (this.data != null && this.data.equals(data)) {
while (cursor.next != null) {
cursor.data = cursor.next.data;
previous = cursor;
cursor = cursor.next;
}
if (previous != null)
previous.next = null;
return;
}
previous = this;
cursor = this.next;
while (cursor != null) {

if (cursor.data != null && cursor.data.equals(data)) {
previous.next = cursor.next;
cursor = cursor.next;
} else {
previous = cursor;
cursor = cursor.next;
}
}
return;
}

public void insertAfter(String afterData, String data) {

LList afterNode = this.find(afterData);
if (afterData == null)
return;
LList newNode = new LList(data);
newNode.next = afterNode.next;
afterNode.next = newNode;
}

public String toString() {
StringBuffer sb = new StringBuffer();
LList curNode;
curNode = this;
while (curNode != null) {
sb.append(curNode.data);
curNode = curNode.next;
}
return sb.toString();
}

/**
* @param args
*/
public static void main(String[] args) {
// insertFron test
LList aList = new LList("z");
aList.insertFront("y");
aList.insertFront("x");
aList.insertFront("w");
aList.insertFront("v");
aList.insertFront("u");
System.out.println(aList);
// find test
LList startNode;
startNode = aList.find("y");
System.out.println(startNode);
System.out.println(aList);
// delete test
aList.delete("w");
System.out.println(aList);
// boundary test
aList.delete("u");
System.out.println(aList);
aList.delete("z");
System.out.println(aList);
// insertfter test
aList.insertAfter("v", "w");
System.out.println(aList);
}

}

1.2 Separate node and list. Node can be reused for implementing queue and stack
package linkedList;

public class ListNode {

public ListNode next;

String data;

public ListNode(String data) {
this.data = data;
this.next = null;
}
public String toString(){
return data;
}
}
package linkedList;

public class LList {

ListNode head;
//this constructor will create the first node in list
public LList(String data) {
this.head = new ListNode(data);
}
//this is much simpler than the node as list solution
public void insertFront(String data) {

ListNode newNode = new ListNode (data);
newNode.next = head;
head = newNode;
}

public ListNode find(String data) {
ListNode nextNode;
nextNode = head;
while (nextNode != null) {
if (nextNode.data != null && nextNode.data.equals(data))
return nextNode;
nextNode = nextNode.next;
}
return null;
}
//delete first node is much easier since it's now head instead of "this". you can not assign new value to "this"
public void delete(String data) {
if (data == null)
return;
ListNode curr = head;
ListNode prev = null;

//head matches,adjust head 
while(head!=null && head.data != null && head.data.equals(data)) {
head = head.next;
}
////situation like aaaaaaa
if (head == null || (head!=null && head.next==null))
return;
//for any other matchings,point previous node's next to matching node's next node 
prev = head;
curr = head.next;
while (curr != null) {

if (curr.data != null && curr.data.equals(data)) {
prev.next = curr.next;
curr = curr.next;
} else {
prev = curr;
curr = curr.next;
}
}
return;
}

public void insertAfter(String afterData, String data) {

ListNode afterNode = this.find(afterData);
if (afterData == null)
return;
ListNode newNode = new ListNode(data);
newNode.next = afterNode.next;
afterNode.next = newNode;
}

public String toString() {
StringBuffer sb = new StringBuffer();
ListNode curNode;
curNode = head;
while (curNode != null) {
sb.append(curNode.data);
curNode = curNode.next;
}
return sb.toString();
}

/**
* @param args
*/
public static void main(String[] args) {
// insertFron test
LList aList = new LList("z");
aList.insertFront("y");
aList.insertFront("x");
aList.insertFront("w");
aList.insertFront("v");
aList.insertFront("u");
System.out.println(aList);
// find test
ListNode startNode;
startNode = aList.find("y");
System.out.println(startNode);
System.out.println(aList);
// delete test
aList.delete("w");
System.out.println(aList);
// boundary test
aList.delete("u");
System.out.println(aList);
aList.delete("z");
System.out.println(aList);
// insertfter test
aList.insertAfter("v", "w");
System.out.println(aList);
}

}

--the following example exercise recursion and iteration to merge two sorted linked list
package linkedList;

public class ListUtil {

/**
* @param args
*/
public static void main(String[] args) {
ListNode aList = new ListNode("u");
aList.next= new ListNode("v");
aList.next.next = new ListNode("w");
aList.next.next.next = new ListNode("x");
aList.next.next.next.next = new ListNode("y");
aList.next.next.next.next.next = new ListNode("z");


ListNode bList = new ListNode("a");
bList.next= new ListNode("b");
bList.next.next = new ListNode("c");
bList.next.next.next = new ListNode("f");
bList.next.next.next.next = new ListNode("o");
bList.next.next.next.next.next = new ListNode("p");

//ListNode merged = mergeSortedList(aList,bList);
ListNode merged2 = mergeSortedListiteration(aList,bList);
System.out.println("done");
}
//recursive
//this returns new conceptual head of the two list
public static ListNode mergeSortedList(ListNode l1, ListNode l2){
ListNode head = null;//this is the head of merged

if (l1==null )
return l2;
else if(l2 ==null)
return l1;
//l1 <= l2, l1 is the new head, and l1 needs to move further to use its next node to continue the comparison
//new head's next will be the smaller new head from next operation
if(l1.data.compareTo(l2.data)<=0){
head = l1;
head.next = mergeSortedList(l1.next,l2);
}
//it does same logic to another list
else if(l1.data.compareTo(l2.data)>0){
head = l2;
head.next = mergeSortedList(l1,l2.next);
}
return head;
}
//iteration method
public static ListNode mergeSortedListiteration(ListNode l1,ListNode l2){
 //still head
        ListNode fakeHead = new ListNode("fake");
//moving head,        
        ListNode p = fakeHead;

        while(l1 != null && l2 != null){
       
          if(l1.data.compareTo(l2.data) <= 0){
              p.next = l1;
              l1 = l1.next;
          }else{
              p.next = l2;
              l2 = l2.next;
          }
 //making new head
          p = p.next;
        }

        if(l1 != null)
            p.next = l1;
        if(l2 != null)
            p.next = l2;

        return fakeHead.next;
}
}

to be continued...

Tuesday, August 26, 2014

Scaling Out

For big web systems, scaling is requirement #0.It's part of requirements even it is also architectural concern which is defined as non-functional requirement conventionally.

machine can always be scaled up, but real scalability comes from being able to  scale out.

Key: partition by function and data. asynchronous everywhere.

Best practices summarized from Randy Shoup's good article finding from here: http://www.infoq.com/articles/ebay-scalability-best-practices

partition by function. such as partition by bidding and order tracking.

split horizontally. within same function, break the workload down to manageable units. for example, as logon servers, one server is dedicated for user id between 1 and 10000, second is dedicated for 10001 and 20000 etc.

SOA principle and make services stateless. this makes it easy to scale out since services are equal to each other. it'd be easier to set up load balancer to distribute the work load among them.

Decouple functions asynchronously. A depends on B implies scaling A has to also scaling B, Failure on B implies also failure on A. Methods to use includes queue, batch process such as ETL, multi-cast messaging or other means to relay or staging the request. After decoupling, A can move forward even B is down.

This principle can also be used inside software itself. At every level, decomposing the processing into stages or phases, and connecting them up asynchronously, is critical to scaling.

Anything that can wait should wait. some back end processes should not be part of front end process in order to provide responsive experience to end user. such as transactions in bank system typically be processed in the night. user can quickly submit their requests, but they can endure the latency of waiting couple days for the transactions being synchronized everywhere in the banking system.

Abstraction everywhere. such as defining simple and long lasting interfaces between components. parameters are typically defined as key -value pairs or XML to support extensibility.

"
The virtual machine in many modern languages abstracts the operating system. Object-relational mapping layers abstract the database. Load-balancers and virtual IPs abstract network endpoints. As we scale our infrastructure through partitioning by function and data, an additional level of virtualization of those partitions becomes critical.
"

Using cache appropriately.
not distributed transactions.
databases are put in shards to server different  functions.

Thursday, August 21, 2014

Git Notes

https://www.atlassian.com/git/tutorial/git-basics#!init

1. Create a repository
go to the directory you want to treat as central repository and run
git init --bare

e.g.
create repository called amaTest.git in /home/ama/gitRepository:
cd /home/ama/gitRepository
git init --bare amaTest.git

# --bare is to create a shared repository for other person to clone from

to be continued...

Friday, August 08, 2014

Reset Garmin Watches (405, 310xt)



Forerunner 310XT


Soft Reset
  1. Connect device to computer (except on Forerunner 310XT)
  2. Press and hold Mode and Lap/Reset for 10 seconds
  3. Release both buttons
  4. Power device on once device starts to charge
Hard Reset (erase user data)


  1. Start with device powered off
  2. Press and hold Mode and Power
  3. Release buttons once Do You Really Want to Erase All User Data? message appears
  4. Select Yes
Master Hard Reset


  1. Power Forerunner off
  2. Press and hold Enter and Mode buttons
  3. Press and release Power button
  4. Press and release Lap/Reset (watch will power off)
  5. Wait 3 seconds
  6. Release Enter and Mode
Forerunner 405


Soft Reset
  1. Connect device to computer using charging clip
  2. Press and hold Start/Stop and Lap/Reset for 10 seconds
  3. Release and wait 3 seconds for device to power on
Master reset
  1. If turned off, power on Forerunner
  2. Press and hold Start/Stop and Lap/Reset simultaneously
  3. Press both buttons until screen goes blank
  4. Release Start/Stop and continue to hold Lap/Reset
  5. Release Lap/Reset when the Do you really want erase all user data? message appears
  6. Select Enter (Start/Stop) to clear user data

Friday, August 01, 2014

EOF

I keep forget EOF in linux, so even it's simple, it's worth to put here to help me to remember:
unix/linux: ctrl+d
windows:ctrl+z