Archive

Tag Archives: connect

9Question

Get the greatest distance between two nodes in a binary tree. Assume links between nodes are bidirectional. Distance is defined as the amount of nodes connected along the path linked two nodes. Write an algorithm to calculate distance between two nodes. Take the figure at the right, the greatest length should be 4.

Solution

Usual post-order recursive binary tree traversal should do the job. In this case, (obviously) the path must passes through the root. So we should do the following. Recursively return the max length (from left or right) to the parent, and make an exception for the root. The result is simply the sum of maxes from left and right.

Example

# node structure
class bst_node:
    left = None
    right = None
    def __init__(self, left=None, right=None):
        self.left = left
        self.right = right

# join left and right max at root, literally
def get_max_len(root):
    left_max = depth_first_traversal(root.left)
    right_max = depth_first_traversal(root.right)
    return left_max + right_max

# a usual traversal, returning the max length begin
# from this node
def depth_first_traversal(node):
    if not node: return 0
    left_max = depth_first_traversal(node.left)
    right_max = depth_first_traversal(node.right)
    return max(left_max, right_max) + 1

# binary tree setup
node_12 = bst_node()
node_13 = bst_node()
node_05 = bst_node()
node_07 = bst_node(node_12, node_13)
node_09 = bst_node()
node_11 = bst_node()
node_06 = bst_node(node_05, node_07)
node_10 = bst_node(node_09, node_11)
node_08 = bst_node(node_06, node_10)

# answer should be 5
root = node_08
print get_max_len(root)
# node structure
class bst_node:
    left = None
    right = None
    left_max_dist = 0
    right_max_dist = 0

    def __init__(self, left=None, right=None):
        self.left = left
        self.right = right

    def max_dist(self):
        return max(self.left_max_dist, self.right_max_dist)

# calculate function
def calculate_max_len(node):

    # check node
    if not node: return 0

    # if left is not empty, then left is is the max + 1
    if node.left:
        calculate_max_len(node.left)
        node.left_max_dist = node.left.max_dist() + 1

    # if right is not empty, right is is the max + 1
    if node.right:
        calculate_max_len(node.right)
        node.right_max_dist = node.right.max_dist() + 1

    # return the max dist
    return node.left_max_dist + node.right_max_dist

# bst
node_12 = bst_node()
node_13 = bst_node()
node_5 = bst_node()
node_7 = bst_node(node_12, node_13)
node_9 = bst_node()
node_11 = bst_node()
node_6 = bst_node(node_5, node_7)
node_10 = bst_node(node_9, node_11)
node_8 = bst_node(node_6, node_10)

# answer should be 5
root = node_8
print calculate_max_len(root)
// 数据结构定义
struct NODE
{
     NODE* pLeft;            // 左子树
     NODE* pRight;          // 右子树
     int nMaxLeft;          // 左子树中的最长距离
     int nMaxRight;         // 右子树中的最长距离
     char chValue;        // 该节点的值
};

int nMaxLen = 0;

// 寻找树中最长的两段距离
void FindMaxLen(NODE* pRoot)
{
     // 遍历到叶子节点,返回
     if(pRoot == NULL) {
          return;
     }
     // 如果左子树为空,那么该节点的左边最长距离为0
     if(pRoot -> pLeft == NULL) {
          pRoot -> nMaxLeft = 0;
     }
     // 如果右子树为空,那么该节点的右边最长距离为0
     if(pRoot -> pRight == NULL) {
          pRoot -> nMaxRight = 0;
     }
     // 如果左子树不为空,递归寻找左子树最长距离
     if(pRoot -> pLeft != NULL) {
          FindMaxLen(pRoot -> pLeft);
     }
     // 如果右子树不为空,递归寻找右子树最长距离
     if(pRoot -> pRight != NULL) {
          FindMaxLen(pRoot -> pRight);
     }
     // 计算左子树最长节点距离
     if(pRoot -> pLeft != NULL) {
          int nTempMax = 0;
          if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight) {
               nTempMax = pRoot -> pLeft -> nMaxLeft;
          }
          else {
               nTempMax = pRoot -> pLeft -> nMaxRight;
          }
          pRoot -> nMaxLeft = nTempMax + 1;
     }
     // 计算右子树最长节点距离
     if(pRoot -> pRight != NULL) {
          int nTempMax = 0;
          if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight) {
               nTempMax = pRoot -> pRight -> nMaxLeft;
          }
          else {
               nTempMax = pRoot -> pRight -> nMaxRight;
          }
          pRoot -> nMaxRight = nTempMax + 1;
     }
     // 更新最长距离
     if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen) {
          nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight;
     }
 }
 //很明显,思路完全一样,但书上给的这段代码更规范!:)。
