Interview was scheduled in afternoon session, but in morning i got a call saying if i am available interview can be conducted in morning session.
Interview was divided into two portion, 1st was programming and 2nd was on the subject we had selected.
Programming:
They asked me to write recursive code for int to binary. And then asked me to modify the code for float to binary conversion.
[Before writing code for float to binary they asked to do that on pen and paper.]
Algorithm questions:
1. What is spanning tree ?
A. Explained with an example of electronics circuit and wire.
2. If i am having ‘n’ edges will it be a spanning tree ?
A. Said it will create cycle.
3. How can you identify cycle in graph ?
A. Said using DFS.
4. They asked what is DFS and how it works?
A. Started explaining the algorithm but they said just give the concept.
5. What is minimum spanning tree ?
A. Told
6. How can you find MST ?
A. I said using Krushkal or Prim’s algorithm.
7. Explain prims algorithm ?
A. Explained it and discussed about it’s time complexity. I had said in it we use heap so the next question was on it.
8. Why we use heap and not other data structures ?
A. Said about time complexity and tried explaining but it seemed they were not convinced.
9. Asked me about the property for which we us heap in prims algorithm.
A. I said about finding minimum in log(n) time but they were asking for something else. [ It continued with awkward silence. Later on it striked they were asking about decrease key operation.]
10. Again they were back on MST and asked me if i decrease weight of edge then how to recalculate MST ?
A. Said as it is in MST so decreasing weight of edge won’t change MST.
11. Then they asked what if i increase the weight ?
A. I said we can re-run algorithm. Then they asked me for efficient solution i said we can remove that particular edge which will result into two disconnected trees. Now out of the available edges to connect this trees we can pick the minimum one. [ Was not much clear at the time of explanation. ]
12. They asked me to prove why after this process the tree will still be MST.
A. It seemed for me obvious and was not able to prove.
