Microsoft Online Assessment (OA) - Widest Path Without Trees
There are N trees (numbered from 0 to N-1) in a forest. The K-th tree is located at coordinates (X[K], Y[K]).
We want to build the widest possible vertical path, such that there is no tree on it.
The path must be built somewhere between a leftmost and a rightmost tree, which means that the width of the path cannot be infinite.
What is the width of the widest possible path that can be built?
Write a function:
1def solution(X, Y)
that, given two arrays X and Y consisting of N integers each, denoting the positions of trees,
returns the widest possible path that can be built.
Example 1:
Input: X = [5,5,5,7,7,7], Y=[3,4,5,1,3,7]
Output: 2
Example 2:
Input: X = [6,10,1,4,3], Y=[2,5,3,1,6]
Output: 4
Example 3:
Input: X = [4,1,5,4], Y=[4,5,1,3]
Output: 3
Try it yourself
Implementation
1from typing import List
2
3def widest_path(x: List[int], y: List[int]) -> int:
4 difference = 0
5 sortedX = sorted(x)
6 for i in range(0, len(sortedX) - 1):
7 diff = sortedX[i + 1] - sortedX[i]
8 if diff > difference:
9 difference = diff
10 return difference
11
12if __name__ == '__main__':
13 x = [int(x) for x in input().split()]
14 y = [int(x) for x in input().split()]
15 res = widest_path(x, y)
16 print(res)
171import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7 public static int widestPath(List<Integer> x, List<Integer> y) {
8 int maxWidth = 0;
9 x.sort(null);
10 for (int i = 0; i < x.size() - 1; i++) {
11 maxWidth = Math.max(maxWidth, (x.get(i + 1) - x.get(i)));
12 }
13 return maxWidth;
14 }
15
16 public static List<String> splitWords(String s) {
17 return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
18 }
19
20 public static void main(String[] args) {
21 Scanner scanner = new Scanner(System.in);
22 List<Integer> x = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
23 List<Integer> y = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
24 scanner.close();
25 int res = widestPath(x, y);
26 System.out.println(res);
27 }
28}
291function widestPath(x, y) {
2 let maxWidth = 0;
3 x = x.sort(function(a, b) {
4 return a - b
5 });
6 for (let i = 0; i < x.length - 1; i++) {
7 maxWidth = Math.max(maxWidth, (x[i + 1] - x[i]));
8 }
9 return maxWidth;
10}
11
12function splitWords(s) {
13 return s == "" ? [] : s.split(' ');
14}
15
16function* main() {
17 const x = splitWords(yield).map((v) => parseInt(v));
18 const y = splitWords(yield).map((v) => parseInt(v));
19 const res = widestPath(x, y);
20 console.log(res);
21}
22
23class EOFError extends Error {}
24{
25 const gen = main();
26 const next = (line) => gen.next(line).done && process.exit();
27 let buf = '';
28 next();
29 process.stdin.setEncoding('utf8');
30 process.stdin.on('data', (data) => {
31 const lines = (buf + data).split('\n');
32 buf = lines.pop();
33 lines.forEach(next);
34 });
35 process.stdin.on('end', () => {
36 buf && next(buf);
37 gen.throw(new EOFError());
38 });
39}
40Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.