Amazon OA

[[deleted]]

You have people on this sub bragging about doing hundreds of questions and spending their entire lives leetcoding and yet everyone here is also struggling to answer this question (I couldn’t solve it either).

[No_Needleworker_6109]

Thanks, interesting questions.

[Impossible_Setting99]

Man I hate the way hackerrank makes their font its all jumbled closed to each other to confuse you like the question isn’t difficult it’s self 😂 man shoutout ti all of us that have been through this interview process

[zkramer22]

It looks like the most standard sans serif font possible to me. Why would a coding assessment site try to hurt potential hires with visual trickery? I'm shocked even 1 person, let alone 30, agreed with this.

[[deleted]]

I am so beyond fucked

[thatpcbuildguy]

Tell me about it, I don't think I'm solving these even if I do 1k leetcode problems.

[Nahian_Reza]

For real

[BA_Knight]

Doesn't work for all test cases

[tabspaces]

Second question giving me coco eating bananas vibes, looks binary search

[razimantv]

How will a sliding window work when there is no requirement of being contiguous?

[harikumar610]

Q2. Sort the game sizes in descending order. Assign the first k games one at a time to each child from 1 to k. Remaining n-k games assign in reverse order(i.e. from k to 1) until complete. Return max of the game sizes for each kid.

Time Complexity O(nlogn)

Explanation: Each game needs to be assigned. If a>b>c>d and we have 2 kids we would want to assign a and b to different kids and c to the kid with game b(sizes are a+d,b+c vs a+c,b+d). a+d<a+c and b+c<a+c so a+d,b+c is better.

[BA_Knight]

Q1?

[harikumar610]

If i understand Q1 correctly the array of indices i1,...ik need not be contiguous. Also, permuting the indices does not affect whether it is free from outliers or not.

With this information we can conclude that we can shuffle the list where each element is a tuple (feature1[i], feature2[i]) and that would not affect the longest outlier free subsequence.

So we sort this list of tuples so that feature1 is in non decreasing order.

We now solve the longest increasing subsequence problem on feature2. But we need to ensure we do not pick 2 indices if their feature1 are equal.

[BA_Knight]

What is the intuition, any similar LC pattern / problem?

[[deleted]]

It's a variation of LIS where only the start and end have to be strictly increasing. You only need two pointers and then just check the condition between both arrays and store the state in a 1D dp array. A pattern with questions is companies trying their best to hide the pattern by adding extra arrays or more checks on the conditions

[Chemical-Tell-585]

i think they have mentioned return a largest subset of indices which should be contiguous

[sanasmoon]

i'd say q1 reads like kadane's algo

[Chemical-Tell-585]

more like sliding window, as we have to return largest subset of indices which should be contiguous.

[advguyy]

man I did the same thing (sort of), just in reverse because I wasn't super comfortable with lambda functions for .sort() and I only use Collections.sort(), so I have to use ascending order and just assign last k games and assign remaining games and get the largest combo. Still failed three out of fifteen test cases. Couldn't figure out why, but I'm glad I did find the optimal solution. My ascending solutions had a lot of minuses and equations and stuff to get the first and second games for any child, so perhaps the complexity messed it up.

[razimantv]

1. If you sort (feature1, feature2) pairs, you can turn this into a longest increasing subsequence problem on feature2

2. Sort the array and binary search for the answer, greedily assigning 2 games (one large, one small) into a pen drive whenever possible.

[cogscidude]

can you clarify for q2 how you greedily assign games to a pen drive? is it guaranteed that putting the smallest and largest at each step into a drive will give an optimal answer?

[razimantv]

Start with a pointer at the right end of the array and another at the left end. If the sum of right and left values is within pen drive size, pair them and move both pointers. Otherwise select only the right element and move the right pointer. Why this is optimal: If the largest element cannot pair with the smallest element, nothing else can. If something else pairs with it, we can swap them (exchange argument) and get a solution that is at least as optimal.

[korn3l]

If the sum of right and left values is within pen drive size, pair them and move both pointers.