//定义一个结构体
struct NODE
{
    NODE* pLeft;
    NODE* pRight;
    int MaxLen;
    int MaxRgt;
};
NODE* pRoot;  //根节点
int MaxLength;

void traversal_MaxLen(NODE* pRoot) {
    if(pRoot == NULL) {
        return 0;
    };
    if(pRoot->pLeft == NULL) {
        pRoot->MaxLeft = 0;
    }
    // 若左子树不为空
    else {
        int TempLen = 0;
        // 左子树上的,某一节点,往左边大,还是往右边大
        if(pRoot->pLeft->MaxLeft > pRoot->pLeft->MaxRight) {
            TempLen+=pRoot->pLeft->MaxLeft;
        }
        else {
            TempLen+=pRoot->pLeft->MaxRight;
        }
        pRoot->nMaxLeft = TempLen + 1;
        traversal_MaxLen(NODE* pRoot->pLeft); // 此处,加上递归
    }

    if(pRoot->pRigth == NULL) {
        pRoot->MaxRight = 0;
    }
    // 若右子树不为空
    else {
        int TempLen = 0;
        // 右子树上的,某一节点,往左边大,还是往右边大
        if(pRoot->pRight->MaxLeft > pRoot->pRight->MaxRight) {
            TempLen+=pRoot->pRight->MaxLeft;
        }
        else {
            TempLen+=pRoot->pRight->MaxRight;
        }
        pRoot->MaxRight = TempLen + 1;
        traversal_MaxLen(NODE* pRoot->pRight); // 此处,加上递归
    }

    if(pRoot->MaxLeft + pRoot->MaxRight > 0) {
        MaxLength=pRoot->nMaxLeft + pRoot->MaxRight;
    }
}

Ssh is a very convenient way to remotely command or control other devices. We use ssh to push commits to git server, to access remote server, and even to manipulate the content of our iphones and ipads. However it’s usually distributing to type your long and elusive password every time. Therefore here I would like introduce a way to create a steady relationship between your computer and the remote server you wanna connect with.

The principle is this, ssh connection establishments requires verification using the computer unique key of both devices. in order to simplify this step, we can generate a public key of your computer in advanced and which allows other to identify you. While you put that public key in the remote device as authorized key, you can kinda fast forward the process.

step 1: open terminal and “ssh-keygen -t dsa”
step 2: open “.ssh/id_dsa.pub” and copy content inside
step 3: open new tab in terminal and ssh server
step 4: paste all content into /home//.ssh/authorized_keys

a@A:~> ssh-keygen -t rsa
a@A:~> ssh b@B mkdir -p .ssh
a@A:~> cat .ssh/id_rsa.pub | ssh b@B ‘cat >> .ssh/authorized_keys’

Recently my blog has been referred by winandmac.com to show how to install the Samsung Kies on Lion. I have been subscribing winandmac.com for a long time and I am so grad to be linked by this international and informative blog. And the followings are the posts. =]

English version: How to: connect Samsung Galaxy Tab 10.1 with Mac OS X Lion
Chinese version: 把Samsung Galaxy Tab 10.1與Mac OS X Lion連接

Json has been an efficient way to handle information and message exchanges in web programming. For example, I usually use PHP to connect MySQL and retrieve information, then display as Json. So a webpage can “AJAX” the displayed Json to create a dynamic view on itself. However, while the information involves unicode characters, PHP turn them into unreadable codes. After google, I found the following is the best way to solve the problem.

