Stable Column Names

MicrosoftOnsiteMedium

A tool exports table schemas repeatedly and must give every column a stable, safe name. You process a sequence of schema snapshots and compute each column's effective name.

Each snapshot is a list of strings: the first item is a table name and the remaining items are that table's current column names, in order. Each table keeps its own independent state across snapshots.

Part 1: Stable renaming with case-insensitive collisions

You are given calls, a list of schema snapshots. Each snapshot is a list of strings: the first item is a table name and the remaining items are that table's current column names, in order.

Return one list per snapshot holding the effective name of each of its columns, in the same order.

Rules:

A column is identified by the name it is listed under. Its first candidate is that name with every . replaced by _.
Within a table, effective names must be unique when letter case is ignored, so Id and id clash.
If a candidate is taken, try the candidate followed by _1, then _2, and so on, and use the first free one. The suffix keeps the candidate's letter case. A name that already looks suffixed is treated like any other name, so a new column a_1 whose candidate is taken becomes a_1_1.
Each table keeps its own record of every column name it has ever seen. Once a column is assigned an effective name it keeps it forever, even if the column disappears from later snapshots and comes back.
An assigned name stays reserved even while its column is absent.
New columns in a snapshot are handled in input order; snapshots are handled in call order.

A snapshot may contain only the table name; its result is an empty list.

Example 1
calls
[["T","a.b","a_b","a_b_1"],["T","a_b"],["T","a_b_1","a.b","A.B"],["U","a_b"]]
Output
[["a_b","a_b_1","a_b_1_1"],["a_b_1"],["a_b_1_1","a_b","A_B_2"],["a_b"]]
Why: In the first call a.b takes a_b, a_b takes a_b_1 and a_b_1 takes a_b_1_1. The second call returns the stored name. In the third call A.B is a new column: A_B and A_B_1 are taken ignoring case, so it gets A_B_2. Table U starts with empty state.

Constraints

1 <= len(calls) <= 1000
The total number of column names across all calls is at most 10^4
Each table and column name is a non-empty string of at most 100 ASCII letters, digits, underscores and dots
Column names within one calls[i] are pairwise distinct
calls[i] may consist of only the table name

Practice this question

Import your own questions

Paste a question you were asked and get a full problem: statement, tests and a checked solution.

Import a question