Back to top

Queues

Overview

In the subsequent sections, we will be providing different patterns of programming questions commonly asked in coding interviews which can be solved using hash table. We don’t want to overwhelm our readers with a plethora of hash table questions. So, we have done the heavy lifting for you by going through almost all the questions on geeksforgeeks and categorizing the different patterns of questions commonly asked in the interviews.

Pattern 1: Application Oriented

Circular Tour

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

        /**
         *
         * We want to calculate the first point from where a truck will be
         * able to complete the circle.
         *
         * Approach: We maintain the indexes which are part of the current
         * run in a queue. If the current petrol is negative then we remove
         * the indexes from the queue. Otherwise, we add the index in the
         * queue.
         *
         * Time Complexity: O(n)
         * Space Complexity: O(n)
         *
         *
         * @param petrol
         * @param distance
         * @return
         */
        int getStartingIndex(int[] petrol, int[] distance) {

            if (petrol.length == 0) {
                return -1;
            }
            int currPetrol = 0;
            Queue<Integer> queue = new LinkedList<>();
            if (petrol[0] - distance[0] > 0) {
                currPetrol = petrol[0] - distance[0];
                queue.add(0);
            }

            for (int i = 1; i < petrol.length; i = (i + 1) % petrol.length) {
                if (!queue.isEmpty() && queue.peek() == i) {
                    return i;
                }
                currPetrol += petrol[i] - distance[i];
                if (currPetrol < 0) {
                    if (i == 0) {
                        return -1;
                    }
                    while (!queue.isEmpty()) {
                        queue.remove();
                    }
                    currPetrol = 0;
                } else {
                    queue.add(i);
                }
            }
            return -1;
        }

Pattern 2: Sliding Window

Maximum in Sliding Window of size K

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

        /**
         * We want to find the max element for every contiguous
         * sub-array of size k in an array.
         *
         * Approach: We maintain a dequeue to maintain the list of
         * indexes. We add the first k elements in the dequeue. After
         * that, we remove the characters which aren't in the current
         * subarray from the front. We also remove the characters smaller
         * than the current character from the end of the queue.
         *
         * Time Complexity: O(n)
         * Space Complexity: O(n)
         *
         * @param a
         * @param k
         * @return
         */
        List<Integer> slidingWindowMaxElement(int a[], int k) {
            List<Integer> maxElements = new ArrayList<>();

            Deque<Integer> q1 = new LinkedList<>();

            int i;
            for( i = 0; i < k; i++) {
                while (! q1.isEmpty()  && a[i] >= a[q1.peekLast()]){
                    q1.removeLast();
                }
                q1.addLast(i);
            }

            for (; i < a.length ; i++) {
                maxElements.add(q1.peek());

                while (!q1.isEmpty() && q1.peek() <= i-k) {
                    q1.removeFirst();
                }

                while (!q1.isEmpty() && a[i] >= a[q1.peekLast()]) {
                    q1.removeLast();
                }
                q1.addLast(i);
            }

            maxElements.add(q1.peek());
            return maxElements;
        }

First Negative Element in Sliding Window of size K

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

        /**
         *
         * We want to find the first negative integer for each window of size k.
         *
         * Approach: We will use a queue to maintain the elements whose value will
         * be less than zero. If there's no negative value in the queue then we just
         * add a "0" instead.
         *
         * Time Complexity: O(n)
         * Space Complexity: O(n)
         *
         * @param a  - input array
         * @param k  - the window size
         * @return the list of negative integers
         */
        List<Integer> firstNegativeIntegerSlidingWindow(int a[], int k) {
            Queue<Node> queue = new LinkedList<>();
            List<Integer> l = new ArrayList<>();

            for(int i = 0; i < k; i++) {
                if(a[i] < 0) {
                    Node node = new Node(i, a[i]);
                    queue.add(node);
                }
            }

            if (queue.isEmpty()) {
                l.add(0);
            } else {
                l.add(queue.peek().val);
            }

            for(int i = k; i < a.length; i++) {
                while (!queue.isEmpty()) {
                    Node node = queue.peek();
                    if(node.index <= i - k){
                        queue.poll();
                    } else {
                        break;
                    }
                }
                if(a[i] < 0) {
                    Node node = new Node(i, a[i]);
                    queue.add(node);
                }
                if(queue.isEmpty()) {
                    l.add(0);
                } else {
                    l.add(queue.peek().val);
                }
            }
            return l;
        }

        class Node {
            int index;
            int val;

            public Node(int index, int val) {
                this.index = index;
                this.val = val;
            }
        }

