Sorting

Question 1

What is the time complexity of sorting an array with Quick Sort?

Answer 1

Average O(n log n), Worst O(n²).

Question 1

What is the best-case and worst-case time complexity of Merge Sort?

Answer 1

O(n log n) for all cases.

Question 2

What is the difference between Quick Sort and Merge Sort?

Answer 2

Quick Sort is in-place, but Merge Sort has better worst-case guarantees.

Question 3

What is the advantage of Heap Sort over Quick Sort?

Answer 3

O(n log n) worst-case complexity; always predictable.

Question 4

Why is Bubble Sort not used in practice?

Answer 4

O(n²) complexity, too many swaps.

Question 5

What sorting algorithms have O(n) time complexity?

Answer 5

Counting Sort, Radix Sort, Bucket Sort (non-comparison-based).

Question 6

What is counting sort, and when is it useful?

Answer 6

Good for small, limited-value integers.

Question 7

What is the time complexity of inserting an element into a balanced BST?

Answer 7

O(log n) for best, worst, and average cases.

Question 8

When should you use Quick Sort, Merge Sort, or Heap Sort?

Answer 8

Quick Sort Best for random data, in-place, very fast O(n log n) avg, O(n²) worst

Merge Sort Best for linked lists or stable sorting O(n log n) worst

Heap Sort Best for priority-based sorting O(n log n) always

Question 9

What is Topological Sorting, and when is it used?

Answer 9

Used in dependency resolution problems (e.g., course scheduling).

Works only on DAGs (Directed Acyclic Graphs).

Can be implemented via DFS (Stack) or Kahn’s Algorithm (BFS In-Degree Count).

function topologicalSort(graph) {
let inDegree = Object.fromEntries(Object.keys(graph).map(node => [node, 0]));

// Compute in-degree for each node
for (let node in graph) {
    for (let neighbor of graph[node]) {
        inDegree[neighbor]++;
    }
}

let queue = Object.keys(inDegree).filter(node => inDegree[node] === 0);
let topoOrder = [];

while (queue.length > 0) {
    let node = queue.shift();
    topoOrder.push(node);
    for (let neighbor of graph[node] || []) {
        inDegree[neighbor]--;
        if (inDegree[neighbor] === 0) {
            queue.push(neighbor);
        }
    }
}

return topoOrder.length === Object.keys(graph).length ? topoOrder : []; // Return empty if cycle detected }