z***u
发帖数: 105 | 1 面试中遇到的数据结构设计题，请教有没有更好的办法。还有最后一问没有打上来，请
教如何设计最后一题。
问题： 有很多不同型号的汽车要测试，每分钟采集一个数据，比如实时的MPG(假设都
是整数), 数据格式如下：["car1", 19], ["car2" 22], ["car3" 21]...
1. 问： 设计一个数据结构来存储每个车最新的数据
答： unordered_map
2. 问： 如何改进来存一天的数据， 并且支持返回某时间段的MPG值，比如get("car1"
, 12：00，13：00）
答： unordered_map 加 map， 如unordered_map< string/*car name*/, map
time stamp*/, int/*MPG data*/> >.
map 是排好序的，用lower_bound，和upper_bound找出时间的区间返回值
3. 如果需要找出N个车，它们的平均MPG最高。如何改进已有的数据结构。
我给出的答案是multimap, 因为不同车的
average mpg可能一样。但是他强调用我前面提出的已有的数据结构改进。
然后我就不知道了。请教如何做.多谢！ |
j******o
发帖数: 4219 | |
z***u
发帖数: 105 | 3 但是如果有很多很多车，只要找出平均MPG最高的比如说5辆车名字，如何利用已有的数
据结构做呢?
【在 j******o 的大作中提到】
: 加个新的变量，每次MPG进来的时候更新下
|
j*********h
发帖数: 1 | 4 要求最高最低的X个什么东西，一般都是用heap来做 |
k**n
发帖数: 3989 | 5 这种需求实际上是用数据库吧...我第一反应是建表..query, group by..
car1"
【在 z***u 的大作中提到】
: 面试中遇到的数据结构设计题，请教有没有更好的办法。还有最后一问没有打上来，请
: 教如何设计最后一题。
: 问题： 有很多不同型号的汽车要测试，每分钟采集一个数据，比如实时的MPG(假设都
: 是整数), 数据格式如下：["car1", 19], ["car2" 22], ["car3" 21]...
: 1. 问： 设计一个数据结构来存储每个车最新的数据
: 答： unordered_map
: 2. 问： 如何改进来存一天的数据， 并且支持返回某时间段的MPG值，比如get("car1"
: , 12：00，13：00）
: 答： unordered_map 加 map， 如unordered_map< string/*car name*/, map: time stamp*/, int/*MPG data*/> >.
|
p**r
发帖数: 5853 | 6 不可能的，除非小项目，
不然必然是数据库，推数据到cache层，
然后再读出来放内存里，不然慢死。
【在 k**n 的大作中提到】
: 这种需求实际上是用数据库吧...我第一反应是建表..query, group by..
:
: car1"
|
i*****e
发帖数: 218 | 7 为了能更好地回答这种问题， 是刷题有用 ？ 还是参加类似下面的，通过做实际项目
来提高更有用 ？
http://www.mitbbs.com/article/JobHunting/32988555_0.html
car1"
【在 z***u 的大作中提到】
: 面试中遇到的数据结构设计题，请教有没有更好的办法。还有最后一问没有打上来，请
: 教如何设计最后一题。
: 问题： 有很多不同型号的汽车要测试，每分钟采集一个数据，比如实时的MPG(假设都
: 是整数), 数据格式如下：["car1", 19], ["car2" 22], ["car3" 21]...
: 1. 问： 设计一个数据结构来存储每个车最新的数据
: 答： unordered_map
: 2. 问： 如何改进来存一天的数据， 并且支持返回某时间段的MPG值，比如get("car1"
: , 12：00，13：00）
: 答： unordered_map 加 map， 如unordered_map< string/*car name*/, map: time stamp*/, int/*MPG data*/> >.
|
z***u
发帖数: 105 | 8 忘了说了，数据结构要用STL实现。。。
【在 p**r 的大作中提到】
: 不可能的，除非小项目，
: 不然必然是数据库，推数据到cache层，
: 然后再读出来放内存里，不然慢死。
|
z***u
发帖数: 105 | 9 接着人气再问一道设计题吧。这个算答出来了。但是总觉的太复杂，请教更好的办法。
题目：
系统接收从全国的旧汽车dealer来的实时Quote，Quote 格式如下
timestamp | model | dealer | buy rate | sell rate
timestamp is a unique integer;
model is a string;
dealer: string
Buy rate: a floating point number。Dealer 愿意买进的价格
Sell rate: floating point number. Dealer 愿意卖出的价格
数据大小：
1. 车行个数在100个左右
2. 车型在100个左右
3. 实时数据是每天千万级别的。
要求：
用STL设计一个数据结构实现，给定车型，查询最好的价格。最好的价格包含: 1.best
buy rate (largest) 2. best sell rate(smallest).
例子：
1.
Input:
1| Model1 | Dealer1 | 1.1 | 1.2
Output:
Best Model1 Buy = 1.1 from Dealer1
Best Model1 Sell = 1.2 from Dealer1
2.
Input:
1| Model1 | Dealer1 | 1.1 | 1.2
1| Model1 | Dealer2 | 1.1 | 1.15
Output:
Best Model1 Buy = 1.1 from Dealer1
Best Model1 Sell = 1.2 from Dealer1
Best Model1 Buy = 1.1 from Dealer1 //如果价格一样，用原来的dealer
Best Model1 Sell = 1.15 from Dealer2
我给出的答案是：
1.第一个
hashmap1
用model名字查询数据
2.第二个hashmap2
3. multimap1
4. multimap2
// unordered_map unordered_map
// ____________
// |____________| ____________
// | |----|____________|
// |model | | dealer |---Quote
// | | |____________|
// | |
// | | __MultiMap______
// | |---| SellRate|Quote |
// | | |_________|______|
// | |
// | | __MultiMap_____
// | |---| BuyRate|Quote |
// |____________| |________|______|
// |____________| |
M******i
发帖数: 468 | 10 这么复杂？ 如果用priority queue，是不是更好？
class CarInfo {
string model;
string dealer;
time t;
float buy;
float sell;
};
priority_queue(string/*car model*/, vector, compare_func(/*based on
buy and sell price*/) |
z***u
发帖数: 105 | 11 priority queue如何更新数据呢？比如说同一个dealer有了新的buy/sell price，要找
到并且替换该dealer的老的报价，否则很可能还是在用老
的报价在比较。
如何在priority queue里找到这个dealer可能会有问题吧？
on
【在 M******i 的大作中提到】
: 这么复杂？ 如果用priority queue，是不是更好？
: class CarInfo {
: string model;
: string dealer;
: time t;
: float buy;
: float sell;
: };
: priority_queue(string/*car model*/, vector, compare_func(/*based on
: buy and sell price*/)
|
k***g
发帖数: 166 | 12 那用vector + make_heap来搞怎么样？
【在 z***u 的大作中提到】
: priority queue如何更新数据呢？比如说同一个dealer有了新的buy/sell price，要找
: 到并且替换该dealer的老的报价，否则很可能还是在用老
: 的报价在比较。
: 如何在priority queue里找到这个dealer可能会有问题吧？
:
: on
|
r****e
发帖数: 10 | 13 如果需求只要最好的一个，为什么不可以在收到quote时直接算好。例如用2个map，一
个是best sell，一个是best buy。key是型号，value是dealer加价格。quote 进来时
直接和map里的比较就像，最好的就更新,不是就忽略。 |
