CodeSignal Technical Assessment Graph and Tree Algorithms 2

Question 1

In Dijkstra's algorithm using a min-heap, what is the time complexity for a graph with V vertices and E edges?

Accepted Answer

O((V + E) log V)

Answer

O(V^2)

Answer

O(E log E)

Answer

O(V * E)

Question 2

Which traversal of a Binary Search Tree visits nodes in sorted ascending order?

Accepted Answer

In-order

Answer

Pre-order

Answer

Post-order

Answer

Level-order

Question 3

A graph has a cycle if and only if DFS produces a back edge. What does a 'back edge' connect?

Accepted Answer

A node to an ancestor in the DFS tree

Answer

Two nodes at the same DFS depth

Answer

Two unvisited nodes

Answer

A node to a node in a different DFS component

Question 4

What is the maximum number of nodes in a complete binary tree of height h?

Accepted Answer

2^(h+1) - 1

Answer

2^h

Answer

h^2

Answer

2h + 1

Question 5

Which algorithm finds the Minimum Spanning Tree by always adding the globally smallest edge that does not form a cycle?

Accepted Answer

Kruskal's

Answer

Prim's

Answer

Borůvka's

Answer

Dijkstra's

Question 6

In a directed graph, what does Kosaraju's algorithm compute?

Accepted Answer

Strongly Connected Components (SCCs)

Answer

Shortest paths from a single source

Answer

Minimum Spanning Tree

Answer

Topological sort

Question 7

What property must a graph satisfy for a topological sort to exist?

Accepted Answer

It must be a DAG (Directed Acyclic Graph)

Answer

It must be undirected

Answer

It must be connected

Answer

It must have no self-loops only