Prim or Kruskal: which would you use, and why?

A strong answer

A strong candidate frames Prim or Kruskal: which would you use, and why? around the exact memory layout, compiler semantics, and hardware execution model covered in Prim's algorithm. Compare the two minimum spanning tree algorithms by graph density, storage and cost, and contrast Prim with Dijkstra.

Kruskal's algorithm builds a forest of many small trees and merges them. Prim's algorithm, published by Robert Prim in 1957 and discovered earlier by Vojtěch Jarník in 1930, grows a single tree. It starts with one vertex and, at every step, adds the cheapest edge that connects the tree to a vertex outside it. After n − 1 steps, every vertex is in the tree.

To find the cheapest outgoing edge quickly, Prim keeps a key for every vertex not yet in the tree: the weight of the cheapest edge from that vertex into the tree, or infinity if there is none. Each step picks the outside vertex with the smallest key, adds it to the tree, and then looks at its edges: any outside neighbor that can now be reached more cheaply gets a lower key.

In a production interview, always connect the specification rule to its concrete runtime consequence: state what lives on the stack versus the heap or static storage segment, how the compiler or operating system validates alignments, lifetimes, and error codes, and what happens under adversarial or boundary inputs (such as zero-length buffers, integer overflow, concurrent mutation, or partial I/O). Backing your explanation with a small trace of register/memory state transitions immediately separates senior systems engineers from candidates who only memorized syntax.

What the interviewer is listening for

• Mastery of core invariant: Run Prim's algorithm, keeping each outside vertex's cheapest edge into the tree.
• Mastery of core invariant: Choose between the O(V²) array version and the O(E log V) heap version.
• Mastery of core invariant: Compare Prim with Kruskal and with Dijkstra.
• Hardware and ABI awareness: Explaining how sizes, alignments, calling conventions, or kernel boundaries behave on real 64-bit targets rather than relying on implementation-defined assumptions.
• Defensive engineering: Naming the exact compiler flags (-Wall -Wextra -Werror), static analyzers, or runtime sanitizers (-fsanitize=address,undefined,thread) that verify correctness in CI.

Common mistakes

• Explaining only surface syntax without tracing the underlying memory addresses, ownership lifetime, or kernel/user-space state transitions.
• Assuming undefined behavior (such as signed overflow, uninitialized reads, strict-aliasing violations, or dangling pointers) will "just work" because it passed an unoptimized -O0 debug build.
• Ignoring return codes, partial reads/writes, alignment padding, or cleanup paths when an allocation or syscall fails midway through a function.