2
\$\begingroup\$

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;
  }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ I don't think this solution satisfies the requirements: the outer array will contain more than 5 elements if the queue has more than 25 elements. \$\endgroup\$ – Benjamin Kuykendall Apr 17 at 3:24
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your great suggestion. Do you think you can provide an example basis on your suggestion? \$\endgroup\$ – user5447339 Apr 22 at 0:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.