Facebook Coding Interview Question - First and Last Position of X in Sorted Array
Vložit
- čas přidán 27. 02. 2020
- 11th May 2022 update - I have two slots in my interview-prep group classes! errichto.com/classes
Finding value in sorted array? Sounds easy, doesn't it? This is a coding interview question from Facebook. You can try it yourself on Leetcode: leetcode.com/problems/find-fi....
Get your CV reviewed and get a referral to FANG company, using www.rooftopslushie.com/invite...
Subscribe for more educational videos on algorithms, coding interviews and competitive programming.
- Github repository: github.com/Errichto/youtube
- Live streams on 2nd YT channel and on Twitch: / errichto2 & / errichto
- FB and Twitter: / errichto & / errichto
- Frequently Asked Questions: github.com/Errichto/youtube/w...
#Coding #Programming #CodingInterview
"Thinking is very good in programming"
That also means: "Not Thinking is too bad in programming!"
lol nice icon
@@NoName-ip4tt *very bad
Damn he's good, and it takes me a minute to just process his logic after he writes it. Someday senpai, someday
Yep. This is a common interview question and it's a good one because it's just different enough from standard binary search to avoid a memorized solution and just simple enough to be implemented and discussed in a half hour interview. Sure, plenty of people have practiced this but writing it out and testing it on a whiteboard still demonstrates programming ability.
Thanks for the video, clear and short as usual. Besides lower_bound and upper_bound, there is one builtin function that not everyone knows about called equal_range that does exactly what required in a single step
:0 sponsor! Thank you for all the videos and content in general, I can't express my gratitude enough
The concept of modifying the function to check element >= x and then using It to find pos of x+1 is lit! The best use of the fact that the array is/can be sorted
Cool, I just coded two binary search one for first pos and other for last pos. Yours is cleaner. Nice :)
If I write in java...I could have just first arranged it in ascending order and then I would have simple typed:- l.indexOf(x) // l being the array and then l.lastIndexOf(X) as simple as that!
@@abhinavdhama7193 uh no.
1) The interviewer is obviously not looking for that
2) It's already in ascending order.
3) indexOf is O(n).
@@Squirrelschaser why is the interviewer not looking for that?
@@abhinavdhama7193 Because he obviously does not want you to use a built-in function and it's not even the optimal solution?
@@Squirrelschaser Not optimal according to what? I guarantee you if you use that in an everyday problem your teammates are going to hang you from your nails.
Thanks, Errichto very nice solution! I did two binary searches, its a nice idea to use the information you obtained on the first search!!!.
Excellent content, I'm learning a lot. Thank you for what you're doing.
heyyy :) first sponsor.
i am feeling like a proud father.
I also got an offer from some game :D
@@Errichto that's nice to here. keep on moving forward.
My first answer probably would have been just looping through the array once and then saving and returning the index if time complexity was irrelevant 😅
I'm really looking forward to your videos on Dynamic Programming and Backtracking since they're fundamental
I did some videos on DP already. Maybe will cover backtracking in the future.
Was waiting for something. Good question to understand important concepts.
Yup, especially when you try to implement this in a simple way.
I have solved a problem like this only twist is the array is not sorted. I remember using the Dutch flag method to do this using pivot value as the given element and use partition method used in quick sort.
@@urstrulyubc O( N ) indeed as we need to traverse through the array and move the numbers lesser than the element to the left and greater elements to the right and to track the elements equal with start and stop indices. Ofcourse we need to handle case of given number not in the list.
I love you videos Errichto !!! Thanks so much !!
Great video! I understood most of it, up until the last bit. I'm still fairly new to programming and don't know algorithms yet, but I am confident I can learn with resources like this. Thank you!
i also had trouble with understanding what he did after he created the function called it two times for the right and the left
it would be cool if @Errichto would explain it a little bit more
Brilliant solution. I thought binary search, but then was stumped with “I found left boundary.. how do I do this without a for loop off of this index?” And then you explained the binary search on x and then a value greater than it, it all clicked. Thank you!
Nice explanations. For the second call of first_pos, if you give the same vector but only starting from "first" index, found in the previous call, I guess it gives a speed up, right? Or is it not worth it?
Thank you for your videos.
Can u tell the right direction to improve the CP for Intermediate.
I can only solve first 1-2 problems in contest. How can i improve that.
Thanks in advance.
I haven't run the code myself but I was dry running it in my mind and it looks like if you assign first_pos as -1, then you don't need to have the check for first
Ah
I wrote the code and I see the importance of the check
It is check for unary array case and I must say that is the most killing logic in whole soln
Nice vid! How would the algo be modify to count all instances of the target num?
You can do this with less opperations with one binary search. By restarting the search a lot of useful information is thrown away.
Even with the solution given here one could have at least started your second binary search from the first element found.
std::equal_range() then check and adjust the iterators pair...
Thanks a lot for putting videos.
The king of algorithms
could you add complexity discussion at the end? I would have just reversed the array at some point which probably would've increased time complexity.
Hi Errichto, thanks for all the work you're doing. Can you please make a video on Manachers Algorithm? #Suggestion
ja trafiłem tu od joma, fajnie ze Polska w kodowaniu cos znaczy 😀możesz polecić jakieś strony z prostymi zadaniami naprawdę prostymi dla beginnerów do próbowania swoich sił?
could you please make a video on concept of magic square and its variations.
There is also the function of
std::equal_range()
in C++.
yeah like this,
vector v = {1,2,3,4,5,5,5,6,7,8,9};
cout
What tool do you use to write to black canvas screen, may be if you're using one note for example, then do you use mouse for writing or do you have touch enabled device?
Binary search questions have a really good disceranble pattern.
I always get compilation error driver not found in leetcode but when i run the same code in intellij it works fine.Can someone help me with this,By the way the error is array.length cannot find symbol[in_Driver_.Java].
Basically you could just search for x+0.5 and x-0.5 in order to achieve it using normal binary search, if the inputs are integers.
First = binsearch(x-0.5)
Last = binsearch(x+0.5)
I havent watched the full video but i used Binary Search to find the position of the number we are looking for, and then store the index of the number into two integer var, represent for the first and last postition of X. And then, i move the integer (first pos) backward until the previous element in the array doesnt have the same value and i do the same with the integer (last pos) but move forward. Then print them out. Is that a good solution ??
Does normal binary search always gives first element in case duplicate value are present in sorted vector ?
Hey,
What if your 'x' is INT_MAX? Would it still work?
I didnt underrstand the last part as to why we initialise firstpos=n and not firstpos=-1 . can anyone help
bcz in the case of n=0 the position would be 0,0 and not -1,-1
You're using C++, right? I know C++ but have done most of my coding in C. Can you recommend some good resources to learn/practice more C++? I know the syntax alright, but I start writing code, C language flows out automatically instead of C++.
Btw, what's your opinion on C or C++, vs something like Python? From a job perspective, is it better to market myself as a C++ programmer vs a Python programmer? (I am only learning Python, never used it to write any large code.)
Hi Errichto, thanks for the video and the cool explanation.
What software do you use to draw your solution? Is it microsoft whiteboard?
Hello, can you please make a video stating important maths topics for programming.
clean and elegant.
Nice and Simple Explanation, thank for video keep it up
I think it can easily be done by upper bound and lower bound. If we can't find the val. in the array then cout -1. I THINK
Errichto, can you please break down the intuition on leetcode problems like buy and sell stock and it’s variants in DP . Thank you .
I try to break down the intuition for all problems I'm covering on my channel ;p
Sir,
How about using binary search to find first occurance...
And using jump search left side and right side to find occurances
Love this video!
Erricto I think e better optimisation with this algorithm might be if we binary search the last_pos only in the subArrary that starts with the index of first_pos and ends at n. What do you think???
it's better, but not by much, since binary search itself is already very fast
Why don't you do a video on the gear that you use to code/build anything? We would love to see it.
is there a problem to solve the question with brute force strategy
what ODE are using sir?
It's not only me who solved a problem 9 (or 1) months ago and then getting "wrong-answer" on re-attempt. :p Until 07:25 I was thinking you are going to solve it in one while loop. Thanks for the lesson, mate! :)
It's very easy for a mistake in such a problem, I also got WA here :D
Wouldn't it breaks if there is no x in your array? First it would return first position of something greater than x (e.g. 9) and then exactly the same position on the second run. Please correct me if I'm wrong.
What's faster? lower_bound method or your implementation?
lower_bound might be slightly faster, but you should never care about so small differences.
I think you could do `last = first_pos(a[first_pos..], x + 1) - 1`
There is no need to take the full array since you know that it's sorted and that x + 1 is going to be bigger than x :)
Oh yes that makes it even faster ! ;)
@@verushannaidoo9450 It's only 1 less iteration of binary search on average, if for example n=2^17 instead of doing 34 iterations in total you'll do 33 on average. It really doesn't matter that much.
@@dorijanlendvaj8356 Makes sense a very slight and unnoticeable difference
Does this also work with an array like [1,2,3,4,5] when you are looking for 5? First_pos(a, 6) returns then -1, so the program returns {-1, -1} instead of [4,4] I think
I think no,
first_pos(a, 5) returns 4
first_pos(a, 6) returns 5 then he subtracts it with 1. The final result is 4,4 which is correct as you mentioned
I used recursion. I find the middle element (mid) first. If this element matches X, then I make two recursive calls - one for the array elements 'start' through mid-1, and the other for array elements mid+1 through 'end' (where 'start' and 'end' represent the indices of the first and last element of the original array). The first recursive call will return the 'left' position and the second one the 'right' position.
What do you think of his approach? What's your opinion on using recursion in general? Thanks.
In my opinion sir, this would take a lot more steps than the ones taken above. Therefore the program would be inefficient. Recursion is good but usually it leads to having many functions in stack which ultimately causes stack overflow.
@@pulkitgupta2009 If you have the right algorithm, that's not a problem. Tail recursion avoids stack overflows because the function call re-uses the same stack frame (which also means it can be converted into a loop, tail recursion done right is more clear than a loop though in my opinion).
Without looking at the video, just use the library functions to reverse it and then the one to find the first element, not fast but 3 lines of code 😁
quite brilliant. I would have just linear searched for min & max positions like most people I presume
Sure, but we also know is slow as fuck, so i would think in other ways too.
I didn't try this question, but I find that if they specify a desired time complexity, your solution can fail if it's too slow for a larger test case
Most non-programmers would. I can't really imagine a programmer not using binary search :D
@@fritt_wastaken Then you have a poor imagination.
I meant binary search for the number, then naively linear search backwards and forwards for the ends of the range. I may not be that smart, but I'm not that not smart...
I made it so that I first find any x with Binary Search then run in a while() as much as possible to the left and right where left and right are indexes of elements that equal x and at the same time right and left are within the array length and 0.
I think it is with the same time complexity as yours. I like your solution more though
No it’s not, your solution is O(N) worst case.
I have much to catch up, I would've just scanned the array from the front and the back until I found the positions
Binary Search is much faster in a SORTED Array
binary search is only posible in a SORTED Array ;-)
Thank you Sir
Can we just use lower_bound and upper_bound-1
Could you please make a video for preparation of Google Code Jam 2020
Solve algo problems, including those from previous editions of Google Code Jam. You're welcome :D
Does programming language matters??? If I use python will it be ok?
Bro is python3 allowed there?
Can you use a hash table to cache all elements and their indices, then search for the target and it’s min and max indices?
yes, you can, but you only need to store the indices of the first, and the last occurrence
I would do a binary search to find the element then create two variables min max intialized to that position , one that goes to the right and the other to the left
if they find another element different from that element , i will save the last position
Your solution is O(N) instead of O(log(N)).
Worst case scenario: O(N)
You will loop through all the element
Errichto encouraged me to train to become a competitive programmer!
Just solve using segtree. First find leftmost position using one query then do same to find rightmost . Node stores count of 8 in the range
Linear iteration would be much faster and simpler than creating a segment tree ;p
@@Errichto yea but I have noticed that thinking in pressure is much harder for me. With segtree there are so many times I don't have to think. I just gave alternate solution. I would have also used upper bound and lower bound and then taken their difference.
@@Errichto Also can you make video bitmask dp I want to understand it properly.
I haven’t watched the full video. Yet i am not an expert programmer but i can say that we can find the first and the last specific element we need by doing the following: first we do a loop starts from index 0 to the first specific element we catch. Then we do a loop starts from array.length-1 and breaks on the first specific element we want.
That's correct, but the time complexity would be O(2n) = O(n), with binary search, the time complexity downs to O(logn), that would be much faster.
Weirdo Beardo i am sorry to say that i have not studied Data Structure yet.
@@DAEDSOLOGAMES Haha, dont say that dude. Glad to help you!
Weirdo Beardo Glad to learn new thing from you. Thanks dude
That kind of only works better for test cases that have a large duplicate string X like, finding bounds of 3 in 12333333333333333333333334. It wouldn't do 112222222222222223333333333333...44444444444444..999999 any favors if you're trying to find bounds of 1.
Thank you.
If you are allowed to use builtin function then you can use equal_range too. It returns pair of iterators returned by lower_bound and upper_bound.
(... I've seen a problem with very tight TL, where lower_bound followed by upper_bound gets TLE and equal_range gets AC. Any idea what optimization equal_range may using? ...)
I actually didn't know about equal_range function. Anyway, coding interviews are about checking your ability to implement something basic yourself, not just use libraries (that would be very language-dependent). Regarding that problem with tight TL, hard to say - I don't think that equal_range doesn't anything anything different than lower and upper bound www.cplusplus.com/reference/algorithm/equal_range/
@@Errichto I commented from competitive programming perspective.
BTW, I think equal_range does something under the hood. Consider this problem: Given four lists, you need to count number of ways to choose one element from each such that they sum up to 0. Standard Meet-in-the-middle:
Problem Link: www.spoj.com/problems/SUMFOUR/
TLE Code: paste.ubuntu.com/p/CdgywfjtqZ/
AC Code: paste.ubuntu.com/p/c9ZyqBz5b6/
As you can see, the ONLY difference is the way number of occurrences is counted. Any ideas on this?
@@rezwanarefin3493 Well, test it locally maybe. Is running time difference bigger than 5%?
please don't get angry with my question but why didn't you use equal_range ?
You have tutorial about algorithm graph problem?
Not yet
Hey errichto, it seemed too complicated solution for such a task. I was wondering if you intended to achieve speed over code simplicity, so that's the reason behind the complexity?
Thanks
I tried my own code in LeetCode. I wanna know why the runtime in LeetCode was different for every trial of the same code? xD
It’s doesn’t really matter or is important. Just be aware of the complexity’s
@8:45 I did not quite get it why "first_pos = size_of_array" rather than "first_pos=-1". Tried to repeat several times but still could not. Can someone help?
I guess this way when your target is not an element of the array, the first position is set to 'size_of_array' so then the second time when you search for index of 'x+1' to find the next element, that index will always be at most 'size_of_array -1' so this way you get {-1, -1} because first > last, and that takes care of any error handling you'd otherwise have to do. I don't know if this is the reason why, but it's what I'm getting out of it.
Has anyone tried rooftop slushie that Ericto is talking about? How is it?
pls make ones and zeros prblm of dp in leetcode
If our array lenght is n , cant we iterate through our array first (n --> 1) , so the first x here is the last x pos and then revers iteratr , the first x here is the first x pos ?
That is the obvious solution, but it takes O(n) time while this takes O(logn). Basically this is a lot faster...
If using stl, equal_range could be used.
Modified binary search, two times
Suppose if we get any position in array and traverse left until we get first value and traverse right until we get different element
Can we apply this approach
Yes, but it will be slow. Your solution is O(n). Whereas solution in video will be O(log n). Where n is number of elements in array.
Correct me if I am wrong.
A more compact way to do it:
int first_pos(vector& a; int x){
int low = -1, high = n;
while(high - low > 1){
int mid = (low + high)/2;
if(a[mid] < x) low = mid;
else high = mid;
}
return high;
}
mid should not be calculated in the manner you have it in your code, it should be low + (high-low)/2, that is done to avoid integer overflow for large array size
@@angelbythewings That's what people often say, but that's outdated info on 64 bit platforms. The 32 bit int can still overflow even with your code. If you want it to not overflow, use a 64 bit int and then it doesn't matter.
@@julesjacobs1 I don't think I completely follow you, how do you claim that it does not matter ?
@@angelbythewings If your 64 bit value overflows, that means that your array is 9223372 terabytes. Until such memory becomes available, there is absolutely no issue.
Hi, what if the array is not sorted? What approach we can apply?
I think that then just checking every element in the array in O(n) would be optimal, we cannot go faster. Because if the array is not sorted, we don't have any information about whether or not some elements we haven't yet checked are equal to the wanted number. I hope this makes sense!
interesting. I would have written a for loop with a switch statement inside.
for loop scans through every value and returns the first index of the value that matches condition then it goes to the next case and does the same thing this time it breaks when it reaches the end of the array.
I initialize the outputs with -1 so it just returns -1,-1 if nothing is found.
I haven't written anything yet. I'm ok mobile. It time complexity is the problem I'll jus learn about a searching algorithm and use it.
Seems like you’re trying to do a strange type of linear search, which in this case you just need to loop through once, no need to break unless it’s the second instance of the target. The problem is it’s not optimal because time complexity is O(n) compared to binary search, which is O(logn)
cool videos!
hey ! does solving this question interview (after being called from Facebook ) , make them accept you directly or it increases your chances to be accepted ?
Why you can't write in python are complete in just 2 lines like this
return [nums.index(target), len(nums) - 1 nums[ :: -1].index(target)]
Why vector&a , not vectora , somebody explain
vector a will create a new copy, while vector &a will take the vector passed from the main function directly (but modifying it also modifies the vector in main)
@@jalsol cool, that's what I thought , Thanks a lot
im wondering if it's possible to get first index and last index in one go
You can implement recursive binary search but it would eventually need to branch into two calls anyway, so it's still 2*log.
Generally, we're looking for two numbers (i, j) and there can be around n^2 possible pairs. You need log(n^2) = 2*log(n) checks at least.
@@Errichto thank you
Upper bound and lower bound
Hello! someone know why he did low+(high-low)/2 for the mid value instead of high+low/2 ?
Okey just did a quick search, in case someone was wondering the same as my its because in C++, Java and other coding languages the integers have a fixed value range so in some cases high and low could be in the value range but their sum produce an overflow.
It's because the value will overflow, suppose high and low is nearly maximum value that data type int can hold , so when we add both ,it won't be able to handle it ,but if we just add simply the difference of them ,we can be saved from overflow.
He explains in the video why.
@@jxggxr_dxv Which minute? I don't find it
@@mayaki2406 Sorry, my bad, indeed is not in this video. I mixed up things. He explains the Binary Search in this video: czcams.com/video/GU7DpgHINWQ/video.html it should start where he explains why is better to use the formula you mentioned. However, I suggest to watch the full video though, it's a good one. :)
@@jxggxr_dxv I will do it for sure!! tyvm sir
do you use a wacom tablet?
yes, why?
@@Errichto just guessing
*programming is understanding*
i solve it using map data structure but why ur solution is faster than mine ?
I did not hear about team blind?, BUT I SURELY DID ABOUT TEAM ROCKET.
Genius
For the last pos. can't we just get the count of 8 (for ex 8 comes 3 times) then the index would be [firstpos, firstpos+(count - 1)]
How do u plan on getting the count tho
@@rahulbansode1537 In Python by l.count(num)
@@ojasshandilya4362 that's still an O(n) operation right