我写故我在

I write, therefore I am

HuLu2012校园招聘笔试题

Posted by ieipi 于 九月 26, 2011

2011年9月23日中科院
70分钟,7张卷子,不得不说十分变态。。。

题目

此幻灯片需要JavaScript支持。

参考解答
 一.填空题
1. 11
2. 29
3. 
4. 1,3??
5. 11
6. 4
7. 32, 1
8. 9
9. 4
10. 141
11. 59
12. n(n+1)/2+1
13. 方块5
14. 9!
15. 5

二.编程题

三.附加题

Advertisements

Posted in 技术 | Tagged: | Leave a Comment »

创新工场2012校园招聘笔试题

Posted by ieipi 于 九月 25, 2011

创新工场笔试2011年9月19日中科院
一个小时。感觉答的不错,结果还是被鄙视了,没有收到面试通知。

题目

此幻灯片需要JavaScript支持。

参考答案
一.选择题
ACDDD BABCC
值得注意的是第7题:
首先:M个球放入N个箱子总共有C(M+N-1,N-1)中方法
方法一:
8个蓝球形成9个空格,放入5个红球共有C(5+9-1, 9-1)=C(13, 8);
若保证红球不相邻,则每个格子最多只能放一个,即C(9,5);
故:C(9,5)/ C(13, 8)=14/143
方法二:
5个红球8个蓝球放一列,相当于从13个球中选出5个(则剩下的8个已定),共有C(13,5)种;
要保证红球不相邻, 则每个红球边至少有一个蓝球,共消耗4个蓝球,剩下4个,相当于从9个球中选4个,则共有C(9,4)种;
故: C(9,4)/C(13,5) =14/143;

二.编程题
1.可以对P和R分别设一加权因子a,b,则对每一个应用,其待排序因素为a*P+b*R,转化为一个普通的一维序列,从而可以采用排序算法解决。
2.源代码如下:

int Fibonacci(int n)
{
	if(n<=0)
		return 0;
	if(n==1 || n==2)
		return 1;
	int first,second,third;//f(n-2),f(n-1),f(n);
	first = 1;
	second = 1;
	for(int i=2; i<=n; i++)
	{
		third = first + second;
		first = second;
		second = third;
	}
	return third;
}

3.约瑟夫环问题


Posted in 技术 | Tagged: | Leave a Comment »

程序员面试题集004

Posted by ieipi 于 九月 16, 2011

题目
输入一个整数和一颗二元树,打印出与输入整数相等的所有从根节点到叶子节点的路径.
思路
首先根据树的遍历算法很容易找到满足条件的叶子节点.
问题是如何打印出从根节点到该节点的路径?
进一步考虑,遍历通常用的是递归算法,从根节点到叶子节点的函数调用过程系统已经保存好了,用到的数据结构就是栈.
树中遍历的过程即是一个入栈和出栈的过程.所以我们同样可以采用一个栈来显式保存遍历的路径.
源代码
/**
 * @brief find the path whose sum equals the specified number.
 *
 * @param pNode root
 * @param expectedSum expected sum.
 * @param path the stack holds the path.
 * @param currentSum sum of the current path.
 */
    void
FindPath (struct BinaryTreeNode *pNode, int expectedSum, vector &path, int &currentSum  )
{
    if(pNode == NULL) {
        return;
    }
    currentSum += pNode->m_nValue;
    path.push_back(pNode->m_nValue);

    bool isLeaf = (pNode->m_pLeft == NULL)&&(pNode->m_pRight == NULL);
    if(currentSum == expectedSum && isLeaf) {
        vector::iterator itr = path.begin();
        for(; itr != path.end(); itr++) {
            cout << *itr << "\t";
        }
        cout << endl;
    }
    if(pNode->m_pLeft)
        FindPath(pNode->m_pLeft, expectedSum, path, currentSum);
    if(pNode->m_pRight)
        FindPath(pNode->m_pRight, expectedSum, path, currentSum);

    currentSum -= pNode->m_nValue;
    path.pop_back();
    return ;
}		/* -----  end of function FindPath  ----- */

 Reference

