Loading page…
Practice problem · easy
A build system ships a settings file with every release. The release notes list what changed since the last release: settings that were added, settings whose value changed and settings that were removed.
A teammate wrote the notes generator with two hash tables. It printed the same changes in different orders on two servers, so the two notes did not match.
You fix it. The notes must be the same on every server, whatever language or table they use.
Write config_changes(old_keys, old_values, new_keys, new_values).
old_keys[i] and old_values[i] are the i-th setting of the last release's file. new_keys[i] and new_values[i] are the i-th setting of the new file.10 and 010 are different values.added <key>. For a key whose value differs from its old value, add the line changed <key>. A key with the same value gives no line.removed <key>.Input: old_keys = ["timeout", "retries", "color", "debug"], old_values = ["30", "3", "red", "on"], new_keys = ["retries", "color", "region", "timeout"], new_values = ["3", "blue", "eu", "45"]
Output: ["changed color", "added region", "changed timeout", "removed debug"]The trace walks the new file, then the old file.
| Step | Walking | Key | In the other file? | Line |
|---|---|---|---|---|
| 1 | new file | retries |
yes, value 3 is the same |
none |
| 2 | new file | color |
yes, red became blue |
changed color |
| 3 | new file | region |
no | added region |
| 4 | new file | timeout |
yes, 30 became 45 |
changed timeout |
| 5 | old file | timeout, retries, color |
yes, in the new file | none |
| 6 | old file | debug |
no | removed debug |
Input: old_keys = ["a", "b"], old_values = ["1", "2"], new_keys = ["b", "a"], new_values = ["2", "1"]
Output: []The settings are the same in another order, so nothing changed.
Input: old_keys = [], old_values = [], new_keys = ["zeta", "alpha"], new_values = ["1", "1"]
Output: ["added zeta", "added alpha"]The lines follow the order of the new file, not the alphabet.
0 ≤ old_keys.length = old_values.length ≤ 20,000, and the same for the new filea to z and 0 to 9. Values have 1 to 6 characters from the same set.Searching the other file's list for every key costs up to one comparison for each key of that file. With 20,000 keys in each file that is about 4 × 10^8 comparisons for the new file alone, and the same again for the old file. Looking a key up in a table takes one step on average.
The limit also hides a trap. A table is fast, but it keeps no order you can rely on. If you build the answer by looping over a table, the order depends on the language.
config_changes · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.