2021-09-12 一个华为校招题目

某公司需要在项目中引入某开源工程,需要评估该开源工程中某模块的编译时间,
当前已知该项目中每个模块的编译时间以及依赖模块列表,在拥有无限数量的并行
任务情况下,求某个指定模块的最短编译时间。
若模块间存在循环依赖或依赖模块不存在,则无法完成编译,返回-1;

输入描述:
第一行输入为目标模块名;
以后每一行输入定义一个模块,包含模块的名字,编译时间,依赖模块列表,用逗号隔开,若依赖模块列表不存在,则表示可以独立编译,例如:

module2,10,module1
module1,10

模块名只包含字母和数字且至少包含一个字符,模块数量不超过50000个。

输出描述:
输出最短编译时间,若无法完成编译则输出-1;

例如:输入
module3
module1,10
module2,5
module3,10,module1,module2

输出:
20

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct module_t
{
    char name[255];
    int  time;
    int  isCompiled;
    struct module_t *next;
    struct module_t *depends;
}module_t;

int parseInput( module_t **mds, char * buf , char* modName )
{
    int state = 0;
    module_t * md = (module_t*)malloc(sizeof(module_t));
    md->next = md->depends = NULL;
    md->isCompiled = 0;
    char *p = strtok(buf,",");
    while( p )
    {
        switch( state )
        {
        case 0 :
            //此处应该校验模块名是否合法
            strcpy(md->name , p );
            state++;
            break;
        case 1:
            md->time = atoi(p);
            state++;
            break;
        default:
            {
                //此处应该校验模块名是否合法

                module_t* dp = (module_t*)malloc( sizeof(module_t));
                dp->next = dp->depends = NULL;
                strcpy(dp->name,p);
                module_t **pp = &md;
                for( module_t *prev = *pp ; prev!=NULL;prev = *pp )
                {
                    pp=&prev->depends;
                }
                dp->depends = *pp;
                *pp = dp;
            }
            break;
        }
        p=strtok(NULL,",");
    }

    if (*mds==NULL)
        *mds = md;
    else {
        md->next = *mds;
        *mds = md;
    }
    if (strcmp(md->name,modName) == 0 )
        return 2;
    return 1;
}


int calculateCompileTime( module_t *mds , module_t *md ,char *lastModName,int *nextTime)
{
    int time = 0;
    int found = 0;
    module_t *depends = md->depends;

    time=md->time;

    while (depends !=NULL) {
        //循环依赖
        if ( strcmp(lastModName,depends->name) == 0 )
        {
            printf("-1\n");
            exit(-1);
        }
        module_t *next = mds;
        while( next != NULL )
        {
            if ( strcmp(next->name , depends->name ) ==  0 )
            {
                //?并行任务中只计算未编译过的模块和编译时间长的模块
                if ( next->time >= *nextTime && next->isCompiled == 0 )
                {
                    time+=calculateCompileTime(mds,next,md->name,nextTime);
                    *nextTime = next->time;
                    next->isCompiled = 1;
                }
                found = 1;
            }
            next = next->next;
        }
        if ( found == 0 )
        {
            printf("-1\n");
            exit(-1);
        }
        depends = depends->depends;
    }
    return time;
}


int main()
{
    char modName[255];
    char inbuf[1024];
    module_t *modList = NULL;;
    int state = 0;
    do
    {
       scanf("%s",inbuf);
       if ( state == 0 )
       {
           strcpy(modName,inbuf);
           state++;
       }
       else if ( parseInput(&modList,inbuf,modName)==2 )
       {
           int nextTime = modList->time;
           printf("%d\n",calculateCompileTime(modList,modList,modList->name,&nextTime));
           break;
       }else if ( state > 50000 )
       {
           printf("You're fucking typing too much!!!\n");
           break;
       }
    }while(1);


    while (modList!=NULL )
    {
        module_t *next = modList->next;

        while(modList->depends!=NULL)
        {
            module_t *pp = modList->depends->depends;
            free(modList->depends);
            modList->depends = pp;
        }
        free(modList);
        modList = next;
    }

    return 0;
}

上一篇:全局安装i5ting_toc 包


下一篇:全局安装i5ting_toc 包