Relational table join
Implement a relational join of two tables given as lists of dicts. Join 'left' and 'right' on the column name 'key' (present in both). For 'inner' join, emit one merged row per matching pair; for 'left' join, also emit left rows with no match, filling right-only columns with the string '__NULL__'. Merged rows contain the left row's fields plus the right row's fields, with right values winning on any shared non-key column name. Preserve left-table order, and for a given left row preserve right-table order of its matches. Return the list of merged dicts.
join_tables(left: list[dict], right: list[dict], how: str) → list[dict][[{"key":1,"name":"a"},{"key":2,"name":"b"}],[{"key":1,"city":"NY"},{"key":1,"city":"LA"}],"inner"]out[{"key":1,"city":"NY","name":"a"},{"key":1,"city":"LA","name":"a"}]State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[[{"key":1,"name":"a"},{"key":2,"name":"b"}],[{"key":1,"city":"NY"},{"key":1,"city":"LA"}],"inner"][{"key":1,"city":"NY","name":"a"},{"key":1,"city":"LA","name":"a"}]not run yetsample