Remove the outdated stocks from the queue

You are given a snapshot of a queue of stocks that have changing prices coming in from a stream. Remove the outdated stocks from the queue

Example:

snapshot = [
  { sym: ‘GME’, cost: 280 },
  { sym: ‘PYPL’, cost: 234 },
  { sym: ‘AMZN’, cost: 3206 },
  { sym: ‘AMZN’, cost: 3213 },
  { sym: ‘GME’, cost: 325 }
]
stockQueue(snapshot)
[
  { sym: ‘PYPL’, cost: 234 },
  { sym: ‘AMZN’, cost: 3213 },
  { sym: ‘GME’, cost: 325 }
]

Strategy

This should be easy, right? I have no idea about stocks, so maybe I’m making wrong assumptions :(

Not stonks meme

Assuming the queue comes in chronological order, we should just remove the duplicates keeping the last appearance of each sym

Solution

interface SnapshotRow {
  readonly sym: string
  readonly cost: number
}

/**
 * Removes outdated items from the snapshot.
 * @param snapshot
 */
export function stockQueue(snapshot: SnapshotRow[]): SnapshotRow[] {
  const result: SnapshotRow[] = []
  const existingSyms: Record<string, boolean> = {}

  for (let i = snapshot.length - 1; i >= 0; i--) {
    if (existingSyms[snapshot[i].sym]) {
      continue
    }

    result.unshift(snapshot[i])
    existingSyms[snapshot[i].sym] = true
  }

  return result
}

This solution traverses the queue backwards, and removes the duplicates (using a map to find them). This function creates a new array instead of mutating the original one, hope that’s fine! (purists will say it is :>). Big-O algorithmic complexity is O(n) since we just traverse the array once and use a map to check duplicates.