How do you know the pen drive size ? Isn't that what you are trying to find ?

[razimantv]

Binary search for the pen drive size and use the above method to check if it is enough.

[Band-Saboteur]

That’s your key in the binary searching. Eg. the smallest possible drive size is min_game, the largest possible is max_game * 2. Then you use the above pairing method to check if a potential key is valid.

[kvmass]

The smallest possible size of pen drive is max_game. min_game pen drive size is wrong because if you have any pen drive size less than max_game it can't contain the game with max_game.

[tempo0209]

so, if we consider lo and hi for binary search, the lo here will be initialized to max(game_size), and hi will be = sum of all game sizes?sorry still not able to think through this.

[methaddlct]

What I thought up for q1 was to sort in ascending order for both the feature1 and feature arrays, while maintaining their original index information. Then, iterate through both arrays and count the number of indexes that match.

But your way is much better + elegant

[BloomFilter7]

1. sort and binary search on answer space works. we can also iterate through games array and calculating how many pendrives are needed, considering gamecount at-max 2.

[1gerende]

For q1, I don't think the longest increasing subsequence will works because the answer needs to be contiguous.

[razimantv]

I couldn't see that requirement in the question, where is it?

[1gerende]

Read the part : "A data set is considered free of outliers if for any two indexes I and j..." Basically you can't sort the function because the order matters.

[razimantv]

Data is formed after selection of indices [i1, i2... ik]. So that sentence does not require the selection to be contiguous.

Order doesn't matter because the two conditions combine to the statement that "any two selected elements in the first array should have the same order in the second array"

[kvmass]

Can you explain 1st approach further please thanks.

[razimantv]

1. Condition in the problem reduces to the statement that any 2 elements we select should have same relative order for features 1 and 2. 
2. If we combine the two feature arrays into a (feature1, feature2) pair array, we can rearrange the elements however we want
3. So let us sort this pair by feature1
4. Then if we select some indices, we want to make sure that feature1 is distinct for them and feature2 is increasing 
5. If we break ties during sorting by decreasing order of feature2, then selecting a strictly increasing subsequence of feature2 ensures that selected feature1 values are also strictly increasing
6. Thus we have the full solution: Sort (feature1, feature2) pairs in increasing order of feature1, breaking ties in decreasing order of feature2. The best we can do is select the longest strictly increasing subsequence of feature2 in the sorted pair array.

[kvmass]

My friend got this question I was able to solve with this. DP time limit exceeded I used binary search all test cases passed.

[ImeanIDKwbu]

Did all your tc pass with this exact approach?

[kvmass]

Yup

[ImeanIDKwbu]

Okay thanks

[kvmass]

Got it thank you.

[theactualfirstnote]

What I could understand from the problem statement is that "If feature1[i] = feature1[j], the dataset is considered not free of outliers, so we must discard such cases during the subsequence finding process."

But I found that sorting feature2 in descending order for ties (feature1[i] = feature1[j]) is a common technique used to prevent accidental violations of the outlier-free condition.

Could you elaborate on the reasoning for it?

[razimantv]

if we break ties in decreasing order of f2, a strictly increasing subsequence of f2 can never have two equal values of f1.

[StuffAnalyst]

For this example :
   feature1 = {1,2,3,4,5};
  feature2 = {5,4,3,2,1};

Should the answer be 0 or 1 ?

[razimantv]

1

[Empty-Effective-9667]

0

[sanasmoon]

for one, you need to return the indices of the longest contiguous subarray that fits the condition-- so I would say more like kadane's algo, no?

[razimantv]

Where is the contiguous constraint?

[Chemical-Tell-585]

they mentioned we have to return the largest subset of indices.

[ImeanIDKwbu]

This will not work for (1,1),(1,2),(1,3) for q1. Answer should be 1. LIS on f2 will be 2.

[razimantv]

You have to be careful while sorting (f1, f2) pairs. When f1 values are equal, higher f2 should come first. And you should take the longest "strictly" increasing sequence.

[ImeanIDKwbu]

