Hi5 Interview Question for Software Developers
- 0of 0 votes
We are given a graph of N nodes. (1-N), where each node has exactly 1 directed edge to some node (this node can be the same node).
We need to answer the queries of type : A, B, which asks time required when 2 objects collide if one start at A and other start at B. Both moves 1 hop in 1 sec. If it's not possible for them to collide time would be -1.
Time : from X -> to Y : 1 hop = 1 second.
N, Q <= 10^5 (number of nodes, number of queries).
Example : for given graph
A -> B -> C -> D -> E ^ | K <- F
Query(A, E) : 3 seconds, as at time t = 3 secs they both will be on node D.- tusharrawat831 December 02, 2021 in United States
Query(C, D) : -1 seconds, as they will never collide.
Brute force will take O(Q * N) time. Can we do better than that?
| Report Duplicate | Flag | PURGE
Hi5 Software Developer Programming Skills
Interview Type: Phone Interview