Explore topic-wise InterviewSolutions in .

Correct OPTION is (a) O(√n)

Best EXPLANATION: For finding the minimum element in a given array of size n using square root decomposition we FIRST divide the array into √n CHUNKS and calculate the result for them individually. So for a given query, the result of middle blocks has to be calculated along with the extreme elements. This takes O(√n) time in the worst case.

Correct option is (C) O((q+N)√n)

For explanation: MO’s ALGORITHM requires O(q*√n) + O(n*√n) time for processing all the QUERIES. It is better than the naive solution where O(n*q) time is required.

Right answer is (c) O(n*q)

Easy EXPLANATION - For finding the RESULT of one query the WORST case time COMPLEXITY will be n. So for q queries the time complexity will be O(q*n). This can be reduced by using square root optimization.

The correct option is (C) O(1)

The best I can explain: The time complexity of QUERY operation remains the same in both square ROOT optimized code and non optimized code. We simply find the chunk in which the update requires to be PERFORMED and then add the new updated value at the desired index.

Right choice is (c) 3*√n

Easiest explanation - After calculating the sum of each chunk individually we require to iterate only 3*√n times to calculate the sum in the WORST case. It is because two of the √n FACTORS consider the worst case time complexity of summing ELEMENTS in the FIRST and last block. Whereas the third √n considers the factor of summing the √n chunks.

Correct choice is (C) O(√n)

The best explanation: When we use SQUARE root optimization we decompose the given ARRAY into √n chunks each of size √n. So after calculating the sum of each chunk individually, we require to iterate only 3*√n times to calculate the sum in the worst CASE.

Correct answer is (a) O(n)

For explanation: For a GIVEN array of size n we have to TRAVERSE all n elements in the WORST CASE. In such a case l=0, r=n-1 so the time complexity will be O(n).

The CORRECT ANSWER is (a) to reduce the time complexity of a code

Explanation: Square decomposition is mainly used in competitive programming to optimize code. It REDUCES the time complexity by a factor of √n.

The CORRECT choice is (B) false

Easy explanation - Co-ordinate compression technique can be applied where such optimization is suitable. It does not require to co-ordinate SYSTEM PROBLEM only.

Right choice is (a) true

The EXPLANATION is: The idea behind co-ordinate COMPRESSION is to reduce the NUMBER of squares in a graph by converting them into rectangles of viable size. This REDUCES the TIME complexity of traversal.

The correct choice is (c) for improving both time and space complexity

Best explanation: Co-ordinate COMPRESSION is the PROCESS of reassigning co-ordinates in order to remove gaps. This HELPS in improving both time and space complexity of a SOLUTION.

The CORRECT option is (a) process of REASSIGNING co-ordinates to REMOVE GAPS

Explanation: Co-ordinate compression is the process of reassigning co-ordinates in order to remove gaps. This HELPS in improving efficiency of a solution.

The correct OPTION is (c) O(n)

Easiest explanation - Best case TIME COMPLEXITY of QUICKSELECT is O(n). It is observed in the case where good pivots are chosen CONSISTENTLY then the array size decreases exponentially and thus the required element is found in linear time.

Correct choice is (d) O(1)

Easy explanation - Quickselect algorithm requires no extra SPACE in order to calculate the DESIRED result. It PERFORMS manipulations in the given ARRAY itself so its AUXILIARY space requirement will be O(1).

Correct choice is (d) 5

The EXPLANATION is: QUICKSELECT algorithm finds the kth smallest element from the GIVEN list. So as here the given value of k is 4 so we need to FIND the fourth smallest element which is 5 in the given ARRAY.

The correct option is (B) hoare’s selection algorithm

To EXPLAIN: Quick SELECT is a selection algorithm. It was developed by Tony Hoare, THUS it is ALSO known as Hoare’s selection algorithm.

Right answer is (a) When there exists a hamiltonian PATH in the graph

Easiest explanation - A hamiltonian path exists in a Directed ACYCLIC Graph when all pairs of consecutive vertices are in sorted ORDER and are connected by edges. In such a case, there exists a unique TOPOLOGICAL sorting order.

Right choice is (c) TOPOLOGICAL Sorting

Best EXPLANATION: As the definition of topological sorting suggests, it is the way to do tasks in PRESCRIBED ORDER. So, if he does topological sorting, it will be easy for him to recognize what should be the order to visit different PLACES.

Correct answer is (a) Pre-order traversal

The best I can EXPLAIN: In pre-order traversal of TREES, we process the root FIRST and then CHILD from LEFT to right.

Right option is (c) Using Depth and Breadth First Search

For explanation: We can implement topological sort by both BFS and DFS. In BFS, we use queue as data structure and in DFS, we use LINKED LIST (if recursive) or Stack (if not recursive) as data structure.

Right choice is (d) Ordered Statistics

Best explanation: Topological sort TELLS what task should be DONE before a task can be STARTED. It also detects cycle in the GRAPH which is why it is used in the Operating System to find the deadlock. Ordered statistics is an APPLICATION of Heap sort.

The CORRECT OPTION is (d) Zero DEGREE

Easiest explanation - Topological sort starts with a node which has zero degree. If MULTIPLE such nodes EXISTS then it can start with any node.

The correct choice is (a) O(V + E)

Explanation: The TOPOLOGICAL sort ALGORITHM has complexity same as Depth FIRST SEARCH. So, DFS has a complexity O(V+E).

Correct answer is (d) DIRECTED ACYCLIC Graphs

Easiest explanation - Every Directed Acyclic Graph has one or more topological ordering WHEREAS Cyclic and Undirected graphs can’t be ORDERED TOPOLOGICALLY.