Structure

How to design a google sheet

know the features
How to store cells in a sheet:

Array Linked List Four Direction Node operations
O(1) O(1) O(1) update
O(m*n) O(m+n) O(p) insert row or column
O(m*n) O(m*n) O(p) space: store cells
Identifying Circular Dependency
DFS: fast but has stack overflow risk
BFS: handle large number of nodes and used in industry
BFS has less space than DFS.
space of each cell
- max number of cells: ( 2*10^6 )
  - ( 2*10^6 = 1M \approx 1s ). The running time can be observed.
  - ( 1M \approx 8MB ) memory limited
- size of each number
  - 8 Byte (64 bit floating point)
  - ![double range]({{ site.url }}/assets/double-precise-ieee-64.png)
    reference wikipedia
  - reserve largest number as infinite
Co-operation’s solution is logs with timestamps
- timestamps: logical > server > logical time
  example: auto increment in MySQL
- get mutex -> do some changes -> submit log and release mutex -> sync everyone
Latency vs Consistency in distributed system:
- latency compensation
  the value is rendered before sync but not display
  need to communicate with server, it may be changed after sync

Array	Linked List	Four Direction Node	operations
O(1)	O(1)	O(1)	update
O(m*n)	O(m+n)	O(p)	insert row or column
O(m*n)	O(m*n)	O(p)	space: store cells