Related InterviewSolutions

• Which of the following standard algorithms is not a Greedy algorithm?(A) Dijkstra’s shortest path algorithm(B) Prim’s algorithm(C) Kruskal algorithm(D) Huffman Coding(E) Bellmen Ford Shortest path algorithm
• A networking company uses a compression technique to encode the message before transmitting over the network. Suppose the message contains the following characters with their frequency:character Frequencya 5b 9c 12d 13e 16f 45Note : Each character in input message takes 1 byte.If the compression technique used is Huffman Coding, how many bits will be saved in the message?(A) 224(B) 800(C) 576(D) 324
• In question #2, which of the following represents the word “dead”?(A) 1011111100101(B) 0100000011010(C) Both A and B(D) None of these
• What is the time complexity of Huffman Coding?(A) O(N)(B) O(NlogN)(C) O(N(logN)^2)(D) O(N^2)
• Which of the following is true about Kruskal and Prim MST algorithms? Assume that Prim is implemented for adjacency list representation using Binary Heap and Kruskal is implemented using union by rank.(A) Worst case time complexity of both algorithms is same.(B) Worst case time complexity of Kruskal is better than Prim(C) Worst case time complexity of Prim is better than Kruskal
• Which of the following is true about Huffman Coding.(A) Huffman coding may become lossy in some cases(B) Huffman Codes may not be optimal lossless codes in some cases(C) In Huffman coding, no code is prefix of any other code.(D) All of the above
• Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge weighted directed graph with vertex P as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized? (GATE CS 2004)(A) P, Q, R, S, T, U(B) P, Q, R, U, S, T(C) P, Q, R, U, T, S(D) P, Q, T, R, U, S