Recipe Card Short Links
A recipe site prints a short link on the back of every recipe card, like rcp.ly/0021, so people can type it into a phone. Behind the link is a plain number: the recipe's row ID in the database. The short code is that number written in base 62, using the digits, the lowercase letters and the uppercase letters.
This is the core of a URL shortener (see Design a URL Shortener): a counter or an ID generator hands out unique numbers (Unique IDs), and base 62 turns each number into a short code and back again on every redirect.
Your task
Write a class ShortCode:
constructor(width): codes are padded on the left with"0"to at leastwidthcharacters. A number that needs more characters gets a longer code; it is never cut.encode(id): return the code forid.decode(code): return the number a code stands for. Leading"0"characters add nothing, so"0021"and"21"both decode to the same number.
The 62 digits, in order of value from 0 to 61, are 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ. So "a" is 10, "z" is 35, "A" is 36 and "Z" is 61. The number 0 is the single digit "0" before padding.
class ShortCode
Examples
new ShortCode(4)
.encode(125)
.decode("0021")
.decode("21")[null, "0021", 125, 125]
125 = 2 × 62 + 1, so in base 62 it has the digits 2 and 1: "21". Padding to width 4 gives "0021". Decoding reads left to right: 0, then 0 × 62 + 0 = 0, then 0 × 62 + 2 = 2, then 2 × 62 + 1 = 125. Without the padding the answer is the same.
new ShortCode(7)
.encode(125000017)
.encode(3844)
.decode("008sudj")[null, "008sudj", "0000100", 125000017]
125,000,017 needs 5 base-62 digits: s, u, d, j are 28, 30, 13, 19 and the leading 8 is 8, and 8 × 62⁴ + 28 × 62³ + 30 × 62² + 13 × 62 + 19 = 125,000,017. 3,844 is exactly 62², so it is written "100", the way 100 is 10² in decimal. Mixing up the order of the letters (uppercase before lowercase) would give a different code that decodes to a different recipe.
Constraints
- 1 ≤ width ≤ 12
- 0 ≤ id ≤ 9,007,199,254,740,991 (the largest safe integer in JavaScript)
- Every code passed to decode uses only the 62 digits, has 1 to 12 characters, and stands for a number in the same range as id.
- At most 1,000 calls per test.
Start with brute force
You could hand out codes by counting up through every string in order ("0", "1", …, "Z", "10", …) and keep a table from number to code. Encoding the millionth recipe means walking a million steps or storing a million rows, and decoding needs the reverse table too.
Base 62 is a formula in both directions, so neither table is needed: encoding and decoding take one step per character, and a code never has more than 12 characters here.
Hints
0 of 4 shown- Hint 1
In decimal, how do you get the last digit of 4,071 and what is left after you remove it? Base 62 works the same way with 62 in place of 10.
- Hint 2
The last base-62 digit of
idisid % 62. Divide by 62 (rounding down) and repeat until nothing is left. The digits come out last first, so build the string from the right. - Hint 3
Padding only ever adds
"0"characters on the left. When a number needs more digits thanwidth, keep all of them: cutting the code towidthwould give two recipes the same link. - Hint 4
To decode, start from 0 and, for each character from left to right, multiply what you have by 62 and add the character's value (its position in the alphabet string). A map from character to value makes each lookup O(1).
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Base 62 is ordinary place value with 62 symbols instead of 10. Each position is worth 62 times the one to its right.
Encode 125 with width 4:
- 125 % 62 = 1, so the last digit is
"1". 125 / 62 rounded down is 2. - 2 % 62 = 2, so the next digit is
"2". 2 / 62 rounded down is 0: stop. - The digits came out as 1, then 2, so the code is
"21". Pad to 4:"0021".
Decode "0021": n = 0 → 0 × 62 + 0 = 0 → 0 × 62 + 0 = 0 → 0 × 62 + 2 = 2 → 2 × 62 + 1 = 125.
Two details break naive versions. Padding must never cut a code: 238,328 needs 4 digits, "1000", and trimming it to width 3 would give "000", the code for 0. And the alphabet order must be exactly the one in the task: it is a contract between the code that writes links and the code that reads them, and changing it later breaks every printed card.
const DIGITS = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
const VALUE = new Map([...DIGITS].map((ch, i) => [ch, i]));
class ShortCode {
constructor(width) {
this.width = width;
}
encode(id) {
let code = '';
do {
code = DIGITS[id % 62] + code; // last digit first
id = Math.floor(id / 62);
} while (id > 0); // do-while: 0 still gives "0"
return code.padStart(this.width, '0');
}
decode(code) {
let n = 0;
for (const ch of code) n = n * 62 + VALUE.get(ch);
return n;
}
}DIGITS = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
VALUE = {ch: i for i, ch in enumerate(DIGITS)}
class ShortCode:
def __init__(self, width):
self.width = width
def encode(self, id):
digits = []
while True:
id, d = divmod(id, 62)
digits.append(DIGITS[d]) # last digit first
if id == 0: # checked after: 0 still gives "0"
break
return "".join(reversed(digits)).rjust(self.width, "0")
def decode(self, code):
n = 0
for ch in code:
n = n * 62 + VALUE[ch]
return nRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.