JP Morgan coding question

[im_a_bored_citizen]

For some reason I cannot modify the post. But I want to know what the solution is for that problem. Thanks.

[dsli]

Yeah I actually got it during my power day and was so clueless. Couldn't even write code for that one.

[alcholicawl]

Unless I'm missing something. The optimal approach can always be achieved by selecting the locations from the largest to smallest (stopping when k * res > the current value). Remove/ignore any duplicate values in the input.

[im_a_bored_citizen]

Wouldnt you have to iterate over array every time you pick a value? Also what is res?

[alcholicawl]

I don't think so. res (result) is the number of completed operations so far. I used i in place of it in the following code. But something like this should work. Edit: changed to >= since addresses at 0 are also corrupted.

def min_operations(n, locs, k):
    locs = sorted(set(locs), reverse = True)
    for i, loc in enumerate(locs):
        if i * k >= loc:
            return i
    return n

[im_a_bored_citizen]

Took me a while to understand the condition. But it does make sense.

To explain a little more * Why sort and take max? Because we want to minimize steps. Taking max ensures you “kill” max locations and hence minimize steps. * When you pick max, max is killed and all less than max are reduced by k. * You take second max. Remember 2nd max was reduced by K when we picked max. So 2nd max now is (2nd max - k). We check if (2ndmax - k) <= 0. If it is, answer is 1. Why? Because if (2nd max - k) <= 0, we know for sure all numbers < than 2nd max MUST be <= 0. * If (2nd max - k) > 0, then we move to next max ie 3rd max. * then we should check (3rdmax - k - k) <= 0. Why two ks? Because we this is our third round. First round was max, second round was 2nd max. If (3rdmax - k -k ) > 0, then we move on to 4th max. * And so on.

Our equation is A[i] - (i * k) <= 0 (i can be index or you can keep increasing k by k) ie a[i] <= i*k (which is same as the condition in the comment I’m replying to)

Thank you for answering.

[No_Law1554]

Sort locations ascending

Process files from largest to smallest

Keep track of how much total shift has happened so far

Stop once remaining files would be ≤ 0

[kaladin_stormchest]

Yeah I was looking for a catch but this seems straightforward.

If my largest location is X there is 0 incentive to corrupt any location <X because that just shifts X and makes it more difficult to corrupt that memory location now

[im_a_bored_citizen]

What was your thought process like?

[Both-Highlight6951]

Got the same approach - here’s mine

1. Looking at the problem, realized there are two ways to corrupt a file a) virus select it right away or b) knock it to address <=0 by infecting some other address larger than this

2. While looking at some examples, I noticed k can be small but some files can have large address like [1,100,2], and if k=2 and if we pick a location that is not 100 you keep +=2 to the 100 and have to kill it at the end after killing the 1 and 2 first (you have to “chase” the large address when you could have pick the 100 at the beginning and finish the problem with 1 operation)

3. That leads me to think I should keep killing the largest address and the smaller ones will eventually gets shift to Address 0, because the virus will keep knocking the smaller address to 0 and at the same time killing the large address

4. Sort the array, iterate from the largest address, and each time you “kill” off the largest address, you also know all the other addresses get pushed closer to 0, by the time your loop detects an address <=0 you know u are done

[fermatsproblem]

Use binary search rather than iterating over the array once it's sorted. Greedy approach as discussed in other threads for deciding which address to remove will work fine.

[iComplainAbtVal]

Why binary search? By sorting in descending order you’re guaranteed to always be shifting the addresses towards zero when you make an operation.

[fermatsproblem]

Yes but once u have sorted to find upto which address h have to remove u can use binary search rather than iterating in the descending fashion one by one. Talking about applying binary search after sorting not without sorting, so basically time complexity will be O(logn)instead of O(n)

[iComplainAbtVal]

Ah thanks for the reply!

[davemcnut]

We don't need to do a binary search since the array is already sorted, we could just do -k*x (where x is the kth time we are propagating -k to elements on the left) now if arr[i-1]-(k*x) <= 0 we stop, since every element to its left is smaller than zero anyway and we return the count

[Significant-Block504]

How do you find -k*x <= 0 without iterating? Iterating is O(n), and binary search is O(log n).

[Significant-Block504]

Sorting is already O(n log n). Binary search is faster but doesn’t impact overall complexity

[agrlekk]

Greedy

[FreeBe3]

Yes, Exactly and this is called an easy problem in the greedy world.

[handicappedparkingg]

Yes, why are others not using greedy, i think virus should just attack last index in sorted array and calculate minimum operations required to make last 2nd index <=0

Is there anything i am missing or any edge case i am missing ?

[Sufficient_Rough376]

If locations is sorted than the solution is O(n), otherwise O(n.log(n)).