1.http://zhedahht.blog.163.com/blog/static/254111742007228357325/

Posted in 算法, 技术 | Tagged: , | Leave a Comment »

程序员面试题集003

Posted by ieipi 于 九月 14, 2011

题目

在O(n)的时间内求出一个输入数组的最大子段和

思路一

最笨的方法就是遍历.遍历所有的子数组,并比较它们的和,获得最大者.
但时间复杂度为O(n^3).
源代码

int MaxSubSum1(const int arr[], int len)
{
    //there is at least one positive value in the input array.
    int MaxSum = 0;

    for ( int i=0; i<len; i++) {
        //start index of the subsequence.
        for ( int j=i; j<len; j++){
            //end index of the subsequence.
            int SubSum = 0;
            //caculate the sum of the subsequence.
            for ( int k=i; k<=j; k++) {
                SubSum += arr[k];
            }
            if(SubSum > MaxSum)
                MaxSum = SubSum;
        }
    }
    return MaxSum;
}

思路二

上述算法可以优化,求子数组和时不必从头开始,可以直接利用上一次求和的结果,从而可以去掉一层循环.
时间复杂度可以降到O(n^2).
源代码

int MaxSubSum2(const int arr[], int len)
{
    int MaxSum = 0;

    for ( int i=0; i<len; i++){
        int SubSum = 0;
        for ( int j=i; j<len; j++) {
            //caculate the sum of the subsequence with help of the last SubSum.
            SubSum += arr[j];
            if ( SubSum > MaxSum ) {
                MaxSum = SubSum;
            }
        }
    }
    return MaxSum;
}

思路三
采用递归,现将输入数组分解为两个子数组,再递归处理两个子数组,最后将结果合并.即标准的Divide-Conquer-Combine模式.
时间复杂度可以进一步降到O(nlogn)
源代码

int MaxSubSumRec(const int arr[], int left, int right)
{
   //base case.
    if(left == right){
        //TODO:
        return arr[left];
    }
    //divide
    int center = (left+right)/2;
    //conquer
    int MaxLeftSum = MaxSubSumRec(arr, left, center);
    int MaxRightSum = MaxSubSumRec(arr, center+1,  right);
    //combine
    int MaxLeftBorderSum = 0; int LeftBorderSum = 0;
    for(int i=center; i>=left; i--){
        LeftBorderSum += arr[i];
        if(LeftBorderSum > MaxLeftBorderSum)
            MaxLeftBorderSum = LeftBorderSum;
    }
    int MaxRightBorderSum = 0; int RightBorderSum = 0;
    for(int i=center+1; i <= right; i++){
        RightBorderSum += arr[i];
        if(RightBorderSum > MaxRightBorderSum)
            MaxRightBorderSum = RightBorderSum;
    }
    int max = MaxLeftSum > MaxRightSum?MaxLeftSum:MaxRightSum;
    int LeftRightSum = MaxLeftBorderSum + MaxRightBorderSum;
    max = max>LeftRightSum?max:LeftRightSum;
    return max;
}
int MaxSubSum3(const int arr[], int len)
{
    return MaxSubSumRec(arr, 0, len-1);
}

思路四
输入数组中的若干个负数将数组划分为几个互补重合的子数组,我们只需分别求出这几个子数组的和并比较大小即可.
只需一次循环,时间复杂度为O(n).
源代码

int MaxSubSum4(const int arr[], int len)
{
   int MaxSum =0;
   int SubSum =0;
   for(int i=0; i<len; i++){
       SubSum += arr[i];
       if(SubSum>MaxSum)
           MaxSum = SubSum;
       else if (SubSum < 0 )
           SubSum = 0;
   }
   return MaxSum;
}

Posted in 算法 | Tagged: | Leave a Comment »

程序员面试题集002

Posted by ieipi 于 九月 14, 2011

