Design a Key-Value Database Supporting Column Queries

Problem: Design a Key-Value Database Supporting Column Queries Design an in-memory key-value database. Each key represents a row, and each row contains multiple columns. Support read/write by (key, column), and also support querying by a column. Implement the following interface (pseudocode): class KVDB: void put(String key, String column, String value) String get(String key, String column) List<String> queryByColumn(String column, String value) Functional requirements put(key, column, value): set the value for a given (key, column). Overwrite if it already exists. get(key, column): return the stored value, or empty/null if missing. queryByColumn(column, value): return all keys whose row satisfies row[column] == value. Output order is unspecified unless stated otherwise. Constraints & edge cases Entirely in memory. key/column/value are strings. When put overwrites an existing value, the query results must be updated accordingly (remove old index entry, add new one). Scale hints Up to 10^6 operations Up to 10^5 distinct keys Variable number of columns per key Discuss Data structure design (e.g., primary storage + secondary indexes) Time complexity and space trade-offs Example Operations: put("u1", "city", "NY") put("u2", "city", "SF") put("u3", "city", "NY") queryByColumn("city", "NY") Return (any order): ["u1", "u3"] Then: put("u1", "city", "SF") # overwrite queryByColumn("city", "NY") Return: ["u3"] Example Input put u1 city NY put u2 city SF put u3 city NY query city NY Output u1 u3