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)
17

1import 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}
29

1function 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}
40

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Introduction

DFS on Tree

Binary Search Tree

Combinatorial Search

Memoization

Pruning

Dedup

Additional Practices

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Sequence

Grid

Dynamic number of subproblems

Partition

Game Theory

Interval

Two Sequences

0-1 Knapsack

Bitmask

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Composite Patterns

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Microsoft Online Assessment (OA) - Widest Path Without Trees

Example 1:

Example 2:

Example 3:

Try it yourself

Implementation