题目
定义栈的数据结构,添加一个min函数,使之能在O(1)的时间内得到栈的最小元素.要求push,pop的时间复杂度都是O(1).
思路1
1.普通栈的push和pop操作都是O(1),但是min()操作为O(n);
2.尝试在每一次push操作时将最小值放在栈顶;但是此时不满足栈的LIFO特点;
3.继续尝试,设置一个minValue,记录当前栈的最小元素,每次push后更新该值,但是一旦该值被pop后,无法在O(1)内得到剩下元素的最小值;
4.继续尝试,可否用空间换取时间?Bingo!设置一个辅助栈,保存栈中当前元素的最小值.每次push,将最小值压栈,每次pop,也将栈顶最小元素出栈,
这样,栈顶元素既是当前元素的最小值.
源代码
/*
 * =====================================================================================
 *
 *       Filename:  MinStack-tmpl.cpp
 *
 *    Description:  Design a stack such that the getMinumun()operation will return the minimum
 *                  of the stack within O(1)time. And the push and pop operation will also run
 *                  in O(1)time.
 *
 *        Version:  1.0
 *        Created:  2011年09月14日 09时09分59秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  XuDingxin (xdxn), xdxn2010@gmail.com
 *        Company:  GUCAS
 *
 * =====================================================================================
 */

#include	<stdlib.h>
#include	<iostream>
#include	<stack>
#include	"assert.h"
using namespace std;

template <class T>
class MinStack
{
    public:
        MinStack(){};
        ~MinStack(){};
        void push(T value);
        T pop();
        T min();

        stack<T> data;
        stack<T> minstack;
};
template <class T>
void MinStack<T>::push(T value)
{
    data.push(value);
    if(minstack.size() == 0){
        minstack.push(value);
    }else{
        T& min = minstack.top();
        if(value >= min){
            minstack.push(min);
        }else{
            minstack.push(value);
        }
    }
}
template <class T>
T MinStack<T>::pop()
{
    assert(data.size()>0);
    assert(minstack.size()>0);
    minstack.pop();
    T top = data.top();
    data.pop();
    return top;
}
template <class T>
T MinStack<T>::min()
{
    assert(data.size()>0);
    assert(minstack.size()>0);
    return minstack.top();
}
/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    MinStack<int> stack;

    stack.push(10);
    stack.push(7);
    stack.push(3);
    stack.push(3);
    stack.push(5);
    stack.push(2);
    stack.push(6);
    cout << stack.min() << endl;
    stack.pop();
    cout << stack.min() << endl;
    stack.pop();
    cout << stack.min() << endl;
    stack.pop();
    cout << stack.min() << endl;
    stack.pop();
    cout << stack.min() << endl;
    stack.pop();
    cout << stack.min() << endl;
    stack.pop();
    cout << stack.min() << endl;
    stack.pop();
    return EXIT_SUCCESS;
}				/* ----------  end of function main  ---------- */

思路二
是否可以不要辅助栈,从而将空间复杂度也降低到O(1)呢?
接着思路一第三步,minValue保存当前最小值,但是栈内元素可以做手脚:
当入栈元素value>=minValue时,直接压栈;
但是当value<minValue时,需要特殊处理,我们将2*value-minValue入栈,
再更新minValue到当前最小值,即value 。
pop()操作也要做相应处理:
当top>=minValue时,说明栈顶元素即是原来压栈元素,直接弹出;
但是当top<minValue时,说明栈顶元素是做过手脚之后的结果,我们需要恢复,
此时minValue值即为原压栈元素,可以直接弹出,但是需要更新minValue=2*value-top
源代码

/*
 * =====================================================================================
 *
 *       Filename:  MinStack-tmpl.cpp
 *
 *    Description:  Without duplicate stack.min(),push(),and pop() are O(1); space is also O(1);
 *
 *        Version:  1.0
 *        Created:  2011年09月14日 09时09分59秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  XuDingxin (xdxn), xdxn2010@gmail.com
 *        Company:  GUCAS
 *
 * =====================================================================================
 */

