Thanks @NeetCodeIO again for the crystal-clear explanation 💖 Btw, I found out this simple optimization make me beating 100% solution yay: if len(heap) < k: heapq.heappush(heap, sum) elif len(heap) >= k and sum > heap[0]: heapq.heappop(heap) heapq.heappush(heap, sum) Simply put, add the sum conditionally instead of checking the size after pre-add the sum to the heap. Have a good day!
You can actually improve the overall time complexity further, from O(n+hlogk) to O(n+n) on average. You can use quickselect on the list of sums, which gives a linear kth element on average. In an interview, you might choose to go with the minheap, because its very simple to implement and explain, but if the interviewer will then ask "How can you improve this further, to linear time", you should mention that Quickselect (which is Quick Sort, minus the sort part, since you just look for the kth element) has a linear time complexity on average, but worst case of O(n^2). FAANG will, and do, ask you this.
I tried your approach, but min heap solution is faster than quick select by a wide margin for larger inputs.... I think on a larger scale n>>hlogk because of that logk factor and also for average case h=logn which is
Thanks once again for the great explanation, I totally didn't think about using a min heap! Even though I found that my times were about the same between the min heap approach and the sorting approach, I suspect that was because the list only needs to be sorted once for this problem. If there was a problem that required getting the kth largest value multiple times (eg. if it had asked to return a list of kth largest values, one for each level of the tree), then the min heap approach would likely be noticably more efficient.
Does anyone have any idea about what difficulty level dsa questions are usually asked for the roles of ml engineer, AI engineer etc. And what topics are asked usually?
Google interview tomorrow. Thanks for all your help. Wish me luck🤞
All the best bro!!
Best of luck bro!!
inshallah
All the best bro😊
good luck king!
Thanks @NeetCodeIO again for the crystal-clear explanation 💖
Btw, I found out this simple optimization make me beating 100% solution yay:
if len(heap) < k: heapq.heappush(heap, sum)
elif len(heap) >= k and sum > heap[0]: heapq.heappop(heap) heapq.heappush(heap, sum)
Simply put, add the sum conditionally instead of checking the size after pre-add the sum to the heap.
Have a good day!
You can actually improve the overall time complexity further, from O(n+hlogk) to O(n+n) on average. You can use quickselect on the list of sums, which gives a linear kth element on average.
In an interview, you might choose to go with the minheap, because its very simple to implement and explain, but if the interviewer will then ask "How can you improve this further, to linear time", you should mention that Quickselect (which is Quick Sort, minus the sort part, since you just look for the kth element) has a linear time complexity on average, but worst case of O(n^2).
FAANG will, and do, ask you this.
I tried your approach, but min heap solution is faster than quick select by a wide margin for larger inputs....
I think on a larger scale n>>hlogk because of that logk factor and also for average case h=logn which is
Thanks once again for the great explanation, I totally didn't think about using a min heap! Even though I found that my times were about the same between the min heap approach and the sorting approach, I suspect that was because the list only needs to be sorted once for this problem. If there was a problem that required getting the kth largest value multiple times (eg. if it had asked to return a list of kth largest values, one for each level of the tree), then the min heap approach would likely be noticably more efficient.
Let's get it!!
Does anyone have any idea about what difficulty level dsa questions are usually asked for the roles of ml engineer, AI engineer etc.
And what topics are asked usually?