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

Interview questions are almost always meant to evaluate you by the clarifying questions you ask.

In this case, what data structures were you allowed to use beyond the arrays? Clearly something was allowed, since the requirement for queue and dequeue methods implicitly allow a class to be used. But was the Queue class allowed to contain auxiliary classes?

If not, the solution calls for the queue to be an Object[5] where the fifth element, when not null, is the next Object[5].

• Requirement said arrays, not ArrayLists.
• The requirement did not specify the type so a generic type should have been used instead of assuming integers are ok.
• Use of primitive types and lack of exceptions means you're limited to positive numbers, as half of the valid value range has been used for errors.
• You have copy-pasted the sub-array initialization code twice. That should have been a shared method.
• When dequeueing, you leave the empty sub-arrays in the outer list, forcing you to perform an O(N) search to find the first element. Should have just removed the empty sub-arrays and gone for the O(1) operation of getting the first element from the first sub-array.
• The check for array.isEmpty() in dequeue is redundant and adds a third exit point for that method.

Edit: I was thrown off by the for-loop in the dequeue method. Fixed my answer.