#include	<stdlib.h>
#include	<iostream>
#include	<stack>
#include	"assert.h"
using namespace std;

template <class T>
class MinStack
{
    public:
        MinStack(){};
        ~MinStack(){};
        void push(T value);
        T pop();
        T min();
        T top();

        stack<T> data;
        T minValue;
};
template <class T>
void MinStack<T>::push(T value)
{
    if(data.size() == 0){
        data.push(value);
        minValue = value;
    }else{
        if(value >= minValue){
            //push the actual value into stack.
            data.push(value);
        }else{
            //update minValue which is the new incomming data.
            //construct a new value_tmp to be pushed.
            T value_tmp = (value - minValue) + value;
            data.push(value_tmp);
            minValue = value;
        }
    }
}
template <class T>
T MinStack<T>::pop()
{
    assert(data.size()>0);
    T top = data.top();
    if(top >= minValue){
        //this is the actual member.
        data.pop();
        return top;
    }else{
        //minValue is the actual pushed data.
        //use top and minValue to restore the next minValue.
        top = minValue;
        minValue = 2*top - data.top();
        data.pop();
        return top;
    }
}
template <class T>
T MinStack<T>::min()
{
    assert(data.size()>0);
    return minValue;
}
template <class T>
T MinStack<T>::top()
{
    return data.top();
}
/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    MinStack<int> stack;

    stack.push(10);
    stack.push(7);
    stack.push(3);
    stack.push(3);
    stack.push(5);
    stack.push(2);
    stack.push(6);

    cout << stack.min() << endl;
    cout << "\ttop:" << stack.top() << endl;
    stack.pop();
    cout << stack.min() << endl;
    cout << "\ttop:" << stack.top() << endl;
    stack.pop();
    cout << stack.min() << endl;
    cout << "\ttop:" << stack.top() << endl;
    stack.pop();
    cout << stack.min() << endl;
    cout << "\ttop:" << stack.top() << endl;
    stack.pop();
    cout << stack.min() << endl;
    cout << "\ttop:" << stack.top() << endl;
    stack.pop();
    cout << stack.min() << endl;
    cout << "\ttop:" << stack.top() << endl;
    stack.pop();
    cout << stack.min() << endl;
    cout << "\ttop:" << stack.top() << endl;
    stack.pop();
    return EXIT_SUCCESS;
}				/* ----------  end of function main  ---------- */

Reference
1.http://zhedahht.blog.163.com/blog/static/25411174200712895228171/
2.http://stackoverflow.com/questions/1377222/min-value-from-stack?answertab=active#tab-top
3.http://stackoverflow.com/questions/685060/design-a-stack-such-that-getminimum-should-be-o1 

Posted in 算法 | Tagged: , | Leave a Comment »

程序员面试题集001

Posted by ieipi 于 九月 10, 2011

题目

将一颗二叉搜索树变成排序的双向链表,要求只改动指针,不创建新的节点。

思路一

    对于二元查找树(Binary Search Tree),其中序遍历的结果即为排序的结果,只需将此结果用双链表表示即可。根据中序遍历的思想,
对于当前节点而言,其左子树已经成功转换,接下来先将当前节点插入链表尾部,再处理其右子树。

伪代码  

1.若当前节点为空,则处理结束,返回.
2.否则:
    2.1递归处理左子树;
    2.2将当前节点加入链表尾部;
    2.3递归处理右子树;

代码

/*
 * =====================================================================================
 *
 *       Filename:  bst2list.cpp
 *
 *    Description:  convert a BST into a sorted double linked list in place.
 *
 *        Version:  1.0
 *        Created:  2011年08月24日 19时54分33秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  XuDingxin (xdxn), xdxn2010@gmail.com
 *        Company:  GUCAS
 *
 * =====================================================================================
 */

#include	<stdlib.h>

#include	<stdio.h>
#include	<iostream>
using namespace std;

struct BSTreeNode
{
    int m_nValue;
    BSTreeNode *m_pLeft;
    BSTreeNode *m_pRight;
};
typedef BSTreeNode DoubleList;
DoubleList *pHead;
DoubleList *pListIndex;

