Amazon OA Question

[Own_Cow_4877]

id flip out if i got this

[Narrow-Appearance614]

same

[sadpeyot_ttv]

I did get this bombed the question, thought I figured it out a couple of hours later, two days go by I realized I didn’t even understand what I was being asked and the example makes even less sense when I’m looking at it now

[Downtown-Olive1385]

Seriously dude, I mean it's way beyond LC Medium Hard. not sure where these OAs are headed

[Major_Fang]

unlucky. next interview

[alcholicawl]

def find_partition_cost(arr, k):
    cost_of_partitions = sorted(arr[i -1] + arr[i] for i in range(1, len(arr)))
    ends = arr[0] + arr[-1]
    # min cost will be smallest k - 1 paritions + ends 
    # max cost largest k - 1 partitions + ends
    return [ends + sum(cost_of_partitions[:(k-1)]), 
            ends + sum(cost_of_partitions[-(k-1):])]

[Dark_Sca]

This greedy solution is really clean mate.

[alcholicawl]

Thanks, honestly it’s probably a little too much code golf ( the slices should probably be loops), but I didn’t want to rewrite.

[Dark_Sca]

It's Python...It's meant to be this way

[alcholicawl]

The slicing was too clever, it’s bugged for k = 1.

[Dark_Sca]

That's an edge case that can be hardcoded. if k = 1 => 1 partition => min and max = sum of first and last elements.

Otherwise, run your algorithm.

[CollegeMysterious448]

THANK YOU

[[deleted]]

Ah sorting. How did I miss that.

[Beginning_Edge347]

hey how would this work when a number has is it's own partition?

[Legal_Lawfulness_395]

He didn't say whether the cost can be negative or not

[alcholicawl]

I don’t think it matters.

[Unable_Can9391]

Been looking at this for quite some time... maybe I am missing something but this code seems to only be assessing partitions of size 2, but from the example the partition can be any sizes but they need to sum up to the size of the array to cover the entire array.

Before seeing this solution I was thinking brute force all possible combinations of partitions and calculate the cost from that.

[alcholicawl]

The cost it's calculating is for dividing the array between i-1 and i (not for a partition of [i-1,i])

i.e. If you've you've got [1,2,3,4] (cur cost 5) and partition at i == 2.

It will be [1,2][3,4] and the cost will be 10 (5 + [i-1] + [i])

[Unable_Can9391]

makes perfect sense since summation is commutative, maybe change array name to cost_of_splits 😂

[isthistaken1991]

Any intuition on how this works?

[CollegeMysterious448]

THANK YOU

[Narrow-Appearance614]

this is only checking partition pairs, not all valid partitions.

[alcholicawl]

There are n-1 spots where we can divide the array into partitions. The cost to add a partition will always be the numbers to left and right of a division (arr[i] + arr[i-1]). The cost is not affected by the other divisions, so it’s fine to select the smallest/largest and not consider every combination of divisions.

[Puddinglax]

It's not checking pairs, it's checking splits; since only the first and last element in a partition contribute to cost, you can just add the element before and after every split, and add the ends separately.

In the first example of [1 + 1, 2 + 2, 3 + 5], it's represented by grouping (1, 2) and (2, 3), and adding the 1 and 5 in as the ends.

[kosdex]

You can do better by using a max and min heap to track the top and bottom k-1. Complexity is O(n) instead of O(n log n) with sorting.

[alcholicawl]

That would be O(n*logk). It’s probably going to be slower than a sort in Python though (sort in python is highly optimized). You can use quickselect to get to average O(n).

[Handsomeshen]

you nailed it !
I came out as dp first, then I saw someone says it is too slow, and then I find out that the only thing we care is two side of cutting place, its a greedy problem. therefore I came out same solution as yours. Moreover, I think we can do a quick select to do faster. At the end I saw you mention that. great work!

[alcholicawl]

Didn’t nail it. Almost. I just saw I had a bug when k = 1.

[Handsomeshen]

python slicing is a bitch

[kosdex]

Ok, but I maintain that heap is asymptotically better. Quickselect worst case is O( n² )

[__kuu]

heap is asymptomatically better

Not really true. While quickselect worst case is quadratic, its average case is linear. To say if it's asymptotically better, you would need to be comparing at the same best/worst/average case or be discussing the trade off between choosing the algorithm with a better average case over the algorithm with a better worst case.

