Backstory
Atticus Yang advised me on how to prepare for a coding interview. He didn’t know exactly where to find this problem, but asked Anthropic’s Claude for the “Design Excel” challenge, and then sent me the result. This was it:
The Challenge: “Design Excel”
Design a data structure that represents an Excel spreadsheet. Implement the following functionalities:
-
set(row: int, col: int, value: int): Sets the value at the given cell (row, col).
-
get(row: int, col: int): Gets the value at the given cell (row, col).
-
setFormula(row: int, col: int, formula: String): Sets a formula for a cell.
-
Formulas are given as strings and can include references to other cells (e.g., “A1+B2”) or simple arithmetic operations.
-
sum(row1: int, col1: int, row2: int, col2: int): Calculates the sum of the rectangular region defined by (row1, col1) as the top-left corner and (row2, col2) as the bottom-right corner.
This problem tests your ability to design a system that can:
- Efficiently store and retrieve cell values
- Parse and evaluate formulas
- Handle dependencies between cells
- Perform range-based operations like sum
Why I Think this is Worthwhile
Because it resembles other challenges I have had to do in various tech interviews. I haven’t done this particular one, but this type of longer-running usage of interconnected data structures to manipulate a central body of data is certainly a theme. I’ve seen undo, I’ve seen a cache-store where each item has a TTL. Each of these challenges so far has taught me a lot, so if Atticus is telling me I may specifically see this questions, I think it’s definitely worthwhile. Spoilers it definitely teaches me some new things.
Conversation with Claude:
AKA: How doing thought experiments on the architecture of Base-10 helps illuminate what encoding to and from Base-N looks like. In this case, Base-26.
Initial Progress
So I get going and get to about here in 20 minutes and feel pretty good.
// Okay remember
// The internal indexing IS 0 based, i.e. for 10x10, bottom right is 99x99, top left is 0, 0
// BUT. the methods automatically uses 1,1 for top left. So we need to translate this stuff
class Excel{
cells: number[][]
rows: number
cols: number
constructor(rows: number, cols: number){
this.rows = rows
this.cols = cols
this.cells = []
for (let col = 0; col < cols; col++){
this.cells.push([])
for (let row = 0; row < rows; row++){
this.cells[col].push(0)
}
}
}
set(row: number, col: number, value: number): boolean {
if (col < 0 || row < 0){
console.log("The top left cell is 1, 1")
return false
}
if (row > this.rows || col > this.cols){
console.log(`(${row},${col}) Is out of bounds`)
return false
}
this.cells[col-1][row-1] = value
return true
}
get(row: number, col: number): number {
if (col < 0 || row < 0){
console.log("The top left cell is 1, 1")
return -1
}
if (row > this.rows || col > this.cols){
console.log(`(${row},${col}) Is out of bounds`)
return -1
}
return this.cells[row-1][col-1]
// Gets the value at the given cell (row, col).
}
But then I look at this next bit and I just baulk. I ask Claude what it would do, and I don’t regret it. At the time and in hindsight, I think that figuring out these next functions on my own is not a good use of my time. They are much higher order, and completely unlike anything I’ve seen before. They are even more challenging for how much simpler they appeared to me at first glance. Claude gives me this:
class Excel {
cells: (number | string)[][]
formulas: { [key: string]: string }
rows: number
cols: number
constructor(rows: number, cols: number) {
this.rows = rows
this.cols = cols
this.cells = []
this.formulas = {}
for (let col = 0; col < cols; col++) {
this.cells.push([])
for (let row = 0; row < rows; row++) {
this.cells[col].push(0)
}
}
}
set(row: number, col: number, value: number): boolean {
if (col < 1 || row < 1 || row > this.rows || col > this.cols) {
console.log(`(${row},${col}) Is out of bounds`)
return false
}
this.cells[col - 1][row - 1] = value
return true
}
get(row: number, col: number): number | string {
if (col < 1 || row < 1 || row > this.rows || col > this.cols) {
console.log(`(${row},${col}) Is out of bounds`)
return -1
}
const cellKey = `${row},${col}`
if (cellKey in this.formulas) {
return this.evaluateFormula(this.formulas[cellKey])
}
return this.cells[col - 1][row - 1]
}
setFormula(row: number, col: number, formula: string): void {
if (col < 1 || row < 1 || row > this.rows || col > this.cols) {
console.log(`(${row},${col}) Is out of bounds`)
return
}
const cellKey = `${row},${col}`
this.formulas[cellKey] = formula
this.cells[col - 1][row - 1] = this.evaluateFormula(formula)
}
sum(row1: number, col1: number, row2: number, col2: number): number {
let sum = 0
for (let row = row1; row <= row2; row++) {
for (let col = col1; col <= col2; col++) {
const value = this.get(row, col)
if (typeof value === 'number') {
sum += value
}
}
}
return sum
}
private evaluateFormula(formula: string): number {
// Simple formula evaluation (supports basic arithmetic and cell references)
const cellReference = /([A-Z])(\d+)/g
formula = formula.replace(cellReference, (match, col, row) => {
const colIndex = col.charCodeAt(0) - 64
return this.get(parseInt(row), colIndex).toString()
})
try {
return eval(formula)
} catch (error) {
console.error('Invalid formula:', formula)
return 0
}
}
private columnToLetter(column: number): string {
let temp: number, letter = ''
while (column > 0) {
temp = (column - 1) % 26
letter = String.fromCharCode(temp + 65) + letter
column = (column - temp - 1) / 26
}
return letter
}
private letterToColumn(letter: string): number {
let column = 0
for (let i = 0; i < letter.length; i++) {
column += (letter.charCodeAt(i) - 64) * Math.pow(26, letter.length - i - 1)
}
return column
}
}It looks good, and explains a lot. In particular, extracting letterToColumn into functions is crucial, because although it’s not many lines, it’s way to complex to reason about within another function, and it’s quite functional - even if I don’t initially understand how it works, I don’t have to in order to use it because the I/O is dead simple.
AA -> 27AZ => 52
But yeah. The machinery inside of the function is whack. I break apart this letterToColumn function in about a half hour or so, after watching an episode of White Lotus to chill out.
For this one, going through it with a few example I/O’s is enough to illuminate the workings.
const lettersToNumber => (letters: string): number => {
column = 0
for (let i = 1; i <= letters.length; i++){
column += (letters.charCodeAt(i)-64) * Math.pow(26, letters.length - i)
}
return column
}I was almost able to just write that from scratch just now, except that I confused charCodeAt with charFromStringwhich isn’t a function (I was sort of thinking of String.fromCharCode, but we’ll get there).
You might notice I change the for loop to be 1-index. I found this reduced the complexity a bit and was easier to reason about, even if it is a bit unconventional.
Here’s some scribbles of me working it out earlier:
// CDA
// 2133
// while 2133 > 0
// 2132 % 26 = 0 (because it goes in 82 times)
// 0 + 65 + '' = A
// column = 2133 - 0 / 26 = 82This type of exercise made understanding it relatively easy.
Although not technically needed for this challenge, I also took it upon myself to understand columnToLetter, but that ended up being WAY harder. I had to go on a whole journey of understanding different Base-N numeric systems to get there, which I will include below:
Me:
This is so hard for me to fully Grok. I understand LetterToColumn pretty well. Somehow though, line by line, it’s really hard for me to get this one:
private columnToLetter(column: number): string {
let temp: number, letter = ''
while (column > 0) {
temp = (column - 1) % 26
letter = String.fromCharCode(temp + 65) + letter
column = (column - temp - 1) / 26
}
return letter
}Can you help me understand it backwards and forwards? Like, really break it down and teach me how it works.
Claude
… Think of it like this: if you were converting a decimal number to binary, you’d repeatedly divide by 2 and keep track of the remainders. This is the same concept, but we’re dividing by 26 instead of 2, and using letters instead of 0 and 1.
Me:
(misunderstanding and thinking Claude was talking about normal base-10, but luckily it works in my favor) Okay yes the base 10 corollary does help. Let’s say we are doing this for 124. We are converting it down to be letters from A-I.
124%10=4 (because 10 goes into 120 12 times, leaving 4)
Line 2 of the while loop really just builds the string
But I think that’s what’s hardest for me to understand and it bothers me - why are we building the end of the string first? How does this correspond to the modulu operation exactly?
We modulo it by 10, get that remainder or 4. That means 4 is going to be the last digit. The smallest digit. But I don’t know why - in my head, it could just as easily be the first digit, I don’t know why it’s one no the other, you know?
Anyways. After adding that to the “end” of the string,
We move on to line 3, we cut off that reminder that we’ve dealt with somehow, and we divide it by 10 (or 26 in the real function) again.
I suppose that’s the reason. Every time we go in the while loop, we’ve divided by our base again…so although our “column” number is shrinking, it’s not shrinking in a normal way. We’re cutting off the parts of it that overflow each level of a base. We start with the first level of a base - in this case, any number that won’t fit into a multiple of 10. We do this, and we are left with 120.
Now we find everything that won’t fit into a multiple of 100 (because now all numbers left over are technically a multiple of 10 - we’ve removed the last “digit”, or in the case of converting one base to another, the level of that base (still sort of a digit, just not a digit in the 10-base sense))
And what we cut off on that stage is 20. 10s fit into 20, but not 100s. 2 tens to be precise, so we can take that entire “stage” and re-encode it to 2, put at the symbolic position of 2.
I guess that’s sort of my challenge too, is the wording.
Each position contains information.
On base 26, a letter at position 2 from the right (1 position left of the first characer), reprsent 2 26s. We could move that same quantity to the 1 position, sort of, in a weird way, but then it would change form, to 52. Which, well, it won’t fit there. It’s 52 units of base 26, which if you wanted to be insane, COULD be represented in base10 as 52 I guess. But that’s sort of like saying, hey, let’s create another 16 characters that represent the numbers from 10-26 so that we can fit 26 characters in the 1st position.
I guess, just to ride this train, we could actually create a base 52 system that uses all the lowercase and uppercase characters together, where lowercase is 1-26 and uppercase is 27-52. If we did THAT, then we could express the base 26 value of “20” (which is the equivalent of Z in the normal excel-style alphabet by the way, when encoded with base 26 characers - it’s also the ASCII character 90) with the character Z (but in the context of a base-52, a-zA-Z character base), and Z alone. That’s the only way we could really FIT it in the first position. I guess you could do other super weird funky stuff if you wanted other ways to express numbers like this, and cram them into the first position.
Like we could I suppose appropriate superscript notation away from exponent expression to mean the amount of bases it represents. With this weird quirky language, in the context still of a base-26 numerical system, we could do 2²
Instead, which is to say that 2 represents 2 26’s (52).
If we just went crazy with this sort of thing, no rules, we could do this:
3¹1³2²
So here, 3 represents 3, 1 represents 676 and 2 represents 52.
This entire “number” would then be 679.
This is really the same as writing 123 in base-26 notation, it’s just that instead of encoding “how many bases up” each number is with their position, we are doing it with the superscript, freeing them to be all over the place in no particular order. Definitely not an improvement, but I think it illuminates how information is being encoded in these different ways.
So yeah. I think I get it.
We start with this big number.
We subtract 1 because excel is 1-indexed and we want to change it to 0-indexed.
We modulo it off of 26. When we do this, we are in the first position of base-26, where each character represents just 1, or 26^0.
In this mode, we can add 65 (the value of A in ASCII) to whatever modulo we cut off. If the entire number is a multiple of 26, we actually don’t have a remainder, because this first position is only for numbers that don’t fit evenly into 26.
We have the + letter for later, but letter = '' right now, so we don’t worry about it.
We go to the last line in the while loop, where we actually go ahead and do what that modulo foreshadowed, and divide our working column amount by our base. This is like saying, okay, for 26⁰, or numbers that don’t evenly go into 26, we’re good. We’ve encoded that in our base-26 encoding with A-Z characters. That’s now in the first position of the string we’re building. Next up, since we’re done with things that aren’t multiples of 26, we now will focus on things that are multiples of 26 but not of 676.
We’ll take THOSE slices of the overall number and we’ll encode them as an A-Z character in the second position.
If there’s still something left over, that’s because we have more than 676 characters, which is the limit of what we could encode with ZZ I believe.
That brings us to ZZA territory, where we have 677.
Damn. Yeah that’s it. Super tricky to wrap my head around but I think I kind of get it now.
What Next?
I’m not quite done with this challenge, but I’m proud of my progress and will pick it up tomorrow.