Implement Queue using fixed size array

Question

I came across below interview question and I am working on it:

Build a queue class with the enqueue and dequeue methods. The queue can store an UNLIMITED number of elements but you are limited to using arrays that can store up to 5 elements max..

Here is what I was able to come up with. Is this the right way to do it in the interview or is there any better way we should implement in the interview?

class Solution {  
  private final List<List<Integer>> array;

  public Solution() {
    this.array = new ArrayList<>();
  }

  public void enqueue(int value) {
    if(array.isEmpty()) {
      List<Integer> arr = new ArrayList<>();
      arr.add(value);
      array.add(arr);
      return;
    }
    if(array.get(array.size() - 1).size() != 5) {
      array.get(array.size() - 1).add(value);   
      return;
    }
    List<Integer> arr = new ArrayList<>();
    arr.add(value);
    array.add(arr);
    return;
  }

  public int dequeue() {
    if(array.isEmpty()) {
      return -1; 
    }
    for(List<Integer> l : array) {
      for(int i=0; i<l.size(); i++) {
        return l.remove(i); 
      }
    }
    return -1;
  }
}

Answer 1

Trade Off - Organize Fixed Size Arrays

Manage arrays based on ArrayList

• enqueue - append new fixed size array - O(1)
• dequeue - remove first fixed size array - O(n)

Manage arrays based on LinkedList

• enqueue - append new fixed size array to linked list - O(1)
• dequeue - remove first fixed size array - O(1)
• cons - extra next pointer to setup linked list

public class FixedArrayQueue<T> {
    private Node<T> head, tail;
    private int front, rear, size;
    private final int SIZE;

    public FixedArrayQueue(int n) {
        SIZE = n;
        head = tail = new Node<T>(SIZE);
        front = rear = size = 0;
    }

    public void enqueue(T t) {
        tail.array[rear++] = t;
        if (rear == SIZE) {
            rear = 0;
            append();
        }
        size++;
    }

    public T dequeue() {
        if (size == 0) {
            throw new EmptyQueueException();
        }
        T ret = head.array[front++];
        if (front == SIZE) {
            front = 0;
            remove();
        }

        size--;
        return ret;
    }

    private void append() {
        tail.next = new Node<T>(SIZE);
        tail = tail.next;
    }

    private void remove() {
        head = head.next;
    }

    private boolean isEmpty() {
        return size == 0;
    }

    private int size() {
        return size;
    }
}

class Node<T> {
    T[] array;
    Node<T> next;

    public Node(int n) {
        array = (T[]) new Object[n];
    }
}

Answer 2

As I mentioned in comments, your solution doesn't really solve the problem because the outer array of 5-element arrays can have more than 5 elements.

Instead, you can implement the queue as a linked list of 4-integer nodes, using the 5th element for a reference to the next array. But there's no reason to assume the elements are integers. This turns out to be pretty simple.

public class SillyQueue<T> {
  private static final int MAX = 5;
  private Object [] head = new Object[MAX], tail = head;
  private int headPtr = 0, tailPtr = 0;

  void enqueue(T x) {
    if (tailPtr == MAX - 1) {
      Object [] a = new Object[MAX];
      tail[MAX - 1] = a;
      tail = a;
      tailPtr = 0;
    }
    tail[tailPtr++] = x;
  }

  T dequeue() {
    if (headPtr == MAX - 1) {
      head = (Object[]) head[MAX - 1];
      headPtr = 0;
    }
    return (T) head[headPtr++];
  }
}

Answer 3

Is this the right way to do it in the interview…?
Presenting uncommented code is never right, let alone in an interview.
In an interactive interview, it would be your task to find out whether you can/should use an unlimited number of arrays. If not, you have to negotiate a way to handle an enqueue() to a queue filled to capacity in addition to a dequeue() to an empty one. Fix the type of items the queue can hold. Agree upon the parameters of the enqueue and dequeue methods.

The task is to Build a queue class, Solution is a bad choice for a name - array for something to access the items is no better.
In a language providing arrays, I'd take limited to using arrays literally - if using something more, why not an implementation of java.util.Queue?
The empty queue handling is entirely redundant: in enqueue(), you could have used
if (!array.isEmpty() && array.get(array.size() - 1).size() < 5); in dequeue() you can just drop it.
Instantiating List<Integer>s, you know there won't be more than five items at a time: tell the constructor.
dequeue() leaves empty List<Integer>s in arrays, giving rise to the current nested loop that desperately needs a comment.

(For the second part of the question, I second Rajkamal Tomar.)

Answer 4

You can use a 1-D array and use Wrap-around indexing to implement the queue with the limitation that queue can contain maximum 5 elements.

For checking the condition of empty queue, maintain a variable that counts the number of elements present in the queue.

Answer 5

Your answer uses ArrayList instead of true arrays, and worse, uses an unlimited arraylist to put those arrays in. I think that the interviewers expected you to implement a singly-linked list of 5-element arrays:

/**
 * A singly-linked list node with an array; supports popping its 1st elements, 
 * and adding elements at the end, possibly by creating a new node
 */
public class ListNode {
    final int MAX = 5;
    private int contents[] = new int[MAX];
    private int size = 0; // valid elements

    private ListNode next = null;
    private ListNode(ListNode next) {
        this.next = next;
    }

    public boolean isEmpty() { return size == 0; }

    public ListNode addLast(int value) {
        ListNode next = this;
        if (size == MAX) {
            next = new ListNode(this);
        }
        next.contents[next.size ++] = value;
        return next;
    }

    public int removeFirst() {
        if (size == 0) {
            throw new NoSuchElementException("empty queue");
        }
        int value = contents[0];
        size --;
        for (int i=1; i<size; i++) contents[i-1] = contents[i];
        return value;
    }
}

/**
 * A simple queue on top of nodes that keep arrays of elements
 */
public class ListArrayQueue {
    ListNode first = new ListNode();
    ListNode last = first;
    public void enqueue(int value) {
        last = last.addLast(value);
    }
    public int dequeue() {
        if (first.isEmpty() && first != last) {
            first = first.next;
        }
        return first.removeFirst();
    }
}

Performance-wise, this can be improved: you can avoid keeping the size in each ListNode, since only the 1st and last nodes can be non-full. You can also avoid the loop in removeFirst, but that would entail replacing size by firstIndex and lastIndex; which could again be moved into the ListArrayQueue to save space in each node.

If they has asked you to build an unlimited array out of 5-element array pieces, you would have had to implement something similar to a b-tree. Which, without handy references, would be quite hard to pull off during an interview.