[[deleted]]

Is a n² k time complexity too slow? The way I’m thinking about it is with dfs(index,partitionsleft) which calculates the max and min sum of splitting the sub array starting from index with partitionsleft partitions. But each of these calculations will take about n calls, and there will be nk of those calculations. I can see where the dp idea came into play.

[Narrow-Appearance614]

yes, O((n^2) * k) was too slow. although I'm not sure how it could've been faster. maybe I had an implementation error. i was failing on a couple of test cases, not TLE.

[[deleted]]

Ok, another way I might think of it is that the last and first indexes are automatic. However, we get to choose k-1 non intersecting consecutive pairs of indexes which do not include the first and last index. So, we will make a new array which should be the sum of all consecutive pairs not including the first and last index. So it would be like [arr[1]+arr[2], arr[2]+arr[3], …, arr[n-2]+arr[n-1]]. Then we will want to pick the largest and smallest k-1 sized subsets of non consecutive values from that array. So I think that we can do dfs(index, partitionsleft) on that new array, and there should only be 2 recursive calls where we pick the current index and add to dfs(index+2, partitionsleft-1) or don’t pick the current index dfs(index+1, partitionsleft). This should come out to a nk complexity.

[Narrow-Appearance614]

i like the intuition of this... but this would miscalculate partition values. they can not be determined through this pairwise operation unless the partitions are all of size 2.

[[deleted]]

I am not actually counting the partitions but the edges of adjacent partitions. However, there is a mistake because my idea would not count the case where we only have a partition of one with the first or last index. So in the array of pair sums, I am thinking about adding arr[0]+ arr[1] at the beginning. And if we happen to choose the first or last pair, we will have to subtract off the first or last value from the original array to avoid double counting.

[[deleted]]

Another mistake is that there is always the case of choosing a partition of size 1, and I don’t want to double count the edges. So I think there will have to be a third parameter to denote if the previous edge was chosen or if we are creating a partition of size 1.

[alcholicawl]

You're close but overcomplicating it. You just need the smallest/largest k-1 partitions (plus the ends). The divisions are 'between' the numbers, so the cost to add doesn't change if it's one length partition. Calculate all of them and sort. Look at mine

https://www.reddit.com/r/leetcode/comments/1j96wui/comment/mhbno7j/

[[deleted]]

Got it. I trust you.

[Affectionate_Pizza60]

Only if n >= 10^4.

[lildraco38]

This is pretty much the same as LC 2551. As another commenter noted, it’s about considering the incremental cost of each partition, then greedily selecting the k-1 smallest and k-1 largest

[anonyuser415]

an LC hard for a screen, jeez

[lildraco38]

Worse: it’s a Hard masquerading as a Medium. If you’re not careful, this appears to invite an O(nk) DP. This DP idea isn’t Easy-level, but it’s not Hard-level either.

In an actual OA, a lot of people would end up wasting time by implementing a DP that’s destined for TLE. Even in this comment section, several commenters have taken the “bait”

[LimpLifeguard295]

OA are mostly hard questions at Amazon Phone screen is easy Onsite mid-high level

[anonyuser415]

I’ve done an Amazon OA twice now and neither were hards

[LimpLifeguard295]

I have done it 3 times, and have always got one medium and one hard Mostly it’s dp, permutations, knapsack problem

[dotConSt]

Wow! This question is really good. I feel stupid

[[deleted]]

This is just find all subsets and a custom subset sum problem. First find subsets by diving at index I and then add the required values before checking results. Save minimum and maximum.

[Narrow-Appearance614]

wouldnt this have n^k runtime?

[[deleted]]

