Data Structures, Algorithms, Programming Concepts (C/C++/Python/Java), OOP & Web Development (Part 8)

Question 1

Under what specific input condition does basic "Quick Sort" (with leftmost or rightmost element chosen as pivot) degrade to its WORST-CASE time complexity of $\mathcal{O}(N^2)$?

Accepted Answer

When the input array is ALREADY sorted in ascending or descending order (producing maximally unbalanced partitions of sizes $0$ and $N-1$ at every step)

Answer

When all elements are random

Answer

When the array contains negative numbers

Answer

When the array size is a prime number

Question 2

In an array-based representation of a Complete Binary Max-Heap (0-based indexing), where are the Left Child, Right Child, and Parent of an element at index $i$ located?

Accepted Answer

Left: 2i + 1; Right: 2i + 2; Parent: ⌊(i - 1) / 2⌋

Answer

Left: 2i; Right: 2i + 1; Parent: i / 2

Answer

Left: i + 1; Right: i + 2; Parent: i - 1

Answer

Left: i^2; Right: i^2 + 1; Parent: √i

Question 3

What is the exact time complexity of building a Binary Heap from an arbitrary unsorted array of $N$ elements using bottom-up "Build-Heap" (Floyd's algorithm)?

Accepted Answer

O(N) (linear time)

Answer

O(N log N)

Answer

O(N^2)

Answer

O(log N)

Question 4

What is the fundamental mathematical lower bound on the time complexity of ANY comparison-based sorting algorithm in the worst case?

Accepted Answer

Ω(N log N)

Answer

Ω(N)

Answer

Ω(N^2)

Answer

Ω(1)

Question 5

Which tree traversal of a Binary Search Tree (BST) visits nodes in strictly SORTED, monotonically ascending numerical order?

Accepted Answer

Inorder Traversal (Left -> Root -> Right)

Answer

Preorder Traversal (Root -> Left -> Right)

Answer

Postorder Traversal (Left -> Right -> Root)

Answer

Level-Order Traversal

Question 6

What is the allowable "Balance Factor" ($BF = 	ext{Height}(	ext{Left}) - 	ext{Height}(	ext{Right})$) for every node in an AVL Tree?

Accepted Answer

BF ∈ {-1, 0, +1}

Answer

BF ∈ {-2, 0, +2}

Answer

BF = 0 only

Answer

BF ≤ 5

Question 7

Which self-balancing binary search tree structure uses node coloring rules (Root is Black, No two adjacent Red nodes, Equal black-height on all root-to-leaf paths) and is implemented in C++ STL `std::map` and Java `TreeMap`?

Accepted Answer

Red-Black Tree

Answer

AVL Tree

Answer

B-Tree

Answer

Splay Tree

Question 8

When deleting a node that has TWO children from a Binary Search Tree, what node should replace it to preserve the BST ordering property?

Accepted Answer

Either its Inorder Successor (smallest node in its right subtree) OR its Inorder Predecessor (largest node in its left subtree)

Answer

The root node of the tree

Answer

The leftmost leaf node

Answer

A newly created empty node

Question 9

What are the space complexities of representing a graph $G = (V, E)$ using an "Adjacency Matrix" versus an "Adjacency List"?

Accepted Answer

Adjacency Matrix: O(V^2); Adjacency List: O(V + E)

Answer

Adjacency Matrix: O(V + E); Adjacency List: O(V^2)

Answer

Both are O(V^2)

Answer

Both are O(E log V)

Question 10

Which data structure is used to implement Breadth-First Search (BFS) and Depth-First Search (DFS) on a graph, respectively?

Accepted Answer

BFS uses a Queue (FIFO); DFS uses a Stack (LIFO / Recursion)

Answer

BFS uses a Stack; DFS uses a Queue

Answer

Both use a Binary Heap

Answer

Both use a Hash Table

Question 11

Why does Dijkstra's Single-Source Shortest Path algorithm FAIL on graphs that contain negative edge weights?

Accepted Answer

Dijkstra is a Greedy algorithm that assumes once a vertex is marked visited with the minimum current distance, its shortest path is permanently finalized; negative edges can later provide a cheaper path, invalidating this greedy choice

Answer

It causes division by zero

Answer

Negative weights turn the graph into a tree

Answer

Dijkstra cannot read negative integers

Question 12

How does the "Bellman-Ford Algorithm" compute single-source shortest paths on graphs with negative weights, and what extra capability does it provide?

Accepted Answer

It relaxes all |E| edges |V|-1 times using Dynamic Programming, and performs an extra |V|-th pass to detect the presence of Negative-Weight Cycles

Answer

It uses random guesses to find paths

Answer

It converts negative weights to positive numbers

Answer

It deletes negative edges from the graph

Question 13

What is the time complexity of the "Floyd-Warshall Algorithm" for finding All-Pairs Shortest Paths in a graph with $|V|$ vertices using dynamic programming?

Accepted Answer

O(V^3)

Answer

O(V^2 log V)

Answer

O(V * E)

Answer

O(V + E)

Question 14

What algorithm design paradigm and disjoint-set data structure are used by "Kruskal's Algorithm" to compute a Minimum Spanning Tree (MST)?

Accepted Answer

Greedy strategy, sorting all edges by weight and adding them using a Disjoint Set Union (DSU / Union-Find with path compression) data structure in O(E log E) time

Answer

Dynamic Programming with an Adjacency Matrix

Answer

Divide and Conquer with a Queue

Answer

Backtracking with a Stack

Question 15

What is a "Topological Sort" of a Directed Acyclic Graph (DAG)?

Accepted Answer

A linear ordering of all vertices such that for every directed edge $(u, v)$, vertex $u$ comes before vertex $v$ in the ordering (used for scheduling task dependencies)

Answer

Sorting vertices by their degree

Answer

A geographical map of vertices

Answer

A tree with no leaves

Data Structures, Algorithms, Programming Concepts (C/C++/Python/Java), OOP & Web Development (Part 8)

Under what specific input condition does basic "Quick Sort" (with leftmost or rightmost element chosen as pivot) degrade to its WORST-CASE time complexity of O(N2)\mathcal{O}(N^2)O(N2)?

Under what specific input condition does basic "Quick Sort" (with leftmost or rightmost element chosen as pivot) degrade to its WORST-CASE time complexity of $\mathcal{O}(N^2)$ ?