请教面试中的数据结构的设计题。 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

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

请教面试中的数据结构的设计题。# JobHunting - 待字闺中

z*u2016-04-12 07:04

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*/, maptime stamp*/, int/*MPG data*/> >.
map 是排好序的，用lower_bound，和upper_bound找出时间的区间返回值
3. 如果需要找出N个车，它们的平均MPG最高。如何改进已有的数据结构。
我给出的答案是multimap, 因为不同车的
average mpg可能一样。但是他强调用我前面提出的已有的数据结构改进。
然后我就不知道了。请教如何做.多谢！

j*o2016-04-12 07:04

2 楼

加个新的变量，每次MPG进来的时候更新下

z*u2016-04-12 07:04

3 楼

但是如果有很多很多车，只要找出平均MPG最高的比如说5辆车名字，如何利用已有的数
据结构做呢?

【在 j******o 的大作中提到】

: 加个新的变量，每次MPG进来的时候更新下

j*h2016-04-12 07:04

4 楼

要求最高最低的X个什么东西，一般都是用heap来做

k*n2016-04-12 07:04

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*r2016-04-12 07:04

6 楼

不可能的，除非小项目，
不然必然是数据库，推数据到cache层，
然后再读出来放内存里，不然慢死。

【在 k**n 的大作中提到】

: 这种需求实际上是用数据库吧...我第一反应是建表..query, group by..
:
: car1"

i*e2016-04-12 07:04

7 楼

为了能更好地回答这种问题，是刷题有用？还是参加类似下面的，通过做实际项目
来提高更有用？
http://www.mitbbs.com/article/JobHunting/32988555_0.html

car1"

【在 z***u 的大作中提到】

z*u2016-04-12 07:04

8 楼

忘了说了，数据结构要用STL实现。。。

【在 p**r 的大作中提到】

: 不可能的，除非小项目，
: 不然必然是数据库，推数据到cache层，
: 然后再读出来放内存里，不然慢死。

z*u2016-04-12 07:04

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*i2016-04-12 07:04

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*u2016-04-12 07:04

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*g2016-04-12 07:04

12 楼

那用vector + make_heap来搞怎么样？

【在 z***u 的大作中提到】

: priority queue如何更新数据呢？比如说同一个dealer有了新的buy/sell price，要找
: 到并且替换该dealer的老的报价，否则很可能还是在用老
: 的报价在比较。
: 如何在priority queue里找到这个dealer可能会有问题吧？
:
: on

r*e2016-04-12 07:04

13 楼

如果需求只要最好的一个，为什么不可以在收到quote时直接算好。例如用2个map，一
个是best sell，一个是best buy。key是型号，value是dealer加价格。quote 进来时
直接和map里的比较就像，最好的就更新,不是就忽略。