[facebook实习面试题目]f intern interview review, second round

(45 minutes - 5 minutes chatting), 2 problems.

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

(n) time complexity o(1) space

怎么第二轮比第一轮简单这么多

第二题不会做。。。想了好久才想出来

void _inner_print(char* strOrg, char* strStart, int nLen)
{
        assert(strStart && nLen >= 0);

        if (0 == nLen)
        {
                cout<<strOrg<<endl;
                return;
        }

        char rec[256];
        memset(rec, 0, sizeof(rec)*sizeof(char));
       
        rec[*strStart]++;
        _inner_print(strOrg, strStart + 1, nLen - 1);
        for (int i = 1; i < nLen; i++)
        {
                if (rec[*(strStart + i)] != 0)
                        continue;

                rec[*(strStart + i)]++;

                swap(*strStart, *(strStart + i));
                _inner_print(strOrg, strStart + 1, nLen - 1);
                swap(*(strStart + i), *strStart);
        }
}

void PrintPerpetuation(char* str)
{
        assert(str);

        int nLen = strlen(str);
        _inner_print(str, str, nLen);
}

void test()
{
        char str[] = "abbcb";
        PrintPerpetuation(str);
}


15 min

证明 : 应为对于任何一个字符串来说, 他的下一步递归一定返回所有子串的全排列, 所以对于n个字符的字符串只需要保证被exclude的那个唯一即可

第二题不会做。。。想了好久才想出来
Imbalism 发表于 2011-10-15 02:58

    什么叫longest path?? 是经过根节点的那条吗??

回复 6# wwwyhx


     不是。。。任意的，careercup 里面有 答案 ，但是他说不能用那种方法

第二题不会做。。。想了好久才想出来
Imbalism 发表于 2011-10-15 02:58

    做后续遍历的递归, 对每个节点可以记录左子树的最大高度和右子树的最大高度, 当递归track back的时候可以得到对每个node做为turning point的时候得最大path, O(n)时间 O(1)空间

记录的高度存哪里？

记录的高度存哪里？
Imbalism 发表于 2011-10-15 03:28

    struct NODE
{
        NODE* pLft;
        NODE* pRgt;

        NODE() : pLft(NULL), pRgt(NULL) {}
};

int FindLongestPath(NODE* pRoot);

//Return Height
int _inner_find(NODE* pNode, int& nMaxPath)
{
        if (NULL == pNode)
                return 0;

        int nRet = 1;
        int nLft = _inner_find(pNode->pLft, nMaxPath);
        int nRgt = _inner_find(pNode->pRgt, nMaxPath);

        int nNew = 1 + nLft + nRgt;
        nMaxPath = nNew > nMaxPath ? nNew : nMaxPath;

        return 1 + nLft > nRgt ? nLft : nRgt;
}

int FindLongestPath(NODE* pRoot)
{
        assert(pRoot);

        int nMax = -1;
        _inner_find(pRoot, nMax);

        return nMax;
}