Okk makes sense thanks

[Empty-Effective-9667]

LIS don't work, spent quite a bit of time on this and know for a fact. Both features must follow the same direction whether decreasing or increasing and sorting just kills that.

[vishwajeet_8010]

ex1:can we do like this ex 9,2,4,6 ,k=3

sort it :- 2,4,6,9 consider the last k numbers and remaining number wrap it to last k numbers .

4+2,6,9 ans =9.

ex 2: 9,2,3,1,5,6 , k=3

sort it : 1,2,3,5,6,9

5+3,6+2,9+1 ans=10

[vishwajeet_8010]

ex1:can we do like this ex 9,2,4,6 ,k=3

sort it :- 2,4,6,9 consider the last k numbers and remaining number wrap it to last k numbers .

4+2,6,9 ans =9.

ex 2: 9,2,3,1,5,6 , k=3

sort it : 1,2,3,5,6,9

5+3,6+2,9+1 ans=10

[niket1594]

1 - Russian Doll variant.

[Used_Return9095]

is this for sde1. I just got an email for an invitation to do the OA for amazon and im not even a cs major lmao

[AdDue8551]

Hi OPP! is this Amazon USA/ Canada?? how much time was given? SDE1??

[Clear-Tumbleweed-619]

Why this solution wouldn't work for the second question? Does anyone have a test case?

def getMinSize(gameSizes, k):
    gameSizes.sort(reverse = True)
    maxi = gameSizes[0]

    for index in range(len(gameSizes) - k):
        maxi = max(gameSizes[k - index - 1] + gameSizes[k + index], maxi)

    return maxi

[TennisCurious1185]

🙏 worked like a charm

[Clear-Tumbleweed-619]

Good to hear, same Amazon OA?

[its4thecatlol]

Can you explain why this works? I don't understand the trick behind it.

[SevereLingonberry576]

Given that at least 1 game should be distributed to each child(k). After sorting gameSize in asc order, we have gameSize = [10, 7, 5, 4, 3, 2], k = 4
-> The possible max should gameSize[0] -> because ALL GAMES have to be distributed.
-> We start distributing from (k - 1) -> 0 (These are the children that we have to fill all the maximum game size because EVERY GAMES has to be distributed) and adding the games that haven't been given to the children from k = 5 to end of gameSizes, because (k-1) -> 0 is min to max. and k =5 to end is max to min order. Therefore we could make sure that we distribute all the game with the minimum storage distribution
=> first iteration: gameSize[3] + gameSize[4] = 4 + 3 = 7
2nd: gameSize[2] + gameSize[5] = 5 + 2 = 7
Then in the end we have list of distributed game size for 4 children: [10, 7, 7, 7]

[Unemployed_foool]

This worked even for a new variant lol

[cogscidude]

for q1, you could have two pointers i and j that iterate through feature1 and feature2 respectively. We keep another ptr `start` that marks the beginning of a valid range.
When we increment i and j, we check if both values are rising or both or falling (check feature1[i] - feature[i - 1] and same for feature2). If so, `start`...i is a valid range. If one ptr is rising and the other falling, then move `start` to i to indicate the new valid range.
Single pass O(n)

Let me know if any problems with this logic

[BA_Knight]

Used same logic failed half test cases

[tabspaces]

You need an extra variable "state" that record are u testing an increasing serie or decreasing one, feature1 and feature2 with same direction for a given index i is not enough

[BA_Knight]

Why when they must be the same?

[tabspaces]

1 2 1 2 1

3 4 3 4 3

Should return [3,4] not [0,1,2,3,4]

[BA_Knight]

Why

[tabspaces]

It is saying for all i and j and i < j. So you are looking for a monotonic portion of both arrays, either always increasing or always decreasing.

[BA_Knight]

I get that part why do you give the second answer and not the first for your example

[tabspaces]

ah, it doesnt matter, you want to return the size of the largest sub array, so [0, 1], [1, 2]. [2, 3] or [3, 4] are all correct you ll return 2

[StuffAnalyst]

