gXa's blog

Netflix Onsite Interview Question
By gXa, history, 3 years ago, In English

An array is given, and an index present in it.

A window must be chosen such that it includes the index, has this component maximized — sum(a[i]...a[j])*(j-i+1), but the component must be equal to or less than the threshold (sum(a[i]...a[j])*(j-i+1) <= threshold).

How we can solve this question optimally?

One example of the problem:

Input

N: 8
Arr[]: [2,-3,-4,5,5,6,7,8]
Ind: 4
Threshold = 20

Output

One possible answer
[5,5]

Explanation of output
[5, 5] = 10*2 = 20 <= 20 (threshold)
  • Vote: I like it
  • +17
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Is it given, that the elements can be non-negative only ?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, they can be negative too.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I can think of an O(nlog(n)). But it will only work when all a[i]>=0.
We will find the minimum index l such that sum(a[l]...a[i])*(i-l+1)<threshold and then we will loop from l to i. For each iteration we will find a suitable right index>=i using binary search and store the maximum valid answer. Whenever we get a better answer, we simply update the answer.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    we can use two pointer as well if they are non-negative. Take two pointers l ,r.pointing to first element of the array initially now we expand the range ( increment r ) as long as we can expand (i.e sum(a[i]...a[j])*(j-i+1) <= threshold) and if the component of our range exceeds the threshold we shrink our range (increment l ). and we can take the maximum among the plausible ranges to get our answer.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      It will give a WA

      Test case
      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Yes, he did mention that it will only work when all the values are non-negative.

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How is the output [5,5] , and do we have to find component with minimum length or any component will work , and what are the constraints .

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Any component will work.

    Explanation of output [5, 5] = 10*2 = 20 <= 20 (threshold)

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Shouldn't it be [4,5] ( 1 based indexing )

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I had placed actual elements there, your output is correct if we return the indexes

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm not sure as I am noob but we can use DP here to compute all values lesser than Or equal to threshold which includes index element and print max of it again I'm not sure I'm just telling one of the possibility that came to my mind

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is O(n²) in the worst case as count of such numbers can be of the order n². For example take threshold value to be very large, and all the elements to 0 maybe. Now whatever combination you take you will get the value less than threshold value. Suppose there are r elements to the right of index and l elements to the left of index (can be index itself). Total number of possibilities = r*l = r*(n-r) This will be maximum at r=n/2. Therefore in the worst case total number of possibilities = n²/4 .... So even if you use some kind of dp to store all the values less than or equal to threshold then also it's O(n²) atleast.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What if we use some kind of modified kadane here?

      → Reply
»
3 years ago, # |
  Vote: I like it +89 Vote: I do not like it

Looks very hard, I've seen some similar problems in the past (no spoilers) and even without the threshold they were rather tough, so I don't think that netflix expects a subquadratic solution here.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the affirmation. I was wondering how one can expect to achieve subquadratic time in an interview.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ok, I posted to get a sense of answers. I proposed quadratic too myself during the interview.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can we use CHT here ??

    like lets say the line $$$y = threshold $$$, passing through the envelope of hull, interesects on two x-coordinates,$$$x_{left}$$$ and $$$x_{right}$$$ , so for the range $$$[x_{left},x_{right}]$$$, answer is the value on the hull, but how to optimally construct envelope for range so we could answer for any point in range $$$[-\infty,\infty] $$$.

    Or any other way to solve this, just curious !! :)

    → Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can't think of anything close to linear/nlogn,i believe that they were expecting O(N*N).

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Did you talk through the bruteforce and then gradually arrived to some optimal solution taking hints from interviewer?

→ Reply