Intersect

const list1 = [1,2,3]
const list2 = [3,6,8,2]
const list3 = []
const list4 = [3]

expect(intersect(list1,list2).toBe([2,3])
expect(intersect(list1,list3).toBe([])
expect(intersect(list2,list4).toBe([3])

// we shouldn't give this upfront,
// and let candidates figure out what test cases should be added
const list5 = [2,2,3,4];
expect(intersect(list1,list5).toBe([2,3]);


function intersect(list1, list2) {
  // turn list2 into a hash map
  const object2 = list2.reduce((memo, item) => {
    memo[item] = true;
    return memo;
  }, {});

  const alreadyAdded = {};

  // iterate only once over list1
  return list1.filter((item) => {
    if (!alreadyAdded[item] && object2[item]) {
      alreadyAdded[item] = true;
      return true
    }
    return false;
  });
}