2015京东校园招聘技术类笔试题

1、

给定字符串(ASCII码0-255)数组,请在不开辟额外空间的情况下删除开始和结尾处的空格,并将中间的多个连续的空格合并成一个。例如:” i am a little boy. “,变成”i am a little boy”,语言不限,但不要用伪代码作答,函数输入输出请参考如下的函数原型:

1
2
3
C++函数原型:
void FormatString(char str[],int len){
}
#include<stdio.h>
#include <string.h>

void FormatString(char str[],int len)
{
    if (str == NULL || len <= 0) {
        return;
    }
    int i = 0;
    int j = 0;
    if (str[i] == ' ') {
        while (str[i] == ' ') {
            ++i;
        }
    }
    while (str[i] != '\0') {
        if (str[i] == ' ' && str[i + 1] == ' ' || str[i + 1] == '\0') {
            ++i;
            continue;
        }
        str[j++] = str[i++];
    }
    str[j] = '\0';
}

int main() {
    char a[] = "   i    am a      little boy.    ";
    int len = strlen(a);
    printf("%d\n",len);
    FormatString(a,len);
    printf("%d\n",strlen(a));
    printf("%s\n",a);
    return 0;
}

2、

给定一颗二叉树,以及其中的两个node(地址均非空),要求给出这两个node的一个公共父节点,使得这个父节点与两个节点的路径之和最小。描述你程序的最坏时间复杂度,并实现具体函数,函数输入输出请参考如下的函数原型:

C++函数原型:
1
2
3
4
5
6
7
strucy TreeNode{
TreeNode* left; //指向左子树
TreeNode* right; //指向右子树
TreeNode* father; //指向父亲节点
};
TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second){
}
int nodeHeight(TreeNode* node)
{
    int height = 0;
    while(node != NULL)
    {
        height++;
        node = node->father;
    }
}
TreeNode* LowestCommonAncestor(TreeNode* first, TreeNode* second)
{
    int diff = nodeHeight(first) - nodeHeight(second);
    if(diff > 0)
    {
        while(diff > 0)
        {
            first = first->father;
            diff--;
        }
    }
    else
    {
        while(diff < 0)
        {
            second = second->father;
            diff++;
        }
    }
    while(first != second)
    {
        first = first->father;
        second = second->father;
    }
    return first;
}

个人资料
bjchenli
等级:8
文章:260篇
访问:22.0w
排名: 3
上一篇: 2015小米校招【安全工程师】网申+笔试真题
下一篇:2014京东招聘面试题-技术类
猜你感兴趣的圈子:
京东笔试面试圈
标签: treenode、str、father、diff、len、面试题
隐藏