Interview Question: Priority Queue

Coding interview question from www.byte-by-byt...
In this video, I show how to implement a priority queue.
Do you have a big interview coming up with Google or Facebook? Do you want to ace your coding interviews once and for all? If so, Byte by Byte has everything that you need to go to get your dream job. We've helped thousands of students improve their interviewing and we can help you too.
Stuck on Dynamic Programming? Check out our free ebook: www.dynamicprogrammingbook.com
50 Practice Questions: www.byte-by-by...
You can also find me on
Twitter: / bytebybyteblog
Facebook: / bytebybyteblog
Email: [e-mail]

[@CorneliusFilm]

Thanks for making these videos! I landed a software internship with amazon largely because I had been preparing with your videos! I probably owe you a beer or something

[@ByteByByte]

you're welcome! I always accept free beer if you're buying ;)

[@crothert]

10% salary >:)

[@l.b76]

Bob Sedgewick has a simple java implementation. The website is algs4

[@RostyslavKobizsky]

Better check Bob Sedgewick implementation - much easy to understand

[@ericacm]

Great presentation! Here's a way to simplify the loop in pop(): // Bubble down the top element to the right spot int pos = 0; int least; do { least = pos; int leftChild = pos * 2 + 1; int rightChild = leftChild + 1; if (leftChild < size && heap[leftChild] < heap[pos]) least = leftChild; if (rightChild < size && heap[rightChild] < heap[pos]) least = rightChild; } while (least != pos); I would also factor out parent()/left()/right()

[@MrSoundChaos]

Great video! The explanations plus the live code make it very easy to understand. I do have a possible errors though.. inside pop() method, heap[size - 1] is copied and then left as is, which i suppose is fine due to size "shrinks", but shouldn't it be set to 0 for cleanliness? Also, the size doesn't decrease until the while loop is finished, so shouldn't the while loop condition be (pos < size / 2 - 1)?

[@ByteByByte]

To your first question, you can do that but it makes absolutely zero difference. I prefer not to because it adds an unnecessary step. For the second, I believe it works as is, but if you're not sure, try out a few different examples and let me know!

[@TheProximator]

Great videos, thank you very much ;)

[@serhiypidkuyko4206]

Hi. I think your code of pop() function isn't good. For example, if you have the heap=(4,3,2,1) - your code swaps TWICE the pair(3,1). You need to change 3rd and 4th rows of the function code. Also I think it would be better to have the loop block as "while (pos

[@rishiraj1616]

Brother, C# doesn't have inbuilt Priority Queue. Am I supposed to create one of my own in an online coding test with limited time? How do programmers tackle this issue? Do they learn multiple languages to cover all data structures?

[@piyush12121]

Great video ! I would create separate methods for getParent and getChildren also.

[@ByteByByte]

Yeah that would be particularly useful for getChildren because you could check whether the right child is in range really easily. Would make the whole while loop in pop() a bit simpler

[@rajmohanvideos]

A very good explanation. Would you also be able to do a video on Splay tree? There aren't good videos on Splay tree.

[@ByteByByte]

What's a splay tree?

[@rajmohanvideos]

It's a type of self-balancing binary search tree with a key property called splaying which is basically moving a node to root through a series of tree rotations. en.wikipedia.org/wiki/Splay_tree

[@rajmohanvideos]

I don't think anyone would ask this in an interview though. It's something I came across few months ago and found it interesting, but difficult to wrap my head around the implementation!