Sort A K Sorted Array - Investigating Applications of Min/Max Heaps

科学和技术

Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Subscribe To Live Tech Offers: offerfeed.io
Join Our Coaching Service: backtobackswe.com/coaching
Question: Write a program which takes as input a very long sequence of numbers and prints the numbers in sorted order. Each number is at most k away from its correctly sorted position. (Such an array is sometimes referred to as being k-sorted).
Pramp: www.pramp.com
Examples:
Input:
[ 3, -1, 2, 6, 4, 5 , 8 ]
k = 2
Each number is no more than 2 indices from its final sorted position.
Output:
[ -1, 2, 3, 4, 5, 6, 8 ]
It is often that data finds itself in an almost sorted state.
For example: A server needs to sort orders coming in internationally and due to differences in server loads and network routes some earlier orders come in after later orders.
How do we efficiently sort this almost sorted data?
Whenever I hear or think of sorting or searching, I think of my fast sorting algorithms, binary search, and min/max heaps.

Approach 1 (Brute Force)
Just run a quick sorting algorithm like mergesort or quicksort and have the array sorted in O( n * log(n) ) time.
This is an obvious answer.
The key insight we need to make is that most of the items are very close to their final positions and therefore we need to just “touch up” the order of the items.
How will we perform this “touch up”?

Approach 2 (Min Heap To The Rescue)
Example:
[ 3, -1, 2, 6, 4, 5, 8 ]
k = 2
How do I know who belongs at index 0?
Well, this leads me to ask you, what are the potentialities for each index? What items could be at index 0?
3 can, -1 can (if it moves 1 spot back), 2 can (if it moves 2 spots back), but 6 cannot (it would have to move 3 spots back but k = 2, this is not allowed).
Now our interest is in k + 1 items, 3, -1, and 2 each could go at index 0.
Our job is now reduced to finding the minimum of k + 1 elements at a time.
What data structure helps me with keeping track of minimums and maximums in a set of data very well?
A heap.
We will use a min heap because we want access to the smallest item across k + 1 items.

The Algorithm
Add the first k + 1 items to a min heap.
Iterate through every index in the array.
Place the min item and add the next item that has not been added yet to the heap.
When we cannot add un-added items to the heap near the end (at some point every item will have seen the heap but we will not be at the end of the iteration just yet) we can just continue ejecting and placing the min items.

Complexities
Time: O( n * log( k ) )
For all n items we will perform an insertion and removal from a min heap holding k + 1 items.
Space: O( k )
The heap will hold k + 1 numbers at maximum before an item is ejected.

++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: cnboth.info/long/Of7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: cnboth.info
GeeksForGeeks: cnboth.info/long/0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: cnboth.info
Success In Tech: cnboth.info/long/-vYrOAmtrx9sBzJAf3x_xw
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is 11.3 in the book "Elements of Programming Interviews"

