AuxDS ] each node2simplify algo #shadow matrix

In some algo questions, I like to add a tiny “metadata” field to the VO.

eg: BFT showing level

Q: how likely is interviewer to accept it?

A: I feel west coast interviews tend to entertain crazy ideas since algo challenges are more free-flowing, exploratory, thought-provoking. I remember the Bbg FX interviewer (Karin?) said my “in-place” is OK if I append to the existing vector then truncate the original portion.

A: I feel if it’s clever then they may appreciate it.

Space/time trade-off. The metadata field

• can be a pointer to parent or next node (like LinkedHashMap)
• can be an iterator into another (static) data structure
• can be the element’s own address if not already available
• can be a sequence id as sorting key
  • insertion id is popular,
• can be a bunch of flags packed into 8-bit integer