void convertToDoubleList(BSTreeNode *pCurrent);
void addBSTreeNode(BSTreeNode *&pCurrent, int value);

/**
 * @brief add a new node to the current BST.
 *
 * @param pCurrent the root of the current BST.
 * @param value the data element of the new node.
 */
    void
addBSTreeNode (BSTreeNode *&pCurrent, int value  )
{

    if ( NULL == pCurrent ) {
        BSTreeNode *pBSTree = new BSTreeNode();
        pBSTree->m_pLeft = NULL;
        pBSTree->m_pRight = NULL;
        pBSTree->m_nValue = value;
        pCurrent = pBSTree;
    }
    else {
        if ( pCurrent->m_nValue > value ) {
            addBSTreeNode(pCurrent->m_pLeft, value);
        }
        else if(pCurrent->m_nValue < value){
            addBSTreeNode(pCurrent->m_pRight, value);
        }
        else {
            cout << "ignore duplicate node"  << endl;
        }
    }
    return ;
}		/* -----  end of function addBSTreeNode  ----- */

/**
 * @brief traverse the BST in inorder and form the double list accordingly.
 *
 * @param pCurrent the root of the current BST.
 */
    void
ergodicBSTree ( BSTreeNode *pCurrent  )
{
    if(NULL == pCurrent) {
        return;
    }
    if(NULL != pCurrent->m_pLeft){
        ergodicBSTree(pCurrent->m_pLeft);
    }
    convertToDoubleList(pCurrent);
    if(NULL != pCurrent->m_pRight) {
        ergodicBSTree(pCurrent->m_pRight);
    }
    return ;
}		/* -----  end of function ergodicBSTreeeNode  ----- */
/**
 * @brief add the current node into the doulbe list.
 *
 * @param pCurrent. the current node to be converted.
 */
    void
convertToDoubleList (BSTreeNode *pCurrent  )
{
    pCurrent->m_pLeft = pListIndex;
    if(NULL != pListIndex) {
        pListIndex->m_pRight = pCurrent;
    }else {
        pHead = pCurrent;
    }
    pListIndex = pCurrent;
    cout << pCurrent->m_nValue << endl;
    return ;
}		/* -----  end of function converToDoubleList  ----- */
/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    BSTreeNode *pRoot = NULL;
    pHead = NULL;
    pListIndex = NULL;
    addBSTreeNode(pRoot, 10);
    addBSTreeNode(pRoot, 4);
    addBSTreeNode(pRoot, 6);
    addBSTreeNode(pRoot, 8);
    addBSTreeNode(pRoot, 12);
    addBSTreeNode(pRoot, 14);
    addBSTreeNode(pRoot, 15);
    addBSTreeNode(pRoot, 16);
    addBSTreeNode(pRoot, 1);
    addBSTreeNode(pRoot, 18);

    ergodicBSTree(pRoot);

    return EXIT_SUCCESS;
}				/* ----------  end of function main  ---------- */

思路二

上述方法虽然本质上用的是递归,但是硬要跟树的遍历扯上关系,有点含混不清.何不直接用一个纯脆的递归方法呢?

伪代码

BST2Dlist(root):
if root=null
   then return null; #base case:null tree to null list.
   else preList=BST2Dlist(left[root]);
        postList=BST2Dlist(right[root]);
        combine preList, root, and postList to form one double list.

源代码

/*
 * =====================================================================================
 *
 *       Filename:  bst2list-3.cpp
 *
 *    Description:  convert a BST to sorted double list in place.
 *
 *        Version:  1.0
 *        Created:  2011年09月10日 00时41分00秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Xu Dingxin (xdxn), xdxn2010@gmail.com
 *        Company:  GUCAS
 *
 * =====================================================================================
 */

#include        <stdlib.h>

#include        <iostream>
using namespace std;

template <class T>
class Node
{
public:
    T data;
    Node *left;
    Node *right;

