Code Uncode 4.0

KMP string matching algorithm runs in?

• O(nm)
• O(n+m)
• O(n logm)
• O(n^2)

Answer explanation

Preprocess pattern in O(m), search in O(n). Total linear.

How many maximum edges are there in a simple undirected graph with V vertices?

• V^2
• V(V-1)/2
• V-1
• V(V-1)

Answer explanation

A Complete graph has exactly V(V-1)/2 edges.

What is the time complexity of Bellman-Ford?

• O(VE)
• O(V logV)
• O(E logV)
• O(V+E)

Answer explanation

Relax edges V-1 times O(VE). Handles negative weights.

Which traversal does not construct a unique BST?

• Preorder + Postorder
• Inorder + Preorder
• Inorder + Postorder
• Level order

Answer explanation

Inorder + any one traversal (pre/post) uniquely defines BST.

Time to build a heap from n elements?

• O(n log n)
• O(n)
• O(log n)
• O(n^2)

Answer explanation

Heapify bottom-up costs linear

Topological sort is possible when the graph is?

• Directed Acyclic Graph
• Any directed graph
• Undirected cycle-free
• Weighted graph

Answer explanation

Only DAGs admit valid topological ordering.

What is the space complexity of recursive DFS on a graph with V vertices?

• 0(1)
• O(V+E)
• O(E)
• O(V)

Answer explanation

Call stack depth up to V in worst case.

Which hashing method handles clustering better?

• Linear probing
• Quadratic probing
• Double hashing
• Random Probing

Answer explanation

Double hashing spreads keys better, reduces clustering.

A Hash table has a load factor > 1. What must be true?

• Collisions are impossible
• Chaining/overflow handling must exist
• At most one element per bucket
• Search always O(1)

Answer explanation

Load factor > 1 → more elements than buckets, collisions guaranteed.

What is true regarding AVL tree and Red-Black tree:

• AVL has faster searching
• Red-Black have stricter balancing
• Both have same search time
• AVL has faster insertion always

Answer explanation

AVL is height-balanced → O(log n) search with smaller constant factor; RedBlack favors updates.