CareerCup

1. Do external sort using key as first node_id of each entry.
2. Search for a given node_id in the file for which sub graph needs to be made.
3. node_id.level = 0. Enque node_id.
4. Repeat 5-8 if Queue is not empty else end.
5. node_id = Dequeue()
6. Read all the entries for second node_id corresponding to node_id (dequeued).
7. For each entries
node_id_xx.level = node_id.level + 1
Enque node_id_xx and at the same time delete it from file (so that if cycle exist we wont enque again).
8. Go to 5.

Yea, this is BFS and should work.

Are there loops in the nodes?

Most efficient Algorithm

Read all entries from file.
Create a hash table and for each entry read from the file, hash it based on the start node_id
Add the cost,dest node_id to the hash table.

Now each entry of hash table is a linked list. So Adding in the above step means add to the linked list.