Collections and data processing

A practical refresher. Read the contract, trace the examples, and attempt the exercise before opening its answer. Code blocks may share context; only ts check blocks are standalone checks.

Keep the latest version

Use a Map keyed by entity ID. Read the current winner, compare versions, and replace only for a strictly larger version. Last in the input is not necessarily newest. A strict comparison retains the first record on ties.

One pass costs O(n) operations and O(k) retained records, plus the cost of processing string keys. Sorting adds work without helping this contract.

type ProductUpdate = {
  productId: string;
  version: number;
  price: number;
};

function latestByProduct(
  updates: readonly ProductUpdate[],
): ProductUpdate[] {
  const latest = new Map<string, ProductUpdate>();

  for (const update of updates) {
    const current = latest.get(update.productId);
    if (current === undefined || update.version > current.version) {
      latest.set(update.productId, update);
    }
  }
  return [...latest.values()];
}

Group and join by key

Build the right-side index once, then map the left side. This is a left join with nested history: entities without history remain present with an empty array. Preserve the order of entities and the input order of history unless chronology is explicitly required.

Repeated entity IDs may share a history array; clone it if independent mutable results are part of the contract.

A Map.get returns the same stored array, so pushing into it does not require another set.

type Product = { id: string; title: string };
type PriceChange = {
  eventId: string;
  productId: string;
  price: number;
  timestamp: number;
};

function attachHistory(
  products: readonly Product[],
  changes: readonly PriceChange[],
): Array<Product & { history: PriceChange[] }> {
  const grouped = new Map<string, PriceChange[]>();

  for (const change of changes) {
    const group = grouped.get(change.productId);
    if (group === undefined) {
      grouped.set(change.productId, [change]);
    } else {
      group.push(change);
    }
  }

  return products.map(product => ({
    ...product,
    history: grouped.get(product.id) ?? [],
  }));
}

Deduplicate deliveries

Entity identity and event identity are different. A legitimate entity may have many changes. Deduplicate by event ID in its declared scope, such as (sourceId, eventId); select the latest state separately by (sourceId, productId).

A Set of objects compares references rather than fields. For first delivery use a Set of keys; for last value use a Map. Updating a Map value does not move its iteration position.

function deduplicate(changes: readonly PriceChange[]): PriceChange[] {
  const seen = new Set<string>();
  const result: PriceChange[] = [];

  for (const change of changes) {
    if (seen.has(change.eventId)) continue;
    seen.add(change.eventId);
    result.push(change);
  }
  return result;
}

Avoid accidental quadratic work

Calling filter or find for every input record repeatedly scans the same data. Build an index when the task repeatedly asks the same lookup question.

Rebuilding an accumulator with object spread inside every reduce can also turn a linear algorithm into quadratic copying. Prefer a clear loop; define key uniqueness and absent values before choosing Map or an object.

JSON.stringify of a pair or nested Maps avoids delimiter collisions, but processing long IDs still has a cost.

Practice

For A/v3, B/v1, A/v2, A/v5, B/v1 retain the first record on equal versions. What remains? Then implement a per-entity event counter rather than a latest-version index.

const events = [
  { eventId: "E1", productId: "A", version: 1 },
  { eventId: "E2", productId: "A", version: 2 },
];
const seen = new Set<string>();
const wrong = events.filter(event => {
  if (seen.has(event.productId)) return false;
  seen.add(event.productId);
  return true;
});
// wrong contains only E1/version 1.

Explain the decision

Explain the key, conflict rule, complexity and order guarantee. “I will index by entity ID and keep the highest version seen” is more useful than merely naming a data structure. Try one new input with repeated IDs and delimiter characters before moving on.