FastPrepPropagate Spreadsheet Cell Updates

Propagate Spreadsheet Cell Updates

OpenAI logoOpenAI● MediumFULLTIMEPHONE SCREEN

Updated

Problem statement

Cells in a spreadsheet have names like A1 or Z99: a capital letter, then a row number. Each cell holds either a plain number or a link that adds up other cells. When a cell changes, every cell built from it, directly or through other cells, must show the new total.

You get a list operations. Run them in order. Each operation is a list of strings:

  • ["set", cell, number] puts the integer number in cell. If cell had a link, the link is removed.
  • ["sum", cell, ref1, ..., refK] links cell to the listed cells: from now on its value is ref1 + ... + refK. This replaces whatever cell held before, including an older link. A cell listed twice is added twice.
  • ["get", cell] reads the value of cell at this moment.

Until a cell gets a number or a link, its value is 0.

Return the values read by the get operations, in order. If there is no get, return an empty array.

Follow-up: reads happen far more often than changes. Can you answer each get without adding anything up?

Function

runCellUpdates(operations: String[][]) → long[]

Examples

Example 1

operations = [["set","B3","7"],["sum","D4","B3","C2"],["set","C2","-2"],["get","D4"],["set","B3","1"],["get","D4"],["get","C2"]]return = [5,-1,-2]

D4 is linked to B3 and C2. C2 is still empty at that point, but the link stays, so when C2 gets -2, the first read sees 7 + (-2) = 5. Then B3 drops to 1, and D4 follows: 1 + (-2) = -1. The last read returns C2 itself, -2.

Example 2

operations = [["set","K5","8"],["sum","M2","K5","P7"],["sum","Q1","M2","M2","K5"],["get","Q1"],["set","K5","10"],["get","Q1"],["set","M2","-1"],["set","K5","5"],["get","Q1"],["get","P7"]]return = [24,30,3,0]

M2 adds K5 and the empty cell P7, and Q1 lists M2 twice plus K5. With K5 = 8, M2 = 8 + 0 = 8 and Q1 = 8 + 8 + 8 = 24. With K5 = 10, M2 = 10 and Q1 = 30.

Giving M2 the number -1 removes its link, so Q1 = -1 + (-1) + 10 = 8. When K5 then changes to 5, M2 stays -1 and Q1 = -1 + (-1) + 5 = 3. P7 was never written, so it reads 0.

Example 3

operations = [["set","A1","1"],["set","B1","2"],["sum","C1","A1"],["sum","D1","C1","C1"],["sum","C1","B1"],["set","A1","50"],["get","D1"]]return = [4]

At first C1 copies A1. The second sum on C1 replaces that link, so C1 now copies B1 and equals 2. D1 lists C1 twice, so it is 4. Changing A1 to 50 no longer affects C1 or D1.

Constraints

  • 1 <= operations.length <= 3000
  • 2 <= operations[i].length <= 10
  • Every string in operations has 1 to 8 characters.
  • operations[i][0] is "set", "sum" or "get". A get has 2 strings, a set has 3, and a sum lists 1 to 8 cells.
  • A cell name is one capital letter from A to Z followed by a row number from 1 to 99 with no leading zero.
  • A set number is an integer from -10^6 to 10^6, written in base 10 without a plus sign or leading zeros.
  • No cell ever depends on itself, directly or through other cells.
  • After every operation, every cell's value is between -10^12 and 10^12.

More OpenAI Phone Screen questions

Similar questions at other companies

OpenAI interview experiences

All OpenAI interview questionsSee OpenAI hiring insights
Saved
class Solution {
    public long[] runCellUpdates(String[][] operations) {
        // Write your code here.
    }
}
Checking account…