Hi Everyone!

I haven't been active lately because of interviews going on. Recently I appeared for Amazon Interview for Internship and there was a problem that I still have doubts with:

I confirmed with the interviewer that there is a formation of the cycle in this, he told me that cycle formation is possible and whenever it happens you have to break the chain there since you don't want to repeat the same elements

As you can see the graph is not an unweighted DAG, Hence, the problem became finding acyclic longest chain in a directed cyclic graph.

I wasn't able to come with a clear solution (O(n)) because it didn't feel right that how I can take care of cases with a cycle using maybe topological sort? So I wanted to ask what is the best possible complexity answer for this.

Thanks!

UPD: The problem might not even be of a graph, I have mentioned the original problem in the exact words as by the interviewer, not that you have to follow the graph approach, I just want to find any possible views on this.

UPD2: Got selected anyway lol :p

Hi!

While solving Div2 D, I came across another problem (not related to solving the actual problem though) :

Given a binary array A of size N, you are required to remove all the occurrence of 1 in the array only using the following step:

• Select any subarray of size K ( K <= N ) and remove it from the array. After removing it, the adjacent parts (if any) will be joined as a single array.

Let's define Ans as the size remaining array after removing all the occurrence of 1 in A. Find the maximum value of Ans or say that it's impossible.

eg,

A : [1, 0, 0, 1, 0, 0, 1, 1] ,
K = 2
We have, Ans = 2 (In the end 3rd and 6th 0 's in the remaining array, Indexing from 1), multiple answers possible.

A simple greedy solution can be to select a window with a maximum frequency of 1s and remove it, continue doing this until all 1s are gone or say it's impossible. O(n^2) Edit: Wrong approach sorry :p

I'd like to hear your approach to this problem.

Thanks in advance!