FastPrep
Problem · Graph

Check Path Presence

Learn this problem
● EasyMicrosoftFULLTIMEOA
See Microsoft hiring insights

Problem statement

You are given an undirected graph consisting of N vertices, numbered from 1 to N, and M edges. The graph is described by two arrays, A and B, both of length M. A pair (A[K], B[K]) for K from 0 to M-1 describes an edge between vertex A[K] and vertex B[K]. Your task is to check whether the given graph contains a path from vertex 1 to vertex N going through all the vertices one by one in increasing order of their numbers. All connections on the path should be direct.

Function

checkPathPresence(N: int, A: int[], B: int[]) → int

Complete the function checkPathPresence in the editor.

checkPathPresence has the following parameters:

  1. 1. N: an integer, the number of vertices
  2. 2. int A[]: an array of integers representing one end of the edges
  3. 3. int B[]: an array of integers representing the other end of the edges

Returns

int: 1 if true there is a path from vertex 1 to vertex N going through all the vertices in increasing order, otherwise 0 (false)

Examples

Example 1

N = 4A = [1, 2, 4, 4, 3]B = [2, 3, 1, 3, 1]return = 1
There is a path 1-2-3-4 using the edges (1,2), (2,3), and (4,3).

Constraints

🍏🍏

More Microsoft problems

drafts saved locally
public int checkPathPresence(int N, int[] A, int[] B) {
  // write your code here
}
N4
A[1, 2, 4, 4, 3]
B[2, 3, 1, 3, 1]
expected1
checking account