评论

  • Back To Back SWE
    Back To Back SWE年 前

    Table of Contents: The Problem Introduction 0:00 - 1:33 Why Not Just Sort It? 1:33 - 2:08 Investigating How We Can Actually Use K 2:08 - 3:22 Expressing The Exhaustive Set of Possibilities 3:22 - 5:57 Analyzing The Critical Information 5:57 - 7:17 We Begin Doing Placements 7:17 - 10:51 Time Complexity 10:51 - 12:47 Space Complexity 12:47 - 13:27 Wrap Up 13:27 - 14:05 The code for the problem is in the description. Fully commented for teaching purposes.

  • mR. sTreEtwEaR

    mR. sTreEtwEaR

    5 个月 前

    @Back To Back SWE I edited little bit of my algorithm and its works fine with array which is not having large max value, but it take a little bit more time than heap sort. But I recently found about Radix sort and Count sort and they are perfect for this question . As I am a beginner , I am learning slowly slowly. And I m grateful you replied me, Thank you. Its really motivating.

  • Back To Back SWE

    Back To Back SWE

    5 个月 前

    hows it going with the question now

  • mR. sTreEtwEaR

    mR. sTreEtwEaR

    5 个月 前

    I am not that good with heap sorting plus O(Nlog(N)) time is taken . If we trade space for time, maybe it can be done in linear time. First make a new array of size maximum value of given array and then count no. of times values appear in given array and place at same index as value in new array. After that just use new array and place the value in sorted manner. idk its right or not. i m still trying,i got this question yesterday in my pramp interview.

  • Mark Bjerke
    Mark Bjerke5 天 前

    Really enjoyed this one, especially the stacking of solutions per index of the possible solution and seeing the binary heap and complexity classes for time/space.

  • Deepti Gupta
    Deepti Gupta2 个月 前

    You are an awesome teacher! Keep doing great work! God bless!

  • Kiordo Miorjo
    Kiordo Miorjo2 个月 前

    I love your videos man!

  • Back To Back SWE

    Back To Back SWE

    2 个月 前

    thx

  • אביב פרידמן
    אביב פרידמן3 个月 前

    build a heap with k elements takes O(k) time so the time complexity is O(n*log(k) + k) == O(n*log(k))?

  • Back To Back SWE

    Back To Back SWE

    3 个月 前

    building a heap with k elements is log(k) per insertion (if we hold k items at max in heap) over k items so Θ(k*logk).

  • vaishnavi kulkarni
    vaishnavi kulkarni4 个月 前

    Hey ben, your approach fails for this example 4 3 1 2 5 with k=2 Any thoughts? Liked your approach BTW

  • Back To Back SWE

    Back To Back SWE

    4 个月 前

    Isn't that '4' 3 positions away from it's final sorted position?

  • Rahul Sharma
    Rahul Sharma4 个月 前

    Awesome explanation! I wonder when the k == n.length, it is best to just run a quick sort and save some space? Since quicksort will be in-place (or in worst case O(log n) space as the time complexity will be same as the heap sort.

  • Back To Back SWE

    Back To Back SWE

    4 个月 前

    Yeah I think? I'm fuzzy on this problem's description, solutions, etc. but yeah one can do internal optimization like that. The worst case will still rule though.

  • Anna Joen
    Anna Joen5 个月 前

    where is the code for it ?

  • Back To Back SWE

    Back To Back SWE

    5 个月 前

    The repository is deprecated - we only maintain backtobackswe.com now.

  • Abhash Jha
    Abhash Jha5 个月 前

    For anyone looking for a code implementation can look at the link below. Hope this helps. I took this video as a reference for the code and also commented where it was required. pastebin.com/2xRuGeAi

  • Abhash Jha

    Abhash Jha

    5 个月 前

    Thanks man :)

  • Back To Back SWE

    Back To Back SWE

    5 个月 前

    nice!

  • Farheen Firdous
    Farheen Firdous5 个月 前

    One of the best video i have ever seen I really wanna say thank you from bottom of my heart 💯

  • Back To Back SWE

    Back To Back SWE

    5 个月 前

    sure!

  • Sergio Bilello
    Sergio Bilello6 个月 前

    where is the code?

  • Back To Back SWE

    Back To Back SWE

    6 个月 前

    The repository is deprecated - we only maintain backtobackswe.com now.

  • SuperPabbs
    SuperPabbs6 个月 前

    Wonderful teaching, Ben. Thank you.

  • Back To Back SWE

    Back To Back SWE

    6 个月 前

    sure

  • Ganesh Reddy
    Ganesh Reddy7 个月 前

    Wow

  • Back To Back SWE

    Back To Back SWE

    7 个月 前

    thx

  • Rachel Halpern
    Rachel Halpern7 个月 前

    I just got this question on Pramp yesterday and was so stuck! Happy to have found your channel :)

  • Back To Back SWE

    Back To Back SWE

    7 个月 前

    haha I got it on Pramp too - welcome

  • Pareksha Manchanda
    Pareksha Manchanda7 个月 前

    Great explanation, if we do this way in an interview, selection is 100%

  • Back To Back SWE

    Back To Back SWE

    7 个月 前

    ye

  • harshit air2 sahu
    harshit air2 sahu9 个月 前

    deeply explained.....good job

  • Back To Back SWE

    Back To Back SWE

    9 个月 前

    thanks.

  • Prativa Das
    Prativa Das9 个月 前

    The way you explain the problems and make the viewers to think critically is amazing. 👍 Thank you

  • Back To Back SWE

    Back To Back SWE

    9 个月 前

    sure.

  • code code
    code code9 个月 前

    super bro

  • Back To Back SWE

    Back To Back SWE

    9 个月 前

    thx

  • Saurav Das
    Saurav Das9 个月 前

    I understand that its almost sorted and hence using the Heap Sort. Since it's no ,can't we try Counting sort? It will be O(n+k) faster than the approach?

  • Back To Back SWE

    Back To Back SWE

    9 个月 前

    I'm not sure

  • Ayoun Ghosh
    Ayoun Ghosh9 个月 前

    this was good

  • Back To Back SWE

    Back To Back SWE

    9 个月 前

    thanks

  • F1mus
    F1mus11 个月 前

    Awesome explanation.

  • Back To Back SWE

    Back To Back SWE

    11 个月 前

    thanks

  • StewartW12
    StewartW1211 个月 前

    Next time can you make sure your biceps aren't blocking view of the board. Thanks. For real though, this is an awesome explanation of the problem, and how to arrive at the solution. Most of these channels skip the thought process behind solving the question, and it's that type of critical thinking that will help people in their interview - not just memorizing algorithms. Thanks mate, keep up the good stuff!

  • Back To Back SWE

    Back To Back SWE

    11 个月 前

    Sure ha

  • Anupriya Singh
    Anupriya Singh11 个月 前

    Thank you very much. I love the way you explain things.

  • Back To Back SWE

    Back To Back SWE

    11 个月 前

    sure

  • Anuradha Desai
    Anuradha Desai11 个月 前

    Hi ..In your code for (int i = 0; i minHeap.add(arr[i]); } shouldn't this be ----- i < K+1 ?

  • Back To Back SWE

    Back To Back SWE

    11 个月 前

    I'm not sure, I wrote it a while back

  • Abhishek sunda
    Abhishek sunda年 前

    great explanation!!!!

  • Back To Back SWE

    Back To Back SWE

    年 前

    thanks

  • Maria Sandru
    Maria Sandru年 前

    Silly question but what is the difference between this and the heap sort? Just the space complexity?

  • Back To Back SWE

    Back To Back SWE

    年 前

    No question is silly, the only similarity is the data structure used to sort. If k=n then yes, this is basically heapsort where all items enter the heap and are placed out. But heapsort only uses the sift up subroutine in the initial build heap phase before the placement phase, and it only sifts up the first n/2 items one by one.

  • Maria Sandru
    Maria Sandru年 前

    I was just reading EPI, and I have seen this problem on the Heaps section. After a few good minutes, I realised I was hopeless, so I decided to search it on youtube. I did not believe I would have much luck. You can not imagine how relieved and excited I was when I saw that YOU (my favourite person on CNboth :)))) made a video on this exact topic.

  • Back To Back SWE

    Back To Back SWE

    年 前

    glad you found us

  • Hamdy Ahmed
    Hamdy Ahmed年 前

    Smart Idea, thank you (Y)

  • Back To Back SWE

    Back To Back SWE

    年 前

    sure

  • Avinash Kumar
    Avinash Kumar年 前

    Man you are amazing... You give great explanation and now I don't need to search for hours on CNboth for a tree questions and it's solution .. Love your thinking process to solve a problem.

  • Back To Back SWE

    Back To Back SWE

    年 前

    sure

  • Aarshi Arora
    Aarshi Arora年 前

    This channel is a gem

  • Back To Back SWE

    Back To Back SWE

    年 前

    nah, u a gem

  • Ian Chui
    Ian Chui年 前

    LOL, I liked your final words, very casual :p

  • Back To Back SWE

    Back To Back SWE

    年 前

    yoyo

  • Anish Chakraborty
    Anish Chakraborty年 前

    Amazing explanation. Very good work.

  • Back To Back SWE

    Back To Back SWE

    年 前

    thanks

  • Indraneel Mukherjee
    Indraneel Mukherjee年 前

    Really llove your explaination

  • Back To Back SWE

    Back To Back SWE

    年 前

    thx

  • Julián Heredia
    Julián Heredia年 前

    Best channel I've found so far....you really made my brain absorb this challenges the right way.....keep up the great job buddy

  • Back To Back SWE

    Back To Back SWE

    年 前

    thanks, will do

  • Sheriff Batcha
    Sheriff Batcha年 前

    Ben, great videos! I have been watching tons of your videos and it has helped me a lot! I have a quick question about this problem. Will bubble sort be a good strategy here? I feel like in this particular case bubble sort will have a time complexity of O(k*n) = O(n). Please correct me if I'm wrong.

  • Back To Back SWE

    Back To Back SWE

    年 前

    @Sheriff Batcha Isn't bubble sort quadratic? I may be missing something

  • Sheriff Batcha

    Sheriff Batcha

    年 前

    @Back To Back SWE In this case, to sort this array we would have to traverse it at most k times with bubble sort. I haven't actually worked it out so I may be wrong.

  • Back To Back SWE

    Back To Back SWE

    年 前

    thanks and how O(k*n)

  • Azim Baghadiya
    Azim Baghadiya年 前

    You are going to change our lives with explanations like these man, you are such an awesome teacher. Going into the interviews more confidently because of you. Can’t thank you enough

  • Back To Back SWE

    Back To Back SWE

    年 前

    Sure

  • Yusra Haider
    Yusra Haider年 前

    Thank you for making this video! Could you please 'prove' that this would work for any general input?

  • Back To Back SWE

    Back To Back SWE

    年 前

    yeah I could do a proof but not worth a full video ya know?

  • somekid
    somekid年 前

    Great video Ben, but I had one question. Ultimately, the time complexity comes out to be O(n log(k)) using heaps, but if we were to just opt with sorting the array as is, with merge sort for example, we would get O(n log(n)). How exactly is it, that just outright sorting the array would prove to be significantly worse than the solution you posed? Is it just in the case when N grows exponentially larger? As I would assume that K would just remain constant(relative to a specific problem i.e. k=3, k=4, etc.)? Thanks, bru.

  • Back To Back SWE

    Back To Back SWE

    年 前

    It may not be significantly worse asymptotically since the 2 bounds are very similar (a linear factor multiplied by a logarithmic factor). It'd be interesting to see the graphs of work on random sets of calls with exponentially large n and k. The tail behaviour would look pretty similar, but this is like comparing y = 100n to y = n, the first function is objectively slower...but it is linear...both are linear. Just because both bound and will have the same shape of graph, doesn't mean that one may not be much much faster with large inputs. Asymptotic measures look at graph behaviour (think of shape) and nothing concrete.

  • Deepak Jha
    Deepak Jha年 前

    Discovered your channel yesterday. Great job. Love how you explain on how to approach the problem.

  • Back To Back SWE

    Back To Back SWE

    年 前

    nice, welcome

  • 406 Kushagra Kumar
    406 Kushagra Kumar年 前

    Amazing explanation. Loved the way you explained the approach towards solving the problem

  • Back To Back SWE

    Back To Back SWE

    年 前

    ye

  • Vivek Pratap Singh
    Vivek Pratap Singh年 前

    Top class explanation

  • Back To Back SWE

    Back To Back SWE

    年 前

    thanks

  • Papa ka naam nhi lete
    Papa ka naam nhi lete年 前

    extraordinary explanation.. need more videos like this sir.

  • Back To Back SWE

    Back To Back SWE

    年 前

    coming right up

  • Abisoye Lawal
    Abisoye Lawal年 前

    Thank you so much for your visualization. Got a hold of it easily. Your code was inspiring too public static void sortNearlySortedArray(int[] A, int k) { PriorityQueue minHeap = new PriorityQueue(); int n = A.length; for (int i = 0; i minHeap.add(A[i]); } int nextIndexToAdd = k + 1; int indexToPlaceMin = 0; while(!minHeap.isEmpty()){ A[indexToPlaceMin++] = minHeap.poll(); if(nextIndexToAdd minHeap.add(A[nextIndexToAdd++]); } } }

  • Back To Back SWE

    Back To Back SWE

    年 前

    nice

  • Warrick Holfeld
    Warrick Holfeld年 前

    Really good videos.

  • Back To Back SWE

    Back To Back SWE

    年 前

    thanks

  • Shr ad
    Shr ad年 前

    You are even better than the geeks for geeks. If I got a job I will definitely donate you my guru Dakshina (my money) By the Way I am from India lol

  • Back To Back SWE

    Back To Back SWE

    年 前

    hahahaha nice, wassup, one world

  • Shr ad
    Shr ad年 前

    worth watching, best video ever You not only give the solution of the problem but show us the path to get that approach of finding a solution

  • Back To Back SWE

    Back To Back SWE

    年 前

    yeah thanks

  • Prashanth Wagle
    Prashanth Wagle年 前

    I paused the video halfway and thinking of sentences to appreciate the video and your channel. Any other person would have directly dealt with the solution. But you give exercise to the brain. Keep the good work going on. Hats Off!

  • Back To Back SWE

    Back To Back SWE

    年 前

    Hahahahaha, glad I exercised your brain

  • Utsav Prabhakar
    Utsav Prabhakar年 前

    Hey man. Awesome video. probably the best placement-prep channel on youtube. like when you made that diagram, before you mentioned heap, heap popped into my mind and i paused the video and came up with the solution. initially when i saw the problem, i had no clue how this was going to happen. Anyway I have a major doubt tho. Where can I learn the analysis of time and space complexities for all kinds of loops, recursion,divide conquer etc.

  • Back To Back SWE

    Back To Back SWE

    年 前

    haha nice! That is so cool. And for time complexities... :) I'm making this twitter.com/thebigoguide, it'll be out the end of July. It's why I've been so quiet for so long on the channel

  • Max Li
    Max Li年 前

    Thank you very much for your explanation. You are the best.

  • Back To Back SWE

    Back To Back SWE

    年 前

    ye

  • Achintya Shivam
    Achintya Shivam年 前

    Your videos are awesome,sir.I subscribed to your channel as soon as i listened to your way of explaining.Please keep making videos,your way of teaching is infinitely times better than my college professors

  • Back To Back SWE

    Back To Back SWE

    年 前

    thanks!

  • Varsha Mehra
    Varsha Mehra年 前

    your videos are very helpful . thank you brother

  • Back To Back SWE

    Back To Back SWE

    年 前

    sure

  • Surfman
    Surfman年 前

    Awesome explanation! The best I've seen on CNboth.

  • Back To Back SWE

    Back To Back SWE

    年 前

    thanks

  • Mr.Selva Kumar
    Mr.Selva Kumar年 前

    very nice explanation about the problem and solution (y)

  • Back To Back SWE

    Back To Back SWE

    年 前

    thanks

  • Gagan Gaur
    Gagan Gaur年 前

    Beautifully Explained thanks please bring some dp questions too for interview preperation

  • Back To Back SWE

    Back To Back SWE

    年 前

    Ok, I'll cover a lot here: , this is the site I'twitter.com/thebigoguidem working on

  • Prakhar Pandey
    Prakhar Pandey年 前

    The way you approach a problem is exactly how the things should be taught. I wish i had find you earlier.

  • Suryaa Jha

    Suryaa Jha

    9 个月 前

    @Back To Back SWE Thanks so much you are just awesome

  • Back To Back SWE

    Back To Back SWE

    年 前

    thanks haha

  • Nagarjun Prasad
    Nagarjun Prasad年 前

    The way you explain stuff from a beginners perspective is really intuitive. Keep up the awesome work. Looking forward to more of your stuff!

  • Back To Back SWE

    Back To Back SWE

    年 前

    thanks yo

  • Lakshay Dutta
    Lakshay Dutta年 前

    your concepts are really very clear ! such a nice explanation dude ! you actually made it look very easy!the best part was that you described the whole process of how to start thinking for this question ! thanks man !

  • Back To Back SWE

    Back To Back SWE

    年 前

    Hahaha I don make it look easy but all these videos are prepared and staged almost....like I'm just a normal dude haha

  • Aman Kumar
    Aman Kumar年 前

    Thankyou for such an amazing explanation...♥️

  • Back To Back SWE

    Back To Back SWE

    年 前

    sure

  • Yousuf
    Yousuf年 前

    Amazing video. Thanks, please keep making such kind of videos. It helped me to understand this algorithm. I was thinking about why we are taking k+1 heap but you have explained it very well. Thanks.

  • Back To Back SWE

    Back To Back SWE

    年 前

    ok

  • Bob Jones
    Bob Jones年 前

    I was reviewing the code you put in the description. It makes sense for the most part, but why did you make it such that the min heap has k + 1 elements at any time instead of just k elements?

  • Back To Back SWE

    Back To Back SWE

    年 前

    @Bob Jones yeah

  • Bob Jones

    Bob Jones

    年 前

    @Back To Back SWE I watched the video before the comment. I think I got it since I have had a night's sleep. I think it is because we include the first element plus the k elements to the right.

  • Back To Back SWE

    Back To Back SWE

    年 前

    Because for the first position (and next positions onward) we compete k+1 elements. It is easiest if you look at the video and see concretely why.

  • Stephy jacob
    Stephy jacob年 前

    Can please make videos mainly on backtracking, greedy, dynamic programming .. it will helpful ..because most people find those problem difficult to solve. Thanks

  • Back To Back SWE

    Back To Back SWE

    年 前

    yeah

  • John LaBarge
    John LaBarge年 前

    With a small enough K probably worth just doing a straight linear minimum.

  • Back To Back SWE

    Back To Back SWE

    年 前

    What is a straight linear minimum?

  • John LaBarge
    John LaBarge年 前

    You are amazing. Such a great communicator. And such an awesome thing to make these videos.

  • Back To Back SWE

    Back To Back SWE

    年 前

    thanks

  • John LaBarge
    John LaBarge年 前

    Bro you been working out?

  • Back To Back SWE

    Back To Back SWE

    年 前

    yeah, I've weakened though

  • Kumar Gaurav
    Kumar Gaurav年 前

    Perfect explanation!

  • Back To Back SWE

    Back To Back SWE

    年 前

    thanks

  • Vardhan Vishnu
    Vardhan Vishnu年 前

    awesome explaination of underneath of the problem

  • Back To Back SWE

    Back To Back SWE

    年 前

    thanks

  • zdanodron
    zdanodron年 前

    This is actually the solution to a slightly different interview problem: k-left sorted array where elements cannot move left more than k positions. In you case the restriction is on both directions so it’s more complicated and your solution doesn’t work. Imagine the first element in your array is the biggest (10). It’ll stay in the min heap all the way to the end and will end up as the last one in the final array so it’d move more thank k=3 positions to the right

  • Murali Balasubramaniam

    Murali Balasubramaniam

    10 个月 前

    (Pressed CR too soon): But if the problem definition is that k is a hint that says that no element will move more than k positions from its current position when sorted, then of course your solution works and is quite elegant.

  • Murali Balasubramaniam

    Murali Balasubramaniam

    10 个月 前

    @Back To Back SWE Sorry this is a very late reply, but I only just stumbled on this. On going through the video I did have the exact issue that @zdanodron had. I assumed that the number k was a restriction on a type of sorting that requires us to do the best sorting we can, provided we do not move elements more than k locations from their current location. If so, then your solution does not work.

  • Back To Back SWE

    Back To Back SWE

    年 前

    @zdanodron No problem, it is no biggie. Glad I cleared it up, I got worried for a second 😅 Keep asking great questions, I'm happy you are challenging things. Continue. It is the sign of a great learner to challenge what they know and make these connections.

  • zdanodron

    zdanodron

    年 前

    Back To Back SWE Fair enough. After reading the problem description again, I find you are correct indeed. I’ve got confused because once I was asked a similar question to produce a K -sorted array for an arbitrary input

  • Back To Back SWE

    Back To Back SWE

    年 前

    @zdanodron Yes, that input is invalid is what I mean. 10 can't be there or else it breaks the problem description since it will be 6 positions from its "final resting place". Does that make sense? It does not conform to the fundamental problem description that allows the approach to work in the first place. The heap approach SHOULDN'T work for that input because of the very nature of it. It breaks our fundamental assumption about the possibilities at any one index. (the elimination we do in the video)

  • Harris Li
    Harris Li年 前

    This is awesome. You're a wonderful wonderful teacher. Clear and Concise. Please do more of these videos.

  • Back To Back SWE

    Back To Back SWE

    年 前

    ok, on it chief

  • Renee Liu
    Renee Liu年 前

    Today, I died on this one at my interview...should have been here yesterday.

  • Dan Russell

    Dan Russell

    2 个月 前

    me too - the interview was for mostly a frontend role but the last challenge was like a backend challenge....this problem was given and i died. knowing now to use a min heap would have definitely helped! oh well we will know for next time! here's my code (js): let unsorted = [3, 2, 1, 5, 6, 4] let kSorted = (arr, k) => { let minHeap = arr.splice(0, k + 1) let sorted = [] while (arr.length || minHeap.length) { while (minHeap.length) { let min = getMin(minHeap) sorted.push(min[0]) minHeap.splice(min[1], 1) } minHeap = arr.splice(0, k + 1) } return sorted } let getMin = (arr) => { let min = [Infinity, null] for (let i = 0; i let curr = arr[i] if (curr min[0] = curr min[1] = i } } return min } console.log(kSorted(unsorted, 2))

  • Back To Back SWE

    Back To Back SWE

    年 前

    dang

  • Marlega Gaming
    Marlega Gaming年 前

    Thankyou Sir

  • Back To Back SWE

    Back To Back SWE

    年 前

    sure

  • Alban .L
    Alban .L年 前

    Wow I just discovered your channel, it's awesome ! Your videos are amazing ! I may not need it now but one thing is sure, I will subscribe to remember where to go when I need it

  • Back To Back SWE

    Back To Back SWE

    年 前

    thanks! I appreciate it!

  • Albert Zhang
    Albert Zhang年 前

    This explanation was brilliant.

  • Back To Back SWE

    Back To Back SWE

    年 前

    Thanks

  • animusdx
    animusdx年 前

    I actually got this problem as my problem for my Twitch Technical phone interview which I messed up really badly. I came up with a brute force solution but I ran out of time before I could really optimize it. But then again a heap never came to mind when I was thinking through it.

  • Back To Back SWE

    Back To Back SWE

    年 前

    Yeah, it happens. Speaking of coincidences, we got a practice exam for my (actual) algorithms exam that is happening tomorrow and this same question was on the practice exam. I didn't even mean for that to happen. Wild

  • Pengfei Song
    Pengfei Song年 前

    Nice walk through. Love it!

  • Back To Back SWE

    Back To Back SWE

    年 前

    sure

  • Michał Z.
    Michał Z.年 前

    Thank you for your hard work on those videos. What do you think about doing an episode about dynamic programming? Explain top down and bottom up approaches, dp table method, how to approach it in general etc.

  • Back To Back SWE

    Back To Back SWE

    年 前

    I could. I feel all the dp videos already teach this though. But I could make a video to tie it all together.

  • lil zjay
    lil zjay年 前

    thumb up before watching

  • Back To Back SWE

    Back To Back SWE

    年 前

    haha

  • Joy Rahman
    Joy Rahman年 前

    Very nice explanation. With that explanation, implementation was very easy. Thumbs up !!

  • Back To Back SWE

    Back To Back SWE

    年 前

    thanks 🌽🚜🌽🌽

  • Cameron Ellis
    Cameron Ellis年 前

    Dude, thank you so much for posting these videos. Keep it up! They give me an even deeper understanding of CS fundamentals that I hope will give me a better chance with interviews in the future. Your explanations are superb

  • Back To Back SWE

    Back To Back SWE

    年 前

    Thanks. I'll probably do this channel for 1-2 more years and see where it takes me. I hope it grows faster and goes down as one of the greatest SWE channels to ever exist. Long way away, so many more avenues to explore and teach in.

  • ravi tanwar
    ravi tanwar年 前

    hey bro i'm here from your solutions on leetcode(minimum window susbstring):- even though approach of your videos is good i think company wise questions approach would be better . for eg :- take all uber questions , then amazon etc . this covers the most asked ones and all the common interview questions irrespective of the company . hope i made sense . cheers .!

  • sam

    sam

    年 前

    Back To Back SWE i think your approach is the correct here. Fundamentals > any specific problem set Uber might have asked.

  • Back To Back SWE

    Back To Back SWE

    年 前

    Yes, this is something I pondered when I started this channel. How would I format things. The thing is...I didn't think that that would be a good choice...to revolve a whole channel and movement around company specific questions....although it does align with the mission of the project (to get people jobs)...I just don't think it'd be a good idea to pander to the idea that companies ask a certain set of questions (although some DO do that) as a long-term content strategy. It'd certainly get the channel WAY more views and give it a viral aspect but... What if a company stops asking a question? What if they stop using these kinds of questions all together? A more stable idea in my belief is to revolve the channel around classes of problem and the fundamentals that guide each problem class. I think anyone can look up the company lists and then do those problems and then...yeah I may just be straight wrong but eh...

  • Best Sports
    Best Sports年 前

    Just a thought..Can we do it in using DEQUEUE instead of Min Heap..? we maintain the smallest element the queue for every k+1 window...

  • Cameron Ellis

    Cameron Ellis

    年 前

    @Back To Back SWE I don't believe a sliding window will work here. This is because we need to always maintain the ordering of the elements to get the smallest value every time

  • Back To Back SWE

    Back To Back SWE

    年 前

    I sort of know what you are saying. Why a dequeue? Even if we maintain the smallest element, how are you cognizant of its position in the underlying structure for removal at all times? Elaborate a little and analyze each operation, I'm interested.

  • Best Sports

    Best Sports

    年 前

    using DQUEUE it will be O(N)

  • tom choi
    tom choi年 前

    Thanks for the video! Great thought process building upto the optimal solution!

  • Back To Back SWE

    Back To Back SWE

    年 前

    wassup, thanks

下一个