A tribute to Aphyr’s Typing the technical interview and Richard Towers’s Typescripting the technical interview. You should read those first, if you have not already. The implementation was inspired by konstin’s delightful sudoku-in-python-packaging.
Criss’s smartwatch buzzed. A technical interview appointment in five minutes.
He sighed. Interviews used to excite him, but lately the candidates had been bewildering. Grabbing a can of water from the fridge, he stepped into the meeting room.
“Hi, nice to meet you!” Better to avoid rhetorical questions.
The candidate looked up and smiled back.
“Well, let’s get into it. I’d like do a little excersize with you, to understand how you solve problems.”
“Of course. Can I use any language?”
“Well, normally yes, but I saw you have Python on your resume.”
“Yes, and adder too.”
“Ada?”
“Adder. A flavor of viper.”
“Never heard of it. But never mind, let’s use Python. Try to be ideomatic. Are you familiar with the n-queens puzzle?”
With Python, Criss could be certain the candidate would not be able to do anything sophisticated with the type system.
The candidate nodded and started typing.
1from nqueens import Queen
“Hold on… I want you to do the implementation yourself.”
“You said ideomatic Python.”
“Ok, but what I meant was you should do the implementation in Python, without using anyone else’s packages.”
“May I define my own packages?”
“Yes, of course.”
1import itertools
2
3def get_exclusions(
4 column: int,
5 row: int,
6 grid_size: int
7) -> list[str]:
8 positions = itertools.product(range(grid_size), repeat=2)
9 return [
10 exclude(c, r)
11 for c, r in positions
12 if (
13 (r == row and c != column)
14 or (
15 (d_c := abs(c - column)) == (d_r := abs(r - row))
16 and (d_c or d_r)
17 )
18 )
19 ]
This was promising! It was a relief to see some functions operating on integers and strings.
20def to_name(column: int) -> str:
21 return f"queen_{chr(ord('a') + column)}"
22
23def to_version(row: int) -> str:
24 return f"{row + 1}"
25
26def exclude(column: int, row: int) -> str:
27 return f"{to_name(column)} != {to_version(row)}"
What was this about versions? Criss made a mental note to circle back, because the candidate was moving quickly.
28from pathlib import Path
29from zipfile import ZipFile
30
31PACKAGE_DIR = Path("packages")
32WHEEL_FILE_CONTENTS = """
33Wheel-Version: 1.0
34Generator: nqueens (1.0.0)
35Root-Is-Purelib: true
36Tag: py3-none-any
37""".strip()
38
39def generate_package(column: int, row: int, grid_size: int):
40 name = to_name(column)
41 version = to_version(row)
42 dependencies = get_exclusions(column, row, grid_size)
43 filename = f"{name}-{version}-py3-none-any.whl"
44 with ZipFile(PACKAGE_DIR.joinpath(filename), "w") as writer:
45 metadata = [
46 f"Name: {name}",
47 f"Version: {version}",
48 "Metadata-Version: 2.2",
49 *(f"Requires-Dist: {d}" for d in dependencies),
50 ]
51 writer.writestr(
52 f"{name}-{version}.dist-info/METADATA",
53 "\n".join(metadata)
54 )
55 writer.writestr(
56 f"{name}-{version}.dist-info/WHEEL",
57 WHEEL_FILE_CONTENTS,
58 )
59 record = f"{name}-{version}.dist-info/METADATA,,"
60 record += f"{name}-{version}.dist-info/WHEEL,,"
61 record += f"{name}-{version}.dist-info/RECORD,,"
62 writer.writestr(f"{name}-{version}.dist-info/RECORD", "")
Suddenly Criss was not feeling as optimistic.
“It looks like you just added a function to generate a package?”
“Several packages, yes. Next we run that function for each position on the board.”
63GRID_SIZE = 8
64package_dir.mkdir()
65for column in range(GRID_SIZE):
66 for row in range(GRID_SIZE):
67 generate_package(column, row, GRID_SIZE)
“Aren’t you worried about computational complexity?” Criss was desperate to bring things back to familiar territory.
“It only needs to run once, and it already did. Criss, we are ready to solve.”
“Ok. Well, let’s keep things tangible. Let’s say we have a Queen at c1, f8, and h4. On which positions are the other five queens?”
“Of course. I just need to install some of my packages.”
$ cat > requirements.txt << EOL
queen-a
queen-b
queen-c==1
queen-d
queen-e
queen-f==8
queen-g
queen-h==4
EOL
$ pip install --find-links packages/ -r requirements.txt
Successfully installed queen-a-5 queen-b-3 queen-c-1 queen-d-7 queen-e-2 queen-f-8 queen-g-6 queen-h-4
“Criss… Criss? See, the other Queens are at a5, b3, d7, e2, and g6.”
Criss thought he could feel his hoodie tightening around him, constricting his neck.
“Criss… You asked for ideomatic Python… What could be more Python than a packaging problem?”