Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 270
Good morning! Here's your coding interview problem for today.

This problem was asked by Twitter.

A network consists of nodes labeled 0 to N. You are given a list of edges `(a, b, t)`, describing the time _t_ it takes for a message to be sent from node _a_ to node _b_. Whenever a node receives a message, it immediately passes the message on to a neighboring node, if possible.

Assuming all nodes are connected, determine how long it will take for every node to receive a message that begins at node 0.

For example, given `N = 5`, and the following edges:
```
edges = [
    (0, 1, 5),
    (0, 2, 3),
    (0, 5, 4),
    (1, 3, 8),
    (2, 3, 1),
    (3, 5, 10),
    (3, 4, 5)
]
```
You should return `9`, because propagating the message from `0 -> 2 -> 3 -> 4` will take that much time.

Pull request:
Day270
Resolves #548.

Patch:
diff --git a/README.md b/README.md
index 287c8ae..4c3e462 100644
--- a/README.md
+++ b/README.md
@@ -274,3 +274,4 @@ problems from
 * [Day 266](https://github.com/vaskoz/dailycodingproblem-go/issues/542)
 * [Day 268](https://github.com/vaskoz/dailycodingproblem-go/issues/544)
 * [Day 269](https://github.com/vaskoz/dailycodingproblem-go/issues/547)
+* [Day 270](https://github.com/vaskoz/dailycodingproblem-go/issues/548)
diff --git a/day270/problem.go b/day270/problem.go
new file mode 100644
index 0000000..6a12ba8
--- /dev/null
+++ b/day270/problem.go
@@ -0,0 +1,69 @@
+package day270
+
+import (
+	"container/heap"
+)
+
+// Edge represents a directed edge from a start to an end with a time cost.
+type Edge struct {
+	Start, End, Time int
+}
+
+type nodeVisit struct {
+	id   int
+	time int
+}
+type priorityQueue []nodeVisit
+
+// TimeAllNodesReceiveMessage returns the time required for all edges to
+// receive the message originating from node '0'.
+// Nodes are from 0 to N inclusive.
+func TimeAllNodesReceiveMessage(n int, edges []Edge) int {
+	graph := make(map[int]map[int]int)
+	for _, edge := range edges {
+		if _, exists := graph[edge.Start]; !exists {
+			graph[edge.Start] = make(map[int]int)
+		}
+		graph[edge.Start][edge.End] = edge.Time
+	}
+	totalTime := 0
+	visited := make(map[int]struct{})
+	visited[0] = struct{}{}
+	pq := make(priorityQueue, n+1)
+	heap.Push(&pq, nodeVisit{0, 0})
+	for len(visited) != n+1 {
+		next := heap.Pop(&pq).(nodeVisit)
+		visited[next.id] = struct{}{}
+		totalTime = next.time
+		for node, time := range graph[next.id] {
+			if _, seen := visited[node]; seen {
+				continue
+			}
+			heap.Push(&pq, nodeVisit{node, next.time + time})
+		}
+	}
+	return totalTime
+}
+
+func (pq priorityQueue) Len() int { return len(pq) }
+
+func (pq priorityQueue) Less(i, j int) bool {
+	return pq[i].time < pq[j].time
+}
+
+func (pq priorityQueue) Swap(i, j int) {
+	pq[i], pq[j] = pq[j], pq[i]
+}
+
+func (pq *priorityQueue) Push(x interface{}) {
+	item := x.(nodeVisit)
+	*pq = append(*pq, item)
+}
+
+func (pq *priorityQueue) Pop() interface{} {
+	old := *pq
+	n := len(old)
+	item := old[n-1]
+	*pq = old[0 : n-1]
+	return item
+}


Test patch:
diff --git a/day270/problem_test.go b/day270/problem_test.go
new file mode 100644
index 0000000..ee24301
--- /dev/null
+++ b/day270/problem_test.go
@@ -0,0 +1,29 @@
+package day270
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	n          int
+	edges      []Edge
+	timeForAll int
+}{
+	{5, []Edge{{0, 1, 5}, {0, 2, 3}, {0, 5, 4}, {1, 3, 8}, {2, 3, 1}, {3, 5, 10}, {3, 4, 5}}, 9},
+}
+
+func TestTimeAllNodesReceiveMessage(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := TimeAllNodesReceiveMessage(tc.n, tc.edges); result != tc.timeForAll {
+			t.Errorf("Expected %v, got %v", tc.timeForAll, result)
+		}
+	}
+}
+
+func BenchmarkTimeAllNodesReceiveMessage(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			TimeAllNodesReceiveMessage(tc.n, tc.edges)
+		}
+	}
+}