Trees Height Solution Amazon OA SDE

Trees Height Solution Amazon OA SDE

There are N trees in Jon’s backyard and height of tree i is h[i]. Jon doesn’t like the appearance of it and is planning to increase and decrease the height of trees such that the new heights are in strictly increasing order. Every day he can pick one tree and increase or decrease the height by 1 unit. Heights can be 0 or even negative (it’s a magical world).

Jon has guests coming after X days, hence he wants to know if it is possible to make heights strictly increasing in no more than X days?

Also See: Amazon OA Online Assessment 2021 Questions and Answers

Input format:

First line contains one integer N<=2000 number of trees, X<=5000 number of days Jon has.
Second line contains N space separated integers where ith integer is h[i]

Output Format:

YES or NO, if it is possible to make tree heights in strictly ascending order in no more than X days, if YES, also print the number of days it will take.

Sample Input 1:

5 13
5 4 3 2 1

Sample Output 1:

YES 12

Explanation:

For the first sample the final array will look like 1 2 3 4 5
Hence the number of days required will be 12.

Sample Input 2:

7 10
7 1 4 10 5 8 12

Sample Output 2:

NO

Solution

Program Python:

def solve(nums, X):
    N = len(nums)
    minn = min(nums)
    # Observe that making any element of our array less than the minimum or more than maximum would result in extra useless operation, hence j can be in the range of [min(nums), max(nums)], both inclusive. Here we can subtract min values from each element in array just to make the code more readable
    for i in range(len(nums)):
        nums[i] -= minn
    maxn = max(nums) + 1 
    
    # dp[i][j] is the minimum number of operations required to make nums[:i+1](till ith index) strictly sorted with nums[i] == j.
    # Hence, our recurrence relation would be: dp[i][j] = abs(nums[i]-j) + min(dp[i-1][:j])
    # This 2D table can be easily converted to 1D dp[j], since we only ever need to know the i-1th state for computing ith state.
    dp = [[float('inf')]*(maxn) for _ in range(N)]

    # Initialize base case
    for j in range(maxn):
        dp[0][j] = abs(nums[0]-j)
    
    for i in range(1, len(nums)):
        min_so_far = min(dp[i-1][:i])
        for j in range(i, maxn): # starting from i to ensure strictly increasing order
            dp[i][j] = abs(nums[i]-j) + min_so_far
            min_so_far = min(min_so_far, dp[i-1][j])
    return "YES " + str(min(dp[-1])) if min(dp[-1]) <= X else "NO"
    

n,m=map(int,input().split())
l=list(map(int,input().split()))
print(solve(l,m))

Also See: AMCAT Study Materials, Preparation Guide

Also See: Microsoft Online Assessment Questions and Solution

Amazon Online Assessment Questions:

• Robot Bounded in Box
• Number Game
• Find All Combination of Numbers Sum to Target / Shopping Options
• Fill the Truck
• Music Pairs
• Slowest key
• Five Star Seller
• Split String Into Unique Primes
• Storage Optimization
• Minimum Difficulty of a Job Schedule
• Autoscale Policy, Utilization Check
• Optimal Utilization
• Merge Two Sorted Lists
• Two Sum Unique Pairs
• Shopping Patterns
• Reorder Data in Log Files
• Top K Frequent Words
• Trees Height
• Counting Binary Substrings Amazon OA Solution
• Grid Connections Amazon OA Solution
• Shipment Imbalance Amazon OA Solution
• Max Profit Amazon OA Solution
• Find Lowest Price Amazon OA Solution
• Simple Cipher Amazon OA Solution
• Decode String Frequency Amazon OA Solution
• Valid Discount Coupons Amazon OA Solution
• Count Maximum Teams Amazon OA Solution
• Minimum Coin Flips Amazon OA Solution