VIRTASANT – Technical test

A long time ago, I needed to do this technical test.

You’ll see my way to resolve it without reinventing the wheel.

The subject

Imagine that you are building an electrical grid for a group of settlements on Mars. As with every grid, it has a central power switching station located in the biggest/central settlement, and it has smaller settlements around it. Each smaller settlement has its power switching station, and they are all interconnected.

Let’s say there are N settlements on Mars that are uniquely numbered between [1…N] The central power switching station is represented with 1. The power between switching stations can be transferred in either direction and it is guaranteed that there will be exactly one path between two stations. This means that there will be N-1 connections that will be used to connect the stations.

As we know from physics, each station also has a power loss parameter measured in MartianWatt(MW) (number in red), which shows exactly how much power will be lost on every transfer.

Electricity will be transferred between two power stations if the power loss is equal to what is projected by the engineers as we want to be sure that we have a precisely planned electrical grid. Otherwise, the power transfer operation cannot be initiated.

The diagram above (top of the page) represents a sample martian electrical grid, and as we can see #1 node is the central power switching station.

Examples of how we calculate power loss between stations:

• Power loss for transferring electricity between stations #3 and #2 is 0.2 + 0.8 = 1MW
• Power loss for transferring electricity between stations #8 and #10 is equal to the sum of power losses on the path between those two stations, which means that the power needs to be transferred through settlement8 ⇔ settlement7 ⇔ settlement1 ⇔ settlement10 accumulating to 0.36+0.44+0.34+0.3 = 1.36MW

Sample Configuration Input:

First, you will receive information about the Martian power grid, with the first line containing integer N that denotes the number of power stations in the grid, excluding the central power grid, followed by N lines of comma-separated integers u, v explaining that u is directly connected to v in the power grid (e.g. like #9 is connected to #7 in the example above). Immediately followed by N+1 lines z representing a power loss in each node. It is important to note that power switching station numbers start with 1 and are incremented by 1.

11
1,2
2,3
1,4
4,5
4,6
1,10
10,11
10,12
1,7
7,8
7,9
0.3
0.2
0.8
0.28
0.32
0.17
0.4
0.36
0.1
0.3
0.2
0.05
3
3,2,1.1
8,10,1.36
3,11,1.8

Constraints:

• 2 ≤ N ≤ 2^6
• 1 ≤ u ≤ v ≤ N
• 0 ≤ z ≤ 3.14

Sample Input:

Immediately after the configuration, you will start receiving requests to confirm whether or not the transfer could be initiated. The first line containing integer N denotes the number of requests that need to be processed followed by many lines containing comma-separated values in u, v, z format, where u is the originating station, v is the destination station and z is the estimated power loss.

3
3,2,1.1
8,10,1.36
3,11,1.8

Your goal is to write the algorithm that will verify if the provided estimated power loss between two power stations is correct and in that case, you should return the string “APPROVED” otherwise return “REJECTED”.

Sample Output:

REJECTED
APPROVED
APPROVED

My code

You need to write a graph, so instead of rewriting a graph system, I used NetworkX.

from networkx import Graph, shortest_path


def add_edge(n1, n2):
    """Add edge between nodes n1 and n2."""
    G.add_edge(n1, n2)


def add_attr_cost(node, attr):
    """Add attribute 'cost' to the node."""
    G.nodes[node]['cost'] = attr


def extract_attr_cost(node):
    """Return the value cost for the node."""
    return G.nodes[node]['cost']


def find_path(n1, n2):
    """Find the path between nodes n1 and n2."""
    return shortest_path(G, n1, n2)


def total_cost(n1, n2):
    """Do the sum of cost for a transfer between nodes n1 and n2."""
    return sum(extract_attr_cost(n) for n in find_path(n1, n2))


def verify_estimated_cost(n1, n2, e):
    """Verify if estimated is equal or not to the computed cost."""
    print('APPROVED' if total_cost(n1, n2) == float(e)
          else 'REJECTED')


G = Graph()

if __name__ == '__main__':
    N = int(input())

    for _ in range(N):
        node1, node2 = list(map(int, input().rstrip().split(sep=',')))
        add_edge(node1, node2)

    for num in range(1, N+2):
        cost = float(input().rstrip())
        add_attr_cost(num, cost)

    nb_requests = int(input())
    for _ in range(nb_requests):
        start, end, estimated = list(map(float,
                                         input().rstrip().split(sep=',')))
        verify_estimated_cost(start, end, estimated)

It was interesting to see a test like that but nothing is perfect and the problems are:

• stupid environment to do it (HackerRank): NumPy isn’t entirely available, networkx is missing, dark mode is just a joke
• staff wanting someone who will reinvent the wheel during the test, sorry I did it a lot during my studies, now, I’m using the right tool for the right job

Maybe the next time with them 🤞