[Object-Oriented Design] interview questions #9

[rygh4775]

Circular Array: Implement a CircularArray class that supports an array-like data structure which can be efficiently rotated. If possible, the class should use a generic type (also called a template), and should support iteration via the standard for (Obj o : circularArray) notation.

[btakeya]

Requirements:

1. array-like data structure:
2. can be efficiently rotated
3. use a generic type
4. iteration via standard for (Obj o : circularArray) notation

   Implementation

5. can access via index (with time complexity O(1))
6. rotate will change its starting point
7. be done as written
8. implement Iterable
   • Iterator<T> iterator():
   • void forEach(Consumer<? extends T> action):
   • Spliterator<T> spliterator():
   • implement Iterator
     • boolean hasNext():
     • T next():
     • void remove():
     • void forEachRemaining():

code

• Run.java

  public class Main {
  
  private void printRuler() {
      System.out.println();
      System.out.println("---------------");
  }
  
  private void doWithCircularArray() {
  
      CircularArray<Integer> cai1 = new CircularArray<>(7);
      cai1.add(5);
      cai1.add(4);
      System.out.println(cai1.get(0) + " / " + cai1.get(1) + " / " + cai1.get(2)); // 5 / 4 / null
      cai1.add(3);
      cai1.add(2);
      cai1.add(1);
      cai1.rotate(3);
      cai1.add(0, 2);
      System.out.println(cai1.get(0) + " / " + cai1.get(1) + " / " + cai1.get(2)); // 2 / 1 / 0
      for (Integer i : cai1) {
          System.out.print(i);
          System.out.print(" ");
      }
  
      printRuler();
  
      CircularArray<String> cai2 = new CircularArray<>(5);
      cai2.add("five");
      cai2.add("four");
      cai2.add("three");
      cai2.add("two");
      cai2.add("one");
      for (String s : cai2) {
          System.out.print(s);
          System.out.print(" ");
      }
  
      printRuler();
  }
  
  public static void main(String[] args) {
      Main m = new Main();
      m.doWithCircularArray();
  }
  }

• CircularArray.java

  
  package com.btakeya.datastructure;

import java.util.Arrays; import java.util.Iterator; import java.util.Objects; import java.util.Spliterator; import java.util.function.Consumer;

public class CircularArray implements Iterable {

private T[] element;
private int size;
private int maximum;
private int head;

public CircularArray() {
    this(10);
}

@SuppressWarnings(value = { "unchecked" })
public CircularArray(int size) {
    this.element = (T[]) new Object[size];
    this.maximum = size;
    this.head = 0;
}

@Override
public Iterator<T> iterator() {
    return new CircularIterator(this);
}

@Override
public void forEach(Consumer<? super T> action) {
    Objects.requireNonNull(action);
}

@Override
public Spliterator<T> spliterator() {
    return null;
}

public void rotate(int amount) {
    // TODO: check index boundness
    this.head += amount % this.size;
}

public T get(int index) {
    return this.element[this.head + index % this.maximum];
}

public void add(T item) {
    this.add(item, this.size);
}

public void add(T item, int index) {
    // TODO: check index boundness
    System.out.println("Add '" + item + "' into " + index + ": [" + Arrays.toString(this.element) + "]");
    this.element[(this.head + index) % this.maximum] = item;
    this.size += 1;
}

public T remove(int index) {
    // TODO: check index boundness
    T toRemove = element[(this.head + index) % this.maximum];
    this.size -= 1;
    this.element[index] = null;

    return toRemove;
}

private class CircularIterator implements Iterator<T> {

    private int _ptr = -1;
    private T[] _element;
    private int _head;

    CircularIterator(CircularArray<T> arr) {
        this._element = arr.element;
        this._head = arr.head;
    }

    @Override
    public boolean hasNext() {
        return this._ptr < this._element.length - 1;
    }

    @Override
    public T next() {
        this._ptr += 1;
        return _element[(this._head + this._ptr) % this._element.length];
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("No considered");
    }

    @Override
    public void forEachRemaining(Consumer<? super T> action) {
        throw new UnsupportedOperationException("No considered");
    }
}

}