Unique Paths to Go Home - Google Top Interview Questions
Problem Statement :
You are given a two-dimensional list of integers edges where each element contains [u, v, distance] representing a weighted undirected graph. You are currently at node 0 and your home is the largest node. You can go from u to v if it's immediately connected and the shortest distance from u to home is larger than the shortest distance from v to home.
Return the number of unique paths possible to go from node 0 to home. Mod the result by 10 ** 9 + 7.
Constraints
1 ≤ n ≤ 100,000 where n is the length of edges
0 ≤ distance
Example 1
Input
edges = [
[0, 1, 1],
[1, 2, 1],
[2, 3, 1],
[1, 3, 2]
]
Output
2
Explanation
There are two unique paths to go home:
We can go 0 to 1 then 1 to 2 then 2 to 3
We can go 0 to 1 then 1 to 3
Example 2
Input
edges = [
[0, 1, 1],
[0, 2, 1],
[1, 2, 2]
]
Output
1
Explanation
There is one unique path to go home: go 0 to 2
We can't go through 0 -> 1 -> 2 because the shortest distance from 0 to 2 is smaller than 1 to 2
Solution :
Solution in C++ :
long long dp[100005];
long long dist[100005];
int n;
vector<pair<int, int>> edges[100005];
int solve(vector<vector<int>>& graph) {
// begin graph initialization
n = 0;
for (auto& edge : graph) {
n = max(n, edge[0]);
n = max(n, edge[1]);
}
n++;
for (int i = 0; i < n; i++) edges[i].clear();
for (auto& edge : graph) {
edges[edge[0]].emplace_back(edge[1], edge[2]);
edges[edge[1]].emplace_back(edge[0], edge[2]);
}
// end graph initialization
// begin dijkstra
for (int i = 0; i < n; i++) dist[i] = 1e18;
dist[n - 1] = 0;
priority_queue<pair<long long, long long>> q;
q.emplace(0, n - 1);
vector<int> orderv;
while (q.size()) {
auto [w, v] = q.top();
q.pop();
w *= -1;
if (dist[v] != w) continue;
orderv.push_back(v);
for (auto edge : edges[v]) {
if (dist[edge.first] > dist[v] + edge.second) {
dist[edge.first] = dist[v] + edge.second;
q.emplace(-dist[edge.first], edge.first);
}
}
}
// end dijkstra
// begin path counting
for (int i = 0; i < n; i++) dp[i] = 0;
dp[n - 1] = 1;
const int MOD = 1000000007;
for (int currv : orderv) {
for (auto& edge : edges[currv]) {
if (dist[edge.first] < dist[currv]) {
dp[currv] += dp[edge.first];
dp[currv] %= MOD;
}
}
}
// end path counting
return dp[0];
}
Solution in Java :
import java.util.*;
class Solution {
public int solve(int[][] edges) {
int N = 0;
for (int[] edge : edges) N = Math.max(N, Math.max(edge[0], edge[1]));
N++;
ArrayList<State>[] graph = new ArrayList[N];
for (int i = 0; i < N; i++) graph[i] = new ArrayList<State>();
for (int[] e : edges) {
long w = (long) e[2];
graph[e[0]].add(new State(e[1], w));
graph[e[1]].add(new State(e[0], w));
}
// Dijkstra's Algorithm
long[] distances = new long[N];
Arrays.fill(distances, Long.MAX_VALUE);
distances[N - 1] = 0L;
PriorityQueue<State> pq = new PriorityQueue<State>();
State s = new State(N - 1, 0L);
pq.add(s);
while (!pq.isEmpty()) {
s = pq.poll();
for (State e : graph[s.node]) {
if (distances[e.node] > distances[s.node] + e.dist) {
distances[e.node] = distances[s.node] + e.dist;
pq.add(new State(e.node, distances[e.node]));
}
}
}
State[] vals = new State[N];
for (int i = 0; i < N; i++) vals[i] = new State(i, distances[i]);
Arrays.sort(vals);
long[] ans = new long[N];
ans[N - 1] = 1L;
for (int i = 1; i < N; i++) {
int u = vals[i].node;
for (State e : graph[u]) {
int v = e.node;
if (distances[u] > distances[v])
ans[u] = (ans[u] + ans[v]) % 1000000007;
}
}
return (int) ans[0];
}
static class State implements Comparable<State> {
int node;
long dist;
public State(int n, long d) {
node = n;
dist = d;
}
public int compareTo(State s) {
return Long.compare(dist, s.dist);
}
}
}
Solution in Python :
class Solution:
def solve(self, edges):
MOD = 10 ** 9 + 7
graph = defaultdict(dict)
for u, v, w in edges:
graph[u][v] = graph[v][u] = w
# Find distance from home to nodes with Dijkstra
home = max(graph)
dist = defaultdict(lambda: float("inf"))
dist[home] = 0
pq = [[0, home]]
while pq:
d, node = heappop(pq)
if dist[node] < d:
continue
for nei, w in graph[node].items():
if d + w < dist[nei]:
heappush(pq, [d + w, nei])
dist[nei] = d + w
# DP on topological order
nodes = sorted(graph, key=dist.__getitem__)
dp = defaultdict(int)
dp[home] = 1
for u in nodes:
for v in graph[u]:
if dist[v] > dist[u]:
dp[v] += dp[u]
dp[v] %= MOD
return dp[0]
View More Similar Problems
2D Array-DS
Given a 6*6 2D Array, arr: 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 An hourglass in A is a subset of values with indices falling in this pattern in arr's graphical representation: a b c d e f g There are 16 hourglasses in arr. An hourglass sum is the sum of an hourglass' values. Calculate the hourglass sum for every hourglass in arr, then print t
View Solution →Dynamic Array
Create a list, seqList, of n empty sequences, where each sequence is indexed from 0 to n-1. The elements within each of the n sequences also use 0-indexing. Create an integer, lastAnswer, and initialize it to 0. There are 2 types of queries that can be performed on the list of sequences: 1. Query: 1 x y a. Find the sequence, seq, at index ((x xor lastAnswer)%n) in seqList.
View Solution →Left Rotation
A left rotation operation on an array of size n shifts each of the array's elements 1 unit to the left. Given an integer, d, rotate the array that many steps left and return the result. Example: d=2 arr=[1,2,3,4,5] After 2 rotations, arr'=[3,4,5,1,2]. Function Description: Complete the rotateLeft function in the editor below. rotateLeft has the following parameters: 1. int d
View Solution →Sparse Arrays
There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. Return an array of the results. Example: strings=['ab', 'ab', 'abc'] queries=['ab', 'abc', 'bc'] There are instances of 'ab', 1 of 'abc' and 0 of 'bc'. For each query, add an element to the return array, results=[2,1,0]. Fun
View Solution →Array Manipulation
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array. Example: n=10 queries=[[1,5,3], [4,8,7], [6,9,1]] Queries are interpreted as follows: a b k 1 5 3 4 8 7 6 9 1 Add the valu
View Solution →Print the Elements of a Linked List
This is an to practice traversing a linked list. Given a pointer to the head node of a linked list, print each node's data element, one per line. If the head pointer is null (indicating the list is empty), there is nothing to print. Function Description: Complete the printLinkedList function in the editor below. printLinkedList has the following parameter(s): 1.SinglyLinkedListNode
View Solution →