Common Reachable Node - Facebook Top Interview Questions
Problem Statement :
You are given a two-dimensional list of integers edges representing a directed graph and integers a and b. Each element in edges contains [u, v] meaning there's an edge from u to v.
Return whether there's some node c such that we can go from c to a and c to b.
Constraints
1 ≤ n ≤ 100,000 where n is the length of edges
Example 1
Input
edges = [
[0, 4],
[4, 3],
[1, 2],
[0, 1],
[0, 2],
[1, 1]
]
a = 2
b = 3
Output
True
Explanation
We can reach 2 and 3 from 0
Example 2
Input
edges = [
[0, 1],
[1, 2],
[1, 3],
[1, 1],
[4, 5]
]
a = 2
b = 4
Output
False
Explanation
2 and 4 are on different connected components.
Example 3
Input
edges = [
[0, 0]
]
a = 0
b = 0
Output
True
Solution :
Solution in C++ :
vector<int> adj[100001];
vector<bool> vis(100001, false);
unordered_map<int, int> mp;
bool flag;
void dfs(int curr) {
vis[curr] = true;
mp[curr]++;
if (mp[curr] > 1) {
flag = true;
return;
}
for (int node : adj[curr])
if (!vis[node]) dfs(node);
}
bool solve(vector<vector<int>>& edges, int a, int b) {
int n = edges.size() + 1;
if (a == b) return true;
for (int i = 0; i < n; i++) adj[i].clear();
for (int i = 0; i < n - 1; i++) {
adj[edges[i][1]].push_back(edges[i][0]);
}
mp.clear();
flag = false;
for (int i = 0; i < n; i++) vis[i] = false;
dfs(a);
for (int i = 0; i < n; i++) vis[i] = false;
dfs(b);
return flag;
}
Solution in Java :
import java.util.*;
class Solution {
static ArrayList<Integer>[] transpose;
static int N;
public boolean solve(int[][] edges, int a, int b) {
N = 0;
for (int[] e : edges) N = Math.max(N, Math.max(e[0], e[1]));
N++;
// build the transpose of the graph
transpose = new ArrayList[N];
for (int i = 0; i < N; i++) transpose[i] = new ArrayList<Integer>();
for (int[] e : edges) transpose[e[1]].add(e[0]);
// find ancestors of A and B
boolean[] visA = bfs(a);
boolean[] visB = bfs(b);
// cehck if there is any overlap
for (int i = 0; i < N; i++) {
if (visA[i] && visB[i]) {
// node i is a common ancestor!
return true;
}
}
return false;
}
public boolean[] bfs(int root) {
ArrayDeque<Integer> q = new ArrayDeque<Integer>();
boolean[] vis = new boolean[N];
vis[root] = true;
q.add(root);
while (!q.isEmpty()) {
int n = q.pollFirst();
for (int p : transpose[n]) {
if (!vis[p]) {
vis[p] = true;
q.add(p);
}
}
}
return vis;
}
}
Solution in Python :
class Solution:
def solve(self, edges, a, b):
graph = defaultdict(set)
for u, v in edges:
graph[v].add(u)
def explore(root):
queue = [root]
seen = {root}
for node in queue:
for nei in graph[node] - seen:
seen.add(nei)
queue.append(nei)
return seen
return bool(explore(a) & explore(b))
View More Similar Problems
Array-DS
An array is a type of data structure that stores elements of the same type in a contiguous block of memory. In an array, A, of size N, each memory location has some unique index, i (where 0<=i<N), that can be referenced as A[i] or Ai. Reverse an array of integers. Note: If you've already solved our C++ domain's Arrays Introduction challenge, you may want to skip this. Example: A=[1,2,3
View Solution →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 →