    Node(){
        data = 0;
        left = NULL;
        right = NULL;
    }
    Node(T data)
    {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};

/**
 * @brief insert a new element to the BST.
 *
 * @param root reference to root of the BST.
 * @param data data field of the new element.
 *
 * @return
 */
    template <class T>
void TreeInsert(Node<T> *&root, T data)
{
    if(root == NULL){
        root = new Node<T>(data);
    }else{
        if ( data < root->data ) {
            TreeInsert(root->left, data);
        }else{
            TreeInsert(root->right, data);
        }
    }
}

/**
 * @brief traverse the BST in inorder.
 *
 * @param root
 */
template <class T>
    void
InorderTraverse (Node<T> *root)
{

    if ( root == NULL ) {
        return;
    }
    InorderTraverse(root->left);
    cout << root->data << "\t";
    InorderTraverse(root->right);
    return ;
}               /* -----  end of function InorderTraverse  ----- */
/**
 * @brief traverse the BST in preorder.
 *
 * @param root
 */
template <class T>
    void
PreOrderTraverse ( Node<T>* root )
{
    if(root == NULL)
        return;
    cout << root->data << "\t";
    PreOrderTraverse(root->left);
    PreOrderTraverse(root->right);
    return ;
}               /* -----  end of function PreOrderTraverse  ----- */
/**
 * @brief traverse the BST in postorder.
 *
 * @param root
 */
template <class T>
    void
PostOrderTraverse ( Node<T>* root )
{
    if(root == NULL)
        return;
    PostOrderTraverse(root->left);
    PostOrderTraverse(root->right);
    cout << root->data << "\t";
    return ;
}               /* -----  end of function PostOrderTraverse  ----- */
/**
 * @brief convert the BST to a sorted double list.
 *
 * @param root root of BST.
 *
 * @return pointer to the list head.
 */
template <class T>
   Node<T>*
BST2DList ( Node<T>* root )
{
    if(root == NULL)
        return NULL;
    Node<T>* left = BST2DList(root->left);
    Node<T>* right = BST2DList(root->right);

    Node<T>* listHead;
    if(left == NULL) {
        listHead = root;
    }else{
        //append root to the left list.
        listHead = left;
        Node<T>* tmp = listHead;
        while(tmp != NULL && tmp->right != NULL){
            tmp = tmp->right;
        }
        tmp->right = root;
        root->left = tmp;
    }

    if ( right != NULL ) {
        root->right = right;
        right->left = root;
    }
    return listHead;
}               /* -----  end of function BST2DList  ----- */
/**
 * @brief append bNode to aNode.
 *
 * @param aNode
 * @param bNode
 */
template <class T>
    static void
Join ( Node<T>*aNode, Node<T>* bNode )
{
    aNode->right = bNode;
    bNode->left = aNode;
    return ;
}               /* -----  end of function Join  ----- */
/**
 * @brief append bList to aList.
 *
 * @param aList
 * @param bList
 *
 * @return
 */
template <class T>
    static Node<T>*
ListJoin ( Node<T>* aList, Node<T>*bList )
{
    if(aList == NULL)
        return bList;
    if(bList == NULL)
        return aList;

    Node<T>* aLast = aList->left;
    Node<T>* bLast = bList->left;

    //append bList to aLast
    aLast->right = bList;
    bList->left = aLast;

    //link bLast to aList to form a circular list..
    bLast->right = aList;
    aList->left = bLast;
    return aList;
}               /* -----  end of function ListJoin  ----- */
/**
 * @brief convert a BST to a sorted double circular list.
 *
 * @param root
 *
 * @return
 */
template <class T>
    Node<T>*
BST2DCList ( Node<T>* root )
{
    if(root == NULL)
        return NULL;

    char tmp;
    Node<T>* left = BST2DCList(root->left);
    Node<T>* right = BST2DCList(root->right);

    //make the root node length-1 double circular list.
    root->left = root;
    root->right = root;

    //combine the left, root and right sub-list.
    left = ListJoin(left, root);
    left = ListJoin(left, right);
    return left;
}               /* -----  end of function BST2DCList  ----- */
/**
 * @brief print double list.
 *
 * @param list
 */
template <class T>
    void
PrintList ( Node<T>*list )
{
    if(list == NULL)
        return;
    Node<T> *tmp = list;
    while(tmp != NULL) {
        cout << tmp->data << "\t";
        tmp = tmp->right;
    }
    return ;
}               /* -----  end of function PrintList  ----- */
/**
 * @brief print double circular list.
 *
 * @param list
 */
template <class T>
    void
PrintDCList ( Node<T>* list )
{
    if(list == NULL)
        return;
    Node<T>* tmp = list;
    do{
        cout << tmp->data << "\t";
        tmp = tmp->right;
    }while(tmp != list);
    return ;
}               /* -----  end of function PrintDCList  ----- */
/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    Node<int> *root = new Node<int>(10);
    TreeInsert(root, 6);
    TreeInsert(root, 8);
    TreeInsert(root, 4);
    TreeInsert(root, 12);
    TreeInsert(root, 14);
    TreeInsert(root, 16);
    TreeInsert(root, 11);