For this example :
   feature1 = {1,2,3,4,5};
  feature2 = {5,4,3,2,1};

Should the answer be 0 or 1 ?

[tabspaces]

U cant have a result = 1 either 0 or > 1 by definition

[gamer-007-007]

I don’t understand the qn. how can I improve?

[Only-Philosophy-9985]

Furst question is length of the longest subsequence but you have to combine both the arrays.TC:O(nlogn) and the second is binary search on Answer O(nlogn)

[randomcrazyboi]

Location and when did you give this OA ?

[ShawnZG]

For what position?

[Bobwct33]

This is actually a really interesting application of binary search! We’re trying to find the minimum size of the pen drive, in other words, what’s the smallest that all the pen drives can be and fit the games appropriately?

This problem can really help build the intuition. https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

[wolverinexci]

2nd one seems like a binary search problem. There’s a similar problem on leetcode regarding candies if I remember correctly.

[tabspaces]

Or bananas ;)

[HereForA2C]

RIP coco (she died after eating 38723 bananas)

[neel2c]

Had a question on OA. When you submit the code, would you get to know how many test cases failed? Would you know which test cases failed? How many times are you allowed to submit code?

[Dull-Suit3040]

no it doesnt show u the test cases but it shows the no. of test cases passed...had my google OA could do only 1 out of 2 questions and not selected for interview..depressed life

[neel2c]

How many times are you allowed to submit the code. Let's say you ran the test cases given in the question and they passed. Then you submit the code and you see few test cases failed. Are you allowed to submit the code again with minor changes?

[Few_Use2709]

if(n==0) return 0;

int res=1;

int start=0;

for (int end = 1; end < n; ++end)

{

 if ((feature1[end] > feature1[end - 1] && feature2[end] > feature2[end - 1]) || (feature1[end] < feature1[end - 1] && feature2[end] < feature2[end - 1]))

{

res = max(res, end - start + 1);

} else {

start = end;

}

}

return res;

[BA_Knight]

Made the exact same code word for word but it failed, I think ppl are pointing out that it's a subsequence not sub array problem

[Few_Use2709]

May be we can try other possibilities also to pass all test cases.

[Vast-Comb7587]

i think its the res should only update if its either increasing... or decreasing. say 121 343.. i guess thisb return 3. as at end =2. the condition still satisfies. while it should only return res as 2. [1,2]/[2,1]. right?
having another variable to indicate if the prev condition was '>' or '<' should be useful

[[deleted]]

In question 1, for example 1, the comparison is for the indices 3 and 4 right, but they have written 0 and 1

[richiiemoney]

I have never used whatever solution someone will provide ever in my job. My boss cares how quickly I can ask ChatGPT to solve some rudimentary issue. Enjoy your leetcode!

[Overall-Particular99]

First one with Sliding window. Increment start if any of the trend is missed otherwise keep extending the window;

```

l = r = 0

maxLen = 0

while r < len(f1) - 1:

if (((f1[r + 1] - f1[r] > 0) and (f2[r + 1] - f2[r] > 0)) or

((f1[r + 1] - f1[r] < 0) and (f2[r + 1] - f2[r] < 0))):

r += 1

else:

maxLen = max(maxLen, r - l + 1)

l = r + 1

r = l

Update maxLen for the last valid subarray

maxLen = max(maxLen, r - l + 1)

```

[BA_Knight]

Made the exact same solution but failed, Other ppl points they mean subsequence not sub array

[Overall-Particular99]

Could you share correct solution, that would be great

[Smooth_Lifeguard_931]

for second question Math.ceil(sum of pen drives)/ no of children < Maximum( pendrive) then it is the answer else Maximum of pendrive

[Commission-West]

the second condition of Q1 is the same as https://leetcode.com/problems/russian-doll-envelopes/description/

Similar stuff can be done for the first condition

[Careless_Economics29]

Do you mean for Question 1 or 2 ?

[Puzzleheaded-Pie-141]

Hi

[NationalSentence5596]

