# Microsoft OA Widest Path Without Trees Solution

Page Contents

## Microsoft OA Widest Path Without Trees Solution

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.

Also See: Microsoft Online Assessment Questions and Solution

What is the width of the widest possible path that can be built?

Write a function:

`def 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`

## Solution:

Program Python:

```from typing import List
def widest_path(x: List[int], y: List[int]) -> int:
difference = 0
sortedX = sorted(x)
for i in range(0, len(sortedX) - 1):
diff = sortedX[i + 1] - sortedX[i]
if diff > difference:
difference = diff
return difference
if __name__ == '__main__':
x = [int(x) for x in input().split()]
y = [int(x) for x in input().split()]
res = widest_path(x, y)
print(res)```

Program Java:

```import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
class Solution {
public static int widestPath(List<Integer> x, List<Integer> y) {
int maxWidth = 0;
x.sort(null);
for (int i = 0; i < x.size() - 1; i++) {
maxWidth = Math.max(maxWidth, (x.get(i + 1) - x.get(i)));
}
return maxWidth;
}
public static List<String> splitWords(String s) {
return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
List<Integer> x = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
List<Integer> y = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
scanner.close();
int res = widestPath(x, y);
System.out.println(res);
}
}```

Program JavaScript:

```function widestPath(x, y) {
let maxWidth = 0;
x = x.sort(function(a, b) {
return a - b
});
for (let i = 0; i < x.length - 1; i++) {
maxWidth = Math.max(maxWidth, (x[i + 1] - x[i]));
}
return maxWidth;
}
function splitWords(s) {
return s == "" ? [] : s.split(' ');
}
function* main() {
const x = splitWords(yield).map((v) => parseInt(v));
const y = splitWords(yield).map((v) => parseInt(v));
const res = widestPath(x, y);
console.log(res);
}
class EOFError extends Error {}
{
const gen = main();
const next = (line) => gen.next(line).done && process.exit();
let buf = '';
next();
process.stdin.setEncoding('utf8');
process.stdin.on('data', (data) => {
const lines = (buf + data).split('\n');
buf = lines.pop();
lines.forEach(next);
});
process.stdin.on('end', () => {
buf && next(buf);
gen.throw(new EOFError());
});
}
```

Also See: AMCAT Study Materials, Preparation Guide

Also See: Amazon OA 2021 (Online Assessment) Questions Preparation

Microsoft Online Assessment 2021 Questions