Coding Interview Question: Priority Queue

July 24, 2017

Question

Implement a Priority Queue

Once you think that you’ve solved the problem, click below to see the solution.

As always, remember that practicing coding interview questions is as much about how you practice as the question itself. Make sure that you give the question a solid go before skipping to the solution. Ideally if you have time, write out the solution first by hand and then only type it into your computer to verify your work once you've verified it manually. To learn more about how to practice, check out this blog post.

Solution

How was that problem? You can check out the solution in the video below.

Here is the source code for the solution shown in the video (Github):

// Implements a priority queue using a max heap. The heap is of fixed size and 
// represented using an array.
public class PriorityQueue {
    int[] heap;
    int size;
    
    // Constructor initializes instance variables
    public PriorityQueue(int maxSize) {
        heap = new int[maxSize];
        size = 0;
    }
    
    // Push an element on to the queue
    public void push(int val) {
        // If the queue is full then throw an exception
        if (size == heap.length) throw new IllegalStateException();
        
        // Put the value in the next available space in the queue
        int pos = size;
        heap[pos] = val;
        
        // While val is bigger than its parent, swap it with its parent
        while (pos > 0) {
            // Get the parent and compare the values
            int parent = (pos+1) / 2 - 1;
            if (heap[parent] > heap[pos]) break;
            swapIndices(parent, pos);
            pos = parent;
        }
        
        // We added an element so increment the size
        size++;
    }
    
    // Pop the max element from the queue
    public int pop() {
        // If the queue is empty, throw an exception
        if (size == 0) throw new IllegalStateException ();

        // The top of the heap is the first item in the array, so save it off
        // to the side so we don't lose it
        int toReturn = heap[0];
        
        // Move the bottom item in the heap to the first position. We don't need
        // to remove it from the array because we have the size variable
        heap[0] = heap[size - 1];
        size--;
        
        // Bubble down the top element to the right spot
        int pos = 0;
        // We're going to be swapping with the children and any pos >= size / 2
        // doesn't have any children
        while (pos < size / 2) {
            int leftChild = pos * 2 + 1;
            int rightChild = leftChild + 1;
            // If the right child exists and is greater than the left child, 
            // compare it to the current position
            if (rightChild < size && heap[leftChild] < heap[rightChild]) { // Only swap if the value is less than the child if (heap[pos] >= heap[rightChild]) break;
                swapIndices(pos, rightChild);
                pos = rightChild;
            } else {
                // Do the same comparison with the left child
                if (heap[pos] >= heap[leftChild]) break;
                swapIndices(pos, leftChild);
                pos = leftChild;   
            }
        }
        
        return toReturn;
    }
    
    // Swap the values at the indices
    private void swapIndices(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

// Implements a priority queue using a max heap. The heap is of fixed size and

// represented using an array.

public class PriorityQueue {

int[] heap;

int size;

// Constructor initializes instance variables

public PriorityQueue(int maxSize) {

heap = new int[maxSize];

size = 0;

}

// Push an element on to the queue

public void push(int val) {

// If the queue is full then throw an exception

if (size == heap.length) throw new IllegalStateException();

// Put the value in the next available space in the queue

int pos = size;

heap[pos] = val;

// While val is bigger than its parent, swap it with its parent

while (pos > 0) {

// Get the parent and compare the values

int parent = (pos+1) / 2 - 1;

if (heap[parent] > heap[pos]) break;

swapIndices(parent, pos);

pos = parent;

}

// We added an element so increment the size

size++;

}

// Pop the max element from the queue

public int pop() {

// If the queue is empty, throw an exception

if (size == 0) throw new IllegalStateException ();

// The top of the heap is the first item in the array, so save it off

// to the side so we don't lose it

int toReturn = heap[0];

// Move the bottom item in the heap to the first position. We don't need

// to remove it from the array because we have the size variable

heap[0] = heap[size - 1];

size--;

// Bubble down the top element to the right spot

int pos = 0;

// We're going to be swapping with the children and any pos >= size / 2

// doesn't have any children

while (pos < size / 2) {

int leftChild = pos * 2 + 1;

int rightChild = leftChild + 1;

// If the right child exists and is greater than the left child,

// compare it to the current position

if (rightChild < size && heap[leftChild] < heap[rightChild]) { // Only swap if the value is less than the child if (heap[pos] >= heap[rightChild]) break;

swapIndices(pos, rightChild);

pos = rightChild;

} else {

// Do the same comparison with the left child

if (heap[pos] >= heap[leftChild]) break;

swapIndices(pos, leftChild);

pos = leftChild;

}

return toReturn;

}

// Swap the values at the indices

private void swapIndices(int i, int j) {

int temp = heap[i];

heap[i] = heap[j];

heap[j] = temp;

}

Did you get the right answer to this coding interview question? Please share your thoughts in the comments below.

DON'T DO ANOTHER CODING INTERVIEW...

...until you've mastered these 50 questions!

The Definitive Guide to Data Structures for Coding Interviews

Data structures are critical to coding interview success. In this post, I'll show you exactly which data structures you need to know to nail your interviews.

Article

10 ways to get unstuck and never fail another coding interview

It happens time and again. People fail coding interviews because they don’t know what to do when stuck on a problem. Developing a clear plan of attack helps you to succeed at any whiteboard coding interview.