Location: Google India
Interviewer : Google Munich (Very experienced)
Role : University Grad

Question:

Design a spreadsheet which can support two operations:

• void set_cell(string cell, string value)

• int get_cell(string cell)

Example:
set_cell("A1", "13)
set_cell("A2", "14)
get_cell("A1") -> 13
set_cell("A3", "=A1+A2")
get_cell("A3") -> 27

Approach:

• Use the hashtable to store the { key(cell), value(value) }pair for set_cell function.
• For get_cell function, parse the string by splitting with '+' or '=' or '-' sign. (For simplicity, consider only addition and subtraction). And return the total value of the expression. (We need to call the get_cell recursively for each cell, until we hit the numeric value. )

Edge case:
Consider the operations:
get_cell("A3", "23")
set_cell("A4", "=A3+11")
get_cell("A4") -> 34
set_cell("A3", "=A4+12")
get_cell("A3") -> -1

Here the cycle forms: get_cell("A3") -> get_cell("A4") -> get_cell("A3") -> get_cell("A4") ... and so on.
Return -1 if cycle forms.

Approach : We can use a visited set to track the cell we have seen. If we encounter the same cell again, there is the cycle.

Optimization: We can use memoization to avoid repetitive evaluation of the already calculated expression.

Can someone provide better approach and also discuss the time and space complexities?

Edit:
About me: A final Year student. (Applied on site, Resume shortlisting, Google Coding Challenge, then this)