Last Updated: 1 Oct, 2020
Find Slope
Easy
Asked in companies
Given a linked list, whose nodes represent the coordinates of the cartesian plane. Find the minimum and the maximum slope of simultaneous points of coordinates.
Linked List : P1(X1, Y1) -> P2( X2, Y2) -> P3(X3, Y3).
Here P1(point1) corresponds to coordinates (X1, Y1), similarly P2(point2) corresponds to coordinates (X2, Y2).
Your task is to find the Maximum(Slope(P1, P2), Slope(P2, P3)) and Minimum(Slope(P1, P2), Slope(P2, P3)).
Note :
You only need to return the starting node for minimum and maximum slope. So if slope(P1, P2) is maximum, just return P1.
In case of more than one possible solution return the first occurring solution.
Input Format:
The first line of input contains an integer 'T' representing the number of Test cases.
The first line of each test case contains linked list elements/nodes separated by space and terminated by -1. Each node would consist of 'X' and 'Y' coordinates.
Output Format:
For each test case, print the Maximum(Slope(P1, P2), Slope(P2, P3)) and Minimum(Slope(P1, P2), Slope(P2, P3)).
Note
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
2 <= N <= 10^3
-10^9 <= X <= 10^9
-10^9 <= Y <= 10^9
Where 'N' denotes the length of the linked list and 'X' and 'Y' denote the coordinates of the 'X' and 'Y' axis respectively.
Time Limit: 1 sec
Approaches
- Initially maintain two variables, one for minimum slope and one for maximum slope.
- Also, create variables to store coordinates corresponding to the minimum and maximum slope.
- Set minimum slope variable value to maximum integer value and maximum slope variable to minimum integer value possible.
- Now, traverse recursively through each pair of consecutive nodes using a helper function.
- Set the base condition as when ‘node->next’ is NULL.
- Calculate the slope between them and store it into a temporary variable.
- Slope would be ‘(node2.y - node1.y)/(node2.x - node1.x)’ ,where ‘node2’ and ‘node1’ are two consecutive pair of nodes in linked list.
- Now compare the temporary variable with the minimum and maximum variables.
- If the temporary variable is less than the minimum variable, set the minimum variable to the temporary variable and replace the coordinates corresponding to the minimum slope with that node.
- Also if the temporary variable is greater than the maximum variable, set the maximum variable to the temporary variable and replace the coordinates corresponding to the maximum slope with that node.
- Now recursively call for the next node.
- Return the minimum slope coordinates and the maximum slope coordinates.
- Initially maintain two variables, one for minimum slope and one for maximum slope.
- Also, create variables to store coordinates corresponding to the minimum and maximum slope.
- Set minimum slope variable value to maximum integer value and maximum slope variable to minimum integer value possible.
- Now, Traverse through each pair of consecutive nodes and calculate the slope between them and store it into a temporary variable.
- Slope would be ‘(node2.y - node1.y) / (node2.x - node1.x)’, where ‘node2’ and ‘node1’ are two consecutive pairs of nodes in the linked list.
- Now compare the temporary variable with the minimum and maximum variables.
- If the temporary variable is less than the minimum variable, set the minimum variable to the temporary variable and replace the coordinates corresponding to the minimum slope with that node.
- Also, if the temporary variable is greater than the maximum variable, set the maximum variable to the temporary variable and replace the coordinates corresponding to the maximum slope with that node.
- Repeat the above process for all consecutive pairs of nodes.
- Return the minimum slope coordinates and the maximum slope coordinates.