gpt4 book ai didi

algorithm - 找出交易量最高的十大公司

转载 作者:行者123 更新时间:2023-12-02 15:15:44 26 4
gpt4 key购买 nike

我一直在处理玻璃门的问题,这是我应该去的公司在一次公司采访中提出的问题。问题是:


如果您拥有所有要交易的公司,并且实时输入正在交易的公司,以及交易量是多少,那么如何维护数据,以便您可以进行以下操作:最有效的股票交易量


我想到了相同的以下解决方案。尽管我不确定这是否有效:您如何维护二叉搜索树。在每次插入时,都插入公司名称和交易量。

我的树的基本节点将是:

class Node
{
String key; // company name
int volume; // volume
Node leftNode;
Node rightNode;
}


因此,在每次新插入时,我都会继续插入树中。在最终检索时,我可以运行以下代码,直到全局计数的计数达到10。

traversal(Node a)
{
if(a!=null)
{
traverse(a.getRightNode());
System.out.println(a.getKey()+a.getValue());
traverse(a.getLeftNode());
}
}


您对此解决方案有何看法?

最佳答案

这个问题与另一个question非常相似,但几乎没有任何转折。首先,如果有人问我这个问题,我会问很多问题。我事先知道公司名称吗?公司数目是多少?他们的人数上限吗?您是指时间效率或内存消耗效率,还是两者兼而有之?交易与顶级公司要求的比率是多少?它没有指定,但我将承担大量交易并按需或在一定时间间隔内显示前10名。如果在每次交易到达堆之后请求前10名,即使N大于10,也将毫无用处,整个算法可能会更简单。我还假设时间效率。然后,内存效率受到CPU缓存行为的限制,因此我们无论如何都不要浪费它。

因此,我们将top N存储在某种结构中,这将使我的成员人数最少。这显然是用于大N堆。我可以使用任何堆实现,即使那些IncKeyMerge操作不正确或根本不执行的操作也是如此。我只需要InsertPeekRemove操作。数字10很小,我什至不需要堆,特别是在具有良好编译器的编译语言中。我可以使用有序数组或列表,甚至可以使用无序数组。因此,在我将提到堆波纹管的每个地方,都可以使用有序或无序数组或列表。只有顶部N中的较大N才需要堆。

就是这样,我们将存储排名前列的N公司name,并且将其放入堆中时为volume

然后,我们需要在一些K / V存储中跟踪公司贸易volume。密钥是name。为此,K / V存储可以是hashmap,trie或Judy。如果我们提前知道公司名称,那将会很好。这将使我们能够为hashmap计算完美的哈希或构造最优的trie。否则,如果我们知道公司的上限,那就太好了;否则,请选择合适的哈希长度和存储桶数。否则,我们将不得不进行可调整大小的哈希或使用Judy。没有什么比散列图或Judy更好的动态K / V实现了。所有这些K / V存储都具有O(k)访问复杂性,其中k是密钥的长度,在这种情况下为name。在每个我将在下面提到哈希图的地方,都可以使用Judy或trie。只有在事先知道所有公司名称的情况下,才能使用trie,并且可以定制超快速优化的代码。

因此,我们将存储公司name作为键,并交易volume到目前为止,而flag指示存储在哈希图中的堆中。

所以这里有算法。我们将具有包含堆,堆中的公司数和哈希图的状态。对于每个到达的公司manevolume,我们将在哈希图中增加volume。然后,如果堆中的公司少于N(10),我们将从哈希表中将此公司namevolume添加到堆中(如果尚不存在)(根据在哈希图中的标记和设置此标志)。否则,如果堆满了并且当前公司不在堆中,我们将窥视堆,并且如果当前公司(在哈希图中)交易的volume少于堆中公司,则我们可以完成此交易并继续下一步。否则,我们必须先更新堆中的公司。虽然位于堆顶部的公司(这意味着volume最少)的堆中的volume小于当前堆中的volume,并且与哈希映射中的值也不同,但我们将更新此volume。可以通过从堆中删除并插入正确的值来完成。然后再次检查堆的顶部,依此类推。注意,我们不需要更新堆中的所有公司,甚至不需要更新所有不是最新的顶级堆公司。很懒。如果当前公司的N仍大于堆顶部,则我们将从堆中删除公司,并插入当前公司并更新哈希映射中的标志。仅此而已。

简要概述:


最小堆存储由volume排序并包含公司name的前volume个公司,或直接索引到哈希图中
堆中的name可能已过期
以公司volume为键和最新的volume以及代表堆成员为值的标志的哈希图
首先在哈希图中更新当前公司volume并记住
如果少于当前交易的公司,则反复更新堆顶
如果仍然少于当前公司,则删除堆顶部,并在堆中添加当前堆顶部


