Write a data structure that can pass the given tests.

datastructure.test.js

/**
 * Data structure that can store up to `cap` elements.
 * Should have 2 methods: `add` and `check`.
 * If the capacity is reached, the next element should be added instead of
 * the latest used element.
 * The newest element is the one tha was `added` or `checked` the last.
 *
 * `check` operation just marks the element as "used".
 * `add` adds a new element
 *   - if the element is already in the structure, just `check` it
 *   - if the capacity is reached, remove the `latest used` element and then add a new one
 *   - otherwise just add a new element
 *
 * Both `check` and `add` operations are O(1).
 */
class Structure {
  constructor() {}
  add() {}
  check() {}

  // For testing
  toArray() {}
  equals(other) {
    const a1 = this.toArray();
    const a2 = other.toArray();
    return JSON.stringify(a1) === JSON.stringify(a2);
  }
}

it('check updates the `usage` of the element (touch)', () => {
  const s1 = new Structure(3);
  const s2 = new Structure(3);
  s1.add(1).add(2).check(1);
  s2.add(2).add(1);
  return s1.equals(s2);
});

it('add the existing element updates the `usage` of the element (touch)', () => {
  const s1 = new Structure(3);
  const s2 = new Structure(3);
  s1.add(1).add(2).add(1);
  s2.add(2).add(1);
  return s1.equals(s2);
});

it('adding over the capacity removes the oldest added element', () => {
  const s1 = new Structure(3);
  const s2 = new Structure(3);
  s1.add(1).add(2).add(3).add(4);
  s2.add(2).add(3).add(4);
  return s1.equals(s2);
});

it('adding over the capacity removes the oldest used element (respecting `check`)', () => {
  const s1 = new Structure(3);
  const s2 = new Structure(3);
  s1.add(1).add(2).add(3).check(1).add(4);
  s2.add(3).add(1).add(4);
  return s1.equals(s2);
});

it('adding over the capacity removes the oldest used element (respecting repetitive `add`)', () => {
  const s1 = new Structure(3);
  const s2 = new Structure(3);
  s1.add(1).add(2).add(3).add(1).add(4);
  s2.add(3).add(1).add(4);
  return s1.equals(s2);
});

function it(name, fn) {
  if (fn()) {
    console.log('PASSED', name);
  } else {
    console.log('FAILED', name);
  }
}