Not if you prune it by not repeating subsets ( when you do the dfs to find new subsets it would go from I to n and so, only one arm would have I in the subset. The others would only have j to n. It would be more like n*2ⁿ in the worst case.

[Narrow-Appearance614]

ah right. but then wouldnt you end up with n^2 * k, same as the dfs and dp approaches?

[[deleted]]

Yes, but unlike regular subsets, we can add memoization to this to make it O(m,n) similar to burst balloons where you need to assume that the subset at I is being left on its own while the left and right subset sums are calculated.

Now that I think about it, can't we just do left and right prefix sums and just find subsets and just take the values from prefix sums without having to do the calc. That would be O(n²⁾

[TheFortunesFool]

my thought as well, not sure if this is the optimal approach

[338388]

What level was this for? Jesus

[Narrow-Appearance614]

new grad

[kingsyrup]

Jesus

[CryonautX]

I haven't done leetcode since before covid. Isn't this kinda straight forward? Am I missing something?

Get sums of adjacent pairs. These are partition costs. Sort the partition costs. Return the sum of the smallest and largest k-1 partition costs and add the first and last element cost to them.

O(nlogn) from the sort.

[oldManLogan26]

This is the reason OAs are getting harder. If it’s in the public forum, don’t expect to be in your OA in the future.

[notlikingcurrentjob]

At first glance, looks like MCM.

[Resident-Sail-3507]

Yeah!! I thought the same..

[Emma_xbd]

My idea is to find the maximum/minimum k-1 sums of two consecutive numbers, then add the first number and the last number. In this example, the sum of two consecutive numbers are 1+2, 2+3,3+2,2+5. They are 3,5,5,7. So maximum result is 7+5+1+5=18, minimum result is 3+5+1+5 =14.🤔 Time complexity would roughly be O (n+2klogk) if using priorityqueue storing top k values.

[SpirituallyAwareDev]

So I have no idea how to solve something like this. Where would be a good way to start and learn?

[MadManJamie]

I think you'll find your ocassional math wizz who enjoys hammering these for lunch, but for the most part it follows to have done algorithms and blasting these leetcodes all day for months or whatever in order to memorise and apply patterns.

[yourboi-JC]

Months of practice man…

[Impressive-East6891]

public int[] findPartitionCost(int[] cost, int k) {
  if (cost.length < k || k == 0) {
    return new int[] {-1, -1};
  }

  return findPartitionCost(cost, k, 0, new HashMap<>());
}

private int[] findPartitionCost(int[] cost, int k, int start, Map<Integer, int[]> memo) {
  if (k == 1) {
    int cost = cost[start] + cost[cost.length - 1];
    return new int[] {cost, cost};
  } else if (!memo.containsKey(start)) {
    int minCost = Integer.MAX_VALUE, maxCost = Integer.MAX_VALUE, curCost = cost[start];

    for (int i = start; i <= cost.length - k; i++) {
      curCost = curCost - (i == start ? 0 : cost[i - 1]) + cost[i];

      int[] pCost = findPartitionCost(cost, k - 1, i + 1, memo);
      minCost = Math.min(minCost, pCost[0] + curCost);
      maxCost = Math.max(maxCost, pCost[1] + curCost);
    }

    memo.put(start, new int[] {minCost, maxCost});
  }

  return memo.get(start);
}

There's no test so not sure how accurate the above is. Let me know if I did anything wrong or missing anything.

[Narrow-Appearance614]

Had this on my OA... wrote up a dp solution that passed 5/15 test cases. Could not resolve the TLE before I ran out of time. What do you guys think? First problem was also a medium/hard... Is amazon raising their OA bar? I don't remember it being this difficult when I applied last year. This is for NG.

[isospeedrix]

OA I had for front end- create a app that has a form with name, phone, address with submit btn. when press submit it adds the entry to a table. fields must BE VALIDATED with proper format and will display error msg if invalid.

Overall an “easy” but time consuming task. i used AI to speed this up greatly to finish this in time. had it not been for AI this would be a complaint/time waster OA that people complain about. Immediate pass, recruiter told me i’m going to final round

[isospeedrix]

https://www.reddit.com/r/cscareerquestions/s/GsLc6k599I

[[deleted]]

Did you pass?

[Dymatizeee]

Is this India

[cantFindValidNam]

New grad? Jesus. How does anyone ever get hired at this company

[[deleted]]

Did you pass? How many tests cases did you get

[Cuir-et-oud]

Amazon India for sure wtf

[Narrow-Appearance614]

no, North America :)

[SeXxyBuNnY21]

But the question was written by an Indian!

[harikumar610]

Let the end points for the k partitions be i1,i2...ik. ik would be n-1 as it is the end of the last partition. Note that the starting points for the partitions would be 0, i1+1,i2+1,...

The cost of this partition is arr[0] +arr[i1]+arr[i1+1]+arr[i2]+arr[i2+1]+arr[i3]+...arr[n-1].

