Minimum Network Cost

What they ask

The timed online assessment for the Associate Software Engineer track in Cairo mixes general problem solving with a graph question built around Prim's algorithm. The link arrives by email roughly two weeks after the CV screen, and you get a window of only three to five days to sit it, so treat it like an exam you cannot reschedule.

A representative version of the graph task: you are given n sites (numbered 0 to n-1) and a list of possible links between them, each with a cost. Return the minimum total cost of a set of links that connects every site, or -1 if that is impossible.

Examples

• n = 4, links = [[0,1,1],[1,2,2],[0,2,4],[2,3,3]] returns 6 (use 0-1, 1-2 and 2-3).
• n = 3, links = [[0,1,5]] returns -1 (site 2 can never be reached).

Constraints

• 1 <= n <= 10^4, 0 <= links.length <= 10^5, costs are positive integers.
• Duplicate links and self loops may appear and must not break your answer.

What they look for

• You recognise a minimum spanning tree problem, can name both Prim and Kruskal, then pick one and implement it cleanly.
• A priority-queue Prim in O(E log V), or union-find Kruskal, with the disconnected case handled explicitly.
• The same assessment had MCQ items on basic AI concepts and a SQL section, so budget your time; do not sink the whole window into this one problem.