Facebook Coding Interview Question - findLongestSubarrayBySum

Preparing For Your Coding Interviews? Use These Resources
————————————————————

Other Social Media
----------------------------------------------

Show Support
------------------------------------------------------------------------------

#coding #programming #softwareengineering

[thesanmi]

Sliding window with two pointer solution breaks down if you have negative numbers in the array.

A more resilient approach is to add the sum as we go and put in a hashmap from sum to index of sum.
So at index i, all we need to do is check if a complement sum exists i.e. (sumSoFar - Target) exists in the map and update if the value from the map map map[ i - index] is larger than max length. this is O(N), uses one pointer and works with negative entries

[RogerGarrett]

I worked my entire career (45 years) as a software engineer and I never, ever had to address a coding problem like this. Why in the world are these kinds of questions part of programmer interview questions?

[emmanuelonwumah]

I see a few people saying the nested while loop makes the time complexity n^2. It does not, because the inner loop is not depending on the size of n. This algorithm is still linear.

[Mahorir]

Can be optimised further by keeping the window size to at least the size of last found window

[Monir]

Nick I had an interview on super short notice and all I did was watch your videos. You were CLUTCH! Aced them. Thanks a lot for the content :)

[popmadalin]

I love this kind of videos.Keep up the good work man <3

[mohamedsamir]

Impressive as usual it all about how you describe the answer and the problem I hope many creators learn from you

[studywithme]

This is exactly how I thought I would solve it but didn't know it has a name "slicing window approach".

[jbkhan]

Excellent job describing these algorithms! I wish I had videos like these when I first started my career in software engineering!

[saulgoodman]

One important thing to know is that this approach works as long as there are no negatives. (2 pointers usually don't work when there's negatives)

[chumaumenze]

I totally agree. Some of the problem description often make things look more complex than it should. I tend to read them like 3 times to make sure I understand it.

[Hogaboga]

OH MY GOD! So I've been watching your videos and solving these questions for the past 4 hours. I could finally come up with the right solution this time. I'm not so rusty after all! So pumped rn! lol

[TechOnScreen]

You write so clean code than other YouTubers out there. Impressed!

[dinhnhobao]

HIGH Quality content!! Gonna watch all your Leetcode qns interview now to help me prepare!!

[deepeshmeena]

Some people think that two nested while loops have time complexity O(n^2). pay attention to the explanation the pointers never go back to the start of the array they just move in one direction so linear time

[davidjames]

Since the first 8 array elements sum to 15, you would then only need to check subarrays of length 9 or longer (starting at elements 2, 3, 4, and 5). Once you don't find any of length 9 and all of those length 9 sums are more than 15, you would be done.

[eldarcivgin]

You can also add a contidion that exits the loop if the total length of the array subtracted by the current position is shorter than the length of the subarray we already found, because then we can't find any subarray longer then that already found.

[scoperesolution]

I love thos channel. We want videos like this... All your videos are great @Nick.

[gabriellerosa]

Love your work in youtube ! Great algo and good question. Ty you're helping me :2

[total_dk]

I might be mistaken, but instead of only incrementing your left pointer when current_sum is higher than s (while r != [-1]), could you not increment both pointers, because you don't care about any array that's shorter than your currently found subarray? (Of course, if you have not found a proper subarray (and r == [-1]), then you need to only increment the left pointer.)

Of course, this would not reduce the solution to less than O(n), but would change it to worst case ~n instead of ~2n (if I'm not mistaken)