Graph and Tree Algorithms Flashcards
7 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 7 Graph and Tree Algorithms flashcards as text
What is the amortized time complexity per operation for Union-Find with both path compression and union by rank?
Answer: O(alpha(N)) — inverse Ackermann
With both optimizations, Union-Find achieves O(α(N)) amortized, where α is the inverse Ackermann function and essentially constant.
In a segment tree built on an array of N elements, what is the time complexity of a range query?
Answer: O(log N)
A segment tree answers range queries in O(log N) by traversing at most O(log N) nodes per query.
Which algorithm solves the All-Pairs Shortest Paths problem in O(V^3) time using dynamic programming?
Answer: Floyd-Warshall algorithm
Floyd-Warshall iterates over all intermediate vertices and updates shortest path estimates in O(V^3).
In a binary heap used as a priority queue, inserting a new element takes which time complexity?
Answer: O(log N)
Insertion places the element at the end and bubbles it up, traversing O(log N) levels of the heap.
What distinguishes a 'bridge' in an undirected graph?
Answer: An edge whose removal disconnects the graph
A bridge is an edge whose removal increases the number of connected components in the graph.
Euler's formula for a connected planar graph states V - E + F = 2. If V=6 and E=12, how many faces F does the graph have?
Answer: 8
F = 2 - V + E = 2 - 6 + 12 = 8 faces, including the outer infinite face.
In the context of graph coloring, what is the chromatic number of a bipartite graph with at least one edge?
Answer: 2
Any bipartite graph with at least one edge requires exactly 2 colors, as it has no odd-length cycles.