Graph and Tree Algorithms Flashcards
6 cards from real CodeSignal Technical Assessment practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.
Read the first 6 Graph and Tree Algorithms flashcards as text
A social media application wants to find the shortest chain of connections between two users (e.g., 'friend of a friend'). If the network is represented as an unweighted graph where users are nodes and friendships are edges, which algorithm is most suitable for this task?
Answer: Breadth-First Search (BFS)
Breadth-First Search (BFS) is guaranteed to find the shortest path in terms of the number of edges in an unweighted graph. It explores the graph layer by layer, ensuring that when it first reaches the target node, it has done so via the fewest possible connections.
A project manager needs to schedule a series of tasks where some tasks have dependencies on others. This can be modeled as a directed graph. What fundamental property must this graph have for a valid task schedule (a topological sort) to be possible?
Answer: The graph must be a Directed Acyclic Graph (DAG).
A topological sort, which provides a linear ordering of tasks based on dependencies, is only possible if the graph has no directed cycles. A cycle would represent a logical impossibility, such as Task A depending on Task B, and Task B depending on Task A.
You are given a non-empty Binary Search Tree (BST). Which of the following traversal methods will visit the nodes in ascending sorted order of their values?
Answer: In-order Traversal
In-order traversal visits the left subtree, then the root node, and finally the right subtree. Due to the inherent property of a BST (left children are smaller, right children are larger), this 'Left-Root-Right' pattern naturally processes the nodes in ascending order of their values.
A GPS navigation system models a road network as a graph where cities are vertices and roads are edges with weights representing travel time. To find the quickest route from a starting city to a destination, which algorithm is the most appropriate choice, assuming all travel times are positive?
Answer: Dijkstra's Algorithm
Dijkstra's algorithm is specifically designed to find the shortest path from a single source to all other nodes in a weighted graph with non-negative edge weights. This makes it the ideal choice for finding the quickest route in a road network where edge weights represent travel time.
A utility company is planning to connect several towns with a new power grid. The goal is to ensure every town is connected to the grid while minimizing the total length of power lines used. This problem is a classic application of finding what structure in a graph?
Answer: A Minimum Spanning Tree (MST)
A Minimum Spanning Tree (MST) is a subgraph that connects all vertices in a weighted, undirected graph with the minimum possible total edge weight, without forming any cycles. This directly corresponds to the problem of connecting all towns with the least amount of cable.
Which of the following graph problems is most effectively solved using Depth-First Search (DFS) by identifying a 'back edge'—an edge that connects a node to one of its ancestors in the traversal tree?
Answer: Detecting the presence of a cycle.
Depth-First Search (DFS) explores as far as possible along each branch before backtracking. If during this traversal, it encounters a neighbor that has already been visited and is currently in the recursion stack (an ancestor), it has found a back edge, which indicates a cycle in the graph.