A long time ago, I needed to do this technical test.<\/p>\n\n\n\n
You’ll see my way to resolve it without reinventing the wheel.<\/p>\n\n\n\n\n\n\n\n
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.<\/p>\n\n\n\n
Let’s say there are N<\/em><\/strong> settlements on Mars that are uniquely numbered between [1\u2026N]<\/em><\/strong> The central power switching station is represented with 1<\/strong>. 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<\/em><\/strong> connections that will be used to connect the stations.<\/p>\n\n\n\n As we know from physics, each station also has a power loss parameter measured in MartianWatt(MW)<\/em><\/strong> (number in red), which shows exactly how much power will be lost on every transfer.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n Examples of how we calculate power loss between stations:<\/p>\n\n\n\n First, you will receive information about the Martian power grid, with the first line containing integer N<\/em><\/strong> that denotes the number of power stations in the grid, excluding the central power grid, followed by N<\/em><\/strong> lines of comma-separated integers u, v<\/em> explaining that u<\/em> is directly connected to v<\/em> in the power grid (e.g. like #9 is connected to #7 in the example above). Immediately followed by N+1<\/em><\/strong> lines z<\/em> 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.<\/p>\n\n\n\n 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<\/em><\/strong> denotes the number of requests that need to be processed followed by many lines containing comma-separated values in u<\/em>, v<\/em>, z<\/em> format, where u<\/em> is the originating station, v<\/em> is the destination station and z<\/em> is the estimated power loss.<\/p>\n\n\n\n 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”.<\/p>\n\n\n\n You need to write a graph, so instead of rewriting a graph system, I used NetworkX<\/a>.<\/p>\n\n\n\n It was interesting to see a test like that but nothing is perfect and the problems are:<\/p>\n\n\n\n\n
Sample Configuration Input:<\/h3>\n\n\n\n
11\n1,2\n2,3\n1,4\n4,5\n4,6\n1,10\n10,11\n10,12\n1,7\n7,8\n7,9\n0.3\n0.2\n0.8\n0.28\n0.32\n0.17\n0.4\n0.36\n0.1\n0.3\n0.2\n0.05\n3\n3,2,1.1\n8,10,1.36\n3,11,1.8<\/code><\/pre>\n\n\n\nConstraints:<\/h4>\n\n\n\n
\n
Sample Input:<\/h4>\n\n\n\n
3\n3,2,1.1\n8,10,1.36\n3,11,1.8<\/code><\/pre>\n\n\n\nSample Output:<\/h4>\n\n\n\n
REJECTED\nAPPROVED\nAPPROVED<\/code><\/pre>\n\n\n\nMy code<\/h2>\n\n\n\n
from networkx import Graph, shortest_path\n\n\ndef add_edge(n1, n2):\n \"\"\"Add edge between nodes n1 and n2.\"\"\"\n G.add_edge(n1, n2)\n\n\ndef add_attr_cost(node, attr):\n \"\"\"Add attribute 'cost' to the node.\"\"\"\n G.nodes[node]['cost'] = attr\n\n\ndef extract_attr_cost(node):\n \"\"\"Return the value cost for the node.\"\"\"\n return G.nodes[node]['cost']\n\n\ndef find_path(n1, n2):\n \"\"\"Find the path between nodes n1 and n2.\"\"\"\n return shortest_path(G, n1, n2)\n\n\ndef total_cost(n1, n2):\n \"\"\"Do the sum of cost for a transfer between nodes n1 and n2.\"\"\"\n return sum(extract_attr_cost(n) for n in find_path(n1, n2))\n\n\ndef verify_estimated_cost(n1, n2, e):\n \"\"\"Verify if estimated is equal or not to the computed cost.\"\"\"\n print('APPROVED' if total_cost(n1, n2) == float(e)\n else 'REJECTED')\n\n\nG = Graph()\n\nif __name__ == '__main__':\n N = int(input())\n\n for _ in range(N):\n node1, node2 = list(map(int, input().rstrip().split(sep=',')))\n add_edge(node1, node2)\n\n for num in range(1, N+2):\n cost = float(input().rstrip())\n add_attr_cost(num, cost)\n\n nb_requests = int(input())\n for _ in range(nb_requests):\n start, end, estimated = list(map(float,\n input().rstrip().split(sep=',')))\n verify_estimated_cost(start, end, estimated)<\/code><\/pre>\n\n\n\n\n