Panda Guru LogoPanda
Guru
Panda Guru LogoPanda
Guru

Microsoft OA

10/9/2024
Open in leetcode

Round 1

Questions:

  1. Easy Question: Given a list of stacks (just a number): each stack has the following operation: every 2 blocks get converted over to 1 and pushed to the next stack. Your goal is to calculate the number of stacks of 1 leftover by the time you complete all possible stack operations.

    Example: If given [5,3,1]:

    • 4 from the first stack can get converted into 2 to the next stack with one left over.
    • 2 + 3 = 5 which follows the same, one left over with the 4 converted into 2 for the next stack.
    • 2 + 1 = 3 which makes two blocks get converted into 1 into the next stack.
    • 1 + 0 = 1, no possible operation.

    Thus, in this example, there are 4 stacks with 1 block leftover, so the answer is 4.

  2. Medium Question: You are given a list of houses, such that A[k] corresponds to the amount of energy needed for house k. You will be installing two types of solar panels:

    • Type 1: a solar panel which provides A[k] amount of power for price X.
    • Type 2: a solar panel which provides 2 * A[k] amount of power for price Y.

    Your goal is to find the minimum cost such that all houses are provided with at least their required amount of power.

    Note: the power distributed from Y is not sequential, as you only focus on providing at least the net amount of energy of all the houses.

    Example: A = [4, 3, 5, 2], X = 2, Y = 5

    • Assign solar panel type Y to A[2], which will cover A[1] and A[3], and then assign solar panel type X to A[0].
    • Thus the minimum cost is 5 + 2 = 7.
Candidate's Approach

For the easy question, I implemented a simple O(N) followed by log(N) simulation. I didn't bother finding a better solution once I reached the last block since the operations are always bounded by O(N).

For the medium question, I used a greedy algorithm based on sorting A in descending order. The key is that the power can be distributed from a house to any other house. I ran a two-pointer solution where I calculated the number of houses on the right side (j-based) that could be powered by A[i]. Once I had that number, I checked if Y <= X * (number of houses covered) to determine if the choice of Y was acceptable. This resulted in an O(NLOGN) solution.

Interviewer's Feedback

No feedback provided.