Pattern 3: Breadth-First Search-Based

Distance of nearest cell having 1 in binary matrix

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

        /**
         * We want to find the distance of nearest cell having 1 in a binary matrix.
         *
         * Approach: We create a {@link Node} object which comprises of the index
         * in the matrix. We start with adding all the '1's in the queue and initializing
         * the distance as '0'. After that, we pop the element from the queue and
         * update the distance of its neighbors.
         *
         * Time Complexity: O(mn), where m and n are dimensions of the matrix
         * Space Complexity: O(mn), where m and n are dimensions of the matrix
         *
         *
         * @param a
         * @return
         */
        int[][] nearestHavingOne(int[][] a) {

            List<Node> ones = new LinkedList<>();
            Queue<Node> queue = new LinkedList<>();
            int[][] d = new int[a.length][a[0].length];
            List<int[]> dirs = Arrays.asList(new int[]{0,1}, new int[]{1, 0}, new int[]{0,-1}, new int[]{-1,0});

            for (int i = 0; i < a.length;i++) {
                for (int j = 0; j < a[0].length; j++) {
                    if(a[i][j] == 1) {
                        d[i][j] = 0;
                        Node node = new Node(i, j);
                        ones.add(node);
                        queue.add(node);

                    } else {
                        d[i][j] = Integer.MAX_VALUE;
                    }

                }
            }

            while (!queue.isEmpty()) {
                int count = queue.size();

                while (count-- > 0) {
                    Node node = queue.poll();
                    int baseVal = d[node.i][node.j];
                    for (int[] dir : dirs) {
                        Node newNode = new Node(node.i + dir[0], node.j + dir[1]);
                        if (isValid(newNode.i, newNode.j, a.length, a[0].length) && !ones.contains(newNode)) {
                            d[newNode.i][newNode.j] = Math.min(baseVal + 1, d[newNode.i][newNode.j]);
                            queue.add(newNode);
                        }
                    }
                }
            }

            return d;
        }

        class Node{
            int i, j;

            public Node(int i, int j) {
                this.i = i;
                this.j = j;
            }

            public boolean equals(Node o){
                return this.i == o.i && this.j == o.j;
            }
        }

        boolean isValid(int i, int j, int m, int n) {
            return i >=0 && j >= 0 && i < m && j < n;
        }

Pattern 4: Implement Data Structures using Queue

Implement Stack using Queue

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

    /**
     * We need to implement a stack using a queue.
     *
     * Approach: We use a queue to implement a stack. For every
     * push we add elements in a queue. After that, we add the
     * elements from the main queue upto this new queue. We then
     * pop the element from the main queue.
     *
     * Time Complexity: O(n) for the push operation
     * Space Complexity: O(n)
     * 
     */
    public class StackImplementation {

        Queue<Integer> q1 = new LinkedList<>();

        int curSize = 0;

        void push(int x){

            Queue<Integer> q2 = new LinkedList<>();
            curSize ++;

            q2.add(x);

            while (q1.isEmpty()) {
                q2.add(q1.remove());
            }

            q1 = q2;
        }

        void pop() {
            if(q1.isEmpty()) {
                return;
            }
            q1.remove();
        }

        int top() {
            if(q1.isEmpty()){
                return -1;
            }
            return q1.peek();
        }
    }