Microsoft OA Min Steps to Make Piles Equal Height

Microsoft Online Assessment, Min Steps to Make Piles Equal Height

Min Steps to Make Piles Equal Height

Given N piles of equal or unequal heights. In one step, You can remove any number of boxes from the pile which has the maximum height and try to make it equal to the one which is just lower than the maximum height of the stack. Determine the minimum number of steps required to make all of the piles equal in height.

Also See: Microsoft Online Assessment Questions and Solution

Example 1:

Input: [5, 2, 1]

Output: 3

Explanation:

Step 1: reducing 5 -> 2 = [2, 2, 1] 

Step 2: reducing 2 -> 1 = [2, 1, 1] 

Step 3: reducing 2 -> 1 = [1, 1, 1]

Solution

Program Python:

from typing import Counter, List
def min_steps(nums: List[int]) -> int:
    cnt = Counter(nums)
    nums = sorted(cnt.keys(), reverse=True)
    k, ans = 0, 0
    for x in nums[:-1]:
        k += cnt[x]
        ans += k
    return ans
if __name__ == '__main__':
    nums = [int(x) for x in input().split()]
    res = min_steps(nums)
    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 minSteps(List<Integer> nums) {
        int nums_size = nums.size();
        if (nums_size < 2) {
            return 0;
        }
        nums.sort(null);
        int sum = 0;
        for (int i = 1; i < nums_size; ++i) {
            if (nums.get(nums_size - i - 1) != nums.get(nums_size - i)) {
                sum += i;
            }
        }
        return sum;
    }
    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> nums = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
        scanner.close();
        int res = minSteps(nums);
        System.out.println(res);
    }
}

Program Javascript:

const nums_size = nums.length;
    if (nums_size < 2) {
        return 0;
    }
    nums.sort();
    let sum = 0;
    for (let i = 1; i < nums_size; ++i) {
        if (nums[nums_size - i - 1] !== nums[nums_size - i]) {
            sum += i;
        }
    }
    return sum;
}
function splitWords(s) {
    return s == "" ? [] : s.split(' ');
}
function* main() {
    const nums = splitWords(yield).map((v) => parseInt(v));
    const res = minSteps(nums);
    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());
    });
}

Program C++:

Lets visualize the piles, lets use A instead of boxes

5: AAAAA

2: AA

1: A

On the first step we cut 5: AAAAA to 2: AA

2: AA

2: AA

1: A

On the second step we cut first strings of 2: AA to 1: A

1: A

1: AA

1: A

On the third step we cut first strings of 2: AA to 1: A

1: A

1: A

1: A

If we will have two piles with the same length, for example:

5: AAAAA

5: AAAAA

1: A

On the first step we cut first 5: AAAAA to 1: A:

1: A

5: AAAAA

1: A

On the second step we cut second 5: AAAAA to 1: A:

1: A

1: A

1: A

In other words in order to determine the minimum number of steps required to make all of the piles equal in height we need to sort the array and count how many piles with different height exists and sum them up.

The C++ code:

int solution(vector<int> v) {
    int v_size = v.size();
    if(v_size < 2) { return 0; }
    std::sort(v.begin(), v.end());
    int sum = 0;
    for (int i = 1; i < v_size; ++i) {
        if (v[v_size - i - 1] != v[v_size - i]) {
            sum += i;
        }
    }
    return sum;
}

Complexity of this solution is O(N* Log(N)) where N is length of the string but I believe there is a solution with linear complexity I just can’t process well all corner cases.

Also See: AMCAT Study Materials, Preparation Guide

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

Microsoft Online Assessment 2021 Questions

2 thoughts on “Microsoft OA Min Steps to Make Piles Equal Height”

Leave a Comment