IIT-Hyderabad Interview Questions_Second_round_25_07_16

Question

Interview question of IIT Hyderabad, second round of interview held on 25th July, 2016.

Asked about the favorite subjects.

1. Difference between Flow control and condition control.
2. In a network, every node Ni, has buffer capacity of Ci. What is the maximum number of packets that can be transfered in the network at a any time 't'?
3. Almost Shortest Path Algorithm :
    Statement: Commuters check application to find the best route from point A to B. Since, everyone will use the road, it gets congested which leads to delay. Hence, find possible solution to solve this problem.
    (Hint: Modification of Dijkstra's algorithm )
4. A set of characters are given, find the possible words from this set that has a meaning(ie. Dictionary entry)? Propose data structures for storing Dictionary.
5. Best algorithms for Sorting and difference between Merge, Quick and Heap Sort.
6. Propose a sorting algorithm with complexity of O(n).

Comments

in first question,did you mean congestion control??

and is the answer of second question (Ci/size of each packet)??

---

1. It is, I also specifically asked "Conditional control", couldn't answer.
2. Yes, summation of (Ci / sizeof each packet).

---

ooh thankyou,,

can you tell what answer you gave for question 4th??

---

@Michail  what is the answer for 3rd question ?

---

Statement: Commuters check application to find the best route from point A to B. Since, everyone will use the road, it gets congested which leads to delay. Hence, find possible solution to solve this problem. (Hint: Modification of Dijkstra's algorithm )

Solution: There are well known solutions to find the shortest path from a source to destination (Dijkstra's algorithm). Everyone can find this and use this path. Since all are using this path, it gets congested so no longer it's the shortest path. Hence, we should look for the next best shortest path.
Hence, the algorithm can be called "Almost Shortest Path".
 Using Dijkstra once, we can get the shortest path from A to B. Now we need to remove their edges one by one using the following relation:
 Considering all the edges (u,v) having weight w in the shortest path:
 If Dist. from A to B  == (Dist. from A to u) + w (weight of the edge) + Distance from (B to v) then Remove the edge.
 After this, Run Dijkstra again to get the next shortest path.

---

@Michail...i did not get your dijkstra solution for 3rd question..can u be more elaborative?

thankyou