Frequently asked questions

Question 1

Solve the recurrance T(n) = T(n−1) + n, with T(1) = 1

Answer 1

Θ(n²)

Question 2

What is the complexity or the algorithm this recurrence represents?

Answer 2

Merge Sort, O(n log n)

Question 3

Which data structure would you use to verify matched brackets like [{()}]?

Answer 3

Stack

Question 4

What is the psudocode for inorder transversal

Answer 4

if node ≠ null:
inorder(node.left)
visit(node)
inorder(node.right)

Question 5

What is the pseudocode for preorder transversal

Answer 5

if node ≠ null:
visit(node)
preorder(node.left)
preorder(node.right)

Question 6

What is the pseudocode for postorder transversal

Answer 6

if node ≠ null:
postorder(node.left)
postorder(node.right)
visit(node)

Question 7

What algorithm is this:
for i = 0 to n - m
j = 0
while (P[j] == T[i + j])

Answer 7

Naive String Matching — searching P inside T

Question 8

Given a DAG or a node sequence, which one is a valid topological sort?

Answer 8

Use dependency direction — earlier node must come before dependent

Question 9

Triple loop where inner while (k < n) k *= 2

Answer 9

O(n² log n)

Question 10

What does Prim’s algorithm compute?

Answer 10

Minimum Spanning Tree (MST)

Question 11

T(n) = 4T(n/2) + n²
Use the Master Theorem to solve this recurrence

Answer 11

Θ(n² log n)