    InorderTraverse(root);
    cout << endl;
    PreOrderTraverse(root);
    cout << endl;
    PostOrderTraverse(root);
    cout << endl;

    //Node<int>* list = BST2DList(root);
    //cout << "convertion result:" << endl;
    //PrintList(list);
    //cout << endl;

    Node<int>* dclist = BST2DCList(root);
    cout << "convertion result:" << endl;
    PrintDCList(dclist);
    cout << endl;
    return EXIT_SUCCESS;
}                               /* ----------  end of function main  ---------- */


在上述思路二中,提供了两种方法,即转换为普通双链表和带环双链表。
在普通双链表中,每次插入当前链表时需要遍历到链表尾端,耗时O(n);在带环双链表中,可以直接从头结点找到尾结点,耗时为
常数时间。

Reference

1.http://blog.csdn.net/v_JULY_v/article/details/6057286
2.http://cslibrary.stanford.edu/109/TreeListRecursion.html 

Posted in 算法, 技术 | Tagged: , | Leave a Comment »

Contiki Introduction II

Posted by ieipi 于 九月 8, 2011

Posted in 研究 | Tagged: | Leave a Comment »

Contiki Introduction I

Posted by ieipi 于 九月 8, 2011

Posted in 研究 | Tagged: | Leave a Comment »

SVN 使用笔记

Posted by ieipi 于 八月 31, 2011

1.设置svn:ignore 属性

svn会默认监测目录下的所有文件,这样当使用svn status时会遇到很多冗余信息。实际上,有很多文件,比如二进制文件,日志文件等是不需要加入svn 版本控制的。我们可以利用每个目录均有的svn:ignore属性来实现这一目的。
1)  设置.svnignore文件
在当前目录上新建.svnignore文件(文件名可行任意),并在其中编辑需要忽略的文件类型。例如

build/
dist/
*.class

2)  设置svn:ignore属性

svn propset svn:ignore –F .svnignore .

3)  其他
这种方法是局部设置,只对当前目录生效。还可以进行全局设置,对所有的svn workcopy均有效。

sudo vim /etc/subversion/config

找到global-ignores条目,在其后加上需要忽略的文件类型。

2.版本代码回滚

svn 本版库包含所有的历史信息,所以你可以回滚到任意历史版本。所有的修改可以看作是由一系列的修改及集组成。可以利用svn merge命令将一个或一组修改集应用当前工作拷贝。基本工作流程为:
1)    更新工作拷贝

svn update

2)    定位可疑目标

svn log test_rollback
svn diff –r 100:101 test_rollback

3)    撤销错误修改集

svn merge –r 101:100 test_rollback

4)    检查修改结果

svn diff test_rollback

5)    提交

svn commit –m"revert the wrong change from r101"

