远景面试算法题——FolderSize

远景面试算法题——FolderSize

描述

文件被存储在磁盘上的时候，通常为cluster方式。

每个cluster具有固定的大小，一个文件所消耗的空间量始终是cluster大小的整数倍。

因此，如果cluster的大小为100字节，165字节的文件将会使用实际使用200字节的存储空间，造成35个空间的浪费。

一个folder会有多个file，每个file单独计算浪费空间；如果某个folder没有出现，浪费空间为0

定义

Method signature: int[] calculateWaste(String[] files, int folderCount,int clustersize)

输入参数说明：

files为输入的folder编号和对应的file大小的数组。

例如{"0 55","0 47"}，表示为folder 0 下面有两个文件，大小分别为55和47，按空格分隔。

folderCount为所有的folder个数。

当folderCount为3的时候，会有0,1,2三个folder编号，clustersize为固定块大小。

返回值：每个folder对应的浪费空间大小

测试用例

files={"0 55","0 47","1 22","1 21"}。

foldercount=3,clustersize=50

Returns：{48,57,0}

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

解题之前先安利两首歌《安河桥》《七月上》

今天面试之前包夜导致自己两眼昏花，看题目费解到半死（我发四我再也不会包夜了！）。

让20min写出来，后来发现其实并不难。

当然代码是否有误还要斟酌

核心：把字符串转换成数字

int * calculateWaste(string* files,int folderCount,int clustersize){

    int* waste=new int[folderCount];

    int filenum=sizeof(files)/sizeof(files[]);

    int folderid=,filesize=;

    string temp;

    if(files==NULL||folderCount==||clustersize==){

        cout<<"参数错误"<<endl;

        return waste;

    }

    for(int i=;i<filenum;i++){

        temp=files[i];

        int j=;

        while(temp[j]!=' '){   //计算folderID

            folderid=folderid*+temp[j]-'';

            j++;

        }

        j++;   //跳跃空格

        while(j<temp.length()){

            filesize=filesize*+temp[j]-'';

            j++;

        }

        waste[folderid]+=(filesize/clustersize+)*clustersize-filesize;

        folderid=;

        filesize=;  //再次扫描下一个file前清空之前的数据

    }

    return waste;

}

代码如上。

为了面试官看的清楚，我还从新誊写了一份，然而···不说了。

关于这道题和同学讨论了一下：

1.要不要释放内存，事实上，是不用的。

因为返回的内存必然是有用的，你以后要用的，所以不需要释放内存。

当程序运行完毕，系统会为你做这个释放。

那关于动态申请的内存一定要记得释放是用于什么情况呢？在类中，如果你定义一个类，类中有动态申请的内存，在你的析构函数里一定要释放内存。

（不知道我这种观点是否有误？）

2.还有关于string [] files，我用sizeof(files)/sizeof(files[0])这种方法求数组长度是基于每个元素是等长的，那如果string数组不等长了我要怎么求得长度呢？这个时候应该给出【长度参数】

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

面试的时候有些问题我真的没有考虑过，所以答的并不好：

1.为什么考seu，意思是怎么没保研

2.为什么不继续做QA（QA事实上也很难，也要求很高的技术，TDD--Testing Driven Develope）

3.自己写的算法代码一定要将细一点，最好分【多个函数】完成功能

4.BAT投了吗，结果如何（内心OS：这种问题我真的不知道怎么回答啊！！）