Question

Goldman Sachs | OA | Office design | Set - 36

Answer 1

Any idea how to proceed with this,or any similar questions that I can find on leetcode!

 

Office Design
A company is repainting its office and would like to choose colors that work well together. They are presented with several various-priced color options presented in a specific order so that each color complements the surrounding colors. The company has a limited budget and would like to select the greatest number of consecutive colors that fit within this budget. Given the prices of the colors and the company's budget, what is the maximum number of colors that can be purchased for this repainting project?
Example
prices = [2,3,5, 1, 1, 2, 1]
money = 7
All subarrays that sum to less than or equal to 7:
Length 1 subarrays are [2],[3],[5],[1],[1], [2],[1 ]
Length 2 - [2,3], [5, 1], [1, 1], [1, 2], [2, 1]
Length 3 - [5. 1. 1],[1, 1, 2],[1,2,1]
Length 4 - [1, 1, 2, 1]
The longest of these, or the maximum number of colors that can be purchased, is 4.
Function Description
Complete the function getMaxColors in the editor below.
getMaxColors has the following parameters:
int prices[n]: the prices of the various paint colors
int money: the amount of money the company can spend on paints
Returns: int the maximum number of colors the company can purchase

Answer 2

The idea that I was following to try and solve this is relatively simple. Since we know that there is an indeterminate amount of prices and order, we know that the data structure is going to be ordered in a way that the colors can complement each other (as well that the office is choosing colors that work well together), therefore we can tackle it a certain way. We can start in the beginning, calculate the prices until it's unacceptable, then return back to the beginning with an increment to the value. This allows us to continue to parse through the data at a different point to try and continue to find a greater length of paints.

A minor alteration to it could allow for the information of what series of paints the Office could purchase to be included, but that's not required by this question.

Python:

def getMaxColors(prices, money):
    test_max = 0
    max = 0
    test_price = 0
    count = 0
    i = count
    flag = False
    while(i < len(prices)):
        #print("price: " + str(prices[i]))
        flag = True
        if (prices[i] + test_price <= money):
            test_price = test_price + prices[i]
            test_max = test_max + 1
            #print("test_price: " + str(test_price))
            #print("test_max: " + str(test_max))
        elif (prices[i] + test_price > money):
            count = count + 1
            i = count
            test_max = 0
            test_price = 0
            flag = False
        if flag:
            i = i + 1
        if test_max > max:
            max = test_max
            #print("max: " + str(max))
    return max
I do not know if this reasoning is bad per se, maybe naive, but I'm sure it can be done better. What I do know is that this results in the expected length = 4 from the example case.

It can be tried by adding this afterward:

if __name__ == "__main__":
    test_prices = [2,3,5,1,1,2,1]
    test_money = 7
    result = getMaxColors(test_prices, test_money)
    print("result: " + str(result))
(I know __name__ == "__main__" comparison isn't necessary, but it's certainly my preference.)

Answer 3

java solution

 

public int optimalColors(int[] prices, int budget) {
        int max = 0;
        int left =0;
        int right = 0;
        while (right < prices.length) {
            int temp = left;
            int total = 0;
            while (temp < right) { //we add up the prices from left (replaced by temp) to right index to see what the current total is
                total += prices[temp];
                if (temp+1 == right) {
                    total+=prices[right];
                    break;
                }
                temp++;
            }
            if (total <= budget) { // if the total falls within budget, we set the max # of indexes shown by right-left+1
                max = Math.max(max, right-left+1);
            }

            if (total >budget) { // if we exceeded budget, left moves up 1
                left++;

            } else { // if we haven't exceeded budget, we try one more index
                right++;
            }
        }

        return max;
    }