单程飞行旅行的问题

您将进行单程间接飞行，其中包括数十亿 未知的非常大量的转移。

• 你不是在同一个机场停留两次。
• 你的旅行的每一部分都有1张票。
• 每张票包含src和dst机场。
• 所有的门票都是随机排列的。
• 你忘了原始的离港机场（第一个src）和你的目的地（最后一个dst）。

devise一个algorithm，以最小的复杂度重构您的旅程。

---

试图解决这个问题，我已经开始使用两套对称的差异 ，Srcs和Dsts：

1）对数组Srcs中的所有src键进行sorting
2）对数组Dst中的所有dst键进行sorting
3）创build一个两个数组的联合集，以find不重复的 – 他们是你的第一个src和最后一个dst
4）现在，有了起点，使用二进制search遍历两个数组。

但是我想应该有另一种更有效的方法。

Answer 1

构build一个散列表并将每个机场添加到散列表中。

<key,value> = <airport, count>

如果机场是源头或目的地，则计算机场增加。 所以对于每个机场来说，除了旅行的来源和目的地之外，每个机场的计数将是2（src为1，dst为1），计数为1。

你需要至less看一次票。 所以复杂度是O（n）。

Answer 2

总结：下面给出一个单通algorithm 。 （也就是说，不仅是线性的，而且每张票只看一次，这当然是每张票的最佳访问次数）。 我把这个总结，因为有很多看似相同的解决scheme，很难find我为什么添加另一个。 🙂

其实我是在接受采访的时候问过这个问题的。 这个概念非常简单：每张票都是一个单独的列表，从概念上来说有两个元素src和dst。

我们使用它的第一个和最后一个元素作为关键字将每个这样的列表编入一个散列表，所以我们可以在O（1）中find一个列表是以某个元素（机场）开始还是结束。 对于每张票，当我们看到它开始于另一个列表结束时，只需链接列表（O（1））。 同样，如果它结束在另一个列表开始，另一个列表join。 当然，当我们把两个链接关联起来的时候，我们基本上就把这两个链接摧毁了。 （N张门票链将在N-1个这样的链接之后build造）。

需要注意保持散列表键不变的恒定性，即散列表键恰好是剩余列表的第一个和最后一个元素。

总而言之，O（N）。

是的，我当场回答:)

编辑忘了添加重要的一点。 每个人都提到了两个哈希表，但是也有一个技巧，因为algorithm不变包括最多一张票单开始或开始于任何一个城市（如果有两个，我们立即join该城市的列表，并删除该城市从散列表）。 渐近地没有区别，这只是简单的。

编辑2另外有意思的是，与使用每个有N个条目的2个哈希表的解决scheme相比，这个解决scheme使用了一个至多具有 N / 2个条目的哈希表（如果我们看到按照例如第一，第三，第五，等等）。 所以这也使用了大约一半的内存，除了更快。

Answer 3

构build两个哈希表（或尝试），其中一个在src上键入，另一个在dst上键入。 随机select一张票，在src-hash表中查找它的dst。 重复这个过程的结果，直到你到达目的地（最终目的地）。 现在在dst-keyed哈希表中查找它的src。 重复结果的过程，直到你开始。

构造哈希表需要O（n），构造列表需要O（n），所以整个algorithm是O（n）。

编辑：你只需要构build一个哈希表，实际上。 假设你构造了src-keyed哈希表。 随机select一张票和之前一样，构build通往最终目的地的列表。 然后从票证中select尚未添加到列表中的另一个随机票证。 跟随它的目的地，直到你打到最初开始的票。 重复这个过程直到你构build完整的列表。 它仍然是O（n），因为最糟糕的情况是你以相反的顺序select票据。

编辑：得到了我的algorithm交换的表名。

Answer 4

它基本上是一个依赖关系图，其中每张票都代表一个节点，而src和dst机场代表定向链接，因此使用拓扑sorting来确定航class顺序。

编辑：虽然因为这是一张机票，你知道你实际上做了一个行程，你可以在物理上执行，按UTC出发date和时间sorting。

