Morning Walk

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
0 upvote
Asked in company
Dunzo

Problem statement

Every morning, Alex and Bob go for their regular morning walk. There are some fixed paths for both of them. Alex starts at point A and goes till point B, and Bob starts at point C and goes till point D. Given the values of A, B, C, and D, can you tell whether they will meet at a point or intersect or never meet each other?

You will output a string containing:

“Never” if they never meet.
“Point” if they meet at a point.
“Intersect” if they intersect each other.

For Example:

For A = 1, B = 3, C = 5, D = 10


They will never meet as their paths have no common points.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.
The first line of each test case contains four space-separated integers representing A, B, C, D.
Output Format: 
For each test case, print a string according to the above conditions.
Output for each test case will be printed in a separate line.
Note: 
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10^4
-10^6 <= A, B, C, D <= 10^9

Time Limit: 1 sec.
Sample Input 1:
2
8 10 1 8
1 10 5 8
Sample Output 1:
Point
Intersect
Explanation For Sample Output 1:
For the first test case,
Alex will walk from 8 to 10 and Bob will walk from 1 to 8, and they both will meet at 8.
So, the output will be Point.

For the second test case.
Alex will walk from 1 to 10 and Bob will walk from 5 to 8, so they will intersect each other as the paths have intersecting points.
So the output will be Intersect.
Sample Input 2:
2
1 10 8 15
1 5 6 10
Sample Output 2:
Intersect
Never
Hint

Try to figure out whether the paths are intersecting or not.

Approaches (1)
Observation and Maths

Consider the paths are in the x-axis. Let us modify the given input such that the starting points of both the person are smaller than their corresponding ending points.

Now if the minimum value of the ending points is greater than the maximum value of starting points, then the paths will be intersecting.
 

Algorithm:

 

  • Let ‘AlexStart’, ‘AlexEnd’, ‘BobStart’, ‘BobEnd’ are the modified values of the given input.
  • ‘AlexStart’ will be the minimum of A and B, and ‘AlexEnd’ will be the maximum of them.
  • ‘BobStart’ will be the minimum of C and D, and ‘BobEnd’ will be the maximum of them.
  • Let ‘END’ be the minimum of both the ending points and ‘START’ be the maximum of both the starting points.
  • If they are equal then the output will be “Point”.
  • Else if ‘END’ is greater than ‘START’, then the output will be “Intersecting”.
  • Else, the output will be “Never”.
Time Complexity

O(1).

 

Constant time is used.

Space Complexity

O(1).

 

Constant space is used.

Code Solution
(100% EXP penalty)
Morning Walk
Full screen
Console