请教面试中的数据结构的设计题。

http://www.mitbbs.com/article_t/JobHunting/33170015.html

发信人: zizhu (windy), 信区: JobHunting
标  题: 请教面试中的数据结构的设计题。
发信站: BBS 未名空间站 (Tue Apr 12 14:00:36 2016, 美东)

面试中遇到的数据结构设计题，请教有没有更好的办法。还有最后一问没有打上来，请
教如何设计最后一题。

问题： 有很多不同型号的汽车要测试，每分钟采集一个数据，比如实时的MPG(假设都
是整数), 数据格式如下：["car1", 19], ["car2" 22], ["car3" 21]...

1. 问： 设计一个数据结构来存储每个车最新的数据
答： unordered_map<string/*车*/， int/*MPG*/ >

2. 问： 如何改进来存一天的数据， 并且支持返回某时间段的MPG值，比如get("car1"
, 12：00，13：00）

答： unordered_map 加 map， 如unordered_map< string/*car name*/, map<int/*
time stamp*/, int/*MPG data*/> >.

map 是排好序的，用lower_bound，和upper_bound找出时间的区间返回值

3. 如果需要找出N个车，它们的平均MPG最高。如何改进已有的数据结构。

我给出的答案是multimap<int /*average MPG*/, string/*car*/>, 因为不同车的
average mpg可能一样。但是他强调用我前面提出的已有的数据结构改进。

然后我就不知道了。请教如何做.多谢！