编辑2：假设每个机场你有一个票使用三个字符的代码，你可以使用这里描述的algorithm（ find三个数字只出现一次 ），以确定两个独特的机场，所有的机场合在一起。

编辑3：这是一些C ++实际上使用异或方法解决这个问题。 整体algorithm如下，假设从机场到整数的唯一编码（假定三个字母的机场代码或使用经度和纬度对机场位置进行整数编码）：

首先，把所有的机场代码都放在一起。 这应该等于最初的来源机场XOR最终的目的地机场。 既然我们知道最初的机场和最后的机场是独一无二的，这个数值不应该是零。 由于它不是零，所以在该值中至less有一个位被设置。 这个位对应于在其中一个机场中设置的位，而不是在另一个机位中设置; 称它为指定位。

接下来，设置两个桶，每个桶都有第一步的XOR值。 现在，每张机票，根据是否有指定位设置，每个机场分别存储一个机场代码和机场代码。 还要跟踪每个桶有多less个源机场和目的地机场去了那个桶。

处理完所有票据后，select其中一个存储桶。 发送到该存储桶的源机场数量应该比发往该存储桶的目标机场数量多一个或less一个。 如果源机场的数量less于目的机场的数量，那就意味着最初的源机场（唯一的唯一源机场）被送到了另一个机场。 这意味着当前桶中的值是初始源机场的标识符！ 相反，如果目的地机场的数量less于源机场的数量，则最终的目的地机场被发送到另一个存储区，所以当前的存储区是最终目的地机场的标识符！

 struct ticket { int src; int dst; }; int get_airport_bucket_index( int airport_code, int discriminating_bit) { return (airport_code & discriminating_bit)==discriminating_bit ? 1 : 0; } void find_trip_endpoints(const ticket *tickets, size_t ticket_count, int *out_src, int *out_dst) { int xor_residual= 0; for (const ticket *current_ticket= tickets, *end_ticket= tickets + ticket_count; current_ticket!=end_ticket; ++current_ticket) { xor_residual^= current_ticket->src; xor_residual^= current_ticket->dst; } // now xor_residual will be equal to the starting airport xor ending airport // since starting airport!=ending airport, they have at least one bit that is not in common // int discriminating_bit= xor_residual & (-xor_residual); assert(discriminating_bit!=0); int airport_codes[2]= { xor_residual, xor_residual }; int src_count[2]= { 0, 0 }; int dst_count[2]= { 0, 0 }; for (const ticket *current_ticket= tickets, *end_ticket= tickets + ticket_count; current_ticket!=end_ticket; ++current_ticket) { int src_index= get_airport_bucket_index(current_ticket->src, discriminating_bit); airport_codes[src_index]^= current_ticket->src; src_count[src_index]+= 1; int dst_index= get_airport_bucket_index(current_ticket->dst, discriminating_bit); airport_codes[dst_index]^= current_ticket->dst; dst_count[dst_index]+= 1; } assert((airport_codes[0]^airport_codes[1])==xor_residual); assert(abs(src_count[0]-dst_count[0])==1); // all airports with the bit set/unset will be accounted for as well as either the source or destination assert(abs(src_count[1]-dst_count[1])==1); assert((src_count[0]-dst_count[0])==-(src_count[1]-dst_count[1])); int src_index= src_count[0]-dst_count[0]<0 ? 0 : 1; // if src < dst, that means we put more dst into the source bucket than dst, which means the initial source went into the other bucket, which means it should be equal to this bucket! assert(get_airport_bucket_index(airport_codes[src_index], discriminating_bit)!=src_index); *out_src= airport_codes[src_index]; *out_dst= airport_codes[!src_index]; return; } int main() { ticket test0[]= { { 1, 2 } }; ticket test1[]= { { 1, 2 }, { 2, 3 } }; ticket test2[]= { { 1, 2 }, { 2, 3 }, { 3, 4 } }; ticket test3[]= { { 2, 3 }, { 3, 4 }, { 1, 2 } }; ticket test4[]= { { 2, 1 }, { 3, 2 }, { 4, 3 } }; ticket test5[]= { { 1, 3 }, { 3, 5 }, { 5, 2 } }; int initial_src, final_dst; find_trip_endpoints(test0, sizeof(test0)/sizeof(*test0), &initial_src, &final_dst); assert(initial_src==1); assert(final_dst==2); find_trip_endpoints(test1, sizeof(test1)/sizeof(*test1), &initial_src, &final_dst); assert(initial_src==1); assert(final_dst==3); find_trip_endpoints(test2, sizeof(test2)/sizeof(*test2), &initial_src, &final_dst); assert(initial_src==1); assert(final_dst==4); find_trip_endpoints(test3, sizeof(test3)/sizeof(*test3), &initial_src, &final_dst); assert(initial_src==1); assert(final_dst==4); find_trip_endpoints(test4, sizeof(test4)/sizeof(*test4), &initial_src, &final_dst); assert(initial_src==4); assert(final_dst==1); find_trip_endpoints(test5, sizeof(test5)/sizeof(*test5), &initial_src, &final_dst); assert(initial_src==1); assert(final_dst==2); return 0; } 

Answer 5

创build两个数据结构：

 Route { start end list of flights where flight[n].dest = flight[n+1].src } List of Routes 

接着：

 foreach (flight in random set) { added to route = false; foreach (route in list of routes) { if (flight.src = route.end) { if (!added_to_route) { add flight to end of route added to route = true } else { merge routes next flight } } if (flight.dest = route.start) { if (!added_to_route) { add flight to start of route added to route = true } else { merge routes next flight } } } if (!added to route) { create route } } 

Answer 6

放入两个哈希：to_end = src – > des; to_beg = des – > src

select任何机场作为起点。

 while(to_end[S] != null) S = to_end[S]; 

S现在是你的最终目的地。 重复与其他地图find你的出发点。

如果没有适当的检查，这感觉O（N），只要你有一个体面的哈希表实现。

Answer 7

哈希表不适用于大尺寸（例如原始问题中的数十亿）; 任何与他们合作过的人都知道，他们只适合小套装。 你可以使用二叉search树，这会给你复杂的O（n log n）。

最简单的方法是两次传递：第一次将它们全部添加到由src索引的树中。 第二步走树并将节点收集到一个数组中。

我们可以做得更好吗？ 我们可以，如果我们真的想：我们可以一口回事。 将每张票据表示为喜欢列表上的节点。 最初，每个节点的下一个指针都有空值。 对于每个票据，在索引中input它的src和dest。 如果发生碰撞，就意味着我们已经有了相邻的票; 连接节点并从索引中删除匹配。 完成之后，您只能进行一次传球，并且有一个空的索引，以及所有门票的链接列表。

这种方法明显更快：只有一次，而不是两次; 而且存储量要小得多（最坏的情况：n / 2;最好的情况：1;典型的情况：sqrt（n）），这样你就可以实际使用散列而不是二叉查找树。

Answer 8

每个机场都是一个node 。 每张票是一个edge 。 用一个邻接matrix来表示图。 这可以作为一个位域来压缩边缘。 你的起点将是没有path的节点（它的列将是空的）。 一旦你知道这一点，你只要按照现有的path。

或者，你可以build立一个机场索引结构。 对于每张票你看它是src和dst 。 如果没有find，那么你需要添加新的机场到你的清单。 当find每一个时，您设置出发机场的出口指针指向目的地，并且指定目的地的到达指针指向出发机场。 当你出门票时，你必须遍历整个列表来确定谁没有path。

另一种方法是在您遇到每张票时连接一个小型旅行的可变长度列表。 每当您添加一张票时，您会看到任何现有的小型旅程的结束是否与您的票的src或dest匹配。 如果没有，那么你现在的票就变成了自己的小旅行，并被添加到列表中。 如果是这样的话，那么新的票据将被添加到它所匹配的现有旅程的末尾，可能将两个现有的小旅程拼接在一起，在这种情况下，它将缩短一个小旅行的列表。

Answer 9

这是单个path状态机matrix的简单情况。 不好意思的是用C＃风格的伪代码，但用对象来expression这个想法更容易。

首先，构build一个收费matrix。 阅读我对收费matrix是什么的描述（不要打扰FSM的答案，只是一个收费matrix的解释） 什么是testing大型国家机器的一些策略？ 。

但是，您所描述的限制使得这种情况成为简单的单一path状态机器。 这是最简单的状态机，完全覆盖。

对于5个机场的简单情况，
vert节点= src /入口点，
水平节点= dst /出口点。

  A1 A2 A3 A4 A5 A1 x A2 x A3 x A4 x A5 x 

请注意，对于每一行以及每列，不应该有一个以上的转换。

为了获得机器的path，你可以将matrixsorting

  A1 A2 A3 A4 A5 A2 x A1 x A3 x A4 x A5 x 

或者sorting成对angular方阵 – 有序对的本征向量。

  A1 A2 A3 A4 A5 A2 x A5 x A1 x A3 x A4 x 

其中有序对是票的列表：

a2：a1，a5：a2，a1：a3，a3：a4，a4：a5。

或更正式的表示法，

 <a2,a1>, <a5,a2>, <a1,a3>, <a3,a4>, <a4,a5>. 

嗯..有序的对吧？ 闻一闻Lisp的recursion？

 <a2,<a1,<a3,<a4,a5>>>> 

机器有两种模式，

1. 旅行计划 – 你不知道有多less个机场，你需要一个通用的旅行计划为不特定的机场数量
2. 旅行重build – 你有过去旅行的所有收费机票，但他们都是在你的手套箱/行李袋一大堆。

我假设你的问题是关于旅行重build。 所以，你从这一堆票中随机挑选一张。

我们假设这个票堆是不确定的大小。

  tak mnx cda bom 0 daj 0 phi 0 

其中0值表示无序票证。 让我们将无序票证定义为票据，其中的票证与其他票证的票据不匹配。

下一张票发现mnx（dst）= kul（src）匹配。

  tak mnx cda kul bom 0 daj 1 phi 0 mnx 0 

在任何时候你select下一张票，有可能连接两个连续的机场。 如果发生这种情况，您可以从这两个节点中创build一个群集节点：

 <bom,tak>, <daj,<mnx,kul>> 

matrix减less，

  tak cda kul bom 0 daj L1 phi 0 

哪里

 L1 = <daj,<mnx,kul>> 

这是主要列表的子列表。

继续挑选下一个随机票。

  tak cda kul svn xml phi bom 0 daj L1 phi 0 olm 0 jdk 0 klm 0 

将existent.dst匹配到new.src
或existent.src到new.dst：

  tak cda kul svn xml bom 0 daj L1 olm 0 jdk 0 klm L2 <bom,tak>, <daj,<mnx,kul>>, <<klm,phi>, cda> 

以上的拓扑练习只是为了视觉理解。 以下是algorithm解决scheme。

这个概念是将有序对集群成子列表，以减less我们将用来容纳门票的散列结构的负担。 逐渐地，将会有越来越多的伪票（由合并的匹配票形成），每个伪票包含有序目的地的增长子列表。 最后，在其子列表中将保留一个包含完整行程向量的伪单票。

正如你所看到的，也许这最好是用Lisp完成的。

但是，作为一个链接列表和地图的练习…

创build以下结构：

 class Ticket:MapEntry<src, Vector<dst> >{ src, dst Vector<dst> dstVec; // sublist of mergers //constructor Ticket(src,dst){ this.src=src; this.dst=dst; this.dstVec.append(dst); } } class TicketHash<x>{ x -> TicketMapEntry; void add(Ticket t){ super.put(tx, t); } } 

所以有效地，

 TicketHash<src>{ src -> TicketMapEntry; void add(Ticket t){ super.put(t.src, t); } } TicketHash<dst>{ dst -> TicketMapEntry; void add(Ticket t){ super.put(t.dst, t); } } TicketHash<dst> mapbyDst = hash of map entries(dst->Ticket), key=dst TicketHash<src> mapbySrc = hash of map entries(src->Ticket), key=src 

当从机上随机挑选一张票时，

 void pickTicket(Ticket t){ // does t.dst exist in mapbyDst? // ie attempt to match src of next ticket to dst of an existent ticket. Ticket zt = dstExists(t); // check if the merged ticket also matches the other end. if(zt!=null) t = zt; // attempt to match dst of next ticket to src of an existent ticket. if (srcExists(t)!=null) return; // otherwise if unmatched either way, add the new ticket else { // Add t.dst to list of existing dst mapbyDst.add(t); mapbySrc.add(t); } } 

检查存在的dst：

 Ticket dstExists(Ticket t){ // find existing ticket whose dst matches t.src Ticket zt = mapbyDst.getEntry(t.src); if (zt==null) return false; //no match // an ordered pair is matched... //Merge new ticket into existent ticket //retain existent ticket and discard new ticket. Ticket xt = mapbySrc.getEntry(t.src); //append sublist of new ticket to sublist of existent ticket xt.srcVec.join(t.srcVec); // join the two linked lists. // remove the matched dst ticket from mapbyDst mapbyDst.remove(zt); // replace it with the merged ticket from mapbySrc mapbyDst.add(zt); return zt; } Ticket srcExists(Ticket t){ // find existing ticket whose dst matches t.src Ticket zt = mapbySrc.getEntry(t.dst); if (zt==null) return false; //no match // an ordered pair is matched... //Merge new ticket into existent ticket //retain existent ticket and discard new ticket. Ticket xt = mapbyDst.getEntry(t.dst); //append sublist of new ticket to sublist of existent ticket xt.srcVec.join(t.srcVec); // join the two linked lists. // remove the matched dst ticket from mapbyDst mapbySrc.remove(zt); // replace it with the merged ticket from mapbySrc mapbySrc.add(zt); return zt; } 

检查存在的src：

 Ticket srcExists(Ticket t){ // find existing ticket whose src matches t.dst Ticket zt = mapbySrc.getEntry(t.dst); if (zt == null) return null; // if an ordered pair is matched // remove the dst from mapbyDst mapbySrc.remove(zt); //Merge new ticket into existent ticket //reinsert existent ticket and discard new ticket. mapbySrc.getEntry(zt); //append sublist of new ticket to sublist of existent ticket zt.srcVec.append(t.srcVec); return zt; } 

我有一个感觉，上面有很多错别字，但是这个概念应该是对的。 发现任何错字，有人可以帮忙纠正错误。

Answer 10

最简单的方法是用散列表，但是没有最好的最坏情况复杂度（ O（n ² ） ）

代替：

1. 创build一堆包含（src，dst） O（n）
2. 将节点添加到列表并按src O（n log n）
3. 对于每个（目标）节点，search相应的（源）节点O（n log n）
4. find开始节点（例如，使用拓扑sorting或在步骤3中标记节点） O（n）

总的来说： O（n log n）

（对于这两种algorithm，我们假设string的长度是可以忽略的，即比较是O（1））

Answer 11

不需要哈希或类似的东西。 这里的实际input大小不一定是票的数量（比如说n ），而是票的总大小（比如N ），也就是编码所需的char总数。

如果我们有一个由k个字符组成的字母表（这里k大约是42），我们可以使用bucketsort技术对一个总数为N的n个string进行sorting，这些string用O（n + N + k）时间。 如果n <= N （平凡）和k <= N （井N是数十亿，那不是）

1. 在门票订单的顺序中，从门票中提取所有机场代码，并将其存储在代码为string且门票索引为数字的结构中。
2. 根据他们的代码将struct数组分成不同的部分
3. 运行槽sorting数组，并为每个新遇到的航空公司代码分配一个序号（从0开始）。 对于所有具有相同代码的元素（它们是连续的），转到票证（我们用代码存储了数字），并将票证的代码（select正确的， src或dst ）更改为序号。
4. 在数组运行期间，我们可以识别原始的源src0 。
5. 现在所有票据都将src和dst重写为序号，票据可以被解释为从src0开始的一个列表。
6. 在门票上做列表排名（=跟踪与src0的距离的toplogicalsorting）。

Answer 12

如果您假设一个可以存储所有内容的可连接列表结构（可能在磁盘上）：

1. 创build2个空的散列表S和D.
2. 抓住第一个元素
3. 在D中查看它的src
4. 如果find，从D中删除关联的节点并将其链接到当前节点
5. 如果找不到，则将该节点插入到src上的S上
6. 从3开始以另一种方式重复src→des→S→D
7. 从下一个节点重复2。

O(n)时间。 至于空间， 生日悖论 （或类似的东西）会使你的数据集比整个集合小很多。 在运气不好的情况下，它仍然很大（最坏的情况是O(n) ），你可以从散列表中抽取随机运行并将它们插入到处理队列的末尾。 你的速度可能会下降，但只要你可以远远超过预期的冲突（〜O O(sqrt(n)) ），你应该期望看到你的数据集（表和input队列组合）定期收缩。

Answer 13

在我看来，像基于图表的方法是基于这里的。

每个机场都是一个节点，每个机票都是一个边缘。 让我们现在就让每一个边缘无方向。

在第一阶段，你正在build立图表：对于每张票，你查找源和目的地，并build立他们之间的边缘。

现在这个图被构造出来了，我们知道它是非循环的，并且通过它有一个单一的path。 毕竟，你只有你的旅行门票，你从来没有去过同一个机场一次。

在第二阶段，您正在search图表：select任何节点，并开始在两个方向的search，直到你发现你不能继续。 这些是你的来源和目的地。

如果您需要具体说明哪些是源代码，哪些是目的地，请将目录属性添加到每个边缘（但将其保留为无向图）。 一旦你有候选人的来源和目的地，你可以知道哪个是基于连接到他们的边缘。

该algorithm的复杂性取决于查找特定节点所花费的时间。 如果你能达到一个O（1），那么时间应该是线性的。 你有n票，所以它需要O（N）步骤来build立图，然后O（N）search和O（N）来重buildpath。 还是O（N）。 一个邻接matrix会给你的。

如果你不能腾出空间，你可以做一个散列的节点，这会给你O（1）在最佳散列和所有的废话。

Answer 14

请注意，如果任务只是确定源机场和目的地机场（而不是重build整个旅程），那么这个难题可能会变得更有趣。

也就是说，假设机场代码是以整数forms给出的，则可以使用O（1）数据传递和O（1）附加存储器（即，不使用散列表，sorting，二进制search等）来确定源机场和目的地机场）。

当然，一旦find源代码，索引和遍历整个路由也是一件小事，但从这一点来说，总的来说至less需要O（n）个额外的内存（除非您可以将数据sorting这个地方，它允许用O（1）额外的存储器在O（n log n）时间内解决原来的任务）

Answer 15

让我们暂时忘记数据结构和图表。

首先我需要指出，每个人都假设没有循环。 如果路线经过一个机场两次，这是一个更大的问题。

---

但是现在让我们保持假设。

input数据实际上是一个有序集合。 每张票都是向一组机场介绍订单的关系中的一个元素。 （英语不是我的母语，所以这些可能不是正确的math术语）

每张票都有这样的信息： airportX < airportY ，所以当一张票通过票时，一个algorithm可以从任何机场重新开始一个有序列表。

---

Now let's drop the "linear assumption". No order relation can be defined out of that kind of stuff. The input data has to be treated as production rules for a formal grammar, where grammar's vocabulary set is a set of ariport names. A ticket like that:

 src: A dst: B 

is in fact a pair of productions:

 A->AB B->AB 

from which you only can keep one.

Now you have to generate every possible sentence, but you can use every production rule once. The longest sentence that uses every its production only once is a correct solution.

Answer 16

先决条件

First of all, create some kind of subtrip structure that contains a part of your route.

For example, if your complete trip is abcdefg , a subtrip could be bcd , ie a connected subpath of your trip.

Now, create two hashtables that map a city to the subtrip structure the city is contained in. Thereby, one Hashtable stands for the city a subtrip is starting with, the other stands for the cities a subtrip is ending with. That means, one city can occur at most once in one of the hashtables.

As we will see later, not every city needs to be stored, but only the beginning and the end of each subtrip.

Constructing subtrips

Now, take the tickets just one after another. We assume the ticket to go from x to y (represented by (x,y) ). Check, wheter x is the end of some subtrip s (since every city is visited only once, it can not be the end of another subtrip already). If x is the beginning, just add the current ticket (x,y) at the end of the subtrip s . If there is no subtrip ending with x , check whether there is a subtrip t beginning with y . If so, add (x,y) at the beginning of t . If there's also no such subtrip t , just create a new subtrip containing just (x,y) .

Dealing with subtrips should be done using some special "tricks".

• Creating a new subtrip s containing (x,y) should add x to the hashtable for "subtrip beginning cities" and add y to the hashtable for "subtrip ending cities".
• Adding a new ticket (x,y) at the beginning of the subtrip s=(y,...) , should remove y from the hashtable of beginning cities and instead add x to the hashtable of beginning cities.
• Adding a new ticket (x,y) at the end of the subtrip s=(...,x) , should remove x from the hashtable of ending cities and instead add y to the hashtable of ending cities.

With this structure, subtrips corresponding to a city can be done in amortized O(1).

After this is done for all tickets, we have some subtrips. Note the fact that we have at most (n-1)/2 = O(n) such subtrips after the procedure.

Concatenating subtrips

Now, we just consider the subtrips one after another. If we have a subtrip s=(x,...,y) , we just look in our hashtable of ending cities, if there's a subtrip t=(...,x) ending with x . If so, we concatenate t and s to a new subtrip. If not, we know, that s is our first subtrip; then, we look, if there's another subtrip u=(y,...) beginning with y . If so, we concatenate s and u . We do this until just one subtrip is left (this subtrip is then our whole original trip).

I hope I didnt overlook somtehing, but this algorithm should run in:

• constructing all subtrips (at most O(n) ) can be done in O(n) , if we implement adding tickets to a subtrip in O(1) . This should be no problem, if we have some nice pointer structure or something like that (implementing subtrips as linked lists). Also changing two values in the hashtable is (amortized) O(1) . Thus, this phase consumes O(n) time.
• concatenating the subtrips until just one is left can also be done in O(n) . Too see this, we just need to look at what is done in the second phase: Hashtable lookups, that need amortized O(1) and subtrip concatenation that can be done in O(1) with pointer concatenation or something.

Thus, the whole algorithm takes time O(n) , which might be the optimal O -bound, since at least every ticket might need to be looked at.

Answer 17

I have written a small python program, uses two hash tables one for count and another for src to dst mapping. The complexity depends on the implementation of the dictionary. if dictionary has O(1) then complexity is O(n) , if dictionary has O( lg(n) ) like in STL map, then complexity is O( n lg(n) )

 import random # actual journey: a-> b -> c -> ... g -> h journey = [('a','b'), ('b','c'), ('c','d'), ('d','e'), ('e','f'), ('f','g'), ('g','h')] #shuffle the journey. random.shuffle(journey) print("shffled journey : ", journey ) # Hashmap to get the count of each place map_count = {} # Hashmap to find the route, contains src to dst mapping map_route = {} # fill the hashtable for j in journey: source = j[0]; dest = j[1] map_route[source] = dest i = map_count.get(source, 0) map_count[ source ] = i+1 i = map_count.get(dest, 0) map_count[ dest ] = i+1 start = '' # find the start point: the map entry with count = 1 and # key exists in map_route. for (key,val) in map_count.items(): if map_count[key] == 1 and map_route.has_key(key): start = key break print("journey started at : %s" % start) route = [] # the route n = len(journey) # number of cities. while n: route.append( (start, map_route[start]) ) start = map_route[start] n -= 1 print(" Route : " , route )