Interview Questions

141. The scenario was something like that

Microsoft Interview Questions and Answers


(Continued from previous question...)

141. The scenario was something like that

Question:
The scenario was something like that:
You have to create a graph in most efficient way from relationship of nodes read from txt file.
text file contains information like:
node_id weight node_id
node_id weight node_id
.....
// which means two nodes are connected with some weight. (undirected) There are around 600K such information for about 65000 nodes.


maybe an answer:


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.

(Continued on next question...)

Other Interview Questions