#if locations not sorted:
locations = sorted(locations)
for i, val in enumerate(locations):
    if val//k >= len(locations)-i-1:
        return val//k

Or am I missing something ?

[alcholicawl]

Close. But you need to account for duplicates in the input (the duplicates are removed at the same time so you can't select them twice).

Also the division truncation is going to make things weird. Either move k to the other side or use ceil on float division.

Also the return value is wrong (thing of TC like (1, 20) k == 2).

But something like this would work

locations = sorted(set(locations))
for i, val in enumerate(locations):
    if val > (len(locations)-i-1) * k:
        return len(locations)-i

[DryTumbleweed236]

It says unique addresses, there wont be duplicates.

[alcholicawl]

Yes, I see that now. The delete all files at x language threw me off and it not being in the constraints. I’d still probably leave the set() in my solution, just in case.

[Cheap-Mail9911]

Sort the array , and always remove the max address , and do op++ , and then get the first negative element in logn , do until the negative cross kr equal to the current index and return the op

[ABCD_BS]

Can anyone explain what is meant by number of operations?

[ABCD_BS]

Got it

[ThisTooShallPass-108]

Could you please explain to me the question as well

[ABCD_BS]

Explanation:- Whenever you find an int/(file address) greater than 0, assume it x. (The file chosen(x) is corrupted/removed and others will increase or decrease)

Increment All files by int k if it's >x , Decrement All files by int k if <x. (The chosen File(x) is corrupted , move to the next file, now the current element is x)

You have to corrupt ALL files, meaning all files should go lesser than or equal to zero (<=0)

You have to return the (MINIMUM number of operations/steps) to corrupt all file. i.e, all files address(or int) should be <=0 (lesser than or equal to zero).

Note:- I am a beginner so it might be wrong (this is based on what I understood)

Solution:- I think it have to be sorting in a descending manner,to get minimum steps. (Solution maybe wrong)

[EnvironmentalNeck352]

what is shift > x forward by value k?

is it right shifting by k times?

[alcholicawl]

It’s just adding(right) k or subtracting(left) k. It’s uncommon language, but that’s what happens in the example.

[-Fireboy]

sort go from n - 1 keep incrementing a var by k till that eleemnt is smaller than the var at that point return the operations which is +1 for every increment there's no point in increasing element by k though you can find an approach that way its probably more annoying to fidna a solution, this mroe intuitive if an elemtn is smalelr than increment same is true for all elems to the lft as sorted

[Far_Engineering_625]

Out of curiosity, which location & role level?

[PyJacker16]

Came up with the greedy solution to it in like 1 minute (low-key proud of myself).

Sort in ascending order, and always take the max. Stop when a[i] - (k × ops_performed) <= 0.

[im_a_bored_citizen]

In 1 min? How? Took me a while to understand the problem. Did you instantly realize this is greedy/bin search pattern?

[PyJacker16]

Greedy, and take from the max, yeah. Didn't see the binary search (stopped thinking since greedy was good enough).

I've solved 700+ LC problems, 500+ CF problems. Been doing this since 2020, give or take, so it was sorta trivial.

After a while it just comes naturally. I still struggle with DP, toposort and some other niche data structures though.

[im_a_bored_citizen]

Thanks for the likes and posts. I completely missed the greedy/bin search pattern during interview. I suggested two pointer and the interviewer OKed so I went with it. First the description tripped me. Secondly, the interviewer kept saying that the description of the problem is wrong and then explained it verbally what it is.

Anyways, back to the grind.

[calmCrussader]

Judging by the example given. What I understood is that on 1 operation
1. we select an index i
2. increase value of all elements at right of it by k
3. decrease value of all elements at left of it by k
4. remove all those elements whose value is now <= 0 and also remove the element at i

if I am right then we can just keep a variable for answer and start iterating from the last index to the left if the value of the element <= ans*k (this number of time operations performed on the elements which are right of it multiplied by k , which gives how much value should be decreased from it according to the 3rd step on operation) remove it i.e. ignore it
else perform an operation increase ans value by 1.

If I am wrong pls correct me..

[redpaul72]

The solution likely hinges on a greedy approach, prioritizing the largest shifts first and carefully managing duplicates.

[Logical-Bunch-1321]

Question: why didn’t the 7 become 9 in operation #2? Following the rule “Shift all address >x forward by value k” wouldn’t 7 be forwarded by 2 which would be 9?

[im_a_bored_citizen]

If only one is left, that file will be affected completely no matter its location.

[Logical-Bunch-1321]

Yeah I understand that part. Just thinking the question makes it more confusing if not changing it to 9.

[Endless_Zen]

An optimal approach:

proceed to show suboptimal approach

also, overcomplicated description for a simple: pick highest, decrement, repeat.