Microsoft OA Widest Path Without Trees Solution

Microsoft OA Widest Path Without Trees Solution

There are N trees in the forest (numbered from 0 to N-1). The Kth tree is located at coordinates (X[k], Y[k]).
We want to build the largest possible vertical path so that there is no tree. The path must be established somewhere between the leftmost tree and the rightmost tree, which means that the width of the path is not infinite.

Also See: Microsoft Online Assessment Questions and Solution

Write a function:
public static Integer solution(int[] X, int[] Y), given the N integers to form the X and Y of the array, they indicate the position of the tree, then return the most constructable The width of the wide path.

Example

Given X=[1,8,7,3,4,1,8] , Y=[6,4,1,8,5,1,7] , the function should return 3.

Solution:

Program Java: Widest Path Without Trees in Java

public static void main(String[] args) {
        int[] M = {1, 8, 7, 3, 4, 1, 8};
        int[] N = {6, 4, 1, 8, 5, 1, 7};
        System.out.println(solution2(M, N));
        int[] M1 = {5, 5, 5, 7, 7, 7};
        int[] N1 = {3, 4, 5, 1, 3, 4};
        System.out.println(solution2(M1, N1));
        int[] M2 = {6, 10, 1, 4, 4};
        int[] N2 = {2, 5, 3, 1, 6};
        System.out.println(solution2(M2, N2));
        int[] M3 = {4, 1, 5, 4};
        int[] N3 = {4, 5, 1, 3};
        System.out.println(solution2(M3, N3));

    }

    public static Integer solution2(int[] X, int[] Y) {

        int maxX = 0;
        int maxY = 0;
        ArrayList<Integer> X = new ArrayList<>();
        ArrayList<Integer> Y = new ArrayList<>();

        for (int i : X) {
            X.add(i);
        }

        for (int i : Y) {
            Y.add(i);
        }

        Collections.sort(X);
        Collections.sort(Y);

        for (int i = 1; i < X.size(); i++) {
            int j = X.get(i) - X.get(i - 1);
            maxX = j >= maxX ? j : maxX;
        }

        for (int i = 1; i < Y.size(); i++) {
            int j = Y.get(i) - Y.get(i - 1);
            maxY = j >= maxY ? j : maxY;
        }

        return maxX >= maxY ? maxX : maxY;
    }

Also See: AMCAT Study Materials, Preparation Guide

Also See: Amazon OA Online Assessment 2021 Questions and Answers

Microsoft Online Assessment 2021 Questions

Leave a Comment