-
-
手机阅读
很多朋友问我：你对新员工在技能上有什么要求呀。
看看下面两个面试题吧，如果能在1小时之内将它们上机编程调试通过，那么，你就是我要找的人了。
死区压缩的算法原理是：
一段按时间顺序从小到大排列的数据，只有前后数据变化的绝对值超过常量COMPRESS_RATE才被保存。
举例（假定COMPRESS_RATE为1.0）：
100 100.5 110 109.9 109.4 108.9 109
结果：100 110 108.9
设数据的结构为：
typedef struct stDataInfo
{
time_t nSecond; // 时间，以秒为单位
short nMill; // 毫秒
double fValue; // 值
} DataInfo;
请编程实现该算法
1、压缩函数
#define COMPRESS_RATE 1.0
int Compress(DataInfo *pDataList, int nDataCount, DataInfo *pResultDataList)
其中：
pDataList为数据列表，已按时间排序
nDataCount为数据个数
pResultDataList为压缩后的数据列表，由调用者申请了空间，最大长度为nDataCount
返回值为压缩后的数据个数
2、压缩后的数据，需要快速查询出来（顺序查找会不会慢了点？）
typedef struct stTimeInfo
{
time_t nSecond; // 时间，以秒为单位
short nMill; // 毫秒
} TimeInfo;
#define RET_SUCCESS 0 // 刚好找到对应的时间点
#define RET_NO_EQUAL 1 // 未找到对应的时间点，但找到两个时间之间的点，需要进行二分插值
#define RET_BEYOND_MIN 2 // 时间比最小时间小
#define RET_BEYOND_MAX 3 // 时间比最大时间大
#define RET_NO_DATA 4 // 数据列表无数据
#define RET_PARAMETER_ERROR 5 // 参数错误
#define COMPRESS_RATE 1.0
int FindDataByTime(DataInfo *pDataList, int nDataCount, TimeInfo *pTime, double *pResultData)
其中：
pDataList为已压缩的数据列表，按时间排序
nDataCount为数据个数
pTime为查询的时间
返回结果：
如果为RET_SUCCESS和RET_NO_EQUAL，pResultData为对应的值
如果为RET_BEYOND_MIN，则pResultData为最小时间点的值
如果为RET_BEYOND_MAX，则pResultData为最大时间点的值
如果为RET_NO_DATA和RET_PARAMETER_ERROR，则为pResultData不需要处理
以上面试题只对程序员有效，你心动了吗？