Thanks a lot of commenting that this was Apple's trending question. always helpful to know that. One question I have is, why not start evicting elements that are no longer relevant, older than 300 in comparison to the last timestamp. that will limit our space to be constant. Also, recently I have started seeing interviews asking for concurrency. So it could also be good if there are separate thread that is working under the hood to remove things as soon as it detects that the size of the storage is becoming larger than 300 time range. and also using lock for that matter. Obviously typical interviews won't ask for that but something I've observed.
Great solution. Could you please add these onto your queue. LC 348 Design Tic Tac Toe, LC 480 Sliding Window Median, LC 1060 Missing Element in Sorted Array, LC 825 Friends of Appropriate ages, LC 1539 Kth Missing Positive Number, LC 16 3Sum Closest, LC Design Skiplist, LC 317 Shortest Distance from All Buildings(Google). I look forward to more content and like the new videos on interviewing
You can use either. You are searching for the value of ts - 300. Suppose you have hit(1), hit(2) and then getHits(301). This means that you want all the hits from timestamp 301 all the way down to, but *not* including, timestamp 1. So you need to find your lower bound index which would be the index where the timestamp is equal to 1. But remember that we don't want to actually include this index because this timestamp is right outside the last 300 seconds time window. So we want the *next* index. If you use
Yes it does handle duplicate values. Each duplicate value is entered in the hits array as a separate entry. The left pointer is being incremented, visualize it as an arrow that starts at the left of this array and is advancing from left to right. This means that when it hits duplicate values, let's say there is 10, 10, 10. The left arrow will be pointing at that first ten and thus include the other tens. If these tens made up the minimum of the valid range, then the last return line of getHits() would essentially remove everything before the tens and include these three hits in the final total. On the other hand, if these tens were not in the range, then the midpoint calculation would ensure that the arrow advances to a new midpoint which would exclude all of these tens. In other words, the tens, or duplicates, will always get treated as a group because (1) the arrow either stops at the first duplicate or (2) advances past all of them. There is no situation where the midpoint calculation of the binary search would lead your arrow to end up in the middle of the group of tens. Hard to explain purely through text so I encourage you to work through some examples you create. Try an array of all duplicates and see what happens. Then try an array of five sets of duplicates and see what happens.
That is a leetcode premium feature unfortunately. Though if you don’t already have it and are serious about getting into FAANG, I’d highly recommend purchasing it. It’s worth every cent
Super underrated. I was neetcode pilled until I found your channel. Pretty good and in-depth explanations.
Thanks a lot of commenting that this was Apple's trending question. always helpful to know that.
One question I have is, why not start evicting elements that are no longer relevant, older than 300 in comparison to the last timestamp. that will limit our space to be constant.
Also, recently I have started seeing interviews asking for concurrency. So it could also be good if there are separate thread that is working under the hood to remove things as soon as it detects that the size of the storage is becoming larger than 300 time range. and also using lock for that matter. Obviously typical interviews won't ask for that but something I've observed.
Please keep the videos coming, your explanations are so clear and understandable
🙏
Great solution. Could you please add these onto your queue. LC 348 Design Tic Tac Toe, LC 480 Sliding Window Median, LC 1060 Missing Element in Sorted Array, LC 825 Friends of Appropriate ages, LC 1539 Kth Missing Positive Number, LC 16 3Sum Closest, LC Design Skiplist, LC 317 Shortest Distance from All Buildings(Google). I look forward to more content and like the new videos on interviewing
In the binary search, how can we determine if it is l
You can use either. You are searching for the value of ts - 300. Suppose you have hit(1), hit(2) and then getHits(301). This means that you want all the hits from timestamp 301 all the way down to, but *not* including, timestamp 1. So you need to find your lower bound index which would be the index where the timestamp is equal to 1. But remember that we don't want to actually include this index because this timestamp is right outside the last 300 seconds time window. So we want the *next* index.
If you use
will this handle the case of multiple hits at same time stamp?
I was wondering the same, how can you do binary search when there are duplicate values?
Yes it does handle duplicate values. Each duplicate value is entered in the hits array as a separate entry. The left pointer is being incremented, visualize it as an arrow that starts at the left of this array and is advancing from left to right. This means that when it hits duplicate values, let's say there is 10, 10, 10. The left arrow will be pointing at that first ten and thus include the other tens. If these tens made up the minimum of the valid range, then the last return line of getHits() would essentially remove everything before the tens and include these three hits in the final total. On the other hand, if these tens were not in the range, then the midpoint calculation would ensure that the arrow advances to a new midpoint which would exclude all of these tens. In other words, the tens, or duplicates, will always get treated as a group because (1) the arrow either stops at the first duplicate or (2) advances past all of them. There is no situation where the midpoint calculation of the binary search would lead your arrow to end up in the middle of the group of tens. Hard to explain purely through text so I encourage you to work through some examples you create. Try an array of all duplicates and see what happens. Then try an array of five sets of duplicates and see what happens.
very good explanation! plz where can I find the most current asked questions per company ?
That is a leetcode premium feature unfortunately. Though if you don’t already have it and are serious about getting into FAANG, I’d highly recommend purchasing it. It’s worth every cent