该算法的优势在于,交易volume只能为正数,因此堆中的IncKey只能小于正确的值,并且如果堆的顶部具有所有堆中的最小值,并且仍然小于正确的值并且仍然大于任何正值hasmap中的公司一切都很完美。否则,我们将必须将所有公司存储在堆中,使用最大堆而不是最小堆,实现O(1)并针对所有交易执行此操作,并在哈希图中保留对堆的反向引用,这将使事情变得更加复杂。

O(1)处理新的交易时间复杂度很好。 O(1)是哈希映射查找,Peek是堆中的Insert。堆中的DeleteO(logN)被摊销为O(1)或N,其中O(1)是常量,因此仍然O(N)。堆中的更新数为O(1),因此为N。当公司数目有上限(开头提到的哈希图大小问题)时,您还可以计算处理时间的上限,因此,如果实施良好,则可以实时考虑。请记住,更简单的解决方案(按有序列表或无序列表,更新所有Top成员等)可以在较小的 为10的编译代码中带来更好的性能,尤其是在现代硬件上。

即使没有函数式哈希表,该算法也可以很好地实现,除非没有纯函数哈希表,但是trie应该具有O(1)行为,或者为此存在一些不纯净的模块。例如,使用排序列表作为堆和哈希表字典的Erlang实现。 (我最喜欢的功能堆是配对堆,但对于10个而言,这是过大了。)

-module(top10trade).

-record(top10, {
n = 0,
heap = [],
map = dict:new()
}).

-define(N, 10).

-export([new/0, trade/2, top/1, apply_list/2]).

new() ->
#top10{}.

trade({Name, Volume}, #top10{n = N, map = Map} = State)
% heap is not full
when N < ?N ->
case dict:find(Name, Map) of
% it's already in heap so update hashmap only
{ok, {V, true}} ->
State#top10{map = dict:store(Name, {V+Volume, true}, Map)};
% otherwise insert to heap
error ->
State#top10{
n = N+1,
heap = insert({Volume, Name}, State#top10.heap),
map = dict:store(Name, {Volume, true}, Map)
}
end;

% heap is full
trade({Name, Volume}, #top10{n = ?N, map = Map} = State) ->
% look-up in hashmap
{NewVolume, InHeap} = NewVal = case dict:find(Name, Map) of
{ok, {V, In}} -> {V+Volume, In};
error -> {Volume, false}
end,
if InHeap ->
State#top10{map = dict:store(Name, NewVal, Map)};
true -> % current company is not in heap so peek in heap and try update
update(NewVolume, Name, peek(State#top10.heap), State)
end.

update(Volume, Name, {TopVal, _}, #top10{map = Map} = State)
% Current Volume is smaller than heap Top so store only in hashmap
when Volume < TopVal ->
State#top10{map = dict:store(Name, {Volume, flase}, Map)};
update(Volume, Name, {TopVal, TopName}, #top10{heap = Heap, map = Map} = State) ->
case dict:fetch(TopName, Map) of
% heap top is up-to-date and still less than current
{TopVal, true} ->
State#top10{
% store current to heap
heap = insert({Volume, Name}, delete(Heap)),
map = dict:store( % update current and former heap top records in hashmap
Name, {Volume, true},
dict:store(TopName, {TopVal, false}, Map)
)
};
% heap needs update
{NewVal, true} ->
NewHeap = insert({NewVal, TopName}, delete(Heap)),
update(Volume, Name, peek(NewHeap), State#top10{heap = NewHeap})
end.

top(#top10{heap = Heap, map = Map}) ->
% fetch up-to-date volumes from hashmap
% (in impure language updating heap would be nice)
[ {Name, element(1, dict:fetch(Name, Map))}
|| {_, Name} <- lists:reverse(to_list(Heap)) ].

apply_list(L, State) ->
lists:foldl(fun apply/2, State, L).

apply(top, State) ->
io:format("Top 10: ~p~n", [top(State)]),
State;
apply({_, _} = T, State) ->
trade(T, State).

%%%% Heap as ordered list

insert(X, []) -> [X];
insert(X, [H|_] = L) when X < H -> [X|L];
insert(X, [H|T]) -> [H|insert(X, T)].

-compile({inline, [delete/1, peek/1, to_list/1]}).

delete(L) -> tl(L).

peek(L) -> hd(L).

to_list(L) -> L.


每秒执行60万笔交易。我期望每秒C实施数百万,具体取决于公司的数量。更多的公司意味着K / V查找和更新速度变慢。

关于algorithm - 找出交易量最高的十大公司,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20213589/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com