Flipkart GRiD DSA Quiz 1

Explanation :
Statement 1: The worst-case complexity of a typical implementation of QuickSort is O(n^2). This occurs when the array is already sorted or reverse sorted, and the pivot chosen is consistently the minimum or maximum element. In such cases, the partition step results in highly imbalanced partitions, leading to quadratic time complexity.

Statement 2: The best-case complexity of a typical implementation of Insertion Sort is O(n). This occurs when the input array is already sorted, and each element just needs to be compared with its previous element and inserted in the correct position. In this case, the inner loop of Insertion Sort is skipped, resulting in a linear time complexity.
Therefore, both statements are true.

Explanation :
A linked list can be implemented using a static array as well as structure and pointers.

Explanation :
To determine the maximum number of nodes in a binary tree, we can use the formula:
Maximum number of nodes = 2^(height + 1) - 1

Using this formula, we can calculate the maximum number of nodes for b1 and b2.
For b1 with a height of 4: Maximum number of nodes in b1 = 2^(4 + 1) - 1 = 2^5 - 1 = 32 - 1 = 31
For b2 with a height of 5: Maximum number of nodes in b2 = 2^(5 + 1) - 1 = 2^6 - 1 = 64 - 1 = 63

Therefore, the correct statement is:
Maximum number of nodes in b1 - Maximum number of nodes in b2 = 31 - 63 = -32
So, the correct option is:
Maximum number of nodes in b1 - Maximum number of nodes in b2 = -32.

Explanation :
Kadane's algorithm is a dynamic programming algorithm used to find the maximum subarray sum in an array of integers. It will work correctly for both inputs provided.

For the first input {-1, -2, -3, -4}, Kadane's algorithm will correctly return 0 because it will consider an empty subarray as the maximum subarray, which has a sum of 0.

For the second input {-9, -5, -8, -8}, Kadane's algorithm will correctly return -5, which is the maximum sum achievable by selecting the subarray [-5].

Therefore, Kadane's algorithm will provide correct results for both inputs.

Explanation : 

Move each of the last 5 elements (i.e., elements from the 6th index to the 10th index) one index to the left.

This approach ensures that all elements after the deleted element are shifted to the left, filling the gap created by the deletion. By moving each element one index to the left, the 6th element will take the place of the 5th element, the 7th element will take the place of the 6th element, and so on. The last element in the array will be overwritten or discarded.

The other options mentioned are not correct for deleting the 5th element:

• Moving each of the last 5 elements one index to the right would result in elements being shifted in the opposite direction, potentially overwriting other elements in the array.


• Changing the value of the 5th element to 0 would only modify the value of the element, but it would not remove it from the array or adjust the positions of other elements.

Explanation :
The data structure that can have a back edge is a graph.
A back edge is an edge that connects a node to one of its ancestors in a graph. It forms a cycle in the graph, indicating a path from a node back to itself or to one of its previous nodes.
In a singly linked list, each node has a reference to the next node, forming a unidirectional chain. There are no back edges in a singly linked list because the links only point forward.
In a tree, there are no cycles, so there are no back edges. The edges in a tree are directed from parent to child, ensuring that no node can be reached by following a back edge.
However, in a graph, which is a collection of nodes (vertices) connected by edges, back edges can exist. They indicate a connection from a node to one of its ancestors, creating cycles within the graph.

Explanation :
Both selection sort and insertion sort have a best-case time complexity of O(n), where n is the number of elements in the input array.
In the best-case scenario, the selection sort compares elements and finds the minimum or maximum element in each pass, and then swaps it with the correct position. Since the array is already sorted, the swapping step is minimal, resulting in linear time complexity.
Similarly, in the best-case scenario, insertion sort only requires comparing each element with its previous element and inserting it in the correct position. Since the array is already sorted, the comparisons and insertions are minimal, resulting in linear time complexity.

Explanation :
The worst-case deletion time complexity in an array depends on the type of deletion operation being performed. The worst-case deletion time complexity in an array is O(n).

Explanation :
After reversing the stack, the top element of the stack will be 1.
When you reverse a stack, the element that was previously at the bottom of the stack becomes the new top element after the reversal.
In this case, the original stack had the elements inserted in the following order: 1 -> 2 -> 3 .
After reversing the stack, the new order becomes 3 -> 2 -> 1.
Therefore, the top element of the reversed stack will be 1.

Explanation :
The queue is :
{23,20,19,45,89,67}

Queue : {23,20,19,45,89,67,45}
Queue : {20,19,45,89,67,45}
Queue : {19,45,89,67,45}
Queue : {19,45,89,67,45,k}