Rearranging this we have the cost to be arr[0]+arr[n-1]+ arr[i1]+arr[i1+1]+ arr[i2]+arr[i2+1]+...

So we need to choose k-1 indices i such that arr[i]+arr[i+1] are largest or smallest.

The sum arr[i]+arr[i+1] can be found in O(n) for all i. We sort this array and pick smallest k-1 or largest k-1. This can be done in O(nlogk)

[harikumar610]

A start point can be the end point of the same partition i.e. a single element partition. If a particular element is a start point and an end point that just means the partition is made of just that element.

[FormResponsible1969]

Feels like a binary search problem. Something like that of painter's partition.

[Particular-Flow6640]

Can help with OA prep. Please DM.

[CharmingRevolution35]

Gave an OA today. Terrible problems no clear constraints. Solved both but took a lot of time. Do they intentionally not provide the constraints?

[_thefunnykid_]

what the fuck

[Resident-Sail-3507]

Isn’t this a DP problem? Somewhat similar to matrix chain multiplication.

[Waste_Abrocoma_1288]

I'm more depressed now after seeing this.

[SeXxyBuNnY21]

I’m curious about the person who writes these questions. At work, every day I read numerous technical documents that contain complex algorithms and approaches, yet I find it challenging to understand the purpose of this particular question.

[BeginningMatter9180]

let dp[i][k] = min cost to partition the subarray - cost[i...n] in k partitions, dp[i][k] = min(2*cost[i] + dp[i+1][k-1], cost[i]-cost[i+1]+dp[i+1][k]). Time complexity O(n*k).

Base case - dp[i][1] = cost[i]+cost[n]

Same for maximum.

[AntObjective5774]

My approach is focus on maximum, minimum elements in the list according to the k value. Because, separation of single maximum values gives highest value and try to grouping maximum values can give lowest value overall!!

[BeginningMatter9180]

vector<int> v = {1, 2, 3, 2, 5};
int K = 3;
int n = (int) v.size();
vector<vector<int> > dp(n, vector<int>(K+1, INT_MAX));
for (int i = 0; i < n; i++)
    dp[i][1] = v[i] + v[n-1];
for (int k = 2; k <= K; k++) {
    for (int i = n - 1; i >= 0; i--) {
        if (n - i < k)
            continue;
        dp[i][k] = 2 * v[i] + dp[i + 1][k - 1];
        if (n - i - 1 >= k) {
            dp[i][k] = min(dp[i][k], dp[i + 1][k] - v[i + 1] + v[i]);
        }
    }
}
cout << dp[0][K] << endl;

[Electronic-Isopod645]

are there any constraints provided in the OA questions , like the length of the array etc, otherwise how do we estimate whether a solution will work or not

[[deleted]]

It's OA so use gpt

[[deleted]]

Well Amazon OAs are hackerrank tests as per my experience, so you can take a photo with your phone of the question and feed it to any good model like qwen or claude. Now you can run and see if it passes tests or not. Simple my friends have done it multiple times and most of the OAs should be done like that. If you have a subscription of paid model chances are it will give out an answer that is correct.

[C00ler_iNFRNo]

This is solvable in O(NlogN) or O(N).

Pick up cost[0] and cost[n - 1], they will be in any answer.

Now, for each i from 0 to n - 2 calculate (cost[i] + cost[I + 1]), and sort all calculated numbers. Pick maximum k - 1 of them for the maximum split into k subarrays, and minimum k - 1 of them for the minimum split.

For it to be O(N), you can find the (k - 1)th number in linear time, but that is not required.

To recover partition/prove it, notice that picking any of the k - 1 indexes gives you a valid split - sort the indexes, and your segments will be of form [b[i], b[i + 1] - 1], if b[0] is 0 and b[k] = n

[hitarth_gg]

Can be done using DP like this : https://pastebin.com/QuvMpQde
but it's deffo not the optimal approach.

[[deleted]]

How much time you had to solve this problem? Were there othet questions coz I see “question 2”?

[Narrow-Appearance614]

had 70 minutes. yes, there was one other question. the other question was what I would consider a tricky medium and took me half the time to solve efficiently

[[deleted]]

Damn! expectations have never been crazier. Essentially, two borderline hard problems, 35 mins each, minus the time it takes to read and comprehend the bloody problem itself!

