Loading page…
Practice problem · medium
A chat app shortens the long links that people share. It gives each new link a short code, and the code opens the link again when a reader taps it.
The same link must always get the same code, and a code that the app never gave out must open nothing. Each operation must take constant time on average.
Write run_links(commands, texts).
commands[i] is "shorten" or "expand". texts[i] is a link for "shorten" and a code for "expand"."shorten" returns the link's code. The first new link gets the code c1, the second new link gets c2, and so on. A link that was shortened before returns its first code."expand" returns the link that has this code. A code is the letter c followed by a number from 1 to the count of links so far, written with no leading zero. For any other text, "expand" returns -.Input: commands = ["shorten", "shorten", "shorten", "expand", "expand", "expand"], texts = ["news1", "photo2", "news1", "c2", "c1", "c3"]
Output: ["c1", "c2", "c1", "photo2", "news1", "-"]The trace shows the table and the array.
| Step | Command | Table (link to number) | Array (number 1, 2, ...) | Answer |
|---|---|---|---|---|
| 1 | shorten news1 |
news1: 1 | news1 | c1 |
| 2 | shorten photo2 |
news1: 1, photo2: 2 | news1, photo2 | c2 |
| 3 | shorten news1 |
unchanged | unchanged | c1 |
| 4 | expand c2 |
unchanged | unchanged | photo2 |
| 5 | expand c1 |
unchanged | unchanged | news1 |
| 6 | expand c3 |
unchanged | only 2 links | - |
Input: commands = ["expand", "shorten", "expand", "expand"], texts = ["c1", "a", "c1", "c01"]
Output: ["-", "c1", "a", "-"]No link exists at the first command. The code c01 has a leading zero, so it is not a code.
Input: commands = ["shorten", "shorten", "shorten", "shorten", "shorten", "shorten", "shorten", "shorten", "shorten", "shorten", "shorten", "expand"], texts = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "c11"]
Output: ["c1", "c2", "c3", "c4", "c5", "c6", "c7", "c8", "c9", "c10", "c11", "k"]The eleventh link has the code c11, and expanding it returns the link k.
1 ≤ commands.length = texts.length ≤ 100,000a to z and 0 to 9. A code to expand has the same form.Searching a list of links for each new link costs up to one comparison for each link so far. With tens of thousands of links and 100,000 commands, that is about 10^9 string comparisons.
A table from link to number answers a shorten in one step, and an array answers an expand in one step.
run_links · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.