$string = '你好嗎';
echo json_encode($string); //Output "u4f60u597du55ce"
echo preg_replace("#u([0-9a-f]+)#ie", "iconv('UCS-2', 'UTF-8', pack('H4', '1'))", json_encode($string)); // Output "你好嗎"

In order to make a program more flexible, it is normal to create an external file to store all the setting. For example, resolution setting of a game is saved in “config.ini” or “settings.prop” so that we can easily modify a program without recompile it. Here I would show you how to do it.

First, we create a config file (you can name it with any name you want as Java read its text only).

# comment
! comment again
Surname=Backham
Othername=Peter

Second, you need to use the Java API “properties” to read in the config text.

try {
  properties = new Properties();
  properties.load(new FileInputStream("config.ini"));
}
catch (Exception e) {
  System.out.println(e);
}

Alternatively, I had created a class for it. You may copy it if you like, just don’t modify it. =]

/*
 * Code by Nicholas Wong. Copyright reserved.
 * Usage:
 * ConfigReader configReader = new ConfigReader("config.ini");
 * SshConnectorOld.hostname = configReader.getProperty("Surname");
 */

import java.util.*;
import java.io.*;

public class ConfigReader {

  private String fileName;
  private Properties properties;

  public String getProperty(String propName) {
    return properties.getProperty(propName);
  }

  public void printPropertyList() {
    properties.list(System.out);
  }

  public ConfigReader(String fileName) {
    this.fileName = fileName;
    readProperties();
  }

  private static String getClassPath() {
    StringBuffer classLocation  = new StringBuffer();
    final String className = SshConnectorOld.class.getName().replace('.', '/') + ".class";
    final ClassLoader classloader = SshConnectorOld.class.getClassLoader();

    if (classloader == null) {
      System.out.println("Cannot load the class");
      return null;
    }
    else {
      String[] classLocationArray = classloader.getResource(className).toString().substring(6).split("/");
      for (int i  = 0; i<classLocationArray.length-2; i++) {
        classLocation.append(classLocationArray[i] + "/");
      }
      return classLocation.toString();
    }
  }

  private void readProperties() {
    try {
      properties = new Properties();
      properties.load(new FileInputStream(getClassPath() + fileName));
      System.out.println("Configuration file is read successfully.");
    }
    catch (Exception e) {
      System.out.println("Configuration file reading failed.");
      System.out.println(e);
    }
  }
}

Suppose we have more than one network adapter, how could we designate the adapter used to access the Internet? One way would be manually configure the default gateway.

Easy way (2 adapters and with little networking knowledge):
Suppose you want to use wireless connection in the condition of having both wire and wireless connection at the same time.

  1. Open up a CMD with administrator right.
  2. Connect internet wire.
  3. Delete default gateway by typing “route delete 0.0.0.0” in CMD opened.
  4. Connect wireless.

Advanced way:
Suppose you have multiple connections to the internet with a number of connections. you can assign default gateway.

  1. Establish all the connections
  2. Open up a CMD with administrator right.
  3. Type “ipconfig /all” and you should be able to see a number of network connections.
  4. Jot down the gateway of the connection you want to use to access the internet.
  5. Delete all the default gateway by typing “route delete 0.0.0.0”.
  6. Create a default gateway to 192.168.0.1 (suppose this is the gateway you want) by typing “route add 0.0.0.0 mask 0.0.0.0 192.168.0.1”.

Also, you can add static routes for hosts you need to reach via any adapter. As a result you can access internet with one connection and send files to friends with another adapter.

  • After the previous steps, Create static routes to 10.1.1.1 (suppose it is your friend’s IP address) via the gateway 192.168.1.1 (suppose it is the desired gateway you want to use to send the files) by typing “route add 10.1.1.1 mask 255.255.255.255 192.168.1.1”.

It is useless to read without a real practice! Try it and you will know how it works!

%d bloggers like this: