Practo Interview Question for SDE1s
- 0of 0 votes
Nuclear Rods- rayasamharish October 04, 2015 in India
A core meltdown has occurred at the Fubaru nuclear plant. There are
n nuclear fuel rods that are damaged and need to be removed using
specialized radiation-hardened robotic equipment
with solid-lead isolation chambers. Remote imaging has already
uniquely identified every damaged fuel rod and assigned it a number
between 1 and n. The imaging data also records which fuel rods were
fused to each other during the meltdown. Every recovery sortie by the
robot can pick up one set of nuclear fuel rods that are directly or
indirectly fused to each other.
The recovery costs per sortie are proportional to the square root of the
number of fused rods recovered. So the cost is K to recover K rods.
Isolation chambers are available for all positive integer costs (1, 2, 3, …).
An isolation chamber can be used multiple times, and each use will
incur the same cost. The robot can also recover a lower number of rods
than a chamber's capacity on a sortie.
Find the minimal cost to recover all the radioactive rods by completing
the given function.
The first parameter integer n specifies the number of rods. The second
parameter pairs is an array of pairs of rods that are fused together. Each
item in the array contains exactly two integers, P and Q separated by a
space (" "), which means that the rod numbered P is fused to the rod
numbered Q. *Note - Each item in the array is a string which needs to be
parsed to P and Q
2 ≤ N ≤ 100,000
1 ≤ P, Q ≤ N
P ≠ Q
Rods #1, #2, #4 are connected to each other (2-1-4) so they are in a
single group of 3. The sortie to recover them will cost 2 (with isolation
chamber capacity 2 = 4). Rod #3 is not fused to any other, so it can be
recovered at a cost of 1 (with isolation chamber capacity 1 = 1).
| Report Duplicate | Flag | PURGE
Interview Type: Written Test
Open Chat in New Window