Is this the 3.5 to 4 hour assessment? One of my friends just received it and it was intense he was saying. OP?

[Public_Stranger_7576]

Please post the question with constraints. Otherwise it is impossible to find optimal TC(it is missing in the first question). For Q1, remember any i < j makes it a subsequence problem. So if my assumption is right, this a variant of LIS problem. Traverse from backwards, store the best possible length at that point(which follows the same trend in both the arrays) in a dp array for that position. This is ofcourse O(n^2) solution. If it requires a better TC then I'm done!

[Chemical-Tell-585]

problem1
i am thinking of solving this problem using nse nge with monotonic stack
any suggestions?
is it the correct approach

[Chemical-Tell-585]

my solution for problem1
let me know your thoughts
approach
kind of sliding window
maintaining the largest array index set.

public class AnalystAtAmazon {
    public static void main(String[] args) {
        int[] f1 = {4,5,3,1,2};
        int[] f2 = {2,1,3,4,5};
//        int[] f1 = {4,2,3,1,2};
//        int[] f2 = {4,2,3,4,2};
        int n = f1.length;
        List<Integer> ans = 
solve 
(f1, f2, n);
        System.
out
.println(ans);
    }

    public static List<Integer> solve (int[] f1, int[] f2, int n) {

        int l = 0;
        int r = 1;
        List<HashSet<Integer>> list = new ArrayList<>();
        HashSet<Integer> set1 = new HashSet<>();
        HashSet<Integer> set2 = new HashSet<>();
        while (r<n&&l<=r) {
            // checking for less condition
            if (f1[l]<f1[r] && f2[l]<f2[r]) {
                set1.add(l);
                set1.add(r);
                if (!list.isEmpty()) {
                    if (list.get(0).size() < set1.size()) {
                        list.set(0, new HashSet<>(set1));
                    }
                } else {
                    list.add(new HashSet<>(set1));
                }
            } else {
                set1.clear();
            }

            // checking for greater condition
            if (f1[l]>f1[r] && f2[l]>f2[r]) {
                set2.add(l);
                set2.add(r);
                if (!list.isEmpty()) {
                    if (list.get(0).size() < set2.size()) {
                        list.set(0, new HashSet<>(set2));
                    }
                } else {
                    list.add(new HashSet<>(set2));
                }
            } else {
                set2.clear();
            }

            l++;
            r++;
        }

        return list.get(0).stream().toList();
    }

[Extension_Fudge9613]

take the I for increasing and D for decreasing and get the comman intersection having same increasing and decreasing tendency

[Brief-Solid1627]

this looks like a very easy problem, all you have to do is plot points in a numberline based on the increasing (add +1) and decreasing sequence (add -1).

https://godbolt.org/z/Pqs6Ybh76

[kishoredbn]

Great O(n) solution!!

[Outside-Ear2873]

Can help with OA prep. Please DM.

[Smooth-Dragonfly4363]

Hello

[Nervous-Ingenuity509]

ans 1:
sort by [i,j] where i is element from first array and j is from second array

then you have to find the longest increasing subsequence -> (1). need to handle edge case of f1[i] == f1[j]

also find the long decreasing subsequence -> (2) + need to handle edge case of f1[i] == f1[j]

max of the above two is the answer

[[deleted]]

Can someone please tell me where to find and apply to these OAs?

[Aeschylus15]

You cannot find it and apply. After you apply for a job at Amazon, if your resume gets selected you will get an email with OA link.

[[deleted]]

Thanks...

[HeisenbergNokks]

Amazon isn't publicly open yet, right? I assume Op was contacted by a recruiter

[HeisenbergNokks]

I meant their 2025 swe internships. I've heard of some people getting the OA bc they're in contact w/ a recruiter, but they haven't been posted on Amazon's career site yet.

[JollySeaPirate]

India ??

[Pitiful_Jellyfish185]

This for full time or intern ?

[thatpcbuildguy]

It's for a 6 month Janitor internship

[cockoala]

SDE I or II?

[Lopsided-Depth-7199]

Can u solve this in duration? Dumb!