Hackerrank TestCases are incorrect? Dijkstra Shortest Reach 2

Question

Hackerrank - Dijkstra Shortest Reach 2

I got stuck at TestCase 7 (the only one I failed) which I thought was my fault. I downloaded the test case and checked against my output generated.

I do git diff and I can't see any difference between them. Can you help me verify what happened to my code?

Or perhaps if there isn't a catch in my code, I would like to alter the question:

Does HackerRank Platform often has bugs?

I often encountered an obscure failure (usually last one or two out of 13 testcases) when doing a HackerRank Challenge for my job interview, hence failed multiple times at these. I wonder if any of you has similar experience. My suspicion is that when I checked my submitted code with friends, we can't find any edge cases or bugs. It should be perfect. As programmer who had been coding in LeetCode, this terrifies me and I started to train on HackerRank.

Please advise. Thanks

Resource:

• Hackerrank Problems: https://www.hackerrank.com/challenges/dijkstrashortreach/problem
• Input and Output for TestCase7: https://drive.google.com/drive/u/0/folders/13Qa0k1mIZ5hVW32bRQa15_s8rH7f0-v4

P.S in the google drive folder, I attached my output: output_me.txt and the ground truth output: output.txt. I did add new lines for both output (initially, all answer are in one long line, added new lines to make it easier to read.)

Code:

import os
from collections import defaultdict
from heapq import heappop, heappush

MAX_INT = 2**31


# Build Graph
def buildGraph(edges):
    graph = defaultdict(list)
    trackMinEdge = {}

    # build min edges from u - v (adjacent)
    # for handling duplicate edges
    for u, v, weight in edges:
        u, v = min(u, v), max(u, v)
        if (u, v) in trackMinEdge:
            minWeight = trackMinEdge[(u, v)]
            if minWeight <= weight:
                # do not update
                continue
        # only update if (u, v) not in trackMinWeight
        # or the new weight is smaller than minWeight
        trackMinEdge[(u, v)] = weight

    # build graph from minimum adjancent edge
    for u, v in trackMinEdge:
        weight = trackMinEdge[(u, v)]
        graph[u].append((weight, v))
        graph[v].append((weight, u))

    return graph

# DJIKSTRA
def djikstra(n, graph, src, dest=None):
    dists = {}

    # setups
    seen = set()
    queue = [(0, src)]
    dists[src] = 0
    while queue:
        dist_u, u = heappop(queue)
        if u in seen: continue

        seen.add(u)
        for weight, v in graph.get(u, []):
            if v in seen: continue

            alt = dists[u] + weight
            if alt < dists.get(v, MAX_INT):
                dists[v] = alt
                heappush(queue, (alt, v))

    return dists


# Complete the shortestReach function below.
def shortestReach(n, edges, src):
    graph = buildGraph(edges)

    # edge cases: src not connected to any node
    if not (src in graph):
        return [-1 for _ in range(n-1)] 

    dists = djikstra(n, graph, src)

    distsTable = []
    for i in range(1, n+1):
        if i in dists and i != src:
            distsTable.append(dists[i])
        elif not (i in dists):
            distsTable.append(-1)

    return distsTable


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w+')

    t = int(input())

    for t_itr in range(t):
        nm = input().split()

        n = int(nm[0])

        m = int(nm[1])

        edges = []

        for _ in range(m):
            edges.append(list(map(int, input().rstrip().split())))

        s = int(input())

        result = shortestReach(n, edges, s)

        fptr.write(' '.join(map(str, result)))
        fptr.write('\n')

    fptr.close()

Regards,

Me

Answer 1

I tried your code and it actually works correctly for Test Case#7 on PyCharm - actual output matches the one in the expected output. However the same code is failing on Hackerrank due to Runtime Error. Why can it happen?

According to Hackerrank FAQ

Runtime error/Segmentation Fault. Your code terminated unexpectedly. Did you overrun your array? Is your code trying to divide by zero?

Obviously, it's not because we divide something by 0 since it works locally. What else? According to Hackerrank Environment for Python there's a memory limit of 512 Mb for solutions.

So, I decided to measure the memory usage for your solution using tracemalloc module.

import tracemalloc
tracemalloc.start()
...
# <solution code here>
...
print("Current usage: %d, Peak usage: %d" % tracemalloc.get_traced_memory())

Output

Current usage: 549627153, Peak usage: 550966939

As you can see, it's actually above the limit of 512 Mb and that's why you can have this Runtime Error. Hence, try to reduce the space complexity for your solution.

I also noticed another problem - if you measure your time complexity using the time module then it takes more than 40 seconds for Test Case#7 to complete. So, it can be your next issue if you fix the space complexity issue first.

And finally, no, there's no bug on Hackerrank here - my Python solution has passed all the tests.

UPDATE

As asked by @Daniel (author of the question) I'm providing my optimised version of the solution that passes all the tests on Hackerrank.

# Complete the shortestReach function below.
def shortestReach(n, distanceMatrix, s):
    queue = list()
    queue.append(s)

    minDistances = [-1] * (n + 1)
    minDistances[s] = 0

    while queue:
        currentNode = queue.pop(0)

        for neighbor in distanceMatrix[currentNode]:
            newDistance = minDistances[currentNode] + distanceMatrix[currentNode][neighbor]
            prevDistance = minDistances[neighbor]
            if minDistances[neighbor] == -1:
                minDistances[neighbor] = newDistance
            else:
                minDistances[neighbor] = min(newDistance, minDistances[neighbor]) 

            if prevDistance != minDistances[neighbor]:
                queue.append(neighbor)      

    del minDistances[s]
    del minDistances[0]
    print (' '.join(map(str, minDistances)))

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

    for t_itr in range(t):
        nm = input().split()

        n = int(nm[0])

        m = int(nm[1])

        distanceMatrix = [dict() for _ in range(n + 1)]
        for _ in range(m):
            edge = list(map(int, input().rstrip().split()))
            i = edge[0]
            j = edge[1]
            weight = edge[2]
            if i not in distanceMatrix[j]:
                distanceMatrix[i][j] = distanceMatrix[j][i] = weight    
            else:
                distanceMatrix[i][j] = distanceMatrix[j][i] = min(weight, distanceMatrix[i][j])

        s = int(input())

        shortestReach(n, distanceMatrix, s)

There's no reason for using a heap here - queue is completely enough. The only criterium of adding a node to queue is if its distance has changed at the current step.