Round 1
Questions:
-
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.
-
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.