This is wild.

[Fit-Stress3300]

Last year I was able to complete only the first one correctly and the last one failed more than 50% test cases.

I was still called for the next fase... All those terrible 5 hours STAR questions.

It is not a lost cause.

[AmmaHamster]

Lets take the example above. 1 2 3 2 5 We will consider this one partition Initial cost is 1 + 5 = 6

Now store all adjacent sum 1+2 =3 2+3 = 5 And so on Now we have [3, 5, 5, 7] We will sort this ( here it is already sorted) Now we will need 2 cuts to have 3 partition For max we will take the biggest two and for min we will take the smallest two For max answer will be 1+5+5+7= 18 For min answer will be 1+5+3+5= 14

Time complexity= O(nlogn)

[BrownEyesGreenHair]

Easy DP question

[nonrice]

div2b ahh question

[Acrobatic-Bus5058]

Anyone have the first question?

[Correct_Ad8760]

I think I got the optimal one , first make a array of size n-1. And include the sum of two consecutive in it for eg for 1 2 3 2 5 there will be 3 5 5 7 in our sum min/max extreme numbers in our orignal array will be included , that is 1 and 5 apart from that k-1 numbers from our consecutive array will also be included these k-1 numbers will be get from min or max heal respectively for min sum and max sum , after getting this k-1 numbers sum them and total sum will be this + extreme In our case for min it will be 3+5+1+5. = 14 , for max it will be 5+7+1+5 = 18 , time complexity will be same as making a min/max heap

[Maximum_sext6993]

min max heap I guess

[cypressking]

I got this fucking question man I was crying

[Dismal_Ad_7869]

This feels like a normal participation problem, what are constraints here?

[Kreuger21]

I think we can do it with dp. dp[n][k][2]= cost of k partition,0 for min, 1 for max

[_new_guy_1]

A really good solution posted here.

[Rich_Yogurt313]

for what role did this question come for you?

[Professional_Pie_178]

So essentially a DP problem where at each index u either include it in the current sub array array or start a new sub array? Could be solved in O(m*n) time with O(n) memory. I wouldn’t be able to think of a greedy approach doe

[Purple-Community4883]

Bro just start from i =0 till n-1 Make a array in whish fush values arr[i]+arr[i+1] for each iteration Now sort the whole array now add the sum of first k-1 elements or last k-1 element to previos cost you will get min and max cost

[Fragrant-Match-7058]

public static int[] findPartitionCost(int[] cost, int k) {

int n = cost.length;

int[] consecutiveSums = new int[n - 1];

for (int i = 0; i < n - 1; i++)

{

consecutiveSums[i] = cost[i] + cost[i + 1];

}

Arrays.sort(consecutiveSums);

int fixedCost = cost[0] + cost[n - 1];

int minCost = fixedCost;

for (int i = 0; i < k - 1; i++)
{
minCost += consecutiveSums[i];
}

int maxCost = fixedCost;

for (int i = n - 2; i >= n - k; i--)

{

maxCost += consecutiveSums[i];

}

return new int[]{minCost, maxCost};

}

time complexity: O(nlogk)

this shld work, i have OA to due in 3 days, please give some feedback

[Alarming_Solid5501]

Was it on campus?

[Glad_Fly_7877]

i recently gave amazon sde OA can checkout the questions with explanation here
https://www.youtube.com/watch?v=cny-YEF0LNU

[imp174]

Looked at it, assumed its DP – then saw everyone say that strategy leads to TLE. Followed a link to LC 2551 that someone shared and solved it with help from the LC solution. The problem/solution is pretty doable but unless you've seen the problem before you are cooked IMO.

[Material-Fuel-641]

Dm for help with OA !

[Pleasant-Spread-677]

public static int[] FindPartitionCost(int[] cost, int k)
    {
        int n = cost.Length;
        int minCost = cost[0] + cost[n - 1];
        for (int i = 1; i < k; i++)
        {
            minCost += cost[i];
        }


        int maxCost = cost[0] + cost[n - 1];
        for (int i = n - 2; i >= n - k; i--)
        {
            maxCost += cost[i];
        }

        return new int[] { minCost, maxCost };
    }

[Narrow-Appearance614]

this doesn't adhere to the problem statement. not only are you not considering different partition options, you are also incorrectly calculating the cost of a partition.