我写故我在

I write, therefore I am

Posts Tagged ‘Interview’

程序员面试题集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 »