Basic Data Structures (Objects, Maps, Sets) Questions

// preserve first occurrence order
const arr = ['a','b','a','c','b'];
const deduped = Array.from(new Set(arr)); // ['a','b','c']

const arr = ['a','b','a','c','b'];
const seen = new Set();
const reversedKeepLast = [];
for (let i = arr.length - 1; i >= 0; i--) {
  if (!seen.has(arr[i])) {
    seen.add(arr[i]);
    reversedKeepLast.push(arr[i]);
  }
}
const result = reversedKeepLast.reverse(); // keeps last occurrences in original order

function dedupeTokens(tokens) {
  const seen = new Set();
  const out = [];
  for (const t of tokens) {
    if (!seen.has(t)) {
      seen.add(t);
      out.push(t);
    }
  }
  return out;
}

class StructuralMap {
  constructor() {
    // primary map: canonicalString -> [{ key, value }]
    this._map = new Map();
  }

  // deterministic canonicalizer with cycle handling
  static _canonicalize(obj) {
    const seen = new WeakMap();
    let nextId = 0;

    function serialize(x) {
      if (x === null) return 'null';
      if (x === undefined) return 'undefined';
      if (typeof x === 'number' || typeof x === 'boolean') return JSON.stringify(x);
      if (typeof x === 'string') return JSON.stringify(x);
      if (typeof x === 'symbol') return `@symbol:${String(x)}`;
      if (typeof x === 'function') return `@function:${(x.name || '<anon>')}`;

      if (seen.has(x)) return `@ref:${seen.get(x)}`; // cycle reference

      const id = nextId++;
      seen.set(x, id);

      if (Array.isArray(x)) {
        const parts = x.map(serialize).join(',');
        return `@arr:${id}:[${parts}]`;
      }

      // plain object: sort keys to ensure canonical order
      const keys = Object.keys(x).sort();
      const parts = keys.map(k => `${JSON.stringify(k)}:${serialize(x[k])}`).join(',');
      return `@obj:${id}:{${parts}}`;
    }

    return serialize(obj);
  }

  // shallow deep equality for collision resolution
  static _deepEqual(a, b, aSeen = new WeakMap(), bSeen = new WeakMap()) {
    if (a === b) return true;
    if (a === null || b === null) return a === b;
    if (typeof a !== typeof b) return false;
    if (typeof a !== 'object') return a === b;
    if (aSeen.has(a) || bSeen.has(b)) return aSeen.get(a) === bSeen.get(b);
    const id = aSeen.size;
    aSeen.set(a, id);
    bSeen.set(b, id);

    if (Array.isArray(a)) {
      if (!Array.isArray(b) || a.length !== b.length) return false;
      for (let i = 0; i < a.length; i++) if (!this._deepEqual(a[i], b[i], aSeen, bSeen)) return false;
      return true;
    }

    const ka = Object.keys(a).sort();
    const kb = Object.keys(b).sort();
    if (ka.length !== kb.length) return false;
    for (let i = 0; i < ka.length; i++) if (ka[i] !== kb[i]) return false;
    for (const k of ka) if (!this._deepEqual(a[k], b[k], aSeen, bSeen)) return false;
    return true;
  }

  set(key, value) {
    const canon = StructuralMap._canonicalize(key);
    const bucket = this._map.get(canon) || [];
    // try to find exact structural match in bucket
    for (const entry of bucket) {
      if (StructuralMap._deepEqual(entry.key, key)) {
        entry.value = value;
        this._map.set(canon, bucket);
        return this;
      }
    }
    bucket.push({ key, value });
    this._map.set(canon, bucket);
    return this;
  }

  get(key) {
    const canon = StructuralMap._canonicalize(key);
    const bucket = this._map.get(canon);
    if (!bucket) return undefined;
    for (const entry of bucket) if (StructuralMap._deepEqual(entry.key, key)) return entry.value;
    return undefined;
  }

  has(key) {
    const canon = StructuralMap._canonicalize(key);
    const bucket = this._map.get(canon);
    if (!bucket) return false;
    for (const entry of bucket) if (StructuralMap._deepEqual(entry.key, key)) return true;
    return false;
  }

  delete(key) {
    const canon = StructuralMap._canonicalize(key);
    const bucket = this._map.get(canon);
    if (!bucket) return false;
    for (let i = 0; i < bucket.length; i++) {
      if (StructuralMap._deepEqual(bucket[i].key, key)) {
        bucket.splice(i, 1);
        if (bucket.length === 0) this._map.delete(canon);
        else this._map.set(canon, bucket);
        return true;
      }
    }
    return false;
  }

  // optional size and iteration helpers
  *entries() {
    for (const bucket of this._map.values()) for (const e of bucket) yield [e.key, e.value];
  }

  [Symbol.iterator]() { return this.entries(); }
}

// removeDuplicates.js
const removeDuplicates = (arr = []) => {
  const seen = new Set();
  const result = [];

  for (const s of arr) {
    if (!seen.has(s)) {
      seen.add(s);
      result.push(s);
    }
  }

  return result;
};

// Usage example
console.log(removeDuplicates(['apple', 'banana', 'apple', 'orange', 'banana']));
// Output: ['apple', 'banana', 'orange']

const DANGEROUS_KEYS = new Set(['__proto__','constructor','prototype','eval','Function']);
const MAX_DEPTH = 10;
const MAX_NODES = 1e6;

function isPlainObject(x){ return x !== null && typeof x === 'object' && Object.getPrototypeOf(x) === Object.prototype; }

function sanitize(value, depth=0, counter={n:0}){
  if (++counter.n > MAX_NODES) throw new Error('payload too large');
  if (depth > MAX_DEPTH) throw new Error('depth limit');

  if (Array.isArray(value)){
    return value.map(v => sanitize(v, depth+1, counter));
  }

  if (value && typeof value === 'object'){
    const out = Object.create(null); // null-prototype safe map
    for (const k of Object.keys(value)){ // only own enumerable keys
      if (DANGEROUS_KEYS.has(k)) continue; // drop dangerous keys
      const v = value[k];
      // type normalization examples:
      if (v === '') { out[k] = null; continue; }
      if (typeof v === 'number' || typeof v === 'boolean' || typeof v === 'string'){
        out[k] = v;
        continue;
      }
      if (typeof v === 'object') out[k] = sanitize(v, depth+1, counter);
      // ignore functions, symbols, undefined
    }
    return out;
  }

  // primitives
  if (['string','number','boolean'].includes(typeof value)) return value;
  return null;
}