Sunday, March 4, 2012

Sort tickets and print the final route.


Write an api to sort the tickets from initial source to final destination.
Tickets are in random order.
path: A->B->C->D->E.


Ticket 1: A->B
Ticket 2: B->C
Ticket 3: C->D
Ticket 4: D->E


Suppose the tickets are in this random order.
D->E
C->D
B->C
A->B


Approach:
1. Create a hashmap H for the source and destination of each tickets.
2. create an Map visited for each of the src of the tickets.
3. for each of the tickets src if its not visited then find its path to the final destination and put in the hashmap H, it will override the previous value for the src.
4. In the end the src with the longest value in the hashMap is the desired path.


Code output:
{D=E, A=BCDE, B=CDE, C=DE}
Path according to sorted tickets: 
ABCDE

No comments:

Post a Comment