6)    其他
当提交更改后,r101的更改集已经从HEAD中删除。但是,r101版本仍然在版本库中。当直接从r101版本checkout时仍会得到错误更改。但是通常我们只对HEAD版本感兴趣,所以从HEAD删除已经足够好了。如果想从版本库中毁掉所有证据,并不容易。

Posted in 工具, 技术 | Tagged: | Leave a Comment »

GSoC 2011 is over

Posted by ieipi 于 八月 31, 2011

Google has announced the final evaluation result and the integration work is underway—my GSoC2011 journey with Jitsi has approached to its final period. Now it’s the right time to reminisce about this unique experience.

I can’t forget the moment when I received the email from Google saying that I had been accepted by Jitsi as a GSoC2011 student. The official announcement time is 19:00 UTC April 25, which is 03:00 here in Beijing. I spent all night waiting for the final moment with butterflies in my stomach. When the announcement came, I was even too excited to fall asleep.

After immersed in the excitement for a week, coding period started.

The project is to implement support for wideband codecs, to be specific, SILK, in Jitsi. So why wideband codecs? Thanks to the advancement of Internet access technology, the available bandwidth has increased a lot, and the major concern of VoIP developers has shifted from using less bandwidth to supporting better quality. Imagine the quality of music rather than speech, that’s cool. And then why SILK? Well, to be honest, Skype has done pretty well in the VoIP industry, and they share their main audio codec, SILK, to the open source community. And we are eager to have it in Jitsi.

The main work is to import SILK from C to Java. Sounds very straightforward, right? It may be easy to start, but you may suffer to make it work well. We’ve decided to translate the C code from scratch rather than using JNI technique. There are some important notes to be taken care of in the translation process.1). Pointers. The C programs use pointers intensively. However, there is no pointer in Java. So you should be careful when encounter pointers. Generally speaking, when the pointer is of complex type, e.g. struct, you can use an object reference in Java to translate it. However, when the pointer points an array, you should use an array reference and a data offset in addition. 2). Callbacks. C supports function pointers, which make callbacks flexible and powerful. Again, no pointers in Java, so you should design carefully based on the interface technique to support callbacks.3). Unsigned data types. There is no unsigned data type in Java, so you should be careful when unsigned data is involved in the operation.4). Shift operations. Java has separated operators for logic shift and arithmetic shift operation. 5). Endianness. Java is big endian, and usually the input data is in the format of little-endian. 6).Float point arithmetic. Subtle problems will arise when float point operation is involved.

The coding work was finished nearly in the mid-term, and then came the test. I should say that test really takes time. The test and debugging can easily take more time than you expect. So I think you should always remember to assign more time than you predict for debugging and test. In the first phase, it was not difficult to clear the bugs and made the program run. Though it gave no error messages, the result was not correct. For example, when I played the music which was encoded/decoded by the codec, the last part of the audio was not clear at all. At first, I tried to find the bugs from top down—debug step by step, and compare the intermediate result with that of the C version. But I found it was really difficult to determine whether they match or not when float point arithmetic operation was involved. Since the float point operation result is not exactly the same in Java as in C, when the intermediate result doesn’t match, it’s difficult to judge whether it’s because of a bug or just because of the float point operation itself. After discussion with my mentor Lyubomir, I decided to use another approach—a down-top approach. Get the intermediate result from C, and hard-coded it into Java to test whether there are bugs in the following parts. By this approach, I finally located the bug. It resides in the re-sampler part, and this explains why only part of encoded/decoded audio is incorrect.

Finally, how to test a codec? I think there are basically two methods. The first is to write a script to compare the result with a reference signal to see whether they match with each other. And the second is by hearing. Let the user test it. You play the audio result which is processed by the encoder and decoder and compare with the original sample audio. If it’s clear enough, I think you can say the codec works correctly.

The 3 months passed quickly, but the memory will last. Thank Google, thank Jitsi, and especially thank my mentor Lyubomir. I hope I can continue to work with the community in the future.

Posted in 